Expected number of cards to draw before first ace using stopping times?

Question

Consider the classic combinatorial problem that asks how many cards we should expect to have to draw on average before we see our first ace. There are several solutions. My first instinct was to write down a brute force solution. Define $T$ as the number cards we need to draw before seeing an ace. Then $$E(T) = \int_0^\infty P(T>t) = \sum_{t=0}^{51}\prod_{i=0}^{t-1} \frac{48-i}{52-i} = 10.6$$ as we'd expect. A more elegant solution pointed out elsewhere on this site is to observe that each non-ace independently has a $1/5$ probability of being before any of the four aces, so the number of cards before all the aces we should expect is $48/5 + 1 \approx 10.6$.

My question is this: when I first saw this problem I felt it was a problem about martingales and stopping times, since we can define a stopping time for when we see the first ace. But I wasn't sure what the relevant martingale to define was. Is there any way to solve this problem using ideas from martingales, stopping times, or random walks thinking along these lines? Are there any other ways to solve this problem besides the three outlined above?

Answer 1

Consider a player who bets each time a card is drawn 1\$: he keeps playing as long as an ace is drawn, and wins $\frac{52-t+1}{4}$ if an ace is drawn at time $t$.

Let's check that his total profit $S_{t}$ is a martingale:

$$\mathbb{E}_{t}[S_{t+1}]=S_{t}-1+\frac{52-t}{4}\times\frac{4}{52-t}=S_{t}$$

Using the optional stopping theorem (as $\tau\leq48$), and the linearity of the expectation:

$$\mathbb{E}[S_1]=0=\mathbb{E}[S_{\tau}]=\frac{52-\mathbb{E}[\tau]+1}{4}-\mathbb{E}[\tau]$$

Which gives, as expected: $$\mathbb{E}[\tau] = \frac{53}{5}\approx 10.6$$