To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Tell a friend about this page
Print version

Card-cyclic-to-random shu… - University of Gothenburg, Sweden Till startsida
Sitemap
To content Read more about how we use cookies on gu.se

Card-cyclic-to-random shuffling with relabeling

Journal article
Authors Johan Jonasson
Published in Alea-Latin American Journal of Probability and Mathematical Statistics
Volume 12
Issue 2
Pages 793-810
ISSN 1980-0436
Publication year 2015
Published at Department of Mathematical Sciences, Mathematics
Pages 793-810
Language en
Links alea.impa.br/articles/v12/12-30.pdf
Keywords mixing time, stability of eigenvalues
Subject categories Discrete Mathematics

Abstract

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.

Page Manager: Webmaster|Last update: 9/11/2012
Share:

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?