Expected number of rolls

Question

A fair m-sided dice is rolled and summed until the sum is at least N. What is the expected number of rolls? In other words what is the number of rolls if we roll a m-sided dice and the sum of rolls become at least N.

Answer 1

If $f(N)$ is the expected number of rolls, by conditioning on the first roll we have $f(N) = 1 + m^{-1} \sum_{j=1}^m f(N-j)$ for $N > 0$, with $f(N) = 0$ for $N \le 0$. The generating function is $$g(z) = \sum_n f(n) z^n = \dfrac{mz}{m - (m+1)z + z^{m+1}}$$

EDIT: If you're interested in the asymptotic behaviour of $f(N)$ as $N \to \infty$ for fixed $N$, you want to look at the smallest root of the denominator, which is $z=1$. We have $$g(z) = \dfrac{2}{(m+1)(z-1)^2} - \dfrac{2(m-4)}{3(m+1)(z-1)} + h(z)$$ where $h(z)$ is analytic in a neighbourhood of the unit disk. Corresponding to this we get $$ f(N) = \dfrac{2 N}{m+1} + \dfrac{2(m-1)}{3(m+1)} + O(c^{-N}) \ \text{as}\ N \to \infty $$ for some $c > 1$ (depending on $m$).

Answer 2

The expected value of any roll of a fair die is the sum of the possible rolls divided by the number of sides, thus an $m$-sided die would have an expected value of $\frac{\frac{m(m+1)}{2}}{m}=\frac{m+1}{2}$ for each roll. From there is should be simple to calculate the expected number of rolls to reach any value.

Answer 3

The naive answer of $\frac N{m/2}$ misses a couple things. First, the expected value of a single roll is $\frac {m+1}2$ because we start counting the sides at $1$. For large $N$, the revision to $\frac {2 N}{m+1}$ is correct. Second, for small $N$ it can't be-certainly for $N=1$ the expected number of rolls is $1$

Answer 4

The nice constant correction $\frac23\frac{m-1}{m+1}$ that comes out of Robert Israel's generating function approach can also be derived directly from the recurrence for the expectations $a_N$:

$$ a_k=1+\frac1m\sum_{j=1}^ma_{k-j}\;. $$

This inhomogeneous linear recurrence has a particular solution linear in $k$, $a_k=\frac2{m+1}k$, and the general solution of the corresponding homogeneous linear recurrence is a constant plus a combination of exponentially decaying solutions. To determine the constant, consider the matrix

$$ \pmatrix{\frac1m&\frac1m&\cdots&\frac1m&\frac1m\\1&0&\cdots&0&0\\0&1&&0&0\\\vdots&&\ddots&0&0\\0&0&\cdots&1&0} $$

corresponding to the recurrence. The eigenvalue $1$ has right eigenvector $(1,\ldots,1)^\top$ and corresponds to the constant solution. We can use the corresponding left eigenvector $(m,m-1,\ldots,2,1)$ to extract the constant from the initial conditions (since left and right eigenvectors for different eigenvalues are orthogonal). With $a_0=a_{-1}=\cdots=a_{-m+1}=0$, we find

\begin{align} \sum_{j=-m+1}^0(m+j)\left(a_j-\frac2{m+1}j\right) &= \sum_{j=0}^{m-1}(m-j)\frac2{m+1}j \\ &=\frac2{m+1}\left(m\sum_{j=0}^{m-1}j-\sum_{j=0}^{m-1}j^2\right) \\ &=\frac2{m+1}\left(\frac{m^2(m-1)}2-\frac{(m-1)m(2m-1)}6\right) \\ &=\frac13m(m-1)\;. \end{align}

The corresponding value for the constant solution with constant $c$ is

$$ \sum_{j=0}^{m-1}(m-j)c=\sum_{j=1}^mmc=\frac{m(m+1)}2c\;, $$

and equating the two and solving for $c$ yields

$$ c=\frac23\frac{m-1}{m+1}\;, $$

in agreement with Robert's result.