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?
Probability – Expected Value of a Sum of a 10-Sided Die
probabilitypuzzlerecreational-mathematics
Related Solutions
If you are trying to maximise the expected score, then since the expected value of the 12-sided die is $6.5$, it makes sense to stop when the 8-sided die shows greater than $6.5$, i.e. when it shows $7$ or $8$, each with probability $\frac18$. So with probability $\frac34$ you throw the 12-sided die.
The expected score is then $$7 \times \frac18 + 8 \times \frac18 + 6.5 \times \frac34 = 6.75.$$
Let $v$ denote the expected value of the game. If you roll some $x\in\{1,\ldots,100\}$, you have two options:
- Keep the $x$ dollars.
- Pay the \$$1$ continuation fee and spin the dice once again. The expected value of the next roll is $v$. Thus, the net expected value of this option turns out to be $v-1$ dollars.
You choose one of these two options based on whichever provides you with a higher gain. Therefore, if you spun $x$, your payoff is $\max\{x,v-1\}$.
Now, the expected value of the game, $v$, is given as the expected value of these payoffs: \begin{align*} v=\frac{1}{100}\sum_{x=1}^{100}\max\{x,v-1\}\tag{$\star$}, \end{align*} since each $x$ has a probability of $1/100$ and given a roll of $x$, your payoff is exactly $\max\{x,v-1\}$. This equation is not straightforward to solve. The right-hand side sums up those $x$ values for which $x>v-1$, and for all such values of $x$ that $x\leq v-1$, you add $v-1$ to the sum. This pair of summations gives you $v$. The problem is that you don't know where to separate the two summations, since the threshold value based on $v-1$ is exactly what you need to compute. This threshold value can be guessed using a numerical computation, based on which one can confirm the value of $v$ rigorously. This turns out to be $v=87\frac{5}{14}$.
Incidentally, this solution also reveals that you should keep rolling the dice for a $1 fee as long as you roll 86 or less, and accept any amount 87 or more.
ADDED$\phantom{-}$In response to a comment, let me add further details on the computation. Solving for the equation ($\star$) is complicated by the possibility that the solution may not be an integer (indeed, ultimately it is not). As explained above, however, ($\star$) can be rewritten in the following way: \begin{align*} v=\frac{1}{100}\left[\sum_{x=1}^{\lfloor v\rfloor-1}(v-1)+\sum_{x=\lfloor v\rfloor}^{100}x\right],\tag{$\star\star$} \end{align*} where $\lfloor\cdot\rfloor$ is the floor function (rounding down to the nearest integer; for example: $\lfloor1\mathord.356\rfloor=1$; $\lfloor23\mathord.999\rfloor=23$; $\lfloor24\rfloor=24$). Now let’s pretend for a moment that $v$ is an integer, so that we can obtain the following equation: \begin{align*} v=\frac{1}{100}\left[\sum_{x=1}^{v-1}(v-1)+\sum_{x=v}^{100}x\right]. \end{align*} It is algebraically tedious yet conceptually not difficult to show that this is a quadratic equation with roots \begin{align*} v\in\left\{\frac{203\pm3\sqrt{89}}{2}\right\}. \end{align*} The larger root exceeds $100$, so we can disregard it, and the smaller root is approximately $87\mathord.349$. Of course, this is not a solution to ($\star\star$) (remember, we pretended that the solution was an integer, and the result of $87\mathord.349$ does not conform to that assumption), but this should give us a pretty good idea about the approximate value of $v$. In particular, this helps us formulate the conjecture that $\lfloor v\rfloor=87$. Upon substituting this conjectured value of $\lfloor v\rfloor$ back into ($\star\star$), we now have the exact solution $v=87\frac{5}{14}$, which also confirms that our heuristic conjecture that $\lfloor v\rfloor=87$ was correct.
Best Answer
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".