Fluctuations of Schensted row insertion
- 1 September 2026
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Probability
- Vol. 54 (5) , 2626-2688
Abstract
We investigate asymptotic probabilistic phenomena arising from the application of the Schensted row insertion algorithm, a key component of the Robinson–Schensted–Knuth (RSK) correspondence, to random inputs. Our analysis centers on a random tableau T with a given shape λ, which may itself be random or deterministic. We examine the stochastic properties of the position of the new box created when inserting a deterministic entry into T. Specifically, we focus on the fluctuations of this position around its expected value as the size of the Young diagram λ approaches infinity. Our findings reveal that these fluctuations are asymptotically Gaussian, with the mean and variance expressed in terms of Kerov’s transition measure of the diagram λ. An important application of this analysis is the RSK algorithm applied to a finite, long sequence of independent, identically distributed random variables. While there remains a gap in the reasoning for this case, we present an explicit conjecture regarding its behavior.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Random sorting networks: local statistics via random matrix lawsProbability Theory and Related Fields, 2018
- Free Probability and Random Matrices2017
- Gaussian fluctuations of characters of symmetric groups and of Young diagramsProbability Theory and Related Fields, 2005
- Representations of Symmetric Groups and Free ProbabilityAdvances in Mathematics, 1998
- The analogues of entropy and of Fisher's information measure in free probability theory, IIInventiones Mathematicae, 1994
- Level-spacing distributions and the Airy kernelCommunications in Mathematical Physics, 1994
- Transition probabilities for continual young diagrams and the Markov moment problemFunctional Analysis and Its Applications, 1993
- Asymptotic theory of characters of the symmetric groupFunctional Analysis and Its Applications, 1981
- Non-equilibrium behaviour of a many particle process: Density profile and local equilibriaProbability Theory and Related Fields, 1981
- Die unzerlegbaren, positiv-definiten Klassenfunktionen der abz hlbar unendlichen, symmetrischen GruppeMathematische Zeitschrift, 1964