Cutoff for random to random card shuffle

DOI10.1214/19-AOP1340MaRDI QIDQ2280558zbMATH OpenFDO

Authors Megan Bernstein, Evita Nestoridi

Publication date 18 December 2019

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.06210, https://projecteuclid.org/euclid.aop/1571731452

zbMATH Keywords

cutoffmixing timescard shufflecyclic-to-randomrandom-to-random

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Algebraic combinatorics (05E99) Representations of finite symmetric groups (20C30)

Abstract: In this paper, we use the eigenvalues of the random to random card shuffle to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at $frac34nlogn-frac14nloglogn$ with window of order $n$, answering a conjecture of Diaconis.

Recommendations

• A lower bound for the mixing time of the random-to-random insertions shuffle
• Cutoff for the cyclic adjacent transposition shuffle
• Extremal measures with prescribed moments
• Cutoff for a one-sided transposition shuffle
• Mixing time of the card-cyclic-to-random shuffle

Cites work

• scientific article; zbMATH DE number 1981749 (Why is no real title available?)
• scientific article; zbMATH DE number 1889799 (Why is no real title available?)
• A Remark on Stirling's Formula
• A lower bound for the mixing time of the random-to-random insertions shuffle
• Comparison techniques for random walk on finite groups
• Convergence of some time inhomogeneous Markov chains via spectral techniques
• Generating a random permutation with random transpositions
• Improved bounds for the mixing time of the random-to-random shuffle
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Merging and stability for time inhomogeneous finite Markov chains
• Merging for time inhomogeneous finite Markov chains. I: Singular values and stability
• Mixing time of the card-cyclic-to-random shuffle
• Probabilistic and combinatorial aspects of the card-cyclic to random insertion shuffle
• Refined estimates for some basic random walks on the symmetric and alternating groups
• Spectra of symmetrized shuffling operators
• Spectral analysis of random-to-random Markov chains
• The cutoff phenomenon for ergodic Markov processes
• The cutoff phenomenon in finite Markov chains.
• Time inhomogeneous Markov chains with wave-like behavior

Cited in

(18)

• Total variation cutoff for the flip-transpose top with random shuffle
• The cutoff phenomenon for randomized riffle shuffles
• Cutoff profile of the metropolis biased card shuffling
• Extremal measures with prescribed moments
• Cutoff phenomenon for the warp-transpose top with random shuffle
• Comparing limit profiles of reversible Markov chains
• Cutoff for the asymmetric riffle shuffle
• Limit profile for random transpositions
• The hit-and-run version of top-to-random
• Cutoff for a one-sided transposition shuffle
• A lower bound for the mixing time of the random-to-random insertions shuffle
• Eigenvalues of symmetrized shuffling operators
• Improved bounds for the mixing time of the random-to-random shuffle
• The \(S_k\) shuffle block dynamics
• Likelihood orders for the \(p\)-cycle walks on the symmetric group
• On random walks and switched random walks on homogeneous spaces
• Cutoff for the cyclic adjacent transposition shuffle
• Shuffling cards by spatial motion

This page was built for publication: Cutoff for random to random card shuffle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2280558)