10
$\begingroup$

I am primarily asking for what this kind of problem would be called.

Say I have one six-sided die. How many times on average would I have to roll it in order to have a sum of at least 30?

Doing some googling, the closest I have found was a geometric distribution. But I am unsure if that is strictly for pass/fail scenarios (such as flipping a coin or drawing a name out of a hat).

The closest I can get is that it will take no more than 30 tries (at a $1/6^30$ chance) and no less than 5 tries (at a $1/6^5$ chance). My problem arises when I think about the number of possible ways to get 6 tries. It would be easy if each die had 2 outcomes, but each one has 6, and many combinations can accomplish this. I don't even know where to begin figuring out how many combinations exist outside of counting (which would take hours).

EDIT: So I found this Help with the Probabilty of Rolling Two Ten-Sided Dice Multiple Times Until 100 is Reached

This is very much what this problem is, but it doesn't mention what the process is called. Which in the end is what my main question is.

$\endgroup$
  • $\begingroup$ "This is very much what this problem is" Sorry but I fail to see where they treat your question. $\endgroup$ – Did Feb 6 at 20:51
8
$\begingroup$

A standard way to solve this is to consider simultaneously the mean number of rolls $t_n$ needed to reach $n$ for every nonnegative integer $n$ (and to remember at the end that the OP is asking for $t_{30}$). So, let us do that...

For every $n\leqslant0$, $t_n=0$. For every $n\geqslant1$, considering the result of the first roll, one sees that $$t_n=1+\frac16\sum_{k=1}^6t_{n-k} $$ Thus, the series $$T(s)=\sum_nt_ns^n$$ solves $$T(s)=\frac s{1-s}+\frac16\sum_{k=1}^6s^kT(s)$$ from which it follows that $$T(s)=\frac{6s}{(1-s)\left(6-\sum\limits_{k=1}^6s^k\right)}=\frac{6s}{6-7s+s^7}$$ To extract the coefficient $t_{30}=[s^{30}]T(s)$ of $s^{30}$ in $T(s)$, rewrite this as $$T(s)=s\left(1-rs\left(1-\frac t7\right)\right)^{-1}=\sum_{n=0}^\infty r^ns^{n+1}\left(1-\frac t7\right)^n$$ where $$r=\frac76\qquad t=s^6$$ hence $$[s^{30}]T(s)=\sum_{k=0}^4r^{5+6k}[t^{4-k}]\left(1-\frac t7\right)^{5+6k}$$ or, equivalently, $$[s^{30}]T(s)=\sum_{k=0}^46^{-5-6k}[t^{4-k}]\left(7-t\right)^{5+6k}=\frac7{6^5}\sum_{k=0}^4(-1)^kr^{6k}{5+6k\choose4-k}$$ that is, $$t_{30}=\frac7{6^5}\left(5-165r^6+136r^{12}-23r^{18}+r^{24}\right) $$ which can be "simplified" into the exact result $$t_{30}= \frac{333366007330230566034343}{36845653286788892983296}$$ with a numerical approximation $$t_{30}\approx 9.047634594384022902065997942672796588425278684184104625$$


Edit: To get some estimates of $t_n$ when $n\to\infty$, note that $$T(s)=\frac s{(1-s)^2Q(s)}$$ where $$Q(s)=\frac16(6+5s+4s^2+3s^3+2s^4+s^5)$$ Furthermore, $(1-s)Q(s)=1-\frac16\sum\limits_{k=1}^6s^k$ has no zero in the closed unit disk except the simple zero $s=1$ hence $Q(s)$ has no zero in the closed unit disk. This implies that $$T(s)=\frac a{(1-s)^2}+\frac b{1-s}+R(s)$$ for some given $(a,b)$ and some rational fraction $R(s)=\sum\limits_nr_ns^n$ with no pole in the closed unit disk. Then, there exists some finite $c$ and some $\varrho$ in $(0,1)$ such that, for every $n$, $$|r_n|\leqslant c\varrho^n$$ This yields, again for every $n$, $$|t_n-a(n+1)-b|=|r_n|\leqslant c\varrho^n$$ Equivalently, $$t_n=an+(a+b)+O(\varrho^n)$$ To identify $(a,b)$, note that $$(1-s)^2T(s)=a+b(1-s)+(1-s)^2R(s)$$ hence $$a=\left.(1-s)^2T(s)\right|_{s=1}=\frac1{Q(1)}$$ and $$b=-\left.\frac d{ds}[(1-s)^2T(s)]\right|_{s=1}=-\frac1{Q(1)}+\frac{Q'(1)}{Q(1)^2}$$ or, equivalently, $$a+b=\frac{Q'(1)}{Q(1)^2}$$ Finally, $Q(1)=\frac72$ and $Q'(1)=\frac{35}6$ hence $a=\frac27$ and $a+b=\frac{10}{21}$, which implies $$t_n=\frac27n+\frac{10}{21}+O(\varrho^n)$$ Edit-edit: More generally, throwing repeatedly a "die" producing a random number of points distributed like $X$, following the same route, one gets $a=E(X)$ and $a+b=Q'(1)/E(X)^2$ with $Q'(1)=\frac12E(X(X-1))$, hence, for some $\varrho_X$ in $(0,1)$ depending on the distribution of $X$, $$t_n=\frac1{E(X)}n+\frac{E(X(X-1))}{2E(X)^2}+O(\varrho_X^n)$$

$\endgroup$
  • $\begingroup$ Nice answer, +1! \\ Do you reckon that, replacing $30$ by $M$ you could get a nice, tractable, limiting result? My (significantly less complete) answer shows that asymptotically it's $\tfrac27 M + \mathcal O(1)$, and the answer to [math.stackexchange.com/questions/3101264] shows that (in your $t_M$ notation) $$\bigl| t_M - \tfrac27 (M + \tfrac83) \bigr| \to 0 \quad \text{as $M \to \infty$}.$$ Do you think your method would be able to give that in a tractable way? $\endgroup$ – Sam T Feb 6 at 14:10
  • $\begingroup$ @SamT Yes, please see edit. Note that the page you link to seems unavailable and that the result in it, as you transcribe it, differs from the one I get by a shift $n\to n+1$ (or $M\to M+1$...) since $\frac27+\frac{10}{21}$ (my result) is also $\frac27\cdot\frac83=\frac{16}{21}$ (the one in your comment). Finally, I hope the way to compute the optimal value of $\varrho$, if need be, is clear from my edit. $\endgroup$ – Did Feb 6 at 18:00
  • $\begingroup$ Dude, you are one analytic/probabilistic machine! I don't know enough about analysis to know why such a $c$ and $\varrho$ exist in the first place; do you have a reference I can read? \\ Regarding the link, just take the final square bracket ] off -- for some reason it's put that in the link. Moreover, I did get the shift wrong (silly calculation error), and your answer of $10/21$ is correct. $\endgroup$ – Sam T Feb 6 at 20:26
  • $\begingroup$ The geometric control follows from the fact that $Q(s)$ is a polynomial with no root in the unit disk hence $$Q(s)=\prod\limits_{k=1}^5(1-\alpha_ks)$$ for some $|\alpha_k|<1$. Thus, the decomposition in simple elements of $T(s)$ reads $$T(s)=\frac a{(1-s)^2}+\frac b{1-s}+\sum_{k=1}^5\frac{\beta_k}{1-\alpha_k s}$$ that is, $$R(s)=\sum_{n=0}^\infty\sum_{k=1}^5\beta_k\alpha_k^ns^n$$ Thus, the bound in my Edit holds with $$c=\sum_{k=1}^5|\beta_k|\qquad\varrho=\max_{1\leqslant k\leqslant 5}|\alpha_k|$$ (This is the idea if the $\alpha_k$s are distinct, otherwise the result remains true.) $\endgroup$ – Did Feb 6 at 21:00
  • $\begingroup$ Cool, thanks! I like this generating function/series approach. I must confess it's not the style of proof that I tend to employ... but I'm beginning to feel that I should employ it more often! $\endgroup$ – Sam T Feb 6 at 21:59
4
$\begingroup$

Let's replace the target "$30$" with a general target $M$. Let $X_n$ denote the 'score' after $n$ throws; define $Y_n = X_n - \tfrac72 n$. Note that $E(Y_n) = 0$, and moreover $E(Y_n \mid Y_{n-1}) = 0$, so it is a martingale. Let $$ \tau = \inf\{ n \ge 0 \mid X_n \ge M \} = \inf\{ n \ge 0 \mid Y_n \ge M - \tfrac72 n \}. $$ Then $\tau$ is a stopping time for $Y$, and so by the optional stopping theorem $E(Y_\tau) = Y_0 = 0$. (Here $\tau$ is deterministically bounded by $M$, and so this is the easy case for OST.) In particular, $$ E(Y_\tau) = 0 \iff E(\tau) = \tfrac27 E(X_\tau). $$ A key point is that while $X_\tau \ge M$, we don't necessarily have equality. Of course, $X_\tau \in [M,M+5]$, and so $$ E(\tau) \in \bigl[ \tfrac27M, \tfrac27(M+5) \bigr], $$ and interval of width $10/7$. If you imagine $M \to \infty$, this means that we know $E(\tau)$ is linear in $M$ (and even know the constant, $\tfrac27$) and our estimate is $\mathcal O(1)$ off.

This is as far as I am able to get. It is not clear to me what the distribution of $X_\tau$ is. (Note that one only needs to know its mean.)


Update. I was interested by this, and posted a very related question: Distribution at First Time a Sum Reaches a Threshold. The answer given there (not by me, unfortunately!) gives the limiting distribution of $X_\tau$, in a simple form from which it is easy to calculate the mean (in the limit $M \to \infty$). Using this question/answer, and a little bit of algebra, one finds that the answer in question is that $$ E(\tau) = \tfrac27 M + \tfrac{10}{21} + o(1). $$

The answer also gives an iterative solution for any $M$, but involves working out a large power of a matrix.

$\endgroup$
  • $\begingroup$ Not $E(\tau) = \tfrac27 M + \tfrac{10}{21}$ but $E(\tau) = \tfrac27 M + \tfrac{10}{21}+o(1)$. $\endgroup$ – Did Feb 6 at 22:02
  • $\begingroup$ Oops, thank you! If you check the link, you'll see the $o(1)$ term is there (implicitly, since $M \to \infty$ is considered). Thanks! $\endgroup$ – Sam T Feb 6 at 22:10
  • $\begingroup$ I know. $ $ $ $ $\endgroup$ – Did Feb 7 at 7:50
  • $\begingroup$ "The answer given there (not by me, unfortunately!) gives the distribution of 𝑋𝜏, in a simple form from which it is easy to calculate the mean" No it does not give it "in a simple form from which it is easy to calculate the mean". $\endgroup$ – Did Feb 8 at 8:43
  • $\begingroup$ I meant "in the limit $M \to \infty$" (hence the $o(1)$ term). I've made this explicit $\endgroup$ – Sam T Feb 8 at 10:12
0
$\begingroup$

The generating function for the distribution of sums when rolling $k$ six sided dice is $$ \left(\frac{x}6+\frac{x^2}6+\frac{x^3}6+\frac{x^4}6+\frac{x^5}6+\frac{x^6}6\right)^k=\left(\frac{x-x^7}{6(1-x)}\right)^k $$ The probability that roll $k$ will put the total to $n$ or greater is, assuming we've made $k-1$ rolls, the probability that the total is $n-1$, plus $\frac56$ of the probability that the total is $n-2$, plus $\frac46$ of the probability that the total is $n-3$, plus $\frac36$ of the probability that the total is $n-4$, plus $\frac26$ of the probability that the total is $n-5$, plus $\frac16$ of the probability that the total is $n-6$. That is, $$ \begin{align} &\left[x^n\right]\left(x+\frac56x^2+\frac46x^3+\frac36x^4+\frac26x^5+\frac16x^6\right)\left(\frac{x^7-x}{6(x-1)}\right)^{k-1}\\ &=\left[x^n\right]\frac{x-\frac76x^2+\frac16x^8}{(1-x)^2}\left(\frac{x^7-x}{6(x-1)}\right)^{k-1} \end{align} $$ Thus, the generating function for the average number of rolls to total $n$ or more is $$ \begin{align} \sum_{k=1}^\infty\frac{x-\frac76x^2+\frac16x^8}{(1-x)^2}k\left(\frac{x^7-x}{6(x-1)}\right)^{k-1} &=\frac{x-\frac76x^2+\frac16x^8}{(1-x)^2}\frac1{\left(1-\frac{x^7-x}{6(x-1)}\right)^2}\\ &=\frac{x-\frac76x^2+\frac16x^8}{(1-x)^2}\left(\frac{1-x}{1-\frac76x+\frac16x^7}\right)^2\\[12pt] &=\frac{x}{1-\frac76x+\frac16x^7} \end{align} $$


Recursion to Compute Coefficients

If we set $$ \frac{x}{1-\frac76x+\frac16x^7}=\sum_{n=1}^\infty\frac{a_nx^n}{6^{n-1}} $$ then we get the recursion $$ a_n=\left\{\begin{array}{} 7^{n-1}&\text{if }1\le n\le7\\ 7\,a_{n-1}-46656\,a_{n-7}&\text{if }n\gt7 \end{array}\right. $$ Thus to answer the question, $$ \begin{align} \frac{a_{30}}{6^{29}} &=\frac{333366007330230566034343}{36845653286788892983296}\\[6pt] &\doteq9.0476345943840229021 \end{align} $$


Power Series to Compute Coefficients $$ \begin{align} \left[x^n\right]\frac{x}{1-\frac76x+\frac16x^7} &=\left[x^{n-1}\right]\sum_{k=0}^\infty\left(\frac76x-\frac16x^7\right)^k\\ &=\left[x^{n-1}\right]\sum_{k=0}^\infty\sum_{j=0}^k\binom{k}{j}\left(\frac76\right)^{k-j}x^{k-j}\left(-\frac16\right)^jx^{7j}\\ &=\left[x^{n-1}\right]\sum_{j=0}^\infty\sum_{k=j}^\infty\binom{k}{j}\left(\frac76\right)^{k-j}x^{k-j}\left(-\frac16\right)^jx^{7j}\\ &=\left[x^{n-1}\right]\sum_{j=0}^\infty\sum_{k=0}^\infty\binom{k+j}{j}\left(\frac76\right)^kx^k\left(-\frac16\right)^jx^{7j}\\ &=\sum_{j=0}^\infty\sum_{k=0}^\infty\binom{k+j}{j}\left(\frac76\right)^k\left(-\frac16\right)^j[k+7j=n-1]\\ &=\sum_{j=0}^{\left\lfloor\frac{n-1}7\right\rfloor}\binom{n-6j-1}{j}\left(\frac76\right)^{n-7j-1}\left(-\frac16\right)^j\\ \end{align} $$ For $n=30$, this gives $$ \begin{align} &\textstyle\binom{29}{0}\left(\frac76\right)^{29}-\binom{23}{1}\left(\frac76\right)^{22}\left(\frac16\right)^1+\binom{17}{2}\left(\frac76\right)^{15}\left(\frac16\right)^2-\binom{11}{3}\left(\frac76\right)^8\left(\frac16\right)^3+\binom{5}{4}\left(\frac76\right)^1\left(\frac16\right)^4\\[6pt] &=\textstyle\frac1{6^{29}}\left(\binom{29}{0}7^{29}-\binom{23}{1}7^{22}6^6+\binom{17}{2}7^{15}6^{12}-\binom{11}{3}7^86^{18}+\binom{5}{4}7^16^{24}\right)\\[3pt] &=\frac{333366007330230566034343}{36845653286788892983296}\\[9pt] &\doteq9.0476345943840229021 \end{align} $$

$\endgroup$

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.