A Stirling-type formula for the distribution of the length of longest increasing subsequences

Abstract

The discrete distribution of the length of longest increasing subsequences in random permutations of $n$ integers is deeply related to random matrix theory. In a seminal work, Baik, Deift and Johansson provided an asymptotics in terms of the distribution of the scaled largest level of the large matrix limit of GUE. As a numerical approximation, however, this asymptotics is inaccurate for small $n$ and has a slow convergence rate, conjectured to be just of order $n^{-1/3}$. Here, we suggest a different type of approximation, based on Hayman's generalization of Stirling's formula. Such a formula gives already a couple of correct digits of the length distribution for $n$ as small as $20$ but allows numerical evaluations, with a uniform error of apparent order $n^{-2/3}$, for $n$ as large as $10^{12}$; thus closing the gap between a table of exact values (compiled for up to $n=1000$) and the random matrix limit. Being much more efficient and accurate than Monte-Carlo simulations, the Stirling-type formula allows for a precise numerical understanding of the first few finite size correction terms to the random matrix limit. From this we derive expansions of the expected value and variance of the length, exhibiting several more terms than previously put forward.

arXiv comment27 pages, 6 figures, 3 tables. V7: final version for journal

References in corpus (8)

• Level-Spacing Distributions and the Airy Kernel
• Level-Spacing Distributions and the Bessel Kernel
• On the Numerical Evaluation of Fredholm Determinants
• Accuracy and Stability of Computing High-Order Derivatives of Analytic Functions by Cauchy Integrals
• Limiting distribution of maximal crossing and nesting of Poissonized random matchings
• A note on the expansion of the smallest eigenvalue distribution of the LUE at the hard edge
• A Stirling-type formula for the distribution of the length of longest increasing subsequences
• Edgeworth Expansion of the Largest Eigenvalue Distribution Function of GOE

Cited by in corpus (6)

• Finite size corrections for real eigenvalues of the elliptic Ginibre matrices
• A Stirling-type formula for the distribution of the length of longest increasing subsequences
• Domain wall fluctuations of the six-vertex model at the ice point
• Asymptotic expansions relating to the distribution of the length of longest increasing subsequences
• Asymptotic expansions relating to the lengths of longest monotone subsequences of involutions
• Random Circuits in the Black Hole Interior