Analysis of top to bottom-k shuffles
Goel, Sharad
Ann. Appl. Probab., Tome 16 (2006) no. 1, p. 30-55 / Harvested from Project Euclid
A deck of n cards is shuffled by repeatedly moving the top card to one of the bottom kn positions uniformly at random. We give upper and lower bounds on the total variation mixing time for this shuffle as kn ranges from a constant to n. We also consider a symmetric variant of this shuffle in which at each step either the top card is randomly inserted into the bottom kn positions or a random card from the bottom kn positions is moved to the top. For this reversible shuffle we derive bounds on the L2 mixing time. Finally, we transfer mixing time estimates for the above shuffles to the lazy top to bottom-k walks that move with probability 1/2 at each step.
Publié le : 2006-02-14
Classification:  Finite Markov chains,  mixing time,  card shuffling,  Rudvalis shuffle,  60,  68
@article{1141654280,
     author = {Goel, Sharad},
     title = {Analysis of top to bottom-k shuffles},
     journal = {Ann. Appl. Probab.},
     volume = {16},
     number = {1},
     year = {2006},
     pages = { 30-55},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1141654280}
}
Goel, Sharad. Analysis of top to bottom-k shuffles. Ann. Appl. Probab., Tome 16 (2006) no. 1, pp.  30-55. http://gdmltest.u-ga.fr/item/1141654280/