Solution

Answer: 17.09661501

Let $T$ be the number of cards drawn until the first time two consecutive cards have the same rank, or until the deck is exhausted.

We want

$$\mathbb E[T].$$

1. Key probabilistic idea

A standard identity for nonnegative integer-valued random variables is

$$\mathbb E[T] = \sum_{n\ge0}\Pr(T>n).$$

Here, $T>n$ means:

after the first $n$ draws, no consecutive cards share the same rank.

Since the deck has only 52 cards,

$$\mathbb E[T] = \sum_{n=0}^{51} q_n,$$

where

$$q_n=\Pr(\text{no adjacent equal ranks among first }n\text{ cards}).$$

Clearly,

$$q_0=q_1=1.$$

So the entire problem reduces to computing the probabilities $q_n$.

2. State compression

A direct brute force over all deck orders is impossible.

Instead we observe:

At any point, the future only depends on

how many ranks currently have 0,1,2,3,4 cards already used,
and how many cards of the last drawn rank have already been used.

Define the state

$$(c_0,c_1,c_2,c_3,c_4;\ell),$$

where

$c_i$ = number of ranks for which exactly $i$ cards have been drawn,
$\ell\in{1,2,3,4}$ = how many cards of the last drawn rank have been used.

Initially, after one card is drawn:

$$(12,1,0,0,0;1).$$

3. Transition rule

Suppose we are in state

$$(c_0,c_1,c_2,c_3,c_4;\ell)$$

after $n$ draws.

There are $52-n$ cards remaining.

To avoid creating a pair, the next card cannot have the same rank as the previous card.

If we choose a rank currently used $j$ times:

there are $4-j$ cards of that rank remaining,
and there are

$$c_j - \mathbf 1_{{\ell=j}}$$

available ranks of that type (excluding the previous rank itself).

Hence the transition probability is

$$\frac{ \left(c_j-\mathbf 1_{{\ell=j}}\right)(4-j) }{ 52-n }.$$

After choosing such a rank:

one rank moves from class $j$ to class $j+1$,
the new last-rank count becomes $j+1$.

This gives a tiny DP state space and computes all $q_n$ exactly.

4. Python implementation

from collections import defaultdict

# dist[state] = probability of being in that state
# after n draws with no adjacent equal ranks
#
# state = (c0, c1, c2, c3, c4, lastk)

dist = {
    (12, 1, 0, 0, 0, 1): 1.0
}

# q[n] = probability that first n draws contain no adjacent equal ranks
q = [1.0, 1.0]

# We already handled n = 1.
# Build q[2] ... q[51].
for draws in range(1, 51):

    next_dist = defaultdict(float)
    survive_prob = 0.0

    remaining = 52 - draws

    for state, prob in dist.items():

        c = list(state[:5])
        lastk = state[5]

        # Choose a new rank type j = 0,1,2,3
        for j in range(4):

            # Number of usable ranks with j used cards,
            # excluding the previous rank if necessary
            usable_ranks = c[j] - (1 if lastk == j else 0)

            if usable_ranks <= 0:
                continue

            ways = usable_ranks * (4 - j)

            p = prob * ways / remaining

            # Update occupancy counts
            nc = c.copy()
            nc[j] -= 1
            nc[j + 1] += 1

            new_state = tuple(nc + [j + 1])

            next_dist[new_state] += p
            survive_prob += p

    dist = next_dist
    q.append(survive_prob)

# Expected value
E = sum(q)

print("{:.12f}".format(E))

5. Code walkthrough

Initialization

dist = {(12,1,0,0,0,1): 1.0}

After the first card:

12 ranks have 0 used cards,
1 rank has 1 used card,
the last rank currently has 1 used card.

Main loop

for draws in range(1, 51):

At step draws, we already know all safe states after that many draws.

We compute the distribution after one more safe draw.

Counting safe choices

usable_ranks = c[j] - (1 if lastk == j else 0)

If the previous rank also lies in class $j$, we must exclude it.

Each usable rank contributes $4-j$ remaining cards.

State update

nc[j] -= 1
nc[j + 1] += 1

A rank with $j$ used cards becomes a rank with $j+1$ used cards.

Expected value

E = sum(q)

using

$$\mathbb E[T] = \sum_{n=0}^{51} q_n.$$

6. Sanity checks

The probability that the first two cards form a pair is

$$\frac{3}{51}=\frac1{17},$$

matching the statement.

If draws were independent with probability $1/13$ of matching the previous rank, the expectation would be roughly $13$.

Because cards are drawn without replacement, repeats become less likely early on, so the true expectation should be somewhat larger.

Obtained value:

$$17.09661501\ldots$$

which is perfectly reasonable.

Answer: 17.09661501

Project Euler Problem 856