Detailed mathematical approach

Problem Summary

A standard deck has 13 ranks and 4 suits, so each rank appears four times. Cards are drawn without replacement until either two consecutive cards share a rank or the deck runs out. The quantity to compute is the expected total number of draws. Since only rank equality matters, suits never need to be tracked individually.

Mathematical Approach

It is convenient to analyze a generalized deck with \(r\) ranks and \(c\) copies of each rank, then substitute \(r=13\) and \(c=4\) at the end. The key observation is that after at least one card has been drawn, the future depends only on how many copies remain of the last rank and on how the other ranks are distributed by remaining multiplicity.

Step 1: Compress the deck into a rank histogram

After any nonterminal history, call the rank of the most recently drawn card the current rank. Let \(m\in\{0,1,\dots,c-1\}\) be the number of undealt cards of that current rank. For every \(j\in\{0,1,\dots,c\}\), let \(a_j\) be the number of other ranks with exactly \(j\) undealt cards.

Then \((m,a_0,\dots,a_c)\) is a complete Markov state. The identities of the ranks do not matter; only the counts matter, because ranks with the same remaining multiplicity are indistinguishable for every future probability calculation.

For the actual problem \(c=4\), so the histogram has buckets \(a_0,a_1,a_2,a_3,a_4\), and the non-current ranks always satisfy

$a_0+a_1+a_2+a_3+a_4=12.$

Step 2: Compute the remaining cards and the stopping probability

If the current state is \((m,\mathbf{a})\), the number of undealt cards is

$R(m,\mathbf{a})=m+\sum_{j=1}^{c} j a_j.$

The next draw creates a consecutive pair exactly when it comes from the current rank, which has \(m\) surviving copies. Therefore

$\Pr(\text{stop on next draw}\mid m,\mathbf{a})=\frac{m}{R(m,\mathbf{a})}.$

If \(m=0\), the last drawn rank is already exhausted, so the next draw cannot stop the process immediately. The same formula still gives probability \(0\).

Step 3: Describe the non-stopping transitions

Suppose the next card comes from a different rank that currently belongs to bucket \(j\), meaning that this rank has \(j\) undealt copies before the draw. There are \(a_j\) such ranks and \(j a_j\) eligible cards, so

$\Pr(\text{choose a rank from bucket }j\mid m,\mathbf{a})=\frac{j a_j}{R(m,\mathbf{a})},\qquad 1\le j\le c.$

After that draw, the newly drawn rank becomes the new current rank and has \(j-1\) cards left. The previous current rank stops being current and re-enters the histogram with \(m\) cards left. Hence the new state is

$\left(j-1,\ \mathbf{a}-\mathbf{e}_j+\mathbf{e}_m\right),$

where \(\mathbf{e}_k\) is the unit vector of the histogram. This update also handles the case \(m=0\): the exhausted previous current rank is simply recorded in the zero bucket.

Step 4: Write the expectation recurrence

Let \(E(m,\mathbf{a})\) denote the expected number of additional draws from state \((m,\mathbf{a})\). If no cards remain, then

$E(m,\mathbf{a})=0\qquad\text{when }R(m,\mathbf{a})=0.$

Otherwise one new card is certainly drawn now, contributing the leading \(1\). If that card matches the current rank, the process stops immediately, so there is no recursive term for that branch. Summing only over the non-stopping branches gives

$E(m,\mathbf{a})=1+\sum_{j=1}^{c}\frac{j a_j}{R(m,\mathbf{a})}\,E\!\left(j-1,\mathbf{a}-\mathbf{e}_j+\mathbf{e}_m\right).$

This is the full dynamic program. Every transition removes exactly one undealt card, so the recursion always moves toward smaller states.

Step 5: Initialize the real 52-card deck

Before any draw there is no current rank, so the recursion is started after the first card is taken. In a deck with \(r\) ranks and \(c\) copies per rank, the first draw leaves

$m=c-1,\qquad a_c=r-1,\qquad a_j=0\ \text{for }j\ne c.$

Therefore the total expected number of draws is

$1+E\!\left(c-1,\mathbf{a}^{(0)}\right).$

For the Project Euler deck, \(r=13\) and \(c=4\), so

$\mathbb{E}[\text{total draws}]=1+E(3,a_0=0,a_1=0,a_2=0,a_3=0,a_4=12).$

The first transition from this state already explains the simple sanity check

$\Pr(\text{stop on draw 2})=\frac{3}{51}=\frac{1}{17}.$

Worked Example: two ranks with two copies each

A very small deck makes the recurrence transparent. Take \(r=2\) and \(c=2\). After the first draw, the state is \(m=1\) and \(a_2=1\), so let

$X=E(1,a_0=0,a_1=0,a_2=1).$

There are \(R=3\) undealt cards. With probability \(1/3\) the next card matches the current rank and the process ends after one more draw. With probability \(2/3\) we move to the state \(E(1,a_0=0,a_1=1,a_2=0)\). Hence

$X=1+\frac{2}{3}E(1,a_0=0,a_1=1,a_2=0).$

Now let

$Y=E(1,a_0=0,a_1=1,a_2=0).$

Then \(R=2\), so

$Y=1+\frac{1}{2}E(0,a_0=0,a_1=1,a_2=0).$

Finally, from \(E(0,a_0=0,a_1=1,a_2=0)\) only one card remains, it cannot match the exhausted current rank, and drawing it empties the deck, so

$E(0,a_0=0,a_1=1,a_2=0)=1.$

Therefore \(Y=1+\frac12=\frac32\), then \(X=1+\frac23\cdot\frac32=2\), and the full expectation is

$1+X=3.$

This matches the small checkpoint used by the implementations and confirms the recurrence.

How the Code Works

The C++, Python, and Java implementations all use the same memoized recursion. They encode the current remainder together with the histogram of remaining rank multiplicities into a compact state key, so each reachable state is evaluated once. For a queried state, the implementation first computes \(R\), returns \(0\) if the deck is empty, and otherwise starts from the mandatory next draw.

It then iterates through the possible buckets \(j=1,\dots,c\). Whenever bucket \(j\) is nonempty, the implementation applies the probability \(\frac{j a_j}{R}\), updates the histogram to reflect the new current rank and the old current rank returning to the bucket structure, and recursively asks for the expectation of the new state. Memoization turns the naive recursion tree into a compact dynamic program over the reachable histogram states.

For the actual input \((r,c)=(13,4)\), the program prints the expectation to eight decimal places. Floating-point arithmetic is sufficient here because the state graph is small and the recurrence is numerically stable for this instance.

Complexity Analysis

For a generalized deck with \(r\) ranks and \(c\) copies per rank, the \(r-1\) non-current ranks can be distributed among the \(c+1\) buckets in at most

$\binom{r+c-1}{c}$

ways. The current rank contributes \(c\) possible values of \(m\in\{0,\dots,c-1\}\), so an upper bound on the number of abstract states is

$|\mathcal{S}|\le c\binom{r+c-1}{c}.$

Each state considers at most \(c\) transitions, so the memoized running time is \(O(c|\mathcal{S}|)\), and the memory usage is \(O(|\mathcal{S}|)\). For the real deck this gives at most

$4\binom{16}{4}=7280$

states, which is tiny.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=856
2. Markov chain: Wikipedia — Markov chain
3. Expected value: Wikipedia — Expected value
4. Hypergeometric distribution: Wikipedia — Hypergeometric distribution
5. Dynamic programming: Wikipedia — Dynamic programming