Simultaneous large deviations for the shape of Young diagrams associated with random words

Abstract

We investigate the large deviations of the shape of the random RSK Young diagrams associated with a random word of size $n$ whose letters are independently drawn from an alphabet of size $m=m(n)$. When the letters are drawn uniformly and when both $n$ and $m$ converge together to infinity, $m$ not growing too fast with respect to $n$, the large deviations of the shape of the Young diagrams are shown to be the same as that of the spectrum of the traceless GUE. In the non-uniform case, a control of both highest probabilities will ensure that the length of the top row of the diagram satisfies a large deviation principle. In either case, both speeds and rate functions are identified. To complete our study, non-asymptotic concentration bounds for the length of the top row of the diagrams, that is, for the length of the longest increasing subsequence of the random word are also given for both models.

Published at http://dx.doi.org/10.3150/14-BEJ612 in the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

References in corpus (4)

• Large Deviations of Extreme Eigenvalues of Random Matrices
• Statistical distribution of quantum entanglement for a random bipartite state
• Asymptotics for random Young diagrams when the word length and alphabet size simultaneously grow to infinity
• On the Limiting Shape of Young Diagrams Associated With Markov Random Words