If we draw cards from a deck without replacement, how many cards would I have to draw on average until I obtain two kings

Question

You have probably heard a similar problem from 50 challenging problems in probability:

"How many cards do I have to draw until I obtain an ace from a standard deck of playing cards?"

The answer for the above problem is 10.6, which can be obtain through manual calculation or using partitions.

I wanted to extend this problem to drawing two cards of a set, and I was wondering how this could be done.

My initial thoughts on the two approaches were:

Brute force approach:

$E[\text{two kings}] = P[\text{two kings in 2 draws}]\times2 + P[\text{two kings in 3 draws}]\times 3 + \dots + P[\text{two kings in 52 draws}]\times 52$

$E[X] = (\frac{4}{52} \frac{3}{51} 2) + {2 \choose 1} (\frac{4}{52}\frac{48}{51}\frac{3}{50}) + \dots + {52 \choose 1} (\frac{4}{52} \frac{48}{51} \dots \frac{1}{1})$

Partition Approach:

$E[\text{two kings}] = E[\text{second king|first king}] + E[\text{first king}]$

And this is where I draw a blank, if I take the average value of the first king here, I get 10.6, and the partition approach no longer works. Any assistance on this would be great.

Answer 1

Solution by Symmetry: (Imagine an $N$ card deck with $4$ Kings).

Add a joker to the deck and shuffle the deck, arranging the cards in a circle. By symmetry we expect the gaps between each of the five special cards (the joker and the Kings) to be equal. Thus the gaps are $\frac {N+1-5}5=\frac {N-4}5$ long. Now, break the circle at the Joker and regard the next as the top card in the shuffled deck. We then get an expected number until the second King as $$2\times \frac {N-4}5+2=\frac {2(N+1)}5$$

Solution by Linearity:

Let $X$ be any non-King. We look at the shuffle and ask for the probability that $X$ appears before the second King. There are two slots among the five that do the job, so the answer is $\frac 25$. There are $N-4$ non-kings so the expected number of such $X$ which appear before the second King is $\frac {2(N-4)}5$. As we need to add back the two Kings we get $$E_{N,0}=\frac {2N-8}5+2=\frac {2(N+1)}5$$ as desired.

Solution by Recurrence:

Let $E_{N,0}$ be the expected number of draws it will take if there are $N$ cards left in the deck and if you have seen no Kings so far. Thus, the answer you want is $E_{52, 0}$.

Let $E_{N,1}$ be the expected number of draws it will take assuming you have seen exactly $1$ King so far.

You know how to compute $E_{N,1}$ recursively; that's essentially the problem you cited at the start. We get $$E_{N,1}=\frac 3{N}\times 1 +\frac {N-3}N\times (E_{N-1, 1}+1)=1+\frac {N-3}N\times E_{N-1, 1}$$

Or, you can use symmetry arguments to get the result, $$E_{N, 1}=\frac {N+1}4$$ as in the other argument.

But, similarly, $$E_{N,0}=1+\frac 4N\times E_{N-1,1}+\frac {N-4}N\times E_{N-1, 0}$$

and the rest is just computation.

The final expression is just $$E_{N,0}=\frac {2(N+1)}5$$