Universal Order Statistics of Random Walks

Abstract

We study analytically the order statistics of a time series generated by the successive positions of a symmetric random walk of n steps with step lengths of finite variance σ^2. We show that the statistics of the gap d_{k,n}=M_{k,n} -M_{k+1,n} between the k-th and the (k+1)-th maximum of the time series becomes stationary, i.e, independent of n as n\to \infty and exhibits a rich, universal behavior. The mean stationary gap (in units of σ) exhibits a universal algebraic decay for large k, <d_{k,\infty}>/σ\sim 1/\sqrt{2πk}, independent of the details of the jump distribution. Moreover, the probability density (pdf) of the stationary gap exhibits scaling, Proba.(d_{k,\infty}=δ)\simeq (\sqrt{k}/σ) P(δ\sqrt{k}/σ), in the scaling regime when δ\sim <d_{k,\infty}>\simeq σ/\sqrt{2πk}. The scaling function P(x) is universal and has an unexpected power law tail, P(x) \sim x^{-4} for large x. For δ\gg <d_{k,\infty}> the scaling breaks down and the pdf gets cut-off in a nonuniversal way. Consequently, the moments of the gap exhibit an unusual multi-scaling behavior.

5 pages, 3 figures. Revised version, typos corrected. Accepted for publication in Physical Review Letters