Large deviations of the length of the longest increasing subsequence of random permutations and random walks

Abstract

We study numerically the distributions of the length $L$ of the longest increasing subsequence (LIS) for the two cases of random permutations and of one-dimensional random walks. Using sophisticated large-deviation algorithms, we are able to obtain very large parts of the distribution, especially also covering probabilities smaller than $P(L)=10^{-1000}$. This enables us to verify for the length of the LIS of random permutations the analytically known asymptotics of the rate function and even the whole Tracy-Widom distribution, to which we observe a rather fast convergence in the larger than typical part. For the length $L$ of LIS of random walks, where no analytical results are known to us, we test a proposed scaling law and observe convergence of the tails into a collapse for increasing system size. Further, we obtain estimates for the leading order behavior of the rate functions of both tails.

7 pages, 8 figures

References in corpus (6)

• The large deviation approach to statistical mechanics
• Growing interfaces uncover universal fluctuations behind scale invariance
• Exact scaling functions for one-dimensional stationary KPZ growth
• Convex Hulls of Random Walks: Large-Deviation Properties
• Convex Hulls of Random Walks in Higher Dimensions: A Large Deviation Study
• Empirical scaling of the length of the longest increasing subsequences of random walks

Cited by in corpus (9)

• Position distribution in a generalised run and tumble process
• Confined run and tumble particles with non-Markovian tumbling statistics
• First-passage area distribution and optimal fluctuations of fractional Brownian motion
• Replica symmetry breaking for Ulam's problem
• Numerical Aspects of Large Deviations
• A numerical investigation into the scaling behavior of the longest increasing subsequences of the symmetric ultra-fat tailed random walk
• Optimal finite-differences discretization for the diffusion equation from the perspective of large-deviation theory
• Dimensionality-induced dynamical phase transition in the large deviation of local time density for Brownian motion
• Longest weakly increasing subsequences of discrete random walks on the integers with heavy tailed distribution of increments