Riffle shuffle a deck of cards once. What is the probability that the original top card ends up on the bottom of the shuffled deck (or vice versa)? This is very unlikely… but suppose that we shuffle again… and again, etc. How many shuffles on average are required until we first see the original top card moved to the bottom of the deck? The motivation for this post is to capture my notes on this problem, which turns out to have a very nice solution.
To begin, we use the Gilbert-Shannon-Reeds (GSR) model of a riffle shuffle, that captures– in a realistic but mathematically tractable way– the random imperfections in how most non-expert humans shuffle cards: by cutting the deck roughly in half, then interleaving the cards back together from the two halves, with some clumping.
There are several different characterizations of the GSR model, all yielding the same probability distribution of possible permutations of the cards in the deck. For our purpose, the most convenient way to model a single random GSR shuffle of a deck with cards is as a uniformly random string of bits (imagine flipping a fair coin times). The number of zero bits indicates how many cards to cut from the top of the deck, and the positions of the zero bits indicate how those top cards are interleaved with the cards from the bottom part of the deck (represented by the one bits). The following Python code illustrates how this works:
import numpy as np def riffle_shuffle(cards, rng=np.random.default_rng()): bits = rng.integers(0, 2, len(cards)) return [cards[k] for k in np.argsort(np.argsort(bits, kind='stable'))] print(riffle_shuffle(range(52)))
This representation of a riffle shuffle as a bit string makes it easy to calculate probabilities of various types of shuffles. For example, of all possible equally likely GSR shuffles, how many move the card from position down to position , where ? This number is equal to the number of bit strings with at least zeros (since the card we want to move down must be in the top half of the cut), and exactly ones before the -th zero. That is,
It’s an exercise for the reader to show that we can extend this approach to also count shuffles that move a card up in the deck (), or that fix a card () so that it remains in its original position, with the result being a transition matrix given by
where indicates the probability that a single GSR shuffle will move the card in position to position .
At this point, we have what we need: consider a Markov chain with states corresponding to the current position of a particular distinguished card in the deck. If this distinguished card starts in position, say, (i.e., the top card of the deck), then our initial state distribution is the -th basis (row) vector, and we can track the distribution of possible future positions of the card after shuffles as .
But we originally asked for the average number of shuffles needed to move the card initially at location to location . To calculate this, let be the matrix obtained from by deleting row and column , and compute the fundamental matrix . Then the expected number of shuffles until the target card starting in position first reaches position is the sum of the values in the -th row of (or the -st row if ).
The answer is interesting and perhaps surprising. First: it typically takes a long time for the top card to reach the bottom of the deck, over 100 shuffles on average. Second: this average is actually exactly 104 shuffles! More generally, given a deck with cards, the expected number of GSR shuffles to move the top card to the bottom of the deck appears to be exactly . This suggests once again that there may be a nice intuitive argument for this result that I don’t yet see.
Finally, and perhaps most surprising: it takes about that same hundred-or-so shuffles on average to move any card to the bottom of the deck!
In the above figure, the x-axis indicates the starting position of the card that we want to track. The y-axis indicates the expected number of shuffles needed to move that card to the bottom of the deck. For example, even the next-to-bottom card of the deck takes about 102.6 shuffles on average to reach the bottom of the deck.