# Universal algorithm to estimate probability of drawing certain combination of coloured balls

I am writing AI for a board game and would be happy for some guidance in creating the function to calculate probabilities.

So, there's a pool of N coloured balls. Up to 7 colours, the quantity of balls in each colour is given (zero or more).

We are about to draw M balls from there. Question is, what is the probability of drawing certain combination of colours (ie, 3 red, 2 blue and 4 white).

All the quantities in pool and drawn are arbitrary, passed to a function as array.

If that would make the algorithm simpler, it is possible use recursion, ie P = something * P([rest of pool], [rest of drawn balls])

I got as far as this:

N - total number of balls in the pool, quantity of each color is n1, n2, n3, etc. M - total balls drawn. Quantity of each color is m1, m2, m3, etc.

The probability, of course, is a fraction, where the denominator is all the possible combinations of M bals drawn, and numerator is the number of valid combinations we are interested in.

The total number of combinations how M unique balls can be drawn from the pool of N unique balls, can be calculated like this:

$$$$C = \frac{N!}{(N - M)!}$$$$

At the numerator, I have to calculate the product of all $$\frac{n_i!}{(n_i - m_i)!}$$, as this reflects in how many ways each colour can be picked mi times, from the pool where there are ni balls in that colour.

So far, I have this:

$$\frac{\frac{n_1!}{(n_1 - m_1)!}\cdot\frac{n_2!}{(n_2 - m_2)!}\cdot\frac{n_3!}{(n_3 - m_3)!}\cdot\ldots}{\frac{N!}{(N - M)!}}$$

Now, this number has to be multiplied by something, because the balls can come at any order of colours they want. And I am not sure how to solve this.

Next, I will have to calculate the probability of drawing certain combination of M balls, when total Q balls are drawn, but that is even more complex, so I have to solve the first step first.

-

We use your notation. Imagine that we have put identity numbers on all the balls.

There are $\binom{N}{M}$ ways to choose $M$ balls from $N$. Note that the binomial coefficient counts the number of possible "hands" of $M$ balls. Order is irrelevant.

In case you are unfamiliar with binomial coefficients, $\binom{n}{k}$, pronounced, in English, "$n$ choose $k$," is the number of ways to choose $k$ objects from $n$ objects. By definition, $\binom{n}{0}=1$ for all $n$, and $\binom{n}{k}=0$ if $k\gt n$.

It turns out that if $0\le k\le n$, then $\binom{n}{k}=\frac{n!}{k!(n-k)!}$.

Now we turn to our problem. We want to find the number of ways to choose $m_1$ objects of colour $1$, $m_2$ objects of colour $2$, and so on, where $m_1+m_2+\cdots+m_k=M$.

There are $\binom{n_1}{m_1}$ ways to choose $m_1$ objects of colour $1$. For each of these ways, there are $\binom{n_2}{m_2}$ ways to choose $m_2$ objects of colour $2$, and so on. So the total number of ways to choose $m_1$ of colour $1$, $m_2$ of colour $2$, and so on is $\binom{n_1}{m_1}\binom{n_2}{m_2}\cdots \binom{n_k}{m_k}$. Thus the required probability is $$\frac{\binom{n_1}{m_1}\binom{n_2}{m_2}\cdots \binom{n_k}{m_k}}{\binom{N}{M}}.\tag{1}$$

As to efficient ways of computing this, the subject has been studied a fair bit, particularly for the case $k=2$. One minor suggestion is to use the following recurrence: $$\binom{b}{a}=\frac{b}{a}\binom{b-1}{a-1}.$$

Remark: The above analysis is close to the one you produced. The difference is that in Formula $(1)$, your denominator gets divided by $M!$, and your numerator gets divided by $m_1!m_2!\cdots m_k!$, precisely to deal with the order issues that you identified.

-
Wow, thanks for an elaborate explanation! Too bad I have too little reputation to vote it up :) As for the computing, I could use some caching of binomial coefficient results to speed things up. – Passiday Mar 5 '13 at 19:15
You are welcome. There is no point in writing an explanation that is not detailed. – André Nicolas Mar 5 '13 at 19:29
What is your suggestion about how to think about the probability of picking the given set, when drawing q balls, where q is greater than k? My approach is to see the total number of order-indifferent combinations of drawing the remaining q-k balls as a multiplier to the main formula in your solution. But there could possibly be some glitches, because the same combination of M balls would be counted several times - once when treated as the originally drawn set, but then several times as unintentionally created with the help of those additional q-m balls. – Passiday Mar 8 '13 at 8:10