Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

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

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.