Mixing time of the Card-Cyclic-to-Random shuffle

2012/07/14 by Ben Morris, Morris, Ben, Weiyang Ning +3
Computer Science · Mathematics · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1207.3406

openalex publication_date 2012/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Θ(n log n).

Related

• Mixing time of the torus shuffle
• A Lower Bound for the Mixing Time of the Random-to-Random Insertions\n Shuffle
• Card-cyclic-to-random shuffling with relabeling
• Mixing Time of the Overlapping Cycles Shuffle
• Shuffling by semi-random transpositions