Expected Insertions to Pay a Parking Meter
You need to pay $\$1$ at a parking meter that only accepts quarters ($\$0.25$ each), so you need 4 real quarters to complete payment. You have an infinitely large pouch of coins where 60% are real quarters and 40% are fake.
The meter has a catch: if you insert a fake quarter, the meter resets to $\$0$ and you lose all progress. You must start over from scratch.
You draw coins one at a time from the pouch and insert them. How many coins do you expect to insert before the meter is fully paid?
Hints
- You need 4 consecutive real quarters. A single fake resets everything. What classic waiting-time problem does this reduce to?
- Let $E_k$ be the expected coins still needed when you have $k$ consecutive reals so far. Write a recursion: each coin either advances you ($k \to k+1$) or resets you ($k \to 0$).
- Solve the recursion backwards from $E_3$ to $E_0$. You will get $E_0(1 - 0.8704) = 2.176$. Alternatively, use the formula $E = \sum_{i=1}^{r} p^{-i}$ for $r$ consecutive successes.
Worked Solution
How to Think About It: This is a consecutive-successes problem. You need 4 real quarters in a row, and each coin is real with probability $p = 0.6$. A single fake coin (probability $0.4$) wipes out all progress and resets you to zero. The question reduces to: what is the expected number of Bernoulli trials to get $r = 4$ consecutive successes?
Before doing any math, get a feel for the answer. If there were no reset penalty, you would need exactly 4 coins. But fakes reset you, and at a 40% fake rate, you will get reset frequently. The probability of 4 consecutive reals is $0.6^4 = 0.1296$, roughly 13%. So you would need on the order of $1/0.1296 \approx 7.7$ "attempts" -- but each failed attempt wastes some coins too. Expect something in the low-to-mid teens.
Quick Estimate: Think of it as a geometric number of "streaks." Each streak attempt either succeeds (probability $0.6^4 \approx 0.13$) or fails partway through. On a failed attempt, you insert on average about 1-2 coins before hitting a fake (roughly $1/0.4 = 2.5$ coins per attempt on average, but failed attempts are shorter since they exclude the successful run). A rough estimate: about $1/0.13 \approx 7.7$ attempts, each costing ~2 coins on average, gives ~15-17 total coins.
Approach: Let $E_k$ denote the expected number of additional coins needed when you currently have $k$ consecutive real quarters inserted. We want $E_0$. Setting up the recursion and solving gives a clean closed-form formula.
Formal Solution:
Define $E_k$ = expected additional coins needed given $k$ consecutive real quarters so far. We have $E_4 = 0$ (done). For $k < 4$:
$$E_k = 1 + p \cdot E_{k+1} + (1 - p) \cdot E_0$$
Each coin costs 1 insertion. With probability $p = 0.6$ it is real and we advance to $k+1$; with probability $1 - p = 0.4$ it is fake and we reset to $E_0$.
Solving backwards from $k = 3$:
- $E_3 = 1 + 0.6 \cdot 0 + 0.4 \cdot E_0 = 1 + 0.4 E_0$
- $E_2 = 1 + 0.6(1 + 0.4 E_0) + 0.4 E_0 = 1.6 + 0.64 E_0$
- $E_1 = 1 + 0.6(1.6 + 0.64 E_0) + 0.4 E_0 = 1.96 + 0.784 E_0$
- $E_0 = 1 + 0.6(1.96 + 0.784 E_0) + 0.4 E_0 = 2.176 + 0.8704 E_0$
Solving for $E_0$:
$$E_0 = \frac{2.176}{1 - 0.8704} = \frac{2.176}{0.1296} \approx 16.79$$
This matches the general formula for $r$ consecutive successes with individual probability $p$:
$$E[T_r] = \sum_{i=1}^{r} \frac{1}{p^i} = \frac{1}{p} + \frac{1}{p^2} + \frac{1}{p^3} + \frac{1}{p^4}$$
Plugging in:
$$E[T_4] = \frac{1}{0.6} + \frac{1}{0.36} + \frac{1}{0.216} + \frac{1}{0.1296} = 1.667 + 2.778 + 4.630 + 7.716 \approx 16.79$$
Alternatively, the closed-form expression is:
$$E[T_r] = \frac{1 - p^r}{(1-p) \, p^r}$$
Answer: The expected number of coins you need to insert is approximately $\boxed{16.79}$, or exactly $\dfrac{1 - 0.6^4}{0.4 \times 0.6^4} = \dfrac{0.8704}{0.05184}$.
Intuition
This is a classic consecutive-successes problem, and it shows up more often in quant work than you might think. Any process where a single failure resets your progress -- filling a buffer of consecutive signals, requiring multiple confirmations in a row before executing -- has this structure. The key insight is that the expected waiting time grows much faster than $r/p$ because failures are catastrophic: you do not just lose one step, you lose all accumulated progress. With $p = 0.6$ and $r = 4$, the naive estimate $4/0.6 \approx 6.7$ badly underestimates the true answer of ~16.8 because it ignores the reset penalty.
The recursive approach ($E_k = 1 + p \cdot E_{k+1} + (1-p) \cdot E_0$) is the workhorse technique for these problems. It decomposes the problem into "what happens on the next trial" and handles the reset cleanly. The resulting formula $E = \sum p^{-i}$ is a geometric series, which means the last term ($1/p^r$) dominates -- getting the final success in the streak is by far the hardest part, because that is when a reset is most painful.