Fluctuations of Schensted row insertion
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912577098874880 |
|---|---|
| author | Marciniak, Mikołaj Śniady, Piotr |
| author_facet | Marciniak, Mikołaj Śniady, Piotr |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_03762 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fluctuations of Schensted row insertion Marciniak, Mikołaj Śniady, Piotr Probability Combinatorics 60C05 (Primary), 60F05, 05E10, 20C30 60K35, 82C22 (Secondary) 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. |
| title | Fluctuations of Schensted row insertion |
| topic | Probability Combinatorics 60C05 (Primary), 60F05, 05E10, 20C30 60K35, 82C22 (Secondary) |
| url | https://arxiv.org/abs/2302.03762 |