Beta Limits for Two-Color Pólya Urns

The Red Proportion in a Reinforced Urn

In a two-color Pólya urn, each draw is followed by returning the drawn ball and adding another ball of the same color. The reinforcement makes future draws depend on past outcomes, but the proportion of red balls has a special property: it is a martingale. Its eventual value is random, and its distribution records the lasting effect of early draws. We will identify that distribution exactly.

Fix positive integers \(a\) and \(b\). Start with \(a\) red balls and \(b\) blue balls, and let \(c=a+b\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \(Y_n\) be the color drawn at draw \(n\), with \(Y_n=1\) for red and \(Y_n=0\) for blue. Define \(R_n=\sum_{k=1}^nY_k\), with \(R_0=0\), and let \(\mathcal{F}_n=\sigma(Y_1,\ldots,Y_n)\), where \(\mathcal{F}_0\) is the trivial sigma-field. The urn has \(a+R_n\) red balls and \(c+n\) balls in total after \(n\) draws.

Conditionally on \(\mathcal{F}_n\), the next draw is red with probability \(X_n\). Consequently, the expected next red proportion equals the current one. This observation gives convergence, while exact probabilities for finite draw sequences will identify the law of the limit.

Martingale Convergence and Finite-Sample Probabilities

First verify the martingale property. Since \(R_{n+1}=R_n+Y_{n+1}\) and \(\mathbb{E}[Y_{n+1}\mid\mathcal{F}_n]=X_n\),

Each \(X_n\) is \(\mathcal{F}_n\)-measurable and lies in \([0,1]\), so it is integrable. Thus it is a martingale. The standard martingale convergence theorem says that a nonnegative martingale with uniformly bounded expectations converges almost surely to a finite limit. Here \(0\le X_n\le1\) and \(\mathbb{E}X_n=\mathbb{E}X_0=a/c\), so the theorem applies. Also, bounded convergence gives \(\mathbb{E}X_\infty=\lim_n\mathbb{E}X_n=a/c\).

To identify more than the mean, consider a specified ordered sequence of \(n\) draws containing \(r\) reds and \(n-r\) blues. Its probability is

Indeed, the red draws contribute the successive factors \(a,a+1,\ldots,a+r-1\); the blue draws contribute \(b,b+1,\ldots,b+n-r-1\). Regardless of their order, the total-ball denominators are \(c,c+1,\ldots,c+n-1\). The probability therefore depends only on the number of each color, not their positions. In particular, the draw sequence is exchangeable: permuting its first \(n\) positions does not change the probability of any specified sequence.

For a nonnegative integer \(r\), write \((r)_{\underline{k}}=r(r-1)\cdots(r-k+1)\) for the falling factorial, with \((r)_{\underline{0}}=1\). Fix a positive integer \(k\) and take \(n\ge k\). The quantity \((R_n)_{\underline{k}}/(n)_{\underline{k}}\) is the fraction of ordered selections of \(k\) distinct draw positions that are all red. Averaging this fraction and using exchangeability gives

This is an exact finite-sample identity. To pass from it to ordinary powers, fix \(k\) and compare two sampling schemes from the \(n\) observed positions: sample \(k\) positions independently and uniformly, or sample them uniformly without replacement. The probability of a collision in the independent scheme is at most \(\binom{k}{2}/n\), since each pair of selected positions agrees with probability \(1/n\). Conditional on no collision, the ordered sample is uniform without replacement. Therefore, for every possible value \(R_n=r\), the difference between the probabilities that all selected positions are red in the two schemes is at most \(\binom{k}{2}/n\). Those probabilities are \((r/n)^k\) and \((r)_{\underline{k}}/(n)_{\underline{k}}\), respectively. It follows that their expectations have the same limit, so

For \(n\ge1\), the difference between the observed red fraction and the urn proportion satisfies \(\left|X_n-R_n/n\right|=|an-cR_n|/[n(c+n)]\le(a+c)/(c+n)\), using \(0\le R_n\le n\). For \(x,y\in[0,1]\), factorization gives \(|x^k-y^k|\le k|x-y|\). Hence \(X_n\) has the same limiting \(k\)th moment. Since \(X_n\to X_\infty\) almost surely and \(0\le X_n^k\le1\), bounded convergence yields

Identifying the Beta Distribution

We now check that these are the moments of \(\operatorname{Beta}(a,b)\). The beta integral satisfies \(B(u+1,v)=\frac{u}{u+v}B(u,v)\) for \(u,v>0\). To see this, integrate the derivative of \(x^u(1-x)^v\) over \([0,1]\); its boundary values are zero, so \(uB(u,v+1)=vB(u+1,v)\). Also, splitting \(1=x+(1-x)\) inside the integral gives \(B(u,v)=B(u+1,v)+B(u,v+1)\). Combining these identities gives the stated recurrence. Iterating it \(k\) times shows that a variable \(Z\) with the beta density has

For completeness, moments determine a probability distribution on \([0,1]\). Here is a justification. If two probability measures on \([0,1]\) have the same moments, they integrate every polynomial equally. For a continuous function \(g\), its Bernstein polynomial of degree \(m\) is \(B_mg(x)=\mathbb{E}[g(V/m)]\), where \(V\) has a binomial distribution with parameters \(m,x\). Uniform continuity of \(g\) implies that, given \(\varepsilon>0\), there is \(\delta>0\) such that \(|g(y)-g(x)|<\varepsilon\) when \(|y-x|<\delta\). Writing \(M=\sup_{[0,1]}|g|\), and using \(\operatorname{Var}(V/m)=x(1-x)/m\le1/(4m)\), Chebyshev’s inequality gives, uniformly in \(x\),

Thus polynomials approximate every continuous \(g\) uniformly. The two measures therefore integrate every continuous function equally. Continuous functions determine probability measures on \([0,1]\): continuous functions that decrease from \(1\) to \(0\) over successively smaller intervals around any point approximate interval probabilities, and continuity of probability under monotone limits recovers the distribution function. Hence the measures are equal. Applying this fact to the moments above proves that \(X_\infty\) has the \(\operatorname{Beta}(a,b)\) distribution, completing the theorem.

Interpretation and a Common Denominator Error

The martingale mean remains fixed at \(a/(a+b)\), but this does not mean the limit equals that constant. Rather, the beta law describes variation between urn histories: early draws can shift the proportion, and reinforcement preserves some of that shift. Almost-sure convergence means the proportion along a single indefinitely continued urn path approaches its own random limit. It does not say that different urn paths have the same limit, nor that the limit has to equal the initial proportion.

A common error is to confuse the number of balls with the number of draws when converting a red count to a proportion. In the one-red, one-blue example after three draws, the denominator is \(1+1+3=5\), not \(3\) or \(4\). The incorrect calculation \((1+3/2)/4=5/8\) uses the wrong denominator. The correct calculation is \((1+3/2)/5=(5/2)/5=1/2\), which also agrees with the martingale mean. For sequence probabilities, the denominator factors are \(2,3,4\), whose product is \(24=4!\); using \(1\cdot2\cdot3=3!\) would likewise omit the initial two balls from the first-draw total.

The beta limit result depends on positive initial counts, which ensure the stated urn probabilities and beta parameters are defined. It also uses the one-ball reinforcement rule: changing the reinforcement mechanism changes the finite-sequence probabilities and need not give this beta limit. The proof’s two components serve different purposes: bounded martingale convergence supplies an almost-sure limit, while the exact finite-sample moments identify its distribution.