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

DOI10.1214/13-AAP964zbMATH Open1321.60143arXiv1207.3406OpenAlexW2047080986MaRDI QIDQ744375FDOQ744375

Weiyang Ning, Ben Morris, Yuval Peres

Publication date: 25 September 2014

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

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

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

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

zbMATH Keywords

Markov chainsmixing time

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
• Probability Inequalities for Sums of Bounded Random Variables
• Generating a random permutation with random transpositions
• Comparison techniques for random walk on finite groups
• Title not available (Why is that?)
• Convergence of some time inhomogeneous Markov chains via spectral techniques
• A lower bound for the mixing time of the random-to-random insertions shuffle
• Title not available (Why is that?)

Cited In (9)

• Cutoff for random to random card shuffle
• Cutoff for the cyclic adjacent transposition shuffle
• Extremal measures with prescribed moments
• Spectral analysis of random-to-random Markov chains
• Shuffling Cards and Stopping Times
• Generation of the symmetric group Sn2
• 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

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)