Limit profile for random transpositions (Q2212595): Difference between revisions

\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\).