**Introduction**

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.

**Approach**

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 ).

**Solution**

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.

The fact that there is a range 8 between the expected number of shuffles for a card at the top of the deck vs the middle seems to correlate reasonably well with the oft-cited idea that it takes about 7 shuffles to randomize a deck.

Interesting concept. Commenting to follow the blog.

Rather than plot the average number of shuffles, what about plotting the distribution vs. original location the in deck?

I imagine doing that will show broad distributions at the ends, and more narrow distribution in the middle. But maybe I am wrong.

These two plots show the distribution of number of shuffles needed to move each card (from position 1 through 51) to the bottom of the deck for the first time. The first plot shows the very similar tails out to 600 shuffles; the second plot just zooms in on the first 10 shuffles.

That early peak in the middle of the deck makes sense: the probability of moving the card in position 26 to the bottom in a single shuffle is , since the only constraints are that (a) there are exactly 26 zeros in the encoding for the shuffle, and (b) one of those zeros is in the last/bottom position.

Pingback: Seven riffle shuffles is not enough– except when it is | Possibly Wrong