Tracking a card through a shuffled deck

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 n=52 cards is as a uniformly random string of n bits (imagine flipping a fair coin n 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 2^n possible equally likely GSR shuffles, how many move the card from position i down to position j, where 1 \leq i<j \leq n? This number s(i,j) is equal to the number of bit strings with at least i zeros (since the card we want to move down must be in the top half of the cut), and exactly j-i ones before the i-th zero. That is,

s(i,j) = \sum\limits_{k=i}^n {j-1 \choose i-1} {n-j \choose k-i}

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 (i>j), or that fix a card (i=j) so that it remains in its original position, with the result being a transition matrix P given by

P_{i,j} = \frac{s(i,j) + s(n+1-i,n+1-j)}{2^n}, 1 \leq i,j \leq n

where P_{i,j} indicates the probability that a single GSR shuffle will move the card in position i to position j.

At this point, we have what we need: consider a Markov chain with n states corresponding to the current position of a particular distinguished card in the deck. If this distinguished card starts in position, say, i=1 (i.e., the top card of the deck), then our initial state distribution \pi_0 is the i-th basis (row) vector, and we can track the distribution of possible future positions of the card after k shuffles as \pi_0 P^k.

But we originally asked for the average number of shuffles needed to move the card initially at location i=1 to location j=n. To calculate this, let Q be the matrix obtained from P by deleting row j and column j, and compute the fundamental matrix N=(I-Q)^{-1}. Then the expected number of shuffles until the target card starting in position i first reaches position j is the sum of the values in the i-th row of N (or the i-1-st row if i>j).

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 n cards, the expected number of GSR shuffles to move the top card to the bottom of the deck appears to be exactly 2n. 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!

Expected number of shuffles to move a card to the bottom of a 52-card 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.

This entry was posted in Uncategorized. Bookmark the permalink.

4 Responses to Tracking a card through a shuffled deck

  1. bhugh says:

    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.

  2. ke3j3j says:

    Interesting concept. Commenting to follow the blog.

  3. Jons says:

    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 {51 \choose 25}/2^{52}, 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.