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.

arXiv comment7 pages, 8 figures

References in corpus (19)

• An efficient, multiple range random walk algorithm to calculate the density of states
• The large deviation approach to statistical mechanics
• Shape Fluctuations and Random Matrices
• Universal Distributions for Growth Processes in 1+1 Dimensions and Random Matrices
• Universal Fluctuations of Growing Interfaces: Evidence in Turbulent Liquid Crystals
• Growing interfaces uncover universal fluctuations behind scale invariance
• Exact scaling functions for one-dimensional stationary KPZ growth
• A pedestrian's view on interacting particle systems, KPZ universality, and random matrices
• Top eigenvalue of a random matrix: large deviations and third order phase transition
• Sampling rare events: statistics of local sequence alignments
• Large-deviation properties of largest component for random graphs
• Large deviations for the height in 1D Kardar-Parisi-Zhang growth at late times
• An Anisotropic Ballistic Deposition Model with Links to the Ulam Problem and the Tracy-Widom Distribution
• Convex Hulls of Random Walks: Large-Deviation Properties
• Ground state energy of noninteracting fermions with a random energy spectrum
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• Convex Hulls of Random Walks in Higher Dimensions: A Large Deviation Study
• Increasing subsequences of random walks
• Empirical scaling of the length of the longest increasing subsequences of random walks

Cited by in corpus (12)

• Long time position distribution of an active Brownian particle in two dimensions
• 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
• How many longest increasing subsequences are there?
• Replica symmetry breaking for Ulam's problem
• Asymptotic behavior of the length of the longest increasing subsequences of random walks
• 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