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

Question

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

Answer 1

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

Answer 2

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.