Empirical scaling of the length of the longest increasing subsequences of random walks

Abstract

We provide Monte Carlo estimates of the scaling of the length $L_n$ of the longest increasing subsequences of $n$-steps random walks for several different distributions of step lengths, short and heavy-tailed. Our simulations indicate that, barring possible logarithmic corrections, $L_n\sim n^{\theta }$ with the leading scaling exponent $0.60\lesssim \theta \lesssim 0.69$ for the heavy-tailed distributions of step lengths examined, with values increasing as the distribution becomes more heavy-tailed, and $\theta \simeq 0.57$ for distributions of finite variance, irrespective of the particular distribution. The results are consistent with existing rigorous bounds for $\theta$, although in a somewhat surprising manner. For random walks with step lengths of finite variance, we conjecture that the correct asymptotic behavior of $L_n$ is given by $\sqrt{n}\ln n$, and also propose the form of the subleading asymptotics. The distribution of $L_n$ was found to follow a simple scaling form with scaling functions that vary with $\theta$. Accordingly, when the step lengths are of finite variance they seem to be universal. The nature of this scaling remains unclear, since we lack a working model, microscopic or hydrodynamic, for the behavior of the length of the longest increasing subsequences of random walks.

14 pages, 4 color figures, 26 references; version v2 corresponds to the published version

References in corpus (4)

• Universal Record Statistics of Random Walks and Lévy Flights
• Universality for mathematical and physical systems
• Universal statistics of longest lasting records of random walks and Lévy flights
• On the Gap and Time Interval between the First Two Maxima of Long Random Walks

Cited by in corpus (4)

• Large deviations of the length of the longest increasing subsequence of random permutations and random walks
• How many longest increasing subsequences are there?
• A numerical investigation into the scaling behavior of the longest increasing subsequences of the symmetric ultra-fat tailed random walk
• Longest weakly increasing subsequences of discrete random walks on the integers with heavy tailed distribution of increments