Dice: Rolling at least N successes where number of succeses vary by dice value

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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