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

References in corpus (5)

• Freezing and extreme value statistics in a Random Energy Model with logarithmically correlated potential
• On the time to reach maximum for a variety of constrained Brownian motions
• Density of near-extreme events
• Extreme statistics for time series: Distribution of the maximum relative to the initial value
• Order statistics of 1/f^α signals

Cited by in corpus (30)

• Extreme value statistics of correlated random variables: a pedagogical review
• Optimizing the search for resources by sharing information: Mongolian gazelles as a case study
• Record statistics of a strongly correlated time series: random walks and Lévy flights
• Record Statistics for Multiple Random Walks
• Near-extreme statistics of Brownian motion
• Universal Order and Gap Statistics of Critical Branching Brownian Motion
• Survival Probability of Random Walks and Lévy Flights on a Semi-Infinite Line
• Spatial Extent of Branching Brownian Motion
• Universal statistics of longest lasting records of random walks and Lévy flights
• Exact extreme value statistics at mixed order transitions
• Branching Brownian Motion Conditioned on Particle Numbers
• On the Gap and Time Interval between the First Two Maxima of Long Random Walks
• Exact Statistics of the Gap and Time Interval Between the First Two Maxima of Random Walks
• Exact statistics of record increments of random walks and Lévy flights
• Mean perimeter and mean area of the convex hull over planar random walks
• Near-extreme eigenvalues and the first gap of Hermitian random matrices
• Erratic non-Hermitian skin localization
• Spectral order statistics of Gaussian random matrices: large deviations for trapped fermions and associated phase transitions
• Universal survival probability for a correlated random walk and applications to records
• Gap statistics close to the quantile of a random walk
• Empirical scaling of the length of the longest increasing subsequences of random walks
• Optimal recruitment strategies for groups of interacting walkers with leaders
• First Gap Statistics of Long Random Walks with Bounded Jumps
• On the Gap and Time Interval between the First Two Maxima of Long Continuous Time Random Walks
• Extreme order statistics of random walks
• Statistical properties of partonic configurations and diffractive dissociation in high-energy electron-nucleus scattering
• New insights into the distribution of the topmost gap in random walks and Lévy flights
• Enhancement of Extreme Events through the Allee effect and its Mitigation through Noise in a Three Species System
• Maximal Minimal Spacing for Random Points
• PhD thesis "Extreme value statistics of strongly correlated systems: fermions, random matrices and random walks"