On the rate of mixing for p-shuffles

Authors
Citation
Sp. Lalley, On the rate of mixing for p-shuffles, ANN APPL PR, 10(4), 2000, pp. 1302-1321
Citations number
8
Categorie Soggetti
Mathematics
Journal title
ANNALS OF APPLIED PROBABILITY
ISSN journal
10505164 → ACNP
Volume
10
Issue
4
Year of publication
2000
Pages
1302 - 1321
Database
ISI
SICI code
1050-5164(200011)10:4<1302:OTROMF>2.0.ZU;2-7
Abstract
The p-shuffle is a natural generalization of the dovetail shuffle. It is de fined as follows. First, the deck is cut into a top stack and a bottom stac k so that the distribution of the size of the top stack is Binomial (N, p), where N is the total number of cards in the deck Then, conditional on the outcome of the cut, the two stacks are " riffled" in such a way that all po ssible riffles (interleavings) of these two stacks are equally likely The m ain result of the paper is an asymptotic (N --> infinity) bound on the numb er of repetitions needed to "randomize" the deck.