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?

  • 3
    $\begingroup$ Computer simulation suggests the answer is around $104$. $\endgroup$ – user142299 May 16 '14 at 21:17
  • $\begingroup$ Thanks, I was looking for an analytical solution $\endgroup$ – neticin May 16 '14 at 21:44
  • $\begingroup$ What about an n-sided die? $\endgroup$ – Joao May 18 '14 at 5:23

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".

  • $\begingroup$ @user147263 Thanks for your attention. I did consider writing the table like you suggested before I submitted the answer, but chose not to for 3 reasons: (1) The poster asked for an analytical answer, if a decimal approximation was good enough then so would a computer simulation and (2) The actual value of the numbers is fairly insignificant, but I think the size is kinda funny (3) to show it is possible to solve without approximation. This is my joking way of saying "well you asked for an exact answer". Although, I ideally, I'd like to put latex inside scrollbars, if that were possible. $\endgroup$ – DanielV May 18 '14 at 0:46
  • 2
    $\begingroup$ Exact numbers are possible to post without the need for the horrendous page bleed. I think that is what @user147263 is implying here. No one is suggesting that you write approximations. We respect your work. $\endgroup$ – J. W. Perry May 18 '14 at 2:20
  • $\begingroup$ @DanielV I don't know if your browser was rendering different than other people's, but I agreed with J.W. Perry and others and felt that the horrendous page bleed in your post needed to be fixed. Your previous comment indicates that you did not want to express the answer in decimal, but rather wanted to show the size, and that the exact value could be computed. I have therefore kept the fractions intact in an attempt to defer to your stylistic choice. (contd) $\endgroup$ – 6005 May 18 '14 at 3:35
  • 1
    $\begingroup$ (contd) However, I will mention that personally I much prefer the decimal value suggested by @user147263. This is not an "approximation", it is the actual value of the result, and it results in a much clearer picture of the probability than this, which is just like "whoa these are big numbers". $\endgroup$ – 6005 May 18 '14 at 3:38
  • $\begingroup$ I hope I didn't accidentally delete any digits... $\endgroup$ – 6005 May 18 '14 at 3:39

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.

  • 1
    $\begingroup$ @Byron Schmuland: I understand how you calculated the probability of starting at $0$ and ending up in $101$. But how did you calculate the other ending probabilities, at $102$, $103$ etc? $\endgroup$ – neticin May 17 '14 at 8:16
  • $\begingroup$ @neticin I've added an explanation over at the other answer math.stackexchange.com/questions/12433/… $\endgroup$ – user940 May 17 '14 at 21:40

Introductory remark. As pointed out by @DanielV what follows does not answer the exact question, which asks for a value more than 100 rather than at least 100. Adapting the solution below is left as an exercise to the reader.

We can actually say a bit more about this problem using generating functions. Suppose we have an $n$-sided fair die and we ask about the expected value of the sum until it is at least $n^2$.

We classify according to the number $k$ of rolls until a value $n^2-q$ is obtained (this is the value before we exceed/hit $n^2$), where $1\le q\le n.$ This scenario is represented by the following generating function:

$$g(z) = \sum_{q=1}^n \frac{1}{n} \left(\sum_{p=1}^{n-q+1} z^{n-p+1}\right) z^{n^2-q} [z^{n^2-q}] \left(\frac{1}{n}\right)^k (z+z^2+\cdots+z^n)^k.$$ Summing over $k$ we obtain for the inner term $$\sum_{k\ge 0} \left(\frac{1}{n}\right)^k (z+z^2+\cdots+z^n)^k = \sum_{k\ge 0} \left(\frac{1}{n}\right)^k z^k \left(\frac{1-z^n}{1-z}\right)^k \\ = \frac{1}{1- z/n \times (1-z^n)/(1-z)} = \frac{1-z}{1-z - z/n \times (1-z^n)}.$$ Call this $f(z).$ This yields for the entire generating function $g(z)$ that $$\sum_{q=1}^n \frac{1}{n} \left(\sum_{p=1}^{n-q+1} z^{n-p+1}\right) z^{n^2-q} [z^{n^2-q}] \frac{1-z}{1-z - z/n \times (1-z^n)}.$$

As this is a PGF we may differentiate and set $z=1$ to obtain the expectation. This operation produces $$\sum_{p=1}^{n-q+1} (n-p+1) + (n-q+1)(n^2-q) = \frac{1}{2} (n-q+1) (2n^2+n-q).$$ We obtain the formula $$\frac{1}{2n} \sum_{q=1}^n (n-q+1) (2n^2+n-q) [z^{n^2-q}] \frac{1-z}{1-z - z/n \times (1-z^n)}.$$

This gives for an ordinary die with six faces the value $$37.666667491012523359$$ and for the ten-sided die the value $$103.00000000410210493.$$

A surprising conjecture. The sequence of values of the expected terminal sum with an $n$-sided die rolled until a sum $\ge n^2$ is reached, times three, for $n=5$ to $n=15$ is extremely close to $$79, 113, 153, 199, 251, 309, 373, 443, 519, 601, 689$$ which is OEIS A144391, i.e. $3n^2+n-1,$ giving the closed form: $$\frac{1}{3} (3n^2+n-1).$$ There are probably upvotes to be had for a proof of this conjecture.

This is the proof. The dominant pole of the generating function is at $z=1$ with residue (apply L'Hopital several times) $$-\lim_{z\to 1} \frac{(1-z)^2}{1-z-z/n\times (1-z^n)} = -\lim_{z\to 1} \frac{-2+2z}{-1-1/n+(n+1)/n\times z^n} \\ = -\lim_{z\to 1} \frac{-2+2z}{-(n+1)/n+(n+1)/n\times z^n} = -\lim_{z\to 1} \frac{2}{(n+1)z^{n-1}} = -\frac{2}{n+1}.$$ Therefore $$[z^{n^2-q}] f(z) \sim \frac{2}{n+1} 1^{n^2-q}$$ and the dominant contribution to the sum is $$\frac{1}{2n} \sum_{q=1}^n (n-q+1) (2n^2+n-q) \times \frac{2}{n+1} \\ = {n}^{2}+1/3\,n-1/3.$$

Since computer simulations are apparently relevant to this problem I am posting some code that can be used to verify the generating function formula.

gf :=

v :=
        option remember;
        1/2/n*add((n-q+1)*(2*n^2+n-q)*coeftayl(gf(n), z=0, n^2-q),q=1..n);

ex :=
    option remember;
    local pb, w, res, dist, dist2, term, pot, delta;

    pb := 1/n; res := 0; dist := 1;

        dist := expand(dist*add(z^k, k=1..n)); dist2 := 0;
        delta := 0;
        for term in dist do
            pot := degree(term);

            if pot < n^2 then dist2 := dist2 + term fi;

            if pot >= n^2 then
                delta := delta + pot*coeff(term, z, pot)*pb;

        res := res+delta;

        if delta > 0 and delta < 10^(-Digits) then break fi;
        if dist2 = 0 then break fi;

        pb := pb*1/n;
        dist := dist2;


Some bugs fixed. Needs higher precision (value of Digits) for values like $n=15.$ The version in v that extracts coefficients is not usable for $n>11.$

  • $\begingroup$ +1 Thanks. I return the courtesy. I respectfully point out that the numbers in your data are somewhat difficult to read due to overflow on the right margin. $\endgroup$ – Marko Riedel May 16 '14 at 23:58
  • $\begingroup$ Thanks. I did some double checking, because NotNotLogical got 104 with a computer simulation and this is the type of problem that would have a very accurate simulation. Unfortunately, we answered the question "at least 100" rather than "more than 100", funny made the same mistake misreading the problem. 104 is correct~ $\endgroup$ – DanielV May 17 '14 at 0:14
  • 1
    $\begingroup$ Btw, how close this is to an integer suggests that there is some very good approximation... like using a known distribution... there is still probably a much better answer to be had for this problem. $\endgroup$ – DanielV May 17 '14 at 0:17

Using generating functions, there is one way to make each of the numbers $1$ through $10$ on each roll: $$G(x)=1x^1+1x^2+\cdots 1x^{10}=x\frac{x^{10}-1}{x-1}$$ To find the possible ways to get to any number $a$ after $n$ rolls, we need to find the coefficient of $x^a$ in the expansion of $G(x)^n$.

So to answer your question, we must find the number of ways to get $101-110$ total, and the number of ways to get each of the outcomes specifically. Thus, we examine the coefficients of $x^{101}$ through $x^{110}$ in the sum of all powers of $G$ (since we don't care about how many rolls it takes). $$G+G^2+\cdots=\frac{G}{1-G}=\frac{x(x^{10}-1)}{(x-1)-x(x^{10}-1)}$$

From here you would have to use a CAS to find the exact result. I got the numbers on Wolfram Alpha, but I have no way to copy them (and they're quite large) so I can't provide the exact answer, but as I mentioned in the comments it will be around $104$.

Alternatively, you could try looking at special (or general) cases to find a pattern or formula which would possibly apply to this case. Depending on where you got this question, there is a good chance that it has a much more elegant solution.

  • $\begingroup$ Yes, 104 is correct to about 8 decimal places. $\endgroup$ – DanielV May 17 '14 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.