<s>[INST] Expected overshoot in a dice stopping problem 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).
 [/INST] 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\ .
$$
</s>