expected value of a sum of a 10 sided die

Question

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?

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

Answer 2

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.

Answer 3

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 :=
proc(n)
        (1-z)/(1-z-z/n*(1-z^n));
end;

v :=
proc(n)
        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);
end;

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

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

    do
        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;
            fi;
        od;

        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;
    od;

    res;
end;

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

Answer 4

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.