how can I calculate the probability to get triples or better when throwing n 6-sided dice?

Question

I've been banging my head on a wall with this question. I'm designing a game and would like to implement a loot system inspired by a game called "Vermintide" where players roll a certain number of dice and gain loot according to the result.

I want my players to get rewards depending on the result of the dice. but I need to evaluate the quality of items, and the number of dice they get to throw based on the probability.

Essentially if they get doubles they get a standard item, if they get triples they get a magic item etc...

I heard of the "birthday problem" and "multinomials" but most of what I could find about it seemed to be very particular cases (I found birthday problem for 2 or more but not for 3 or more, which seems much less trivial).

Is there a smart way to go about this problem which I first thought was going to be trivial, and the more I search the more it seems complicated.

Answer 1

The OP is correct in saying that this is a generalization of the Birthday Problem and that it is harder because we are interested in cases where the number of people with the same birthday is greater than two. One approach is by way of exponential generating functions.

Let's take a concrete example. Suppose we want to roll $10$ six-sided dice and find the probability that at least one number comes up $5$ or more times. It seems easier to consider the complementary event, i.e. all numbers come up $4$ or fewer times. There are $6^{10}$ possible sequences of die rolls, all of which we assume are equally likely. We would like to count the number of sequences in which no number comes up more than $4$ times. We generalize the problem a bit and think about a sequence of $n$ die rolls, and let the number of sequences in which no number appears more than $4$ times be $a_n$.

The exponential generating function of $a_n$ is defined to be $$f(x) = \sum_{n=0}^{\infty} \frac{1}{n!} a_n x^n$$ Since each die has $6$ sides and each number appears no more than $4$ times, $$f(x) = \left( \sum_{i=0}^4 \frac{1}{i!} x^i \right)^6$$ The number we want in our problem, $a_{10}$, is $10!$ times the coefficient of $x^{10}$ when $f(x)$ is expanded. I suppose a pencil and paper solution is possible, but I took the easy way out and used a computer algebra system to find that the coefficient of $x^{10}$ is $2177 / 144$. Therefore the number of sequences of $10$ die rolls in which no number appears more than $4$ times is $$a_{10} = 10! \times \frac{2177}{ 144} = 54,860,400$$

So the probability that no number appears more than $4$ times in $10$ rolls is $$p = \frac{a_{10}}{6^{10}} = 0.907291$$ and the probability that at least one number appears $5$ times or more is $$1-p = 0.0927093$$

Answer 2

Hint

You can compute the probability of not getting triple. The number $f_n$ of possibilities of not getting triples in $n$ throws is: $$f_1 = \binom{6}{1}\\ f_2 = \binom{6}{2}2!+\binom{6}{1}\\ f_3=\binom{6}{3}3!+\binom{6}{1}\binom{5}{1}\frac{3!}{2!}\\ f_4=\binom{6}{4}4!+\binom{6}{1}\binom{5}{2}\frac{4!}{2!}+\binom{6}{2}\frac{4!}{2!2!}\\ f_5=\binom{6}{5}5!+\binom{6}{1}\binom{5}{3}\frac{5!}{2!}+\binom{6}{2}\binom{4}{1}\frac{5!}{2!2!}\\ f_6=\binom{6}{6}6!+\binom{6}{1}\binom{5}{4}\frac{6!}{2!}+\binom{6}{2}\binom{4}{2}\frac{6!}{2!2!}+\binom{6}{3}\frac{6!}{2!2!2!}\\ f_7=\binom{6}{1}\frac{7!}{2!}+\binom{6}{2}\binom{4}{3}\frac{7!}{2!2!}+\binom{6}{3}\binom{3}{1}\frac{7!}{2!2!2!}\\ f_8=\binom{6}{2}\frac{8!}{2!2!}+\binom{6}{3}\binom{3}{2}\frac{8!}{2!2!2!}+\binom{6}{4}\frac{8!}{2!2!2!2!}\\ f_9=\binom{6}{3}\frac{9!}{2!2!2!}+\binom{6}{4}\binom{2}{1}\frac{9!}{2!2!2!2!}\\ f_{10} = \binom{6}{4}\frac{10!}{2!2!2!2!}+\binom{6}{5}\frac{10!}{2!2!2!2!2!}\\ f_{11}=\binom{6}{5}\frac{11!}{2!2!2!2!2!}\\ f_{12}=\binom{6}{6}\frac{12!}{2!2!2!2!2!2!}$$ For $k>13$ we have $f_k=0$

The number of all possible throws $\omega_n$ is: $$\omega_n=6^n$$ Now you can compute the probability of not getting triple: $$p_n=\frac{f_n}{\omega_n}$$ and probability of getting triple: $$q_n=1-p_n$$

Answer 3

In what follows I will refer to “pattern” in the dice rolls. For example the pattern AAABC means that three of the dice show the same number and the other two dice are different from the first three and also different from each other. The roll $1 2 2 4 2$ has this pattern, but $1 2 2 1 2$ does not; that has the pattern AAABB, and similarly $2 2 2 2 1$ is not patternAAABC but AAAAB.

There are seven patterns possible with five dice:

AAAAA
AAAAB
AAABB
AAABC

AABBC
AABCD
ABCDE

If you want three of a kind “or better” on five dice, you are interested in the sum of the first four patterns and you want to disregard the other three. What follows is an explanation of how to compute the probability for each pattern.

We will represent the patterns numerically like this: AAABC will be $(2, 0, 1)$ because there are two letters that appear once, no letters that appear twice, and one letter that appears three times. AAABB will be $(0, 1, 1)$ because there are no letters that appear once, one that appears twice, and one that appears three times. AABCD is $(3, 1)$ (we omit the trailing zero) and ABCDE is $(5)$. We'll refer to these numbers as $n_1, n_2, \ldots$. For AAABC, we have $n_1 = 2, n_2 = 0, n_3 = 1$. For five dice, the representations of the seven patterns are:

$$\begin{array}{lrrrrr} & n_1 & n_2 & n_3 & n_4 & n_5 \\ AAAAA & 0 & 0 & 0 & 0 & 1 \\ AAAAB & 1 & 0 & 0 & 1 \\ AAABB & 0 & 1 & 1 \\ AAABC & 2 & 0 & 1 \\ AABBC & 1 & 2 \\ AABCD & 3 & 1 \\ ABCDE & 5 \end{array} $$

Now suppose we're rolling $N$ dice each with $d$ sides. If there are $N$ dice, we should always have $\sum i\cdot n_i = N$. We'll also take $k=\sum n_i$; this is just the number of different letters in the pattern.

Then it transpires that the number of ways of rolling any pattern is:

$$ \color{maroon}{d\choose k}\color{darkblue}{k!} {\color{darkgreen}{N!}\over \color{purple}{\prod {i!}^{n_i}{n_i}!}} $$

To get the probability, just divide by $d^N$.

I'll work through one example to demonstrate the formula. How many ways are there to roll the pattern AAABC, which is three of a kind, but not counting full house, for of a kind, or five of a kind. For AAABC we have $n_1=2, n_2=0, n_3 = 1$, so $k=n_1+n_2+n_3 = 3$, and the formula gives:

$$\color{maroon}{6\choose 3}\color{darkblue}{3!} {\color{darkgreen}{5!}\over \color{purple}{(1!^2\cdot2!)(2!^0\cdot0!)(3!^1\cdot1!)}} = \color{maroon}{20}\cdot \color{darkblue}{6}\cdot {\color{darkgreen}{120}\over \color{purple}{2\cdot1\cdot6}} = \mathbf{1200} $$

There are 1200 ways to roll the pattern AAABC, so the probability is $\frac{1200}{6^5} \approx 15.43\%$. Similar calculations for the other three patterns of interest give:

$$\begin{array}{lrrl} A A A B C & 1200 & 15.43 & \% \\ A A A B B & 300 & 3.86 \\ A A A A B & 150 & 1.93 \\ A A A A A & 6 & 0.08 \\ \hline \text{Total} & 1656 & 21.30 & \% \end{array} $$

So you can expect to get three of a kind or better around one time in five.

(By far the most common pattern is the single pair AABCD, which occurs almost half the time.)

I explained the formula in more detail in a blog post. This page tabulates the probabilities for every pattern of up to 12 dice. You program that generated these tables is available online: the URL

    https://perl.plover.com/misc/enumeration/tabulate-dice.cgi?N=7&S=11

generates a table for seven dice each with 11 sides. You can adjust the 7 and 11 to suit yourself. Related materials, including program source code, are available also.

Answer 4

If I understand your problem correctly, you're looking for a generalization of the binomial distribution to $n > 2$ where $n$ is the number of possible classes. The term for this is a multinomial distribution.

We can view a $n = 2$ side analog of a dice as a coin. The probability of a single outcome is a Bernoulli distribution (e.g. $\Pr(H)$). The probability of multiple outcomes is a Binomial distribution (e.g. $\Pr(HT)$).

For $n > 2$, the probability of a single outcome is a Categorical distribution (e.g. $\Pr(1)$). The probability of multiple outcomes is a Multinomial distribution (e.g. $\Pr(1126)$).

Remember that a multinomial distribution will only tell you the distribution of, say 5 of the rolls being $1$. So if you're looking for pairs or triplets regardless of the class -- whether its 1 or 2, you don't care -- you have to multiply your probability (if its a fair dice) or construct a sum in the case the dice is not fair.