9
$\begingroup$

Rules

I have four different types of dice: six-, eight-, ten- and twelve-sided (d6, d8, d10 & d12, respectively).

The number of successes vary by the value rolled (and thus indirectly by dice type).

  • One success is gained by rolling 6 or 7.
  • Two successes are gained by rolling 8 or 9.
  • Three successes are gained by rolling 10 or 11.
  • Four successes are gained by rolling 12.

This means that a 1d6 can result in at most 1 success, 1d8 1-2 successes, 1d10 1-3, and 1d12 1-4.

Successes are added together after the roll, so rolling 6 dice and getting [12, 3, 8, 7, 10, 1] will result in 4 + 2 + 1 + 3 = 10 successes.

Input is the number of dice and how many sides they have, and the minimum amount of successes I want to achieve.

Question

My main question is this:

Given that I roll a known combination of d6s, d8s, d10s and d12s, how do I calculate the probability of rolling N or more successes? Q1

(though feel free to answer any other questions in this post as well, indexed Q$n$ for your convenience)

Context

I know how to calculate the probability of rolling at least $N$ successes for an arbitrary number of d6's, since they can only yield one success at most.

I am stuck, however, when it comes to calculating at least $N$ successes when rolling a mix of differently sided dice, where some of them can yield more than one success.

For example, with $5$d6, $1$d8, $1$d12, how likely am I to roll $\geq$ 4 successes? Q2


EDIT: It's been brought to my attention that there is no closed form solution to this question.

That is fine; any solution or clever approximation that's more efficient than running 100k simulated rolls is a sufficient answer.

Can the problem be split into separate probabilities that can later be combined? E.g., given 5d6 & 1d12 and that I'm looking for the probability of at least $k$ successes, can I calculate the probabilities for each die type separately and later combine them somehow? Q3

Also, how would I go about calculating $\geq k$ successes for 1d12? For 2d12? For $n$d12? Q4

Currently, I can 'solve' the problem by running a simulation, but it irks me that I am not able come up with anything better.

$\endgroup$
7
  • $\begingroup$ The answer will be different for every possible combination of dice and doesn't really have a general closed form. $\endgroup$
    – Math1000
    Jun 23, 2020 at 22:51
  • $\begingroup$ Could you show how this is the case? I am also interested in partial solutions that combined would provide an answer, e.g.: a mathematical model that would allow a faster numeric computation compared to arriving at a result by running a simulation. $\endgroup$
    – imolit
    Jun 24, 2020 at 0:00
  • $\begingroup$ Are you aware of generating functions? You can easily derive number of desired cases of a certain scores sum, compared to total cases it would give the probability. But no closed formula in either case, yeah. $\endgroup$ Jun 24, 2020 at 0:57
  • $\begingroup$ I was not aware, thank you for the link. However, I've tried solving this problem by using the solutions to similar questions on this site, but unfortunately my skills in math are not sufficient. You might think it's easy, but for me it's not, so I would be very grateful if you could show me :) $\endgroup$
    – imolit
    Jun 24, 2020 at 22:45
  • $\begingroup$ It would be more clear if instead of "success" we speak of "points". Then however it is not clear how you count / cumulate the points upon throwing the mix of dice. Suppose you have 5 dice and get $[3,6,7,10,10]$ would that give $8$ points? $\endgroup$
    – G Cab
    Jun 25, 2020 at 0:00

3 Answers 3

5
$\begingroup$

Representation via generating functions

This isn't satisfactory in the sense that we still cannot obtain a closed form, but the representation is concise and easily programmable. Suppose we have $(k_6, k_8, k_{10}, k_{12})$ dice of types d6, d8, d10, and d12 respectively. Let \begin{align*} f_6(x) &= \left(\frac{5}{6}+\frac{1}{6}x\right)^{k_6} \\ f_{8}(x) &= \left(\frac{5}{8}+\frac{2}{8}x+\frac{1}{8}x^2\right)^{k_8} \\ f_{10}(x) &= \left(\frac{5}{10}+\frac{2}{10}x+\frac{2}{10}x^2+\frac{1}{10}x^3\right)^{k_{10}}\\ f_{12}(x) &= \left(\frac{5}{12}+\frac{2}{12}x+\frac{2}{12}x^2+\frac{2}{12}x^3+\frac{1}{12}x^4\right)^{k_{12}} \\ f(x) &= f_6(x)f_8(x)f_{10}(x)f_{12}(x) \end{align*} Let $N$ be the random variable denoting the total number of successes (slightly different notation from your post, where you let $N$ represent the value of interest). Then, the probability of getting exactly $n$ successes is \begin{align*} P(N = n) =[x^n]f(x) \end{align*} where $[x^n]f(x)$ is the coefficient of $x^n$ of $f(x)$. The cumulative distribution function (i.e. the probability of getting $n$ successes or fewer) is \begin{align*} P(N \le n) = [x^n]\frac{f(x)}{1-x} \end{align*} And so \begin{align*} P(N \ge n) = 1 - [x^{n-1}]\frac{f(x)}{1-x} \end{align*}

Finite-Sample Upper Bound

Let \begin{align*} K = k_6 + k_{8} + k_{10} + k_{12} \end{align*} and so the proportion of the $K$ dice which are d6, d8, d10, and d12 are respectively \begin{align*} (p_6, p_8, p_{10}, p_{12}) = (k_6, k_8, k_{10}, k_{12})/K \end{align*} Let $N_k \in \{0, \cdots, 4\}$ ($k = 1, \cdots, K$) be the random variable denoting the success number for each die, and \begin{align*} X_m = \sum_{k=1}^{K}\mathbb{I}(N_k = m) \end{align*} denote the number of successes produced from the $K$ dice. Then the proportion of the $K$ dice falling in each $m$ ($m = 0, \cdots, 4$), is \begin{align*} q_0 &= \frac{5}{6}p_6 + \frac{5}{8}p_8 + \frac{5}{10}p_{10} + \frac{5}{12}p_{12} \\ q_1 &= \frac{1}{6}p_6 + \frac{2}{8}p_8 + \frac{2}{10}p_{10} + \frac{2}{12}p_{12} \\ q_2 &= \frac{0}{6}p_6 + \frac{1}{8}p_8 + \frac{2}{10}p_{10} + \frac{2}{12}p_{12} \\ q_3 &= \frac{0}{6}p_6 + \frac{0}{8}p_8 + \frac{1}{10}p_{10} + \frac{2}{12}p_{12} \\ q_4 &= \frac{0}{6}p_6 + \frac{0}{8}p_8 + \frac{0}{10}p_{10} + \frac{1}{12}p_{12} \end{align*} So, $(X_0, \cdots, X_4) \sim \text{Multinomial}(K, (q_0, \cdots, q_4))$.

Finally, \begin{align*} P(N \ge n) &= P\left(\sum_{m=0}^{4} mX_m \ge n\right) \\ &= P\left(\exp\left(t\sum_{m=0}^{4} mX_m\right) \ge \exp(tn)\right) & z \mapsto e^{tz} \text{ is increasing for } t>0\\ &\le \frac{E\left[\exp\left(t\sum_{m=0}^{4} mX_m\right)\right]}{e^{tn}} & \text{Markov's inequality} \\ &= e^{-nt}\left(\sum_{m=0}^{4}q_m e^{mt}\right)^K \\ &= \left(\sum_{m=0}^{4}q_m e^{t(m - K^{-1}n)}\right)^K \end{align*} and so we can form the Chernoff bounds \begin{align*} P(N \ge n) \le \left(\inf_{t>0}\sum_{m=0}^{4}q_m e^{t(m - K^{-1}n)}\right)^K \end{align*}

Example

Let's suppose we have $(k_6, k_8, k_{10}, k_{12}) = (5, 7, 11, 13)$ and want to find $P(N \ge 30)$. Then \begin{align*} P(N \ge 30) = 1 - [x^{29}]\frac{f(x)}{1-x} = 1- \frac{56649270689104302470179125877}{148888471031133469396697088000} \approx 0.6195 \end{align*} Using the Chernoff bound with \begin{align*} K = 36, \mathbf{q} = (0.5405, 0.1931, 0.1456, 0.0907, 0.0301) \end{align*} We find that the infimum is attained at $t^* = 0.0894$ giving us $P(N \ge 30) \le 0.8453$.

$\endgroup$
6
  • 1
    $\begingroup$ by $[x^N]$ do you mean $[x^n]$? $\endgroup$ Jun 27, 2020 at 22:27
  • $\begingroup$ Yes! I've edited. $\endgroup$
    – Tom Chen
    Jun 28, 2020 at 1:16
  • $\begingroup$ excellent answer (+1) $\endgroup$
    – G Cab
    Jul 1, 2020 at 10:59
  • $\begingroup$ Thank you for supplying an example. Can you show how to get "the coefficient of x^n of f(x)" (e.g., how did you go from [x^29]f(x)/(1-x) to 56649270689104302470179125877 / 148888471031133469396697088000)? If it makes things easier, you can use fewer dice and smaller N, e.g. (k_6, k_8, k_10, k_12) = (3, 2, 0, 1), N = 3. As you allude to in your answer, I would like to write a small program that can calculate the probability. $\endgroup$
    – imolit
    Jul 3, 2020 at 7:23
  • $\begingroup$ What I did was use the SeriesCoefficient command in Mathematica (or Wolfram Alpha): SeriesCoefficient[(5/6+1/6*x)^5*(5/8 + 2/8*x + 1/8*x^2)^7*(5/10 + 2/10*x + 2/10*x^2 + 1/10*x^3)^11*(5/12 + 2/12*x + 2/12*x^2 + 2/12*x^3 + 1/12*x^4)^13/(1-x), {x, 0, 29}] $\endgroup$
    – Tom Chen
    Jul 3, 2020 at 11:45
1
+100
$\begingroup$

A simple and crude approximation can be obtained by the CLT. Denoting by ($k_6, k_8...$) the amount of (six-,eitght-...) dice, we are interested in

$$ X = \sum_{i=1}^{k_6} X^{(6)}_i +\sum_{i=1}^{k_8} X^{(8)}_i +\sum_{i=1}^{k_{10}} X^{(10)}_i +\sum_{i=1}^{k_{12}} X^{(12)}_i \tag 1 $$

where $X_i^{(j)}$ is the result for a $j-$die. $X_i^{(j)}$ are assumed independent, and the pmf (probability mass function), mean and variance of each one is:

\begin{array}{|c c c|} \hline j & 6 & 8 & 10 & 12 \\ \hline P(X_i=0) & 5/6 & 5/8 & 5/10 & 5/12 \\ \hline P(X_i=1) & 1/6 & 2/8 & 2/10 & 2/10 \\ \hline P(X_i=2) & 0 & 1/8 & 2/10 & 2/10 \\ \hline P(X_i=3) & 0 & 0 & 1/10 & 2/10 \\ \hline P(X_i=4) & 0 & 0 & 0 & 1/10 \\ \hline \text{mean} & 1/6 & 4/8 & 9/10 & 16/12 \\ \hline \text{variance} & 5/36 & 64/64 & 109/100 & 272/144 \\ \hline \end{array}

Then, from the properties of mean and variance of a sum, we can compute the mean and variance:

$$E[X]=k_6 \frac{1}{6} + k_8 \frac{1}{2} + k_{10} \frac{9}{10} + k_{12} \frac{4}{3}$$

$$\sigma_X^2=k_6 \frac{5}{36} + k_8 + k_{10} \frac{109}{100} + k_{12} \frac{17}{9}$$

All the above is exact. But this is not enough to compute $P(X\ge 30)$.

The approximation consists in assuming $X$ follows a normal distribution with that mean and variance, and compute the desired probability with the gaussian integral.

This approximation can be expected to be good for large number of dice, and $n$ not too low or too high (that is, not too far from the mean), because of the CLT.

Then, we assume that $Z = \frac{X-E[X]}{\sqrt{\sigma_X^2}}$ can be approximated by a standard normal distribution. Denoting by $\Phi(z)=\int_{-\infty}^z \phi(u) \, du $ the cumulative distribution function, our desired probability can be approximated thus:

$$P(X \ge x) \approx 1-\Phi\left(\frac{x-E[X]}{\sqrt{\sigma_X^2}}\right)$$

Actually, because we are approximating a discrete random variable, it makes much sense to add a continuity correction, so

$$P(X \ge x) \approx 1- \Phi\left(\frac{x-\frac12 - E[X]}{\sqrt{\sigma_X^2}}\right)$$

Taking the example in Tom Chen's answer, $(k_6, k_8, k_{10}, k_{12}) = (5, 7, 11, 13)$ we get $E[X]=31.566,$ $\sigma_X^2=40.74$, hence the approximation gives

$$ P(X \ge 30) \approx 1-\Phi\left(\frac{29.5-31.566}{\sqrt{40.74}}\right)=0.62695\cdots $$

... not far from the true value ($0.6195187559065025$).

Added: since you asked for something better than run a simulation, here's a simple Python program to compute the probability numerically (exactly), by doing the convolutions.

# convolution of two pmf, starting at zero
def conv(p1, p2):
    n1 = len(p1)
    n2 = len(p2)
    res = [0] * (n1+n2-1)
    for i in range(0, len(res)):
        ac = 0
        for j1 in range(0,len(p1)):
            j2 = i - j1
            if j2 >=0 and j2 < len(p2):
                ac += p2[j2] * p1[j1]
        res[i] = ac
    return res

p6 = [5/6.0, 1/6.0]
p8 = [5/8.0, 2/8.0, 1/8.0]
p10 = [5/10.0, 2/10.0, 2/10.0, 1/10.0]
p12 = [5/12.0, 2/12.0, 2/12.0, 2/12.0, 1/12.0]

def compute(k6,k8,k10,k12):
    global p6,p8,p10, p12
    p = [1]
    for _ in range(0, k6):
        p = conv(p,p6)
    for _ in range(0, k8):
        p = conv(p,p8)
    for _ in range(0, k10):
        p = conv(p,p10)
    for _ in range(0, k12):
        p = conv(p,p12)
    return p    

def probgt(p, n):
    return sum ( p[n:])

p = compute(5,7,11,13)
prob = probgt(p,30)
print(prob)

https://ideone.com/Fw2yPg

This computation is not very different to what one would need to extract the $n$ coefficient in the generating function, as in Tom Chen's nice answer.

Here's a comparison of the exact pmf vs the CLT approximation

enter image description here

$\endgroup$
3
  • $\begingroup$ Wow. Pragmatically, the numerical solution is exactly what I needed. Thanks! Have a bounty. However, the answer seems a bit hastily written (did you mean 'variance' on the second row on your table? should it really be $k_{12} \frac{9}{10}$?), and glosses over some details which makes it hard for me to follow (how did you calculate the means and variances? where does '29.5' come from?). $\endgroup$
    – imolit
    Jul 5, 2020 at 2:00
  • $\begingroup$ It might be obvious to trained mathematicians, but I would like to know why/how CLT, Convolution of PMF and Gaussian integrals are applicable to solve the problem and leads to $\Phi\left(\cdots\right)$, so I think it would be remiss of me to accept this as an answer. Thanks for introducing me to the concepts, though; I have some reading up to do, I think! $\endgroup$
    – imolit
    Jul 5, 2020 at 2:02
  • $\begingroup$ Sorry for the errors, I'm fixing them and adding some detail. $\endgroup$
    – leonbloy
    Jul 5, 2020 at 15:24
1
$\begingroup$

A straightforward combinatorial answer.

I assume that all dices are fair, that is any side of any $d_i$ has a probability $1/i$ to be dropped after a roll.

Let for any $i$ and any non-negative integer $k$, $P_i(k)$ be a probability to have exactly $k$ successes. For instance $P_8(0)=5/8$, $P_8(1)=1/4$, $P_8(2)=1/8$, and $P_8(k)=0$ otherwise.

It follows that if we have $i$ fixed and have $n$ instances of a dice $d_i$ then for each non-negative integer $k$ a probability $P_i(k,n)$ to have exactly $k$ successes is $$\sum_{k_1+k_2+\dots k_{n}=k\hskip5pt} \prod_{j=1}^{n} P_i(k_j).$$ In particular, $P_i(k,n)=0$ iff $$(i=6 \wedge k>n) \vee (i=8 \wedge k>2n) \vee (i=10 \wedge k>3n) \vee (i=12 \wedge k>4n).$$ In particular, if $n=0$ then $P_i(0,0)=1$ and $P_i(k,0)=0$ for each $k>0$.

If $n>1$ then probability $P_i(k,n)$ can also be calculated recurrently by a formula $$P_i(k,n)=\sum_{k_1+k_2=k} P_i(k_1)P_i(k_2,n-1).$$

In special cases an expression for $P_i(k,n)$ can be simplified. For instance, $P_6(k,n)={n\choose k} 5^{n-k}6^{-n}$.

Finally, if we have $i$ fixed and have $n_i$ instances of a dice $d_i$ for each $i$, for each non-negative integer $k$ a probability $P(k)$ to have at least $k$ successes is

$$\sum_{k_1+k_2+k_3+k_4\ge k} P_6(k_1,n_1) P_8(k_2,n_2) P_{10}(k_3,n_3)P_{12}(k_4,n_4).$$

In particular, $P(k)=0$ iff $k>n(6)+2n(8)+3n(10)+4n(12)$.

$\endgroup$
5
  • 1
    $\begingroup$ I might misunderstand something, but it seems to me that e.g., P_8 will affect the sum even if I don't have any d_8 when rolling my dice, since P_8 only returns 5/8, 1/4, 1/8 or 0 (but never 1). Can you provide a simple example of how you would use the formulas above to arrive at an answer? $\endgroup$
    – imolit
    Jul 3, 2020 at 7:31
  • $\begingroup$ @imolit I missed $n_i$’s in the sum, sorry. Thanks for noticing. I fixed this issue. $\endgroup$ Jul 3, 2020 at 8:18
  • $\begingroup$ So I'm having some trouble with your second formula. $P_6(1, 2) \approx 0.306$, but applying the formula I get $P_6(1, 2) = P_6(1) P_6(0, 1) + P_6(0) P_6(1, 1) = P_6(1) P_6(0) P(0, 0) + P_6(0) *(P_6(1) P_6(0, 0) + P_6(0) P_6(1, 0)) = P_6(1) P_6(0) + P_6(0) P_6(1) = 1/6 * 5/6 + 5/6 * 1/6 = 10 / 36 \approx 0.278$ Am I using it incorrectly? $\endgroup$
    – imolit
    Jul 4, 2020 at 1:16
  • 1
    $\begingroup$ For context, I like this answer because it shows how the problem can be solved with a general purpose programming language (since it doesn't depend on using a proprietary command to find coefficients), but I cannot verify that the solution works in practice. If you could demonstrate with a simple example how/that it works, I would give you the bounty and mark this as the accepted answer. $\endgroup$
    – imolit
    Jul 4, 2020 at 13:33
  • $\begingroup$ @imolit Since $P_6(k,n)={n\choose k} 5^{n-k}6^{-n}$ (I fixed this in my answer, sorry again), we have $P_6(1,2)= {2\choose 1} 5^{1}6^{-2}=\frac {10}{36}$. Indeed, rolling two d6, we have $36$ different outcomes. Ten of them, when a dropped side of one dice is $6$, and the dropped side of the other side is from $1$ to $5$, constitute the cases with exactly one success. So the results which you calculated according to my formulae is correct. Sorry for the delay with the answer. $\endgroup$ Jul 5, 2020 at 4:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .