Mixing time of the card-cyclic-to-random shuffle

DOI10.1214/13-AAP964MaRDI QIDQ744375zbMATH OpenOpenAlexFDO

Authors Ben Morris, Weiyang Ning, Yuval Peres

Publication date 25 September 2014

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

Full work available at URL https://arxiv.org/abs/1207.3406, https://projecteuclid.org/euclid.aoap/1403812363

zbMATH Keywords

Markov chainsmixing time

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: The Card-Cyclic-to-Random shuffle on $n$ cards is defined as follows: at time $t$ remove the card with label $t$ mod $n$ and randomly reinsert it back into the deck. Pinsky introduced this shuffle and asked how many steps are needed to mix the deck. He showed $n$ steps do not suffice. Here we show that the mixing time is on the order of $Theta(nlogn)$.

Recommendations

• Card-cyclic-to-random shuffling with relabeling
• Mixing time bounds for overlapping cycles shuffles
• How many times are needed for card shuffling?
• Improved mixing time bounds for the Thorp shuffle
• The Mixing Time of the Thorp Shuffle

Cites work

• scientific article; zbMATH DE number 1942428 (Why is no real title available?)
• scientific article; zbMATH DE number 6472599 (Why is no real title available?)
• A lower bound for the mixing time of the random-to-random insertions shuffle
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
• 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
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Probability Inequalities for Sums of Bounded Random Variables

Cited in

(18)

• Cutoff for random to random card shuffle
• Cutoff for the cyclic adjacent transposition shuffle
• Card-cyclic-to-random shuffling with relabeling
• Generation of the symmetric group \(S_{n^2}\)
• A shuffle that mixes sets of any fixed size much faster than it mixes the whole deck
• Extremal measures with prescribed moments
• Shuffling cards by spatial motion
• Mixing time bounds for overlapping cycles shuffles
• The overhand shuffle mixes in \(\Theta(n^2\log n)\) steps
• Improved mixing time bounds for the Thorp shuffle
• Spectral analysis of random-to-random Markov chains
• Probabilistic and combinatorial aspects of the card-cyclic to random insertion shuffle
• Shuffling Cards and Stopping Times
• Mixing time of the Rudvalis shuffle
• Rapid mixing of dealer shuffles and clumpy shuffles
• Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain
• Improved bounds for the mixing time of the random-to-random shuffle
• A lower bound for the mixing time of the random-to-random insertions shuffle

This page was built for publication: Mixing time of the card-cyclic-to-random shuffle

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