Expected number of cards turned over before seeing first Ace?

Question

A standard 52-car deck is shuffled, and cards are turned over one-at-a-time starting with the top card. What is the expected number of cards that will be turned over before we see the first Ace? (Recall that there are 4 Aces in the deck.)

There's a very clever way to do this. The $4$ aces partition the deck into $5$ components, with size on average ${{52 - 4}\over5} = 9.6$. We then have to draw the first Ace, so the expected number of cards that'll be turned over before we see it is $9.6 + 1 = 10.6$.

However, for those out there who are stupid like myself (or more generously put, want to practice our computational fortitude), let's do it by brute force. We want to calculate$$1\left({4\over{52}}\right) + 2\left({{48}\over{52}}\right)\left({4\over{51}}\right) + 3 \left({{48}\over{52}}\right)\left({{47}\over{51}}\right)\left({{4}\over{50}}\right) + 4 \left({{48}\over{52}}\right)\left({{47}\over{51}}\right)\left({{46}\over{50}}\right)\left({{4}\over{49}}\right) + \ldots + 48\left({{48}\over{52}}\right)\left({{47}\over{51}}\right)\ldots\left({{2}\over{6}}\right)\left({{4}\over{5}}\right) + 49\left({{48}\over{52}}\right)\left({{47}\over{51}}\right)\ldots\left({{2}\over{6}}\right)\left({{1}\over{5}}\right)\left({{4}\over{4}}\right) = {4\over{52}} + \sum_{n = 2}^{49}\left(n \left(\prod_{i=1}^{n-1} {{49 - i}\over{53 - i}}\right) \left({4\over{53 - n}} \right)\right)$$However, I'm not sure how to proceed with evaluating that expression. How on Earth can I get it to evaluate to $10.6$?

Answer 1

Your summation can be written as $$ \sum_{n=0}^{48}(n+1)\cdot \frac{\binom{48}n}{\binom{52}{n}}\cdot \frac{4}{52-n} $$ The fraction $\binom{48}n \over \binom{52}n$ is the probability the first $n$ cards are not aces, and $4\over 52-n$ is the probability that the $(n+1)^\text{st}$ card is an ace. We can rewrite this sum as \begin{align} 4\sum_{n=0}^{48} (n+1)\cdot\frac{\binom{48}n}{(52-n)\binom{52}{n}} &= 4\sum_{n=0}^{48} (n+1)\cdot\frac{\binom{48}n}{52\cdot\binom{51}{n}} \\&= \frac{4}{52}\sum_{n=0}^{48} (n+1)\cdot\frac{\binom{51-n}3}{\binom{51}{3}} \\&= \frac{4}{52\cdot \binom{51}3}\sum_{n=0}^{48} \binom{n+1}1\cdot\binom{51-n}3 \\&\stackrel{\color{red}\star}= \frac{4}{52\cdot \binom{51}3}\binom{53}5 \\&=\frac{53}{5}=10.6. \end{align} The $\stackrel{\color{red}\star}=$ step is a special case of the identity $$ \sum_{k=r-m}^{n-s} \binom{m+k}{r} \binom{n-k}{s} =\binom{m+n+1}{r+s+1}. $$ where $m=1,r=1,n=51,s=3$. For several proofs of that identity, see this MSE question and the duplicate it links to.

Answer 2

Regroup your sum:

$$1\left({4\over{52}}\right) + 2\left({{48}\over{52}}\right)\left({4\over{51}}\right) + 3 \left({{48}\over{52}}\right)\left({{47}\over{51}}\right)\left({{4}\over{50}}\right) + 4 \left({{48}\over{52}}\right)\left({{47}\over{51}}\right)\left({{46}\over{50}}\right)\left({{4}\over{49}}\right) + \ldots + 48\left({{48}\over{52}}\right)\left({{47}\over{51}}\right)\ldots\left({{2}\over{6}}\right)\left({{4}\over{5}}\right) + 49\left({{48}\over{52}}\right)\left({{47}\over{51}}\right)\ldots\left({{2}\over{6}}\right)\left({{1}\over{5}}\right)\left({{4}\over{4}}\right)$$

This is equal to:

$$\begin{align}&\frac{4}{52}\left(1+\frac{48}{51}\left(2+\frac{47}{50}\left(3+\frac{46}{49}\left(\cdots\frac{1}{4}\left(49\right)\right)\right)\right)\right)\end{align}$$

Consider the recurrence relation:

$$\begin{align}a_0&=49\\a_n&=\frac{n}{n+3}\cdot a_{n-1}+(49-n)\\S&=\frac{1}{13}\cdot a_{48}\end{align}$$

I believe this is the fastest way to calculate the sum $S$.

The Python code:

a = 49

for i in range(1, 49):
    x = i / (i + 3)
    x *= a
    x += 49 - i
    a = x

return a / 13

Gives the answer $10.6$ that you are looking for in hardly any time at all.

The code for your original summation formula:

s = 1 / 13

for i in range(2, 50):
    x = 4 * i / (53 - i)
    
    for i in range(1, i):
        x *= (49 - i) / (53 - i)
    
    s += x

return s

Gives the same answer but runs on average (by a benchmark with $100,000$ trials) almost exactly $20$ times slower than my summation method. A $20\times$ speedup is the best thing, in the interests of "computational fortitude", that I can get you.