1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What are your thoughts so far? $\endgroup$ – Null Nov 5 '14 at 16:23
  • 1
    $\begingroup$ I'm guessing the answer isn't just $\frac{N}{m/2}$. That would be the naive answer! $\endgroup$ – Shane Nov 5 '14 at 16:23
  • $\begingroup$ This question is similar to question 24 in the pdf "A Collection of Dice Problems" by Matthew M. Conroy where the answer is equal to "e". However in my question I search for number of rolls of m-sided (and not n sided) which the sum result n. madandmoonly.com/doctormatt/mathematics/dice1.pdf $\endgroup$ – peyman pouyan Nov 5 '14 at 16:42
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you please explain more about how do you obtain your answer? Is there any relation between N you use in your notation and the summation result (N)? $\endgroup$ – peyman pouyan Nov 5 '14 at 17:13
  • $\begingroup$ My $N$ is the same as your $N$: the target sum. I multiplied each side of my equation by $z^N$, summed over $N$, expressed the result in terms of $g$ and solved for $g$. $\endgroup$ – Robert Israel Nov 5 '14 at 17:58
  • $\begingroup$ This is very nice; I wasn't aware that there's a constant correction $\frac23\frac{m-1}{m+1}$ that can be derived like this. This prompted me to post an answer deriving this directly from the recurrence. $\endgroup$ – joriki Jun 18 '16 at 11:59
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ It's correct in the sense that it has the right asymptotic behaviour, but there's a constant correction (see Robert's answer and mine). $\endgroup$ – joriki Jun 18 '16 at 12:02
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ first of all, I have to say, that because of my lack of knowledge I did not understand to the end neither your answer or Robert Israel's answer. Hopefully, I'll try to understand them later on. However, may I still ask, what is the meaning of this "constant correction" , because basically even if we take $N=2$ and $m=6$ the answer is clearly $\frac{7}{6}$, but if I added the "constant correction" to the "naive answer" of $\frac{2N}{m-1}$ I get a bit lower answer. and my try with $N=20$ yields indeed much more close answer, but this time higher than the real answer. $\endgroup$ – d_e Jun 19 '16 at 10:45
  • 1
    $\begingroup$ @d_e: These are results for large $N$. In Robert's answer, there's a term $O\left(c^{-N}\right)$; I also mentioned the exponentially decaying solutions. The exact solution is a linear combination of the linear term $\frac{2N}{m+1}$, the constant term $\frac23\frac{m-1}{m+1}$ and $m-1$ geometric terms of the form $c\lambda^N$ with $\lambda\lt1$. For small $N$ like $N=2$ these latter terms are large. For $m=6$, $N=20$, I get $\frac{2N}{m+1}\approx5.71$ from the linear term and $\frac23\frac{m-1}{m+1}\approx0.48$ from the constant term, for a total of $6.19$, which agrees with simuations. $\endgroup$ – joriki Jun 19 '16 at 11:05
  • $\begingroup$ @d_e: Note that there's a typo in your comment; where it says $\frac{2N}{m-1}$ it should be $\frac{2N}{m+1}$. In case you used that expression, that might explain any discrepancies you found. $\endgroup$ – joriki Jun 19 '16 at 11:08
  • $\begingroup$ interesting. thanks for the explanation. indeed I had a typo. $\endgroup$ – d_e Jun 19 '16 at 11:10

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.