CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Card-cyclic-to-random shuffling with relabeling

Johan Jonasson (Institutionen för matematiska vetenskaper, matematik)
Alea-Latin American Journal of Probability and Mathematical Statistics (1980-0436). Vol. 12 (2015), 2, p. 793-810.
[Artikel, refereegranskad vetenskaplig]

The card-cyclic-to-random shuffle is the card shuffle where the n cards arc labeled 1,...,n according to their starting positions. Then the cards are mixed by first picking card] 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 et al. (2014) recently showed that the order of the number of shuffles needed to mix the deck in this way is n log n. 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 n log n.

Nyckelord: mixing time, stability of eigenvalues



Denna post skapades 2016-10-19. Senast ändrad 2016-11-16.
CPL Pubid: 243702

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)

Ämnesområden

Diskret matematik

Chalmers infrastruktur