How many riffles does it take until all permutations are possible?

So yesterday I was working on new Wikipedia articles on riffle shuffle permutations (an awkward name: I would have preferred riffle permutations but I couldn't find enough sources that called them that) and the Gilbert–Shannon–Reeds model of random shuffling. There's been a lot of work on how many riffles you need to do until all permutations are nearly equally likely (by some reasonable measures, the answer is \( 1.5\log_2 n \)) but it occurred to me to ask a simpler question: how many riffles do you need to do until all permutations have nonzero probability? If you riffle the deck only once, for instance, you can only form a small fraction of the possible permutations: there are roughly \( 2^n \) different riffles, a much smaller number than \( n! \). And which permutation requires the most riffles to be generated?

The answer turns out to be surprisingly easy, if one thinks about riffles from the point of view of dynamical systems rather than card shuffling, as Bayer and Diaconis did. Consider any set of n points in the unit interval \( [0,1), \) and to avoid collisions assume that no two of the points differ by a dyadic rational. Then the doubling map that doubles each number and then takes the fractional part of the results transforms the point set by a riffle, and any riffle can be achieved in this way. Another way of thinking about this map, in more computer science related terms, is that we shift the binary representations of each number left by one position and then chop off the top bit. More strongly, repeating the doubling map \( k \) times (shifting left by \( k \) positions then chopping) gives a permutation that is the result of \( k \) riffles, and each \( k \)-riffle permutation can be achieved in this way, because the chopped-off bits give all the information needed to describe what happens in each riffle. (If the initial positions of the points are uniformly random and independent of each other, then this process preserves that uniform independent distribution, and the permutations one gets are distributed exactly according to the Gilbert–Shannon–Reeds model. But we don't need that for what follows.)

So, suppose you want to achieve the permutation that takes the initially sorted card deck and reverses its order. And suppose you try to do this with fewer than \( log_2 n \) riffles. Then the number of different patterns of chopped-off bits that you can achieve will be fewer than \( n \), and by the pigeonhole principle some two cards will have the same pattern. But then, those two cards will remain in the same order throughout the sequence of riffles, preventing you from achieving a complete reversal. That is, the reversal permutation is not a product of fewer than \( \log_2 n \) riffles. On the other hand, with exactly \( \lceil\log_2 n\rceil \) riffles, you can give each card its own distinct pattern of chopped-off bits, allowing any permutation to be realized. So the number of riffles you need to perform, in order to guarantee that all permutations have nonzero probability, is exactly \( \lceil\log_2 n\rceil. \)

Bayer and Diaconis give a precise formula for the probability of a given permutation after a given number of riffles, in the Gilbert–Shannon–Reeds model, in terms of the number of rising sequences; this formula can also be used to derive the same \( \lceil\log_2 n\rceil \) for the number of riffles needed for all permutations to have nonzero probability. However, the number of riffles needed does not depend on the details of the probability distribution on riffles, but only on the fact that a single riffle should be able to produce all of the different riffle permutations with nonzero probability.

---

Comments: