Expected overshoot in a dice stopping problem

Question

You throw a 6-sided dice and keep track of the sum $S$ of the rolls so far. Stop throwing when $S\geq N$ for some integer threshold $N$. What is $\mathbb{E}(S)$? (I'm in particular interested in the case $N$ going to infinity)

Note: for example, if $N=20$ and you throw $6, 4, 5, 6$, giving $S=21$, so you stop.

Intuitively, since the average roll is $3.5$, we can guess that $S-X$ is "roughly uniform between $0$ and $3.5$", giving a guess of $1.75$.

Motivation: Part of the problem from here (Maths Problems, Q14).

Answer 1

Here's a proof that $\ \mathbb{E}(S-N)\rightarrow\frac{5}{3}\ $. Let $\ S_r\ $ be the sum after $\ r\ $ rolls. Then the conditional expectation $e_j:= \mathbb{E}\big(S-N\,\big|\,S_r=j\,\big)\ $ is independent of $\ r\ $ as long as $\ r\le j\le 6r\ $ (it's undefined otherwise). Then $$ \begin{align} e_j&=\frac{1}{6}\sum_{i=1}^6e_{j+i}&&\text{ for } 0\le j\le N-1, \text{ and}\\ e_{N+i}&=i &&\text{ for } 0\le i\le 5. \end{align} $$ Solving the recurrence, it follows that $$ e_j=c_0+\sum_{k=1}^5c_k\lambda_k^j\ , $$ where the recurrence has characteristic polynomial \begin{align} &x^6+x^5+x^4+x^3+x^2+x-6\\ &=(x-1)\big(x^5+2x^4+3x^3+4x^2+5x+6\big)\\ &=:(x-1)g(x) \end{align} and $\lambda_k$ are the roots of $g(x)$. Wolframalpha tells us that $g(x)$ has one real and two pairs of complex conjugate roots, all of which have absolute values strictly greater than $1$.

There are six initial conditions. We will combine them all to get $c_0$.

Let $\ f_j=e_j-c_0=\sum_\limits{k=1}^5c_k\lambda_k^j\ $. Then \begin{align} \sum_{i=0}^5(6-i)f_{j+i}&=\sum_{i=0}^5(6-i)\sum_\limits{k=1}^5c_k\lambda_k^{j+i}\\ &=\sum_\limits{k=1}^5c_k\lambda_k^j\sum_{i=0}^5\underbrace{(6-i)\lambda_k^i}_{=g(\lambda_k) = 0} = 0.\\ \end{align} In particular, letting $j = N$, \begin{align} 0&=\sum_{i=0}^5(6-i)f_{N+i}\\ &=\sum_{i=0}^5(6-i)\big(e_{N+i}-c_0\big)\\ &=\sum_{i=0}^5(6-i)i-21c_0\\ &=35-21c_0\ , \end{align} so $\ c_0=\frac{5}{3}\ $.

The expectation we want is $\ e_0\ $, and we have $$ e_{i+N}=i=\frac{5}{3}+\sum_{k=1}^5c_k\lambda_k^{i+N} $$ for $\ 0\le i\le5\ $, or $$ \pmatrix{-\frac{5}{3}\\-\frac{2}{3}\\\frac{1}{3}\\\frac{4}{3}\\\frac{7}{3}\\\frac{10}{3}}=\pmatrix{1&1&\dots&1\\ \lambda_1&\lambda_2&\dots&\lambda_5\\ \lambda_1^2&\lambda_2^2&\dots&\lambda_5^2\\ \vdots&\vdots&\ddots&\vdots\\ \lambda_1^5&\lambda_2^5&\dots&\lambda_5^5}\pmatrix{c_1\lambda_1^N\\c_2\lambda_2^N\\\vdots\\c_5\lambda_5^N}\ . $$ Since the roots $\ \lambda_k\ $ are all distinct, the transposed Vandermonde matrix on the right of this equation is invertible. Therefore, if $$ \pmatrix{d_1\\d_2\\\vdots\\d_5}=\pmatrix{1&1&\dots&1\\ \lambda_1&\lambda_2&\dots&\lambda_5\\ \lambda_1^2&\lambda_2^2&\dots&\lambda_5^2\\ \vdots&\vdots&\ddots&\vdots\\ \lambda_1^5&\lambda_2^5&\dots&\lambda_5^5}^{-1}\pmatrix{-\frac{5}{3}\\-\frac{2}{3}\\\frac{1}{3}\\\frac{4}{3}\\\frac{7}{3}\\\frac{10}{3}}\ $$ we have $\ c_k=d_k\lambda_k^{-N}\ $ and $$ e_0=\frac{5}{3}+\sum_{k=1}^5d_k\lambda_k^{-N}\rightarrow\frac{5}{3}\ \ \text{as }\ N\rightarrow\infty\ . $$

Answer 2

It might be helpful to think of how we can have an overshoot:

• the ways to overshoot of $5$ is $1$ (being at (S-1) then rolling $6$)
• the ways to overshoot of $4$ is $2$ ((S-1) + $5$ and (S-2) + $6$)
• the ways to overshoot of $3$ is $3$
• the ways to overshoot of $2$ is $4$
• the ways to overshoot of $1$ is $5$
• the ways to overshoot of $0$ is $6$

I think it is most natural to understand that every way from the above ways to overshoot is equally likely as $N$ tends to ${\infty}$, but I'm unsure how to show this formally.

We have then $21$ ways to overshoot, with the the total sum of overshoot of $35$. yielding $35/21$ or $5/3$ as the average overshoot.