Pólya Urn Proportions and Dirichlet Limits

Why the Pólya urn has a random limiting composition

In a classical Pólya urn, each draw reinforces the color just observed: draw a ball, return it, and add one more ball of that color. This feedback makes draws dependent. A color that appears early becomes more common in the urn and is therefore more likely to appear again. Consequently, long-run proportions need not settle at the initial color proportions; they settle at a random vector.

The introductory material on random limits in classical urn schemes establishes the setting in which such random limits arise. Here the focus is the exact distribution of the limit and its connection to the finite-sample count distribution. That connection is useful because it turns an apparently dependent sequence of draws into a familiar probability mixture.

Model and notation

Consider an urn with $K$ colors. Initially, color $i$ has $a_i>0$ units, for $i=1,\ldots,K$, and let $A=\sum_{i=1}^K a_i$. The values $a_i$ may be positive integers (initial ball counts) or positive real numbers (initial masses). At each draw, select a color with probability equal to its current mass divided by the total current mass, then return the drawn unit and add one unit of that color. There is no removal, no change in the reinforcement amount, and no external allocation rule.

Let $N_i(n)$ be the number of times color $i$ has been drawn in the first $n$ draws. The observed draw proportion is $N_i(n)/n$. The urn-composition proportion after those draws is $(a_i+N_i(n))/(A+n)$. These are different at finite $n$, but their difference vanishes as $n$ grows.

Definition: A $K$-dimensional random vector $P=(P_1,\ldots,P_K)$ has a Dirichlet distribution with parameters $(a_1,\ldots,a_K)$, written $P\sim\operatorname{Dirichlet}(a_1,\ldots,a_K)$, if its density on $p_i>0$, $\sum_i p_i=1$, is proportional to $\prod_{i=1}^K p_i^{a_i-1}$. Its normalizing constant is $\Gamma(A)/\prod_i\Gamma(a_i)$. For $K=2$, $P_1$ has a beta distribution with parameters $a_1,a_2$.

The assumptions matter: the reinforcement is exactly one unit after every draw, all initial parameters are positive, and the draw probability is proportional to the current mass. Changing the reinforcement rule or allowing other transitions generally changes the law; the formulas below are not generic properties of every adaptive urn.

Finite draw probabilities reveal the mixture

For a particular ordered sequence of $n$ draws, let $n_i$ be the number of times color $i$ occurs, so $\sum_i n_i=n$. At each step the total mass is the current total, increasing from $A$ by one after every draw. The numerator for each occurrence of color $i$ successively contributes $a_i,a_i+1,\ldots,a_i+n_i-1$. Write $(x)_m=x(x+1)\cdots(x+m-1)$, with $(x)_0=1$. Multiplying the sequential conditional probabilities gives

P(\text{specified ordered sequence}) =\frac{\prod_{i=1}^K (a_i)_{n_i}}{(A)_n}.

This probability depends on the sequence only through its color counts. Thus the draw sequence is exchangeable: reordering a given collection of colors does not change its probability. The same expression also arises by first drawing a latent probability vector $P\sim\operatorname{Dirichlet}(a_1,\ldots,a_K)$, then making conditionally independent draws with color probabilities $P_1,\ldots,P_K$.

Write the conditional sequence probability.
Given $P$, a specified sequence with counts $n_i$ has probability $\prod_i P_i^{n_i}$.

Average over the Dirichlet vector.
The Dirichlet density gives $E[\prod_i P_i^{n_i}]=\frac{\Gamma(A)}{\Gamma(A+n)}\prod_i\frac{\Gamma(a_i+n_i)}{\Gamma(a_i)}$.

Identify the urn probability.
Using $\Gamma(x+m)/\Gamma(x)=(x)_m$, the integrated probability is $\prod_i(a_i)_{n_i}/(A)_n$, exactly the sequential urn probability.

The equality for every finite ordered sequence proves equality of the finite-dimensional distributions of the two processes. In the mixture construction, conditional on $P$, the strong law of large numbers gives $N_i(n)/n\to P_i$ almost surely for every color. Since the two infinite sequences have the same finite-dimensional laws, the classical urn has the same limiting-proportion law.

Theorem: Under the stated classical Pólya urn assumptions, the vector of draw proportions converges almost surely to a random vector $P\sim\operatorname{Dirichlet}(a_1,\ldots,a_K)$. The urn-composition proportions converge to the same vector, because $$ \frac{a_i+N_i(n)}{A+n}-\frac{N_i(n)}{n}\longrightarrow 0 $$ almost surely as $n\to\infty$.

Finite-sample counts: beta-binomial and Dirichlet-multinomial

For two colors, write the initial parameters as $a$ and $b$, and let $K_n$ denote the number of draws of the first color among $n$ draws. There are $\binom{n}{k}$ ordered sequences with $k$ first-color draws, and each has the same probability. Therefore

P(K_n=k)=\binom{n}{k}\frac{(a)_k(b)_{n-k}}{(a+b)_n}, \qquad k=0,\ldots,n.

This is the beta-binomial distribution. Equivalently, draw $P_1\sim\operatorname{Beta}(a,b)$, then draw $K_n\mid P_1\sim\operatorname{Binomial}(n,P_1)$. For $K$ colors, the count vector has the Dirichlet-multinomial probability

P(N_1(n)=n_1,\ldots,N_K(n)=n_K) =\frac{n!}{\prod_i n_i!}\frac{\prod_i(a_i)_{n_i}}{(A)_n}, \qquad \sum_i n_i=n.

The multinomial coefficient counts the possible orderings of the specified color counts. The resulting count law is not generally the multinomial law with fixed probabilities $a_i/A$: mixing over the random $P$ induces extra variability and dependence among draws.

Worked Example: A Two-Color Beta-Binomial Count

Suppose a hypothetical urn begins with $a=2$ red units and $b=3$ blue units, with one unit of reinforcement after every draw. Find the probability of exactly three red draws in four draws.

The assumptions match the classical model: both initial masses are positive, the draw probability is proportional to current mass, and the drawn unit is returned with one additional unit of its color. The beta-binomial formula gives

P(K_4=3)=\binom{4}{3}\frac{(2)_3(3)_1}{(5)_4} =4\frac{(2)(3)(4)(3)}{(5)(6)(7)(8)} =\frac{288}{1680} =\frac{6}{35}\approx 0.1714.

Thus the probability of exactly three red draws is about $17.14\%$. For comparison, the limiting red proportion has a $\operatorname{Beta}(2,3)$ distribution, with mean $2/5=0.4$. The four-draw count is not binomial with fixed success probability $0.4$: the urn’s reinforcement makes the count distribution more dispersed.

Worked Example: A Three-Color Limiting Distribution

Consider a hypothetical urn with initial masses $(1,2,3)$ for colors 1, 2, and 3. The limiting vector is $P\sim\operatorname{Dirichlet}(1,2,3)$, and $A=6$. The Dirichlet mean, variance, and covariance formulas are

E[P_i]=\frac{a_i}{A},\qquad \operatorname{Var}(P_i)=\frac{a_i(A-a_i)}{A^2(A+1)},\qquad \operatorname{Cov}(P_i,P_j)=-\frac{a_i a_j}{A^2(A+1)}\quad(i\ne j).

Substituting the parameters, the mean limiting proportions are $(1/6,2/6,3/6)=(0.1667,0.3333,0.5000)$. For color 1,

\operatorname{Var}(P_1)=\frac{1(6-1)}{6^2(7)} =\frac{5}{252}\approx 0.01984.

For colors 1 and 2, the covariance is

\operatorname{Cov}(P_1,P_2) =-\frac{(1)(2)}{6^2(7)} =-\frac{1}{126}\approx -0.007937.

The limiting proportions sum to one, so an unusually large share for one color must be offset by smaller shares for the others; the negative covariance is consistent with that constraint. The means equal the initial mass fractions, but an individual urn’s limiting vector is not fixed at those fractions.

Worked Example: Two Draws and Reinforcement

Use the same hypothetical three-color parameters $(1,2,3)$. Find the probability that after two draws there is one draw of color 1 and one of color 2, in either order. The Dirichlet-multinomial formula gives

P(N_1(2)=1,N_2(2)=1,N_3(2)=0) =\frac{2!}{1!1!0!}\frac{(1)_1(2)_1(3)_0}{(6)_2} =2\frac{(1)(2)(1)}{(6)(7)} =\frac{2}{21}\approx 0.09524.

The same value follows by adding the two possible orders: color 1 then color 2 has probability $(1/6)(2/7)=1/21$, and color 2 then color 1 has probability $(2/6)(1/7)=1/21$. If instead each draw used fixed probabilities $(1/6,2/6,3/6)$ independently, the corresponding probability would be $2(1/6)(2/6)=1/9$, which is different. The urn’s predictive probabilities change after the first draw.

Moments and interpretation of the limit

The Dirichlet moment formulas follow from the same integrated probability identity. In particular, $E[P_i]=a_i/A$, and for distinct colors $i,j$, $\operatorname{Cov}(P_i,P_j)<0$. The limiting vector’s mean is therefore the initial composition, but its realized value remains random. A large number of draws reduces the difference between the observed proportion and the urn’s latent limiting proportion; it does not force that latent proportion to equal its mean.

The finite-sample count variance makes the distinction from fixed-probability sampling explicit. In the two-color case,

E[K_n]=n\frac{a}{A},\qquad \operatorname{Var}(K_n)=n\frac{ab(A+n)}{A^2(A+1)}.

A binomial count with fixed probability $a/A$ has variance $n ab/A^2$. The beta-binomial variance is larger by the factor $(A+n)/(A+1)$, which exceeds one for $n>1$. The additional variation reflects uncertainty in the random limiting probability, not measurement error in a fixed probability.

Diagnostics, alternatives, and limitations

When deciding whether these formulas apply, check the mechanism rather than just the appearance of the data. The classical model requires constant reinforcement of one unit to the color just drawn, with selection proportional to current mass. Useful checks include:

Confirm that the total mass after $n$ draws is exactly $A+n$, and that the probability of the next color is its current mass divided by that total.
Check whether the observed mechanism is exchangeable. In the classical urn, the probability of a specified sequence depends on its color counts, not their order.
Compare observed count variability with the multinomial benchmark. Excess variability can be compatible with reinforcement, but it does not establish that a Pólya urn generated the data.
Verify that every initial parameter is positive. A zero initial mass is not covered by the stated density and may make that color impossible to draw under the ordinary rule.

A common mistake is to reason that reinforcement averages out, so the proportions must converge to the initial fractions. The initial fractions are the expectations of the limiting proportions, not their almost-sure values. For example, with initial parameters $(2,3)$, the limiting red fraction is beta distributed, not identically $0.4$.

The main alternative for finite counts is a multinomial model with fixed probabilities. It assumes independent draws with the same color probabilities on every trial; the Pólya urn instead has dependent draws and a random probability vector in its mixture representation. Sampling without replacement is also distinct: it decreases the available mass of a selected color rather than reinforcing it. These alternatives are not interchangeable merely because each produces a vector of color counts.

The Dirichlet mixture is an exact description of this classical urn, not a universal representation for adaptive allocation. It assumes the specified reinforcement mechanism and does not by itself describe response-dependent allocation, changing reinforcement, or additional constraints. In applications, a fitted beta-binomial or Dirichlet-multinomial pattern should therefore be interpreted in light of the actual allocation process.

Key takeaway: The classical Pólya urn has an exact finite-sample Dirichlet-mixture representation. Its draw proportions converge almost surely to a Dirichlet-distributed random vector, while its finite color counts follow beta-binomial or Dirichlet-multinomial laws.

Check Your Understanding

Answer each question using the classical urn assumptions stated above. Brief solutions are included for checking.

For a two-color urn with initial masses $a=1$ and $b=1$, what is the distribution of the limiting proportion of the first color?
For parameters $(2,4)$, compute the probability that both of the first two draws are of the first color.
For a Dirichlet limit with parameters $(2,3,5)$, give the mean limiting proportion of the second color.
In one sentence, explain why the beta-binomial count is generally more variable than a binomial count with probability $a/(a+b)$.

Solutions. (1) The first-color limit has a $\operatorname{Beta}(1,1)$ distribution, uniform on $(0,1)$. (2) The ordered-sequence probability is $(2)_2/(6)_2=(2)(3)/[(6)(7)]=1/7\approx0.1429$. (3) The mean is $3/(2+3+5)=0.3000$. (4) The beta-binomial mixes binomial counts over a random success probability, adding variation from that probability’s uncertainty.