# Expected number of rolls required to get sum greater than n for n faced die?

Suppose a guy has a die with $n$ faces. He can go on rolling it as many times as possible and add the sum of each outcome. What is the expected number of rolls after which the sum is at least $n$?

• 1) do you really mean "n faces, sum n" or "n faces, sum m"? 2) do you need the sum to be n or greater than n? Nov 8, 2013 at 9:10
• Try some simple cases: $n=1,2,3,4$. Do the results follow a simple pattern? Nov 8, 2013 at 9:14
• n faces and sum n Nov 8, 2013 at 9:14
• @Michael No, there is not a simple pattern. But for large number of N (greater than 300) result gets stable to 2.7 Nov 8, 2013 at 9:34
• I would like to thank you for re-allocating your Green check to my answer, BUT: @Matthew Conroy 's answer may have been narrower in scope than mine, but it answered exactly what you were asking, and it provided an obviously much easier computational algorithm. So I believe you owe it to Matthew to explain why you decided to switch back. Nov 10, 2013 at 19:06

I'm assuming the OP means what is the expected number of rolls until the sum is at least $n$ (as Alecos assumes in his answer).

Let $E(m)$ be the expected number of rolls until the sum is at least $n$, starting with a sum of $m$.

Then we have, for a start: \begin{align*} E(n) &=0 \\ E(n-1) &=1 \\ E(n-2) &=1+\frac{1}{n}E(n-1) = 1+\frac{1}{n} \\ E(n-3) &=1+\frac{1}{n}E(n-2)+\frac{1}{n}E(n-1) \\ &=1+\frac{1}{n}(1+\frac{1}{n}E(n-1))+\frac{1}{n} \\ &=1+\frac{2}{n} + \frac{1}{n^2} \\ E(n-4) &=1+\frac{1}{n}E(n-3) + \frac{1}{n}E(n-2)+\frac{1}{n}E(n-1) \\ &=1+\frac{3}{n}+\frac{3}{n^2}+\frac{1}{n^3}\\ \end{align*} We observe a pattern here, and you can prove with induction that $$E(n-k) = \sum_{i=0}^{k-1} \frac{\binom{k-1}{i}}{n^i}$$ for $1 \le k \le n$.

The value we seek is $E(0)$: $$E(0)=\sum_{i=0}^{n-1} \frac{ \binom{n-1}{i}}{n^i} = \left( 1+\frac{1}{n} \right)^{n-1}.$$

Note that as $n \rightarrow \infty$, $E(0) \rightarrow e$.

• Nice observation. Thanks I was trying from E(0) to E(n) and hence was not getting any pattern. Nov 9, 2013 at 7:07
• That's a very clever approach Matthew, starting with conditional expectations to "reach down" to the conditional expectation that becomes identical with the unconditional one, bravo. Nov 9, 2013 at 15:38
• @AlecosPapadopoulos Thanks, Alecos. I've seen it used on a number of SE probability problems in the past, so... Cheers! Nov 9, 2013 at 17:13
• Any hint how this could be expanded to dice that can have zeroes on them? Jan 18, 2016 at 14:49
• @Let_Me_Be The main difference is that $E(n-1)$ would not be $1$: if your die faces are labelled $0,1,\dots,n-1$ (so there are still $n$ faces, and we assume the die is fair), then $E(n-1)=n/n-1$. All the initial $1$s in the values I showed above should be replace by $n/n-1$, and in the recursions you'd have to consider the possibility of rolling a zero (which was not possible before), so your relationships would be a little different. Cheers! Jan 20, 2016 at 17:50

I understand that the $n$ faces of the dice have values $1,...,n$. I also assume that the dice is constructed fairly, and the rolls are independent. Then each roll $i$ can be mapped to a discrete uniform random variable $X_i$ taking values $\{1,...,n\}$ with probability mass function

$$P(X_i=k) =1/n, \qquad k=1,...,n$$

Then you want to consider the random variable (s)

$$S_k = \sum_{i=1}^{k}X_i,\qquad k=1,...,n$$

each having support $\{k,k+1,...,nk\}$

You are asking "what is the expected number of rolls after which the sum is $n$?" Obviously the sum won't stay fixed, so I understand it as "what is the expected number of rolls in order for the sum to reach or exceed $n$?" Given the structure of the problem, it is certain that we will reach the value $n$, even if we have to roll the dice $n$ times. This will happen if all rolls come up $1$. But of course we may reach the value $n$ sooner -the minimum number of rolls is $1$, if the first roll turns up $n$. Denote the number of rolls at which we reach or exceed $S_k=n$ for the first time, by $R$. But this hints towards conditional probabilities, since we are searching for the minimum number of rolls. Then, given $n$,

\begin{align} P(R=1) &= P(S_1=n) = 1/n\\ P(R=2) &= P(S_2\ge n \mid S_1<n) \cdot P(S_1<n)\\ &...\\ P(R=k) &= P(S_k\ge n \mid S_{k-1}<n) \cdot P(S_{k-1}<n) = P(S_k\ge n,S_{k-1}<n)\\ &etc \end{align}

We are multiplying by $P(S_1<n)$ because we want to make an ex ante probabilistic statement, before the rolling begins - we are not in the middle of the rolling process. Now, $S_k=S_{k-1}+X_k$. So (for $k\ge 2$)

$$P(R=k) = P(S_{k-1}+X_k\ge n,S_{k-1}<n) = P(X_k\ge n-S_{k-1}, S_{k-1}<n)$$

Since $X_k$ is independent of $S_{k-1}$, $$P(X_k\ge n-S_{k-1}, S_{k-1}<n) = \sum_{i=k-1}^{n-1}\left(P(S_{k-1}=i)\sum_{j=n-i}^{n}P(X_k=j)\right)$$

$$=\sum_{i=k-1}^{n-1}\left(P(S_{k-1}=i)(\frac {i+1}{n})\right) = \frac 1n \sum_{i=k-1}^{n-1}(i+1)P(S_{k-1}=i) = P(R=k)\equiv P_R(k)$$

Then $$E(R) = \sum_{k=1}^nkP_R(k),\qquad P_R(1) =1/n$$

In order to compute $E(R)$ we need the probability distribution of the $S_k$'s.

The probability generating function (PGF), denote it $G(z)$, of each $X_i$ is

$$G_{X_i}(z) = \sum_{i=1}^{n}p_{X_i}(x_i)z^{x_i} = \frac 1n(z+z^2+...+z^n)$$

Then the PGF of $S_k$ is (due to the i.i.d assumption)

$$G_{S_k}(z) = \frac 1{n^k}\left(z+z^2+...+z^n\right)^k$$

The probability mass function of $S_k$ relates to its PGF by

$$P(S_k=s) = \frac {1}{s!}\frac {d^sG_{S_k}(z)}{dz^s}|_{z=0}$$

and with this we can compute the various $P_R(k)$'s. It looks like it gets computationally monstrous very quickly.

• Thanks for such a explanatory answer but I guess am missing some point in P(Xk≥n−Sk−1,Sk−1<n), here why inner limit is till n, is it because that n is maximum number of rolls to get sum n for first time ? Nov 8, 2013 at 15:39
• It is $n$ because we do not want the sum to have exceeded this number before roll #k. Saying "because $n$ is the maximum number of rolls needed to..." is probably the same thing. Nov 8, 2013 at 16:30