How many longest increasing subsequences are there?

Abstract

We study the entropy $S$ of longest increasing subsequences (LIS), i.e., the logarithm of the number of distinct LIS. We consider two ensembles of sequences, namely random permutations of integers and sequences drawn i.i.d.\ from a limited number of distinct integers. Using sophisticated algorithms, we are able to exactly count the number of LIS for each given sequence. Furthermore, we are not only measuring averages and variances for the considered ensembles of sequences, but we sample very large parts of the probability distribution $p(S)$ with very high precision. Especially, we are able to observe the tails of extremely rare events which occur with probabilities smaller than $10^{-600}$. We show that the distribution of the entropy of the LIS is approximately Gaussian with deviations in the far tails, which might vanish in the limit of long sequences. Further we propose a large-deviation rate function which fits best to our observed data.

arXiv comment10 pages, 8 figures

References in corpus (17)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• 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
• A pedestrian's view on interacting particle systems, KPZ universality, and random matrices
• Sampling rare events: statistics of local sequence alignments
• Large-deviation properties of largest component for random graphs
• An Anisotropic Ballistic Deposition Model with Links to the Ulam Problem and the Tracy-Widom Distribution
• High-precision simulation of the height distribution for the KPZ equation
• Large-deviation properties of the largest biconnected component for random graphs
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• Optimal Online Selection of a Monotone Subsequence: a Central Limit Theorem
• Large deviations of the length of the longest increasing subsequence of random permutations and random walks
• Increasing subsequences of random walks
• Empirical scaling of the length of the longest increasing subsequences of random walks
• Asymptotic behavior of the length of the longest increasing subsequences of random walks

Cited by in corpus (6)

• 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
• Variations on Hammersley's interacting particle process
• Longest weakly increasing subsequences of discrete random walks on the integers with heavy tailed distribution of increments