Riffle Shuffles And Their Associated Dynamical Systems

. It is shown that for every stationary sequence of random riffle permutations there is a natural associated dynamical system consisting of random orbits in the space of sequences from a finite alphabet. For many interesting models of card-shuffling, the associated dynamical systems have simple descriptions in terms of random or deterministic measure-preserving maps of the unit interval. It is shown that the rate of mixing for a card-shuffling process is constrained by the fiber entropy h of this map: at least (log N)=h repititions of the shuffle are needed to randomize a deck of size N , when N is large. 1. Introduction The preferred method of randomizing a deck of N cards is the riffle shuffle--cut the deck into two stacks, then riffle the two stacks together. A number of mathematical models have been proposed for this process. The model which has received the most attention, and about which the most is known, is the GSR (for Gilbert, Shannon, and Reeds) shuffle. In this model, al..