How Long Will It Take To Blow Out The Birthday Candles?

It’s your 30th birthday (congrats, by the way), and your friends bought you a cake with 30 candles on it. You make a wish and try to blow them out. Every time you blow, you blow out a random number of candles between one and the number that remain, including one and that other number. How many times do you blow before all the candles are extinguished, on average?

The Riddler, FiveThirtyEight(original post)

Solution

Let $T_n$ be the expected number of blows to clear $n$ candles. A single blow removes a number uniform on $\{1,\dots,n\}$, so the count left is uniform on $\{0,1,\dots,n-1\}$, and $$T_n = 1 + \frac1n \sum_{j=0}^{n-1} T_j, \qquad T_0 = 0.$$ Claim $T_n = H_n = 1 + \tfrac12 + \cdots + \tfrac1n$, the $n$th harmonic number. Suppose it holds below $n$. Using the identity $\sum_{j=1}^{n-1} H_j = n H_{n-1} - (n-1)$, $$1 + \frac1n \sum_{j=0}^{n-1} H_j = 1 + \frac{n H_{n-1} - (n-1)}{n} = H_{n-1} + \frac1n = H_n,$$ so the claim follows by induction. For the cake, $$T_{30} = H_{30} \approx \boxed{3.995}.$$ Remarkably, blowing out thirty candles takes only about four breaths on average, because the early blows tend to clear many candles at once.

The computation

Blow out the cake directly: from the candles that remain, remove a uniformly random number between $1$ and that count, repeat until none are left, and average the number of blows over many cakes. The mean matches $H_{30}$.

import numpy as np
rng = np.random.default_rng(0)
runs = 1_000_000
total = 0
for _ in range(runs):
    candles = 30; blows = 0
    while candles:
        candles -= rng.integers(1, candles + 1)   # blow out 1..remaining
        blows += 1
    total += blows
print(total / runs)                                # ~3.995
print(sum(1 / k for k in range(1, 31)))            # H_30 = 3.99499...