4
$\begingroup$

Imagine a game with two dice, played by two people and a referee. The referee rolls the first die and the number will determine the number of times that the second die will be rolled. The two players never know the result of the first die and they must place bets on the total outcome (the sum of the numbers rolled with the second die). They can review the bet each time after the second die is rolled. With two regular (1:6) dice, and before any die is rolled, there are 55986 different combinations (6^6+6^5+...6^1), that will sum up in 36 total (from 1 to 36). My question is: how can I calculate the probability of each sum (from 1 to 36) without brute force?

I attach a simple example with two dice of (1:3) instead of (1:6); in this case we have 3^3+3^2+3^1=39 combinations and it is easy to use brute force.

The probabilities of the dice outcomes are:

enter image description here

enter image description here

$\endgroup$
  • $\begingroup$ To clarify, do you want an approximation for large values? Can we (mis)use the Central Limit Theorem? $\endgroup$ – Calvin Lin Mar 5 '14 at 12:47
  • $\begingroup$ A general formula would be the perfect answer. Any approximation is welcome, so your approach is valid. $\endgroup$ – Luis Gonilho Mar 5 '14 at 12:53
4
$\begingroup$

You could use probability generating functions (PGFs) to model the situation. The PGF for rolling the first die is $\frac{1}{6}(z^{1}+\dots+z^{6})$ . The exponents label the pips of the die, the coefficients give the number of occurrences of an event, weighted with the probability $\frac{1}{6}$ for each occurrence. To model the roll(s) of the second die $z$ is substituted by $z\mapsto\frac{1}{6}(x^{1}+\ldots+x^{6})$, since for each pip the second die will be rolled once. So, the PGF for the rolls of the second die is

$$A(x)\mathrel{\mathop:}=\frac{1}{6}\sum_{k=1}^{6}\frac{1}{6^{k}}\left(x^{1}+\dots+x^{6}\right)^{k}$$

To calculate the wanted probabilities for the resulting sums $1,\ldots,36$, we have to determine the coefficients $[x^{t}]$ of $x^{t}$ in $A(x)$ for each $t\in{1,\ldots,36}$. So,

\begin{eqnarray} [x^{t}]A(x) &=&[x^{t}]\sum_{k=1}^{6}\frac{1}{6^{k+1}}x^{k}\left(\sum_{j=0}^{5}x^{j}\right)^{k}\\ &=&\sum_{k=1}^{6}\frac{1}{6^{k+1}}[x^{t-k}]\left(\frac{1-x^{6}}{1-x}\right)^{k}\\ &=&\sum_{k=1}^{6}\frac{1}{6^{k+1}}[x^{t-k}]\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}x^{6j}\frac{1}{(1-x)^{k}}\\ &=&\sum_{k=1}^{6}\frac{1}{6^{k+1}}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}[x^{t-k-6j}]\sum_{l\geq0}\binom{-k}{l}(-x)^{l}\\ &=&\sum_{k=1}^{6}\frac{1}{6^{k+1}}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}[x^{t-k-6j}]\sum_{l\geq0}\binom{k+l-1}{l}x^{l}\\ &=&\sum_{k=1}^{6}\frac{1}{6^{k+1}}\sum_{{j=0}\atop{t-6j-1\ge0}}^{k}(-1)^{j}\binom{k}{j}\binom{t-6j-1}{t-6j-k} \end{eqnarray}

Finally,

$$ [x^{t}]A(x)=\sum_{k=1}^{6}\frac{1}{6^{k+1}}\sum_{{j=0}\atop{t-6j\ge1}}^{k}(-1)^{j}\binom{k}{j}\binom{t-6j-1}{k-1}\qquad\qquad t=1,\ldots,36 $$

Which $t$ would you choose for a bet? :-)

Note: The polynomial in $z$ encodes the probability distribution of rolling the first die. E.g. $z^4$ encodes the event: rolling a $4$. So, $z^1+\dots+z^6$ encodes all possible events, namely rolling $1,\dots,6$. These events are weighted with the probability of occurrence, giving a total of $1/6\cdot(1+\dots+1)=(1/6)\cdot 6=1$. How is $4$ encoded when rolling the second die? Since, we have to roll the second die four times, the contribution is $(x^1+\dots+x^6)^4$. Expansion of this expression shows that all $6^4$ quadruples from $(1,1,1,1) \mapsto x^1x^1x^1x^1$ up to $(6,6,6,6) \mapsto x^6x^6x^6x^6$ are encoded. This is weighted with the probability ${(1/6)}^4$ according to the number of possible 4-tuples. But, rolling a $4$ (first die) occurs only in $1$ out of $6$ cases, so we have to multiply with an additional factor $1/6$ resulting in ${(1/6)}^5$.

$\endgroup$
  • $\begingroup$ It sure seems very useful, but I'm not sure if I've fully understood how to use. For instance, before any die are rolled, and using your formula, what is the probability of the final total sum is 1 (it should be 1/6 x 1/6 = 1/36)? And 36 (it should be ((1/6)^6)x(1/6)? And my bet is 11 :-) $\endgroup$ – Luis Gonilho Mar 9 '14 at 12:07
  • 1
    $\begingroup$ I've added a small note in the answer above with some additional info. Btw: My favorite is 6 showing a probability of 6,003872%. The ranking of the 36 different values is interesting and reflects most of all the fact, that the contribution of an event to a value is smaller (by a factor 1/6) depending on the number of additional rolls of the second die. :-) $\endgroup$ – Markus Scheuer Mar 9 '14 at 19:50
  • $\begingroup$ This is absolutely brilliant, Markus. It is elegantly correct! Indeed 6 is the bet with 6,00387%, followed by 5 with 5,146% and then 11 with 4,876%. Can I challenge you more? Imagine that instead of die you had two power functions describing the probabilities, one for the "rolls" (a.x^-k) and one for number of repetitions (b.x^-m), where x is a positive integer >=1. Is there a "clean" solution like the one above? Many thanks for your help. $\endgroup$ – Luis Gonilho Mar 10 '14 at 10:59
  • $\begingroup$ Thanks for your nice answer. And I see, we share the same bets now! :-) Your challenge is interesting. You could place it as a question by its own. Best regards, Markus $\endgroup$ – Markus Scheuer Mar 10 '14 at 12:33
  • $\begingroup$ The new question. I hope it is clear enough. math.stackexchange.com/questions/706778/… $\endgroup$ – Luis Gonilho Mar 10 '14 at 14:30
2
$\begingroup$

Let the first dice have $n$ faces, and the second dice have $m$ faces.

Let $D(i,m)$ denote the pdf for the sum of $i$ rolls of a $m$-sided die. Note that it has mean $i \times \frac{m+1}{2}$ and standard deviation $i \times \frac{m^2-1}{12}$

Then, the total pdf can be expressed as

$$ \sum_{i=1}^n \frac{1}{n} PDF ( D(i,m) )$$

We (abuse) use the central limit theorem, for large $n$, which gives us

$ D(i,m) \sim N(i \times \frac{m+1}{2},i \times \frac{m^2-1}{12}) $

It is then much easier to determine the probability.

$\endgroup$
1
$\begingroup$

I am afraid you cannot, in the sense that there will not be any general formula where you can simply plug the value of the sum S, and obtain probability.

Here's the best that I can do though.

  • Obtain the number of possible ways a sum, say $S$ can be achieved, i.e, the number of solutions of the equation, $$x_1 + x_2 +\cdots +x_6 = S \text{ for } 0 \le x_i \le6$$

  • There will be solutions where some $x_i = 0$. The number of non-zero $x_i$ is equal to the original number on the first dice.

  • The probability of that particular number occurring is $\frac16$. And the probabilities of any one solution occuring are all equal.

  • Thus we may conclude, the relative odds of a total sum, is the number of ways said sum may be achieved.

Not sure though, and there may be better ways to calculate. Marking as community-wiki.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I can always use brute force with a 6x6 since 55986 combinations are easy to compute. The problem is, for example, if you have a real problem with 2000x40, because here you have 1.1E+132 combinations and a quad-core will take 100+ years to solve... $\endgroup$ – Luis Gonilho Mar 5 '14 at 12:32
  • $\begingroup$ Since you're saying that using a computer is valid, I am asumming this isn't probability class. What is it then? Also where do you get 2000x40? If you provide context about the actual question, I might be able to help. $\endgroup$ – Guy Mar 5 '14 at 12:35
  • $\begingroup$ A general formula would be a great help and I still think it is a great probability challenge. The 2000x40 example is an extreme situation. In biology, there are certain organisms that can live 1-40 days (with different probabilities) and each day they can infect 1-2000 other organisms (with different probabilities). If I had a formula I could easily compute this. $\endgroup$ – Luis Gonilho Mar 5 '14 at 12:38
  • $\begingroup$ @LuisGonilho oh I see. Differing probabilities is even more intense. Maybe cross post to stackoverflow with a link to this question, asking for help. Since we aren't being able to calculate it mathematically anyway, might as well optimize the computation, avoiding actual brute force. :) $\endgroup$ – Guy Mar 5 '14 at 12:52
  • $\begingroup$ I would suggest using a generating function + a computer, if you want to count the exact number of terms. It's not that hard (for the computer). $\endgroup$ – Calvin Lin Mar 5 '14 at 12:59

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.