Finite-Sample Variability in Pólya Urns

Reinforcement and Finite-Sample Variability

In a two-color Pólya urn, each draw is returned to the urn along with one additional ball of the same color. A red draw therefore makes future red draws more likely, while a blue draw makes future blue draws more likely. The draw indicators are not independent, even though each draw has the same marginal probability of being red. This dependence has an exact finite-sample effect on the variability of the urn’s color proportion.

Consider a probability space \((\Omega,\mathcal{F},\mathbb{P})\) carrying the successive draws. The urn starts with \(a\) red balls and \(b\) blue balls, where \(a,b\) are positive integers, and one ball of the drawn color is added after each draw. Write \(s=a+b\). Let \(I_k=1\) if draw \(k\) is red and \(I_k=0\) if it is blue, and let \(\mathcal{F}_n=\sigma(I_1,\ldots,I_n)\), with \(\mathcal{F}_0\) containing only the initial information. The number of red balls after \(n\) draws is \(a+\sum_{k=1}^n I_k\), and the red proportion is

Given the first \(n\) draws, the urn has \(a+\sum_{k=1}^n I_k\) red balls out of \(s+n\) total balls. Thus the conditional probability that draw \(n+1\) is red is \(Z_n\). In particular, the probability is well-defined for every history because \(s+n>0\).

The proportion \(Z_n\) is a martingale: its conditional expected value at the next draw is its current value. But this fact alone does not make the draws independent. We will establish the finite-sample variance by first identifying their dependence exactly.

Exchangeability and Pairwise Dependence

For a particular sequence of \(m\) draws containing \(r\) reds and \(m-r\) blues, its probability can be computed by multiplying the successive conditional probabilities. The red factors contribute \(a(a+1)\cdots(a+r-1)\), the blue factors contribute \(b(b+1)\cdots(b+m-r-1)\), and the denominators are \(s(s+1)\cdots(s+m-1)\). Empty products are defined to be \(1\). Therefore, regardless of the order of the colors, the probability of that sequence is

This expression depends on the sequence only through its number of red and blue draws. Permuting the draw indices preserves that count and the probability, proving exchangeability. Since the first draw is red with probability \(a/s\), exchangeability also gives \(\mathbb{E}[I_k]=a/s\) for every \(k\).

Proof. Exchangeability lets us calculate the joint probability for any two distinct indices using the first two draws. The probability that both are red is \(\mathbb{P}(I_1=1,I_2=1)=\frac{a}{s}\frac{a+1}{s+1}=\frac{a(a+1)}{s(s+1)}\). The marginal red probability is \(p=a/s\), so \[ \operatorname{Cov}(I_i,I_j) =\mathbb{E}[I_iI_j]-\mathbb{E}[I_i]\mathbb{E}[I_j] =\frac{a(a+1)}{s(s+1)}-\frac{a^2}{s^2} =\frac{a((a+1)s-a(s+1))}{s^2(s+1)} =\frac{a(s-a)}{s^2(s+1)} =\frac{ab}{s^2(s+1)}. \] For an indicator with success probability \(a/s\), its variance is \((a/s)(1-a/s)=ab/s^2\). The correlation is covariance divided by the product of the two standard deviations, which here is the variance \(ab/s^2\); hence it equals \(1/(s+1)\). The assumptions \(a,b>0\) ensure this variance is positive, so the correlation is defined. \(\square\)

Variance of the Red Proportion

The red count contributed by the draws is \(K_n=\sum_{k=1}^n I_k\), so \(Z_n=(a+K_n)/(s+n)\). Since the initial count \(a\) and the denominator are nonrandom, the variance of \(Z_n\) is the variance of \(K_n\) divided by \((s+n)^2\). The exact result follows by including both the individual indicator variances and the covariances between distinct draws.

Proof. By linearity of expectation and the marginal probability already established, \(\mathbb{E}[K_n]=\sum_{k=1}^n\mathbb{E}[I_k]=na/s\). Consequently, \[ \mathbb{E}[Z_n]=\frac{a+na/s}{s+n} =\frac{a(s+n)/s}{s+n} =\frac{a}{s}. \] To compute the variance for \(n\geq1\), expand the variance of the sum. There are \(n\) individual variances and \(n(n-1)/2\) distinct pairs, each appearing twice in the expansion. Thus \[ \begin{aligned} \operatorname{Var}(K_n) &=n\frac{ab}{s^2}+n(n-1)\frac{ab}{s^2(s+1)}\\ &=\frac{nab}{s^2}\left(1+\frac{n-1}{s+1}\right)\\ &=\frac{nab}{s^2}\frac{s+n}{s+1}. \end{aligned} \] Since \(Z_n=(a+K_n)/(s+n)\), division by \((s+n)^2\) gives \(\operatorname{Var}(Z_n)=nab/[s^2(s+1)(s+n)]\). At \(n=0\), \(Z_0=a/s\) is constant and has variance zero, as stated. \(\square\)

The same urn proportion also has a martingale interpretation. This verifies that its constant expectation is not a coincidence, while the variance calculation above describes how much its value still fluctuates at a fixed sample size.

Proof. The proportion \(Z_n\) is determined by the first \(n\) draws, so it is \(\mathcal{F}_n\)-measurable; also \(0\leq Z_n\leq1\), so it is integrable. Given \(\mathcal{F}_n\), the next red indicator has conditional expectation \(\mathbb{E}[I_{n+1}\mid\mathcal{F}_n]=Z_n\). Therefore \[ \mathbb{E}[Z_{n+1}\mid\mathcal{F}_n] =\frac{a+\sum_{k=1}^n I_k+\mathbb{E}[I_{n+1}\mid\mathcal{F}_n]}{s+n+1} =\frac{(s+n)Z_n+Z_n}{s+n+1} =Z_n. \] This is the defining conditional-expectation identity for a martingale. \(\square\)

Comparison with Independent Bernoulli Sampling

For comparison, suppose instead that \(n\) draws are independent Bernoulli observations with red probability \(p=a/s\), the same marginal probability as for the urn. Their indicators have variance \(p(1-p)=ab/s^2\), but covariance zero for distinct draws. Thus the variance of their red fraction \(K_n/n\) is \(ab/(s^2 n)\). In the urn, the corresponding draw fraction \(K_n/n\) has variance \[ \operatorname{Var}(K_n/n) =\frac{ab}{s^2 n}\frac{s+n}{s+1}. \] For \(n>1\), the factor \((s+n)/(s+1)\) is greater than one; for \(n=1\), it equals one. The urn’s draw fraction is therefore more variable than the independent-sampling fraction at every sample size greater than one.

One can make the same comparison for the urn proportion \(Z_n=(a+K_n)/(s+n)\), which includes the initial balls. If independent Bernoulli draws with probability \(a/s\) are used in this same expression, its variance is \(n ab/[s^2(s+n)^2]\). The urn-proportion variance divided by this independent-sampling variance is again \((s+n)/(s+1)\), for \(n\geq1\). The reason is the same in both comparisons: the urn indicators contribute positive pairwise covariances instead of zero covariances.

A Common Independence Pitfall

A tempting but incorrect calculation is to use the correct marginal variance for each urn draw and then treat the indicators as independent. For the urn with \(a=2,b=3,n=4\), this gives \(\operatorname{Var}(K_4)=4(6/25)=24/25\), and therefore \(\operatorname{Var}(Z_4)=(24/25)/81=8/675\). This omits all six distinct pairs and their contribution \(2(6)(1/25)=12/25\). Including it gives \(\operatorname{Var}(K_4)=36/25\), hence \(\operatorname{Var}(Z_4)=4/225\), the correct value. The difference is not a rounding error or a change in marginal red probability; it comes exactly from positive dependence between draws.

The formulas distinguish three related quantities: the red proportion in the entire urn, the fraction of red draws, and the fraction from independent Bernoulli observations. Their denominators differ, so their variances should not be interchanged. In each comparison above, the variance follows from the stated random count and its precise denominator.