Maxima of Two Random Walks: Universal Statistics of Lead Changes

We investigate statistics of lead changes of the maxima of two discrete-time random walks in one dimension. We show that the average number of lead changes grows as $pi^{-1}ln(t)$ in the long-time limit. We present theoretical and numerical evidence that this asymptotic behavior is universal. Specifically, this behavior is independent of the jump distribution: the same asymptotic underlies standard Brownian motion and symmetric Levy flights. We also show that the probability to have at most n lead changes behaves as $t^{-1/4}[ln t]^n$ for Brownian motion and as $t^{-beta(mu)}[ln t]^n$ for symmetric Levy flights with index $mu$. The decay exponent $beta(mu)$ varies continuously with the Levy index when $0<mu<2$, while $beta=1/4$ for $mu>2$.