Cutoff for random to random card shuffle

DOI10.1214/19-AOP1340zbMATH Open1448.60154arXiv1703.06210MaRDI QIDQ2280558FDOQ2280558

Authors: Megan Bernstein, Evita Nestoridi 

Publication date: 18 December 2019

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

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.

Full work available at URL: https://arxiv.org/abs/1703.06210

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

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)

Cites Work

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

Cited In (18)

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

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)