expected value of a sum of a 10 sided die
Suppose you have a fair die with 10 sides with numbers from 1 to 10. You roll the die and take the sum until the sum is greater than 100. What is the expected value of this sum?
Solution 1:
Well, you can make numbers from 1 to 110, that's 110 possible states you can be in. That's a large transition matrix, but not intractable. Define transition matrix $M$ as:
$$\begin{align} M_{i,j} = \begin{cases} \frac{1}{10} & \text{ if } 1 \le j - i \le 10 \text{ and } 1 \le i \le 100 \\ 1 & \text{ if } i = j\text{ and } 100 < i \le 110 \\ 0 & \text{ otherwise} \end{cases} \end{align}$$
Define the initial state vector: $$\begin{align} V_{j} = \begin{cases} \frac{1}{10} & \text{ if } 1 \le j \le 10 \\ 0 & \text{ otherwise} \end{cases} \end{align}$$
This matrix compute the probability that you end up in state $j$. I won't wrote out the whole thing here. The steady state $S$ is given by:
$$S = VM^{\infty}$$
I don't recommend doing this by hand.
Anyway, you get the following probabilities:
$$\begin{array} {c|c} \text{End State} & \text{Probability} \\ \hline 101 & \frac{{ 14545454540916238222253308031039403263876427137099 \atop 728738149747953197899302063661139633020606426446001 }}{10^{101}} \\ \hline 102 & \frac{{ 18181818143103207886299794518678653455112915813572 \atop 471568730433172695421560362344285718841548526446001 }}{10^{101}} \\ \hline 103 & \frac{{ 16363636337149401877562367260240328253764897737948 \atop 745622241485421850822156839220501392260147526446001 }}{10^{101}} \\ \hline 104 & \frac{{ 12727272741576429962125352735631301525861758140731 \atop 984148880861015973102098820410322797857111216446001 }}{10^{101}} \\ \hline 105 & \frac{{ 10909090931874858870242133363925460156752233410373 \atop 601637391699278967219484863685353489177266485446001 }}{10^{101}} \\ \hline 106 & \frac{{ 90909091116377120481295620461022602720063194921283 \atop 52571281564919296780386873223909380629437281346001 }}{10^{101}} \\ \hline 107 & \frac{{ 72727272852713068490158133017227152668140086810036 \atop 91839439446721479480174650845945205326825156836001 }}{10^{101}} \\ \hline 108 & \frac{{ 54545454582842347527531906998645390126303113111522 \atop 24370063982379262253640845972771391003951819875001 }}{10^{101}} \\ \hline 109 & \frac{{ 36363636346255163502142715869656509893927302281916 \atop 05910755643757924951410231819125651609791149217901 }}{10^{101}} \\ \hline 110 & \frac{{ 18181818155610931814042064558296878037883980477975 \atop 93593065135379352069784448816645340273314411495091 }}{10^{101}} \\ \hline \end{array}$$
Expected state is calculated as always, and the final answer is :
$$\sum_{k=100}^{109} k\cdot S_{j,k} = \frac{{ 2080000000053214123545556126144601328836935442611255 \atop 847240374822309959920561393884518831211143790906011 }}{2\cdot10^{100}}$$
which is almost exactly $104$ (to eight decimal places).
EDIT-- Corrected post, originally answered the question "at least 100" rather than "more than 100".
Solution 2:
An argument like the one in this answer, shows that the distribution of the final position is very closely approximated by $[10/55,9/55,8/55,\dots ,1/55]$ on the states $[101,102,103,\dots, 110]$. Therefore the average position at the end of the game is very close to $$\sum_{i=1}^{10} (100+i)(11-i)/55=104. $$
Added: Here is some further information on the approximate hitting distribution.
Let's express the hitting distribution of $100,101,102,\dots$ as $\sum_{i=0}^9 \pi_i \,\delta_{100+i}$, and the hitting distribution of $101,102, 103,\dots$ as $\sum_{i=0}^9 \pi^\prime_i\, \delta_{101+i}$, where $\pi=(\pi_0,\dots,\pi_9)$ and $\pi^\prime=(\pi^\prime_0,\dots,\pi^\prime_9)$ are distributions on $\{0,1,2,\dots,9\}$.
By the strong Markov property, we have $$\pi^\prime=\pi_0 U+\sum_{i=1}^9 \pi_i\delta_{i-1} $$ where $U$ is the uniform distribution on $\{0,1,2,\dots,9\}$.
On the other hand, since the process has been running for a long time, we have $\pi\approx \pi^\prime$. If you take this as equality, write $\pi=\pi_0 U+\sum_{i=1}^9 \pi_i\delta_{i-1}$, and solve for $\pi$ you get the required pattern.