At Least Six II

Work backwards from the target. Let $E_i$ be the expected number of further rolls when the running total is $i$, so $E_i = 0$ once $i \ge n$. What is $E_{n-1}$, and how does $E_i$ depend on the totals above it?

Compute $E_{n-1}$, $E_{n-2}$ and $E_{n-3}$ and spot the pattern. To prove it, write the equations for two neighbouring totals and subtract: almost everything cancels.

Method 1: work backwards (recursion and induction). This is the same approach as At Least Six I, generalised.

Let $E_i$ be the expected number of further rolls when the running total is $i$. We stop once the total reaches $n$, so $E_i = 0$ for $i \ge n$. From a total $i < n$ you always spend one roll, then land on $i + 1, \dots, i + n$ with chance $\tfrac1n$ each, and only landings below $n$ add anything:

The first few values.

• $E_{n-1} = 1$, since any roll finishes.
• $E_{n-2} = 1 + \tfrac1n E_{n-1} = \tfrac{n+1}{n}$.
• $E_{n-3} = 1 + \tfrac1n\big(E_{n-1} + E_{n-2}\big) = 1 + \tfrac1n + \tfrac{n+1}{n^2} = \tfrac{(n+1)^2}{n^2}$.

The pattern suggests

Proof by induction. The base case $k = 1$ is $E_{n-1} = 1$. For the step, write the equations for two neighbouring totals, $n - k$ and $n - k + 1$:

The two sums are the same except for the last term $E_{n-k+1}$. Subtracting the second equation from the first, everything else cancels:

So each step back from the target multiplies the expected number of rolls by $\tfrac{n+1}{n}$. If $E_{n-k+1} = \left(\tfrac{n+1}{n}\right)^{k-2}$, then $E_{n-k} = \left(\tfrac{n+1}{n}\right)^{k-1}$, which completes the induction.

Answer. Starting from total $0$ means $k = n$:

For $n = 6$ this is $\left(\tfrac76\right)^5 \approx 2.16139$, matching At Least Six I. For $n = 18$:

Method 2: count the ways to stay below the target. A second proof, which also explains why the answer is a clean power.

Let $S_k$ be the running total after $k$ rolls, with $S_0 = 0$, and write $m = n - 1$ for the largest total that has not yet reached the target.

Step 1: Turn $E[T]$ into a sum of probabilities. Any whole number $T \ge 1$ can be counted as

For example, if $T = 3$, the terms for $0, 1, 2$ are each $1$ and the rest are $0$. Taking expectations,

And "$T > k$" means "after $k$ rolls we still haven't reached $n$", i.e. $S_k \le m$. So

Step 2: Count the ways to stay at or below $m$. Suppose $k$ rolls keep the total at most $m$. The running totals $S_1, S_2, \dots, S_k$ are

• strictly increasing, since every roll is at least $1$, and
• all between $1$ and $m$.

So they are $k$ different numbers chosen from $\{1, \dots, m\}$.

It also works the other way round. Pick any $k$ different numbers from $\{1, \dots, m\}$, sort them and treat them as the running totals. Each roll is the gap between neighbouring totals, which is at least $1$ and at most $m = n - 1$, so it is always a legal face of the die.

That is a one-to-one match, so the number of roll sequences is $\binom{m}{k}$, out of $n^k$ equally likely sequences:

Check with $n = 6$, $k = 2$: $\binom{5}{2} = 10$, and directly, the pairs of rolls with sum at most $5$ are $4 + 3 + 2 + 1 = 10$ out of $36$. They match.

Step 3: Add them up. $\binom{m}{k} = 0$ once $k > m$, so

using the binomial theorem $(1 + x)^m = \sum_k \binom{m}{k} x^k$ with $x = \tfrac1n$.

Answer. $E[T] = \left(1 + \frac1n\right)^{n-1}$. For $n = 6$ this is $\left(\tfrac76\right)^5 \approx 2.16139$, matching At Least Six I. For $n = 18$:

As $n$ grows, $\left(1 + \frac1n\right)^{n-1}$ approaches $e \approx 2.71828$, the same answer as adding uniform random numbers until the sum passes $1$.