Limit profile for random transpositions
\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\).
- Random walks generated by the Ewens distribution on the symmetric group
- Cutoff for a one-sided transposition shuffle
- On the cut-off phenomenon for the transitivity of randomly generated subgroups
- Shuffling large decks of cards and the Bernoulli-Laplace urn model
- The random \((n-k)\)-cycle to transpositions walk on the symmetric group
- Stein's method and descents after riffle shuffles
- Analysis of Top To Random Shuffles
- Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles
- A random walk on the symmetric group generated by random involutions
- A strong uniform time for random transpositions
- Compositions of random transpositions
- Cut-off phenomenon for random walks on free orthogonal quantum groups
- Cutoff for conjugacy-invariant random walks on the permutation group
- Cutoff for random to random card shuffle
- Generating a random permutation with random transpositions
- scientific article; zbMATH DE number 44579 (Why is no real title available?)
- scientific article; zbMATH DE number 3552764 (Why is no real title available?)
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Mixing times for random \(k\)-cycles and coalescence-fragmentation chains
- Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group
- On trees and characters
- Random generators of the symmetric group: diameter, mixing time and spectral gap.
- Rapidly mixing random walks and bounds on characters of the symmetric group
- Representation theory of symmetric groups
- The cutoff profile for the simple exclusion process on the circle
- Trailing the dovetail shuffle to its lair
- Limiting behavior for the distance of a random walk
- A Markov chain on the symmetric group and Jack symmetric functions
- Cutoff for conjugacy-invariant random walks on the permutation group
- Limit profiles for reversible Markov chains
- A sharp log-Sobolev inequality for the multislice
- A phase transition for repeated averages
- Cutoff profile of ASEP on a segment
- Cutoff profiles for quantum Lévy processes and quantum random transpositions
- Cutoff for the warp-transpose top with random shuffle
- Cutoff for a one-sided transposition shuffle
- The random \((n-k)\)-cycle to transpositions walk on the symmetric group
- Compositions of random transpositions
- Total variation cutoff for the flip-transpose top with random shuffle
- Double coset Markov chains
- Partial Shuffles by Lazy Swaps
- Cutoff phenomenon for the warp-transpose top with random shuffle
- Cutoff for rewiring dynamics on perfect matchings
- Cutoff profile of the metropolis biased card shuffling
- Advances in quantum permutation groups
- Comparing limit profiles of reversible Markov chains
- Limit profiles for projections of random walks on groups
- Mixing time and cutoff for the k-SPEP
- Limit profile for the transpose top-2 with random shuffle
- Cutoff in total variation for the shelf shuffle
- Every cutoff profile is possible
- Limit profile for the Bernoulli-Laplace urn via diffusions
- Limit profile for the ASEP with one open boundary
- Representation theory and cycle statistics for random walks on the symmetric group
- A strong uniform time for random transpositions
- Stein's method and descents after riffle shuffles
This page was built for publication: Limit profile for random transpositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2212595)
