Deriving the Multinomial Probability Formula

From Trial Sequences to Category Counts

In a categorical experiment, the recorded result may be a count for each category rather than the order in which the outcomes occurred. For example, after several trials we might know that category A occurred twice and category B occurred three times, without retaining whether the outcomes arrived in the order A, B, A, B, B or another order. To find the probability of those counts, we need two ingredients: the probability of one particular ordered sequence and the number of sequences that produce the same counts.

Assume there are \(k\) categories, labelled \(1,\ldots,k\), and \(n\) independent trials. On every trial, category \(j\) occurs with probability \(p_j\), where \(p_j\geq 0\) and \(\sum_{j=1}^k p_j=1\). Write \(X_j\) for the number of trials resulting in category \(j\). The count vector is \((X_1,\ldots,X_k)\). The key feature of this model is that each trial has the same category probabilities and the trials are independent.

For a fixed count vector, every compatible ordered sequence has the same probability. Independence gives that probability by multiplying the category probabilities for its \(n\) trial outcomes. The count probability is then the sum of those equal sequence probabilities over all compatible sequences.

Counting the Compatible Sequences

First determine how many ordered sequences produce counts \((x_1,\ldots,x_k)\). Choose the \(x_1\) trial positions occupied by category 1 from the \(n\) available positions. From the remaining positions, choose \(x_2\) for category 2. Continue until the positions for the final category are determined.

The number of choices at these stages is \(\binom{n}{x_1}\), then \(\binom{n-x_1}{x_2}\), and so on, ending with \(\binom{x_k}{x_k}=1\). Multiplying gives

To see the cancellation, write each binomial coefficient as a factorial ratio. The first numerator is \(n!\); each later numerator is the remaining-position factorial from the previous denominator. These intermediate factorials cancel, leaving \(n!/(x_1!\cdots x_k!)\). Every sequence with the specified counts is counted exactly once: its positions for each category determine one set of choices, and any such set of choices specifies exactly one sequence.

Deriving the Multinomial Probability Formula

Consider any one ordered sequence that contains \(x_j\) occurrences of category \(j\). By independence, its probability is the product of the probabilities of its individual outcomes. Since the same probability \(p_j\) appears once for each occurrence of category \(j\), that product is \(\prod_{j=1}^k p_j^{x_j}\). All sequences with the same counts have this same probability. Their events are disjoint, so adding their probabilities multiplies the probability of one sequence by the number of compatible sequences.

The derivation has two separate parts: the factorial ratio counts how many sequences yield the given counts, while the product of powers gives the probability of each one. Neither part alone is the count probability.

Worked Calculations

Why the Formula Sums to One

A useful check is that the probabilities assigned to all possible count vectors add to one. Every ordered sequence of \(n\) trial outcomes has exactly one count vector, so the events corresponding to the count vectors partition all possible sequences. For completeness, the sum of the formula over the count vectors can also be seen directly.

Indeed, group all ordered sequences according to their count vector. The formula gives the sum of the sequence probabilities within each group. Summing across all groups therefore gives the sum over every ordered sequence. Alternatively, sum first over the category chosen on each trial; distributivity of finite sums gives

The middle sum is over the \(k^n\) ordered sequences \((y_1,\ldots,y_n)\). It equals the sum of the grouped probabilities because each sequence belongs to exactly one count vector. The final equality uses the fact that the category probabilities sum to one.

Common Mistake: Forgetting the Number of Orderings

A frequent error is to calculate the probability of one sequence and report it as the probability of the count event. In the first worked example, the sequence A, B, A, C, B has probability \(0.0045\), but there are 30 sequences with the required counts. The count-event probability is \(30(0.0045)=0.135\). The opposite error is to multiply by \(n!\) without dividing by the factorials of the counts; that counts permutations that exchange identical category labels as if they were different orderings. The correct number is \(n!/(x_1!\cdots x_k!)\).