I'm attempting to solve this problem Expected number of cards you should turn before finding an ace using the law of total expectation and recursion, but my solution approach seems really convoluted, and I'm not sure if I'm missing something obvious
I start with a top-down approach. Let $A$ denote the event of drawing the first ace.
Let $M$ denote the number of cards we're drawing from, $N$ the number of draws to get the first ace. Then the law of total expectation gives us the following recurrence relationship:
$$
E[N|M=d] = \frac{d-4}{d}\big(1+E[N|M=d-1]\big) + \frac{4}{d}(1)
$$
The base case is
$$
E[N|M=4] = 1
$$
So we can write a out a few more cases
$$
E[N|M=5] = \frac{1}{5}\big(1+E[N|M=4]\big) + \frac{4}{5}
= 1.2 \\
E[N|M=6] = \frac{2}{6}(1+1.2) + \frac{4}{6} = 1.4 \\
E[N|M=7] = \frac{3}{7}(1+1.4) + \frac{4}{7} = 1.6 \\
$$
So it appears each time we increment $M$, the expectation increases by 0.2, where we can then deduce the following non-recurrent formula:
\begin{align}
E[N|M=d] = 1+0.2*(d-4)
\end{align}
We can prove that this formula holds for all $4 \leq k \leq 52$ by induction and assume this formula holds for $M=k$:
$$
E[N|M=k] = 1+0.2(k-4)
$$
and use this to make the claim that this holds for $M=k+1$
$$
E[N|M=k+1] = 1+0.2(k-3)
$$
To prove this, we can use the recurrence relationship we derived earlier along with $E[N|M=k] = 1+0.2(k-4) $
\begin{align}
E[N|M=k+1] = (1+E[N|M=k])\frac{k-3}{k+1} + \frac{4}{k+1}
\\
= (1+1+0.2(k-4))\frac{k-3}{k+1} + \frac{4}{k+1} \\
= (2-0.8 + 0.2k))\frac{k-3}{k+1} + \frac{4}{k+1} \\
= (1.2 + 0.2k)\frac{k-3}{k+1} + \frac{4}{k+1} \\
= \frac{(1.2k + 0.2k^2 – 3.6 – 0.6k)}{k+1} + \frac{4}{k+1} \\
= \frac{(0.6k + 0.2k^2 +0.4)}{k+1} \\
= \frac{0.2(3k + k^2 +2)}{k+1} \\
= 0.2(k+2) \\
= 1+ 0.2*(k-3)\\
\end{align}
We have shown that this formula holds through proof by induction.
The other solutions that were posted are much shorter. Were there any tricks that I missed in my approach that could have shortened this?
Best Answer
Just to make things a little more compact, I'll write $$e_d=E[N|M=d]$$ Then your recurrence relation is $$e_d=1+\frac{d-4}de_{d-1}$$ or $$de_d = d +(d-4)e_{d-1}\tag1$$ and we know $e_4=1$. You have guessed the formula $$e_d=1+.2(d-4)\tag2$$ $(2)$ is clearly correct when $d=4$. To prove it correct for $d\ge4$, all you need to do is substitute $(2)$ in both sides of $(1)$ and check that the statement is true.