Multinomial probability

A basic problem first solved by Jakob Bernoulli is to find the probability of obtaining exactly i red balls in the experiment of drawing n times at random with replacement from an urn containing b black and r red balls. To draw at random means that, on a single draw, each of the r + b balls is equally likely to be drawn and, since each ball is replaced before the next draw, there are (r + b) ×⋯× (r + b) = (r + b)ⁿ possible outcomes to the experiment. Of these possible outcomes, the number that is favourable to obtaining i red balls and n − i black balls in any one particular order is

The number of possible orders in which i red balls and n − i black balls can be drawn from the urn is the binomial coefficient

where k! = k × (k − 1) ×⋯× 2 × 1 for positive integers k, and 0! = 1. Hence, the probability in question, which equals the number of favourable outcomes divided by the number of possible outcomes, is given by the binomial distribution

where p = r/(r + b) and q = b/(r + b) = 1 − p.
For example, suppose r = 2b and n = 4. According to equation (3), the probability of “exactly two red balls” is

In this case the

possible outcomes are easily enumerated: (rrbb), (rbrb), (brrb), (rbbr), (brbr), (bbrr).
(For a derivation of equation (2), observe that in order to draw exactly i red balls in n draws one must either draw i red balls in the first n − 1 draws and a black ball on the nth draw or draw i − 1 red balls in the first n − 1 draws followed by the ith red ball on the nth draw. Hence,

from which equation (2) can be verified by induction on n.)
Two related examples are (i) drawing without replacement from an urn containing r red and b black balls and (ii) drawing with or without replacement from an urn containing balls of s different colours. If n balls are drawn without replacement from an urn containing r red and b black balls, the number of possible outcomes is

of which the number favourable to drawing i red and n − i black balls is

Hence, the probability of drawing exactly i red balls in n draws is the ratio

If an urn contains balls of s different colours in the ratios p₁:p₂:…:p_s, where p₁ +⋯+ p_s = 1 and if n balls are drawn with replacement, the probability of obtaining i₁ balls of the first colour, i₂ balls of the second colour, and so on is the multinomial probability

The evaluation of equation (3) with pencil and paper grows increasingly difficult with increasing n. It is even more difficult to evaluate related cumulative probabilities—for example the probability of obtaining “at most j red balls” in the n draws, which can be expressed as the sum of equation (3) for i = 0, 1,…, j. The problem of approximate computation of probabilities that are known in principle is a recurrent theme throughout the history of probability theory and will be discussed in more detail below.