Card-cyclic-to-random shuffling with relabeling

MaRDI QIDQ3465408zbMATH OpenFDO

Authors Johan Jonasson

Publication date 21 January 2016

Full work available at URL https://arxiv.org/abs/1501.05485, http://alea.impa.br/articles/v12/12-30.pdf

zbMATH Keywords

card-cyclic-to-random shuffleeigenvaluesmixing timestability

Mathematics Subject Classification ID

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

Abstract: The card-cyclic-to-random shuffle is the card shuffle where the $n$ cards are labeled $1,ldots,n$ according to their starting positions. Then the cards are mixed by first picking card $1$ from the deck and reinserting it at a uniformly random position, then repeating for card $2$, then for card $3$ and so on until all cards have been reinserted in this way. Then the procedure starts over again, by first picking the card with label $1$ and reinserting, and so on. Morris, Ning and Peres cite{MNP} recently showed that the order of the number of shuffles needed to mix the deck in this way is $nlogn$. In the present paper, we consider a variant of this shuffle with relabeling, i.e. a shuffle that differs from the above in that after one round, i.e. after all cards have been reinserted once, we relabel the cards according to the positions in the deck that they now have. The relabeling is then repeated after each round of shuffling. It is shown that even in this case, the correct order of mixing is $nlogn$.

Recommendations

• Mixing time of the card-cyclic-to-random shuffle
• How many times are needed for card shuffling?
• Shuffling cards by spatial motion
• Mixing time bounds for overlapping cycles shuffles
• Rapid mixing of dealer shuffles and clumpy shuffles

Cited in

(4)

• Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain
• Non-random shuffling for multiple decks
• Moving Card i to Position j with Perfect Shuffles
• Mixing time of the card-cyclic-to-random shuffle

This page was built for publication: Card-cyclic-to-random shuffling with relabeling

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