  In the context of order statistics of discrete time random walks (RW), we
investigate the statistics of the gap, $G_n$, and the number of time steps,
$L_n$, between the two highest positions of a Markovian one-dimensional random
walker, starting from $x_0 = 0$, after $n$ time steps (taking the $x$-axis
vertical). The jumps $\eta_i = x_i - x_{i-1}$ are independent and identically
distributed random variables drawn from a symmetric probability distribution
function (PDF), $f(\eta)$, the Fourier transform of which has the small $k$
behavior $1 - \hat f(k) \propto |k|^\mu$, with $0 < \mu \leq 2$. For $\mu=2$,
the variance of the jump distribution is finite and the RW (properly scaled)
converges to a Brownian motion. For $0<\mu<2$, the RW is a L\'evy flight of
index $\mu$. We show that the joint PDF of $G_n$ and $L_n$ converges to a well
defined stationary bi-variate distribution $p(g,l)$ as the RW duration $n$ goes
to infinity. We present a thorough analytical study of the limiting joint
distribution $p(g,l)$, as well as of its associated marginals $p_{\rm gap}(g)$
and $p_{\rm time}(l)$, revealing a rich variety of behaviors depending on the
tail of $f(\eta)$ (from slow decreasing algebraic tail to fast decreasing
super-exponential tail). We also address the problem for a random bridge where
the RW starts and ends at the origin after $n$ time steps. We show that in the
large $n$ limit, the PDF of $G_n$ and $L_n$ converges to the {\it same}
stationary distribution $p(g,l)$ as in the case of the free-end RW. Finally, we
present a numerical check of our analytical predictions. Some of these results
were announced in a recent letter [S. N. Majumdar, Ph. Mounaix, G. Schehr,
Phys. Rev. Lett. {\bf 111}, 070601 (2013)].
