Expected Rolls Until Cumulative Sum Reaches n
You have a fair $n$-sided die with faces numbered $1$ through $n$. You roll the die repeatedly until the cumulative sum of all rolls is greater than or equal to $n$.
What is the expected number of rolls? Compute the answer for $n = 6$.
Hints
- Define $E_k(n)$ as the expected rolls remaining when your current sum is $k$. Condition on the next roll to get a recurrence.
- Work backwards from $E_{n-1} = 1$. Compute $E_{n-2}, E_{n-3}, E_{n-4}$ and look for binomial coefficients in the pattern.
- The pattern is $E_{n-k}(n) = (1 + 1/n)^{k-1}$. Prove it by induction using the geometric series formula, then evaluate at $k = n$.
Worked Solution
How to Think About It: Let $E_k(n)$ be the expected number of additional rolls needed when your current cumulative sum is $k$. You need $E_0(n)$. Each roll advances your sum by 1 to $n$ uniformly, and once your sum hits $n$ or above, you stop. The trick is to compute $E_{n-1}, E_{n-2}, \ldots$ backwards and spot a pattern. Gut feeling: the mean of one roll is $(n+1)/2$, so you need roughly $n / ((n+1)/2) = 2n/(n+1)$ rolls. For $n = 6$ that is about $12/7 \approx 1.71$. But that is just the ratio of target to mean roll -- the actual answer should be a bit higher because you overshoot.
Quick Estimate: For $n = 6$, mean roll is 3.5, so the naive estimate is $6/3.5 \approx 1.71$ rolls. But this ignores the integer structure. We expect the answer to be somewhat above 2 since you often need 2 rolls to reach 6.
Approach: Build the recurrence $E_k(n) = 1 + \frac{1}{n}\sum_{j=k+1}^{\min(k+n, n-1)} E_j(n)$ and solve by working backwards from $E_{n-1}$.
Formal Solution:
Define $E_k(n)$ as the expected number of rolls to reach a cumulative sum $\ge n$, given current sum $k$. For $k \ge n$, $E_k(n) = 0$. For $k < n$:
$$E_k(n) = 1 + \frac{1}{n}\sum_{j=1}^{n} E_{k+j}(n) = 1 + \frac{1}{n}\sum_{j=k+1}^{k+n} E_j(n)$$
Since $E_j(n) = 0$ for $j \ge n$, only terms with $j < n$ survive:
$$E_k(n) = 1 + \frac{1}{n}\sum_{j=k+1}^{n-1} E_j(n)$$
Working backwards:
$E_{n-1}(n) = 1$ (any roll completes the game).
$E_{n-2}(n) = 1 + \frac{1}{n} E_{n-1}(n) = 1 + \frac{1}{n}$.
$E_{n-3}(n) = 1 + \frac{1}{n}(E_{n-2} + E_{n-1}) = 1 + \frac{1}{n}\left(1 + \frac{1}{n} + 1\right) = 1 + \frac{2}{n} + \frac{1}{n^2}$.
$E_{n-4}(n) = 1 + \frac{1}{n}(E_{n-3} + E_{n-2} + E_{n-1}) = 1 + \frac{3}{n} + \frac{3}{n^2} + \frac{1}{n^3}$.
Spotting the pattern: The coefficients are binomial:
$$E_{n-k}(n) = \sum_{i=0}^{k-1} \binom{k-1}{i} \frac{1}{n^i} = \left(1 + \frac{1}{n}\right)^{k-1}$$
by the binomial theorem.
Proof by induction: Assume $E_{n-m}(n) = (1 + 1/n)^{m-1}$ for $m = 1, \ldots, k-1$. Then:
$$E_{n-k}(n) = 1 + \frac{1}{n}\sum_{m=1}^{k-1} E_{n-m}(n) = 1 + \frac{1}{n}\sum_{m=1}^{k-1} \left(1 + \frac{1}{n}\right)^{m-1}$$
$$= 1 + \frac{1}{n} \cdot \frac{(1+1/n)^{k-1} - 1}{1/n} = 1 + (1+1/n)^{k-1} - 1 = \left(1 + \frac{1}{n}\right)^{k-1}. \quad \checkmark$$
Setting $k = n$ to get $E_0(n)$:
$$E_0(n) = \left(1 + \frac{1}{n}\right)^{n-1}$$
For $n = 6$:
$$E_0(6) = \left(\frac{7}{6}\right)^5 = \frac{7^5}{6^5} = \frac{16807}{7776} \approx 2.161$$
Answer: The expected number of rolls is $\left(1 + \dfrac{1}{n}\right)^{n-1}$. For $n = 6$, this equals $\dfrac{16807}{7776} \approx 2.161$.
Intuition
The elegant answer $(1 + 1/n)^{n-1}$ has a nice limiting interpretation. As $n \to \infty$, this converges to $e \approx 2.718$, which is the expected number of uniform $[0,1]$ random variables you need to sum before exceeding 1. That continuous problem is a classic (the answer is exactly $e$), and this discrete version converges to it.
The binomial pattern in the recurrence is not a coincidence. Each backwards step introduces one more factor of $(1 + 1/n)$, because adding the new partial expectations telescopes into a geometric series that collapses via the binomial theorem. This kind of "self-similar" recurrence -- where the solution at one level is a clean multiplicative factor times the previous level -- shows up frequently in problems involving cumulative sums, coupon collecting, and threshold crossing.