Multinomial distribution Created 2026-09-24 Updated 2026-10-14
A multinomial distribution describes category counts from independent trials, each choosing exactly one of categories with the same probabilities . Require to be an integer, , and . If counts the trials in category , then and
The are integers, and the mass is zero for other count patterns. A category with has count zero almost surely, with in this formula. For a specified ordered trial sequence, independence gives the product of numbers ; the multinomial coefficient counts the different sequences with that same count pattern.
For four trials with category probabilities , the count pattern can occur in orders, each of probability . Thus its total probability is . This is a constructed independent-trial example, distinct from drawing four objects without replacement from a ten-object population of composition , where the multivariate hypergeometric distribution gives .
Figure 1.
Three category counts from four independent trials: every point fixes the third count through the total
. Details.
The diagram shows all fifteen possible count patterns. Coordinates determine ; the triangle is a constraint on integer counts, not a continuous probability density. The mode is , where the probability mass function is largest, but the expected values are not a possible count pattern.
Each single count has a binomial distribution, because recording category versus all other categories reduces every trial to a Bernoulli trial. Consequently,
These statements about the joint count model are summarized in Aditya Guntuboyina's lecture notes.[ref]
Independent trials do not make the resulting counts independent random variables. Within one trial the indicator random variables for two distinct categories cannot both equal one, so their product is zero and their covariance is . Summing over independent trials gives . In the four-trial example, the variances are and the pairwise covariances are . Knowing that all four trials were in the first category fixes the other two counts at zero.
The attraction is that one formula describes any fixed-total list of category counts while preserving the constraint that they add up to . It underlies multinomial likelihood calculations and uniform balls-in-bins allocation. The multinomial aggregation rule lets us merge categories without leaving this family of probability distributions. Allowing independent category counts with an unfixed total instead leads to a different model, related through Poisson-multinomial conditioning.
For each of the balls, let be the indicator random variable that ball survives the round of uniform balls-in-bins allocation. Condition on its chosen bin. Each of the other balls avoids that bin with probability , independently, so the probability that ball is served is . Hence, for ,
We used linearity of expectation to sum the indicator random variables; their mutual independence is unnecessary. For or , the next count is zero. This states the boundary cases without an ambiguous when .
For any fixed bin, each ball supplies an independent Bernoulli distribution indicator with success probability . Summing the indicator variables gives
The full occupancy vector has a multinomial distribution, the basic uniform balls-in-bins allocation. Distinct bin counts are not independent when and . To see this, write . For the same ball, if , while indicators from distinct balls are independent. Their covariance is therefore
With no balls the counts are deterministic; with one bin there are no distinct bin pairs. These degenerate cases do not contradict the conclusion.
Poisson limit for occupancy fractions Created 2026-10-06 Updated 2026-11-05
In a uniform balls-in-bins allocation with and , a fixed bin count has convergence in distribution to a Poisson distribution variable of mean by the Poisson limit theorem. If counts bins containing exactly balls, symmetry and the linearity of expectation give for each fixed . In particular the expected empty fraction tends to , and the expected fraction with at least two balls tends to . These are statements about expectations; convergence of the random fractions requires an additional argument.
Repeated singleton-removal allocation Created 2026-10-31 Updated 2026-11-05
Fix bins. In repeated uniform balls-in-bins allocation, throw each remaining ball independently into those same bins, remove every ball that is alone in its bin, and repeat with the survivors. Let be the number remaining before round .
Conditional on , a specified ball is alone with probability . Its survival probability is therefore , so linearity of expectation gives
For or the next count is zero. Here denotes the fixed bin count, not the current number of balls; confusing those two quantities changes the process.
The survival indicator random variables are generally dependent. For two initial balls and two bins, they survive together exactly when they choose the same bin, of probability each round. Hence and for . In particular, replacing the conditional formula by the same nonlinear function of would not be justified by linearity of expectation.