Limit profile for random transpositions (Q2212595): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1905.08514 / rank | |||
Normal rank |
Revision as of 03:13, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Limit profile for random transpositions |
scientific article |
Statements
Limit profile for random transpositions (English)
0 references
24 November 2020
0 references
\textit{P. Diaconis} and \textit{M. Shahshahani} [Z. Wahrscheinlichkeitstheor. Verw. Geb. 57, 159--179 (1981; Zbl 0485.60006)] showed that a sequence of random compositions of transpositions on the symmetric group \(S_n\) on \(n\) symbols (the random transposition shuffle) exhibits a so-called cut-off phenomenon at time \(f(n) \equiv\frac{1}{ 2}n\log(n)\). This means roughly that the distribution of the resulting Markov chain is almost uniform on \(S_n\) at times larger than \(f(n)\) and very far from uniform at times smaller than \(f(n)\). In this paper the author describes more precisely the way this transition to uniform occurs. The key tool is an improved version of the Diaconis-Shahshahani upper bound lemma, which is used to compute the limiting value of the distance to stationarity. The main result is the following description of the limit profile for the random transposition shuffle: Let \(c\) be a real number. The total variation distance between the distribution of the transposition shuffle on \(S_n\) at time \(\lfloor{f(n)+cn}\rfloor\) and the uniform distribution on \(S_n\) converges to the distance between the Poisson distribution with parameter \(1 + e^{-2c}\) and the Poisson distribution with parameter 1, as \(n \to \infty\).
0 references
cutoff phenomenon
0 references
mixing times
0 references
Markov chains
0 references
card shuffling
0 references
symmetric group
0 references
random transpositions
0 references