We investigate statistics of lead changes of the maxima of two random walks in one dimension. We show that the average number of lead changes grows as (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 Lévy flights. We also show that the probability to have at most n lead changes behaves as t^(−1/4) [lnt]^n for Brownian motion and as t^(−β(μ)) [lnt]^n for symmetric Lévy flights with index μ. The decay exponent β(μ) varies continuously with the Lévy index when 0<μ<2.

[Work done with E. Ben-Naim (Los Alamos National Laboratory) and Paul Krapivsky (Boston University)]