On The Rate Of Mixing For p-Shuffles

. The p-shuffle is a natural generalization of the dovetail shuffle that is defined as follows. First, the deck is cut into a top stack and a bottom stack 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 possible riffles (interleavings) of these two stacks are equally likely. The main result of the paper is an asymptotic (N !1) bound on the number of repetitions needed to "randomize" the deck. 1. Introduction The p-shuffle (or GSR-p shuffles, for Gilbert, Shannon, and Reeds) is a simple and natural generalization of the dovetail (or GSR) shuffle studied in [3] and [1]. For 0 ! p ! 1 and a deck of size N , the p-shuffle is defined as follows: First, "cut" the deck into two stacks in such a way that the cardinality of the top stack has the Binomial (N; p) distribution. Next, "riffle" the two stacks by dropping cards o..