On the Distributions of the Lengths of the Longest Monotone Subsequences in Random Words

Abstract

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating function gives the distribution of the smallest eigenvalue in the k x k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N -> infinity limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k x k hermitian matrices of trace zero.

30 pages, revised version corrects an error in the statement of Theorem 4

References in corpus (2)

• Correlation Functions, Cluster Functions and Spacing Distributions for Random Matrices
• Random Words, Toeplitz Determinants and Integrable Systems. II

Cited by in corpus (46)

• Operator Spreading in Random Unitary Circuits
• Application of the $\tau$-Function Theory of Painlevé Equations to Random Matrices: PIV, PII and the GUE
• How instanton combinatorics solves Painlevé VI, V and III's
• Random Words, Toeplitz Determinants and Integrable Systems. II
• The transition between the gap probabilities from the Pearcey to the Airy process; a Riemann-Hilbert approach
• Universality for mathematical and physical systems
• A q-weighted version of the Robinson-Schensted algorithm
• A Limit Theorem for Shifted Schur Measures
• Characteristic polynomials of complex random matrices and Painlevé transcendents
• Supersymmetric $U(N)$ Chern-Simons-matter theory and phase transitions
• Asymptotic performance of port-based teleportation
• The uses of random partitions
• The Hilbert series of U/SU SQCD and Toeplitz Determinants
• Toeplitz minors and specializations of skew Schur polynomials
• A mean identity for longest increasing subsequence problems
• Matrix models for classical groups and Toeplitz$\pm$Hankel minors with applications to Chern-Simons theory and fermionic models
• Multiple phases in a generalized Gross-Witten-Wadia matrix model
• Asymptotics for random Young diagrams when the word length and alphabet size simultaneously grow to infinity
• Local tail bounds for functions of independent random variables
• On the Limiting Shape of Young Diagrams Associated With Markov Random Words
• Asymptotics of Plancherel measures for symmetric groups
• Sparse long blocks and the variance of the longest common subsequences in random words
• Vicious Walkers and Hook Young Tableaux
• Discrete orthogonal polynomial ensembles and the Plancherel measure
• Correlations for symplectic and orthogonal Schur measures
• On the Limiting Shape of Markovian Random Young Tableaux
• Matrix models and stochastic growth in Donaldson-Thomas theory
• On the limiting law of the length of the longest common and increasing subsequences in random words
• Recursion relations for Unitary integrals, Combinatorics and the Toeplitz Lattice
• Generalised unitary group integrals of Ingham-Siegel and Fisher-Hartwig type
• On the rate of approximation in finite-alphabet longest increasing subsequence problems
• Quantum Spectrum Testing
• Fundamental solutions of heat equation on unitary groups establish an improved relation between $\epsilon$-nets and approximate unitary $t$-designs
• Determinantal point processes from symplectic and orthogonal characters and applications
• Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting
• Moments of characteristic polynomials enumerate two-rowed lexicographic arrays
• Virasoro action on Schur function expansions, skew Young tableaux and random walks
• Vicious walkers and random contraction matrices
• Longest common subsequences between words of very unequal length
• Joint moments of derivatives of characteristic polynomials
• Bialternant formula for Schur polynomials with repeating variables
• A path-transformation for random walks and the Robinson-Schensted correspondence
• Applications of Symmetric Functions to Cycle and Increasing Subsequence Structure after Shuffles (Part 2)
• A growth model in a random environment
• Complete homogeneous symmetric polynomials with repeating variables
• Simultaneous large deviations for the shape of Young diagrams associated with random words