Pólya Urn Proportions as Martingales

Why an Urn Proportion Can Be a Martingale

In a two-color Pólya urn, a ball is drawn and returned to the urn together with additional balls of the same color. The urn’s composition changes randomly, so its red-ball proportion usually changes from one draw to the next. With the same number of balls added after either color is drawn, however, the next proportion has conditional expectation equal to the current one. That is precisely the martingale property: although individual outcomes move the proportion up or down, their conditional average does not favor either direction.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Initially the urn contains \(a\) red balls and \(b\) blue balls, where \(a,b\) are nonnegative integers and \(a+b>0\). After each draw, return the drawn ball and add \(c\) balls of its color, where \(c\) is a fixed positive integer. Let \(R_n\) and \(B_n\) be the red and blue counts after \(n\) draws, and let \(Z_n=(R_n,B_n)\). The count process has state space \(S=\{(a+cr,b+cs):r,s\in\mathbb{N}_0,\ r+s=n\text{ for some }n\geq0\}\). Define the red proportion \(X_n=R_n/(R_n+B_n)\), and let \(\mathcal{F}_n\) be the information generated by the first \(n\) draws. Thus \(X_n\) is measurable with respect to \(\mathcal{F}_n\), and \(0\leq X_n\leq1\).

Let \(T_n=R_n+B_n\). Since each draw adds exactly \(c\) balls to the total, \(T_n=a+b+nc\) is determined by \(n\). Given \(\mathcal{F}_n\), the probability of drawing red next is \(R_n/T_n\), and the probability of drawing blue is \(B_n/T_n\). Both conditional probabilities are defined because \(T_n\geq a+b>0\).

Proof. Fix \(n\geq0\), and condition on the history \(\mathcal{F}_n\). Write \(R=R_n\), \(T=T_n\), and \(p=R/T=X_n\). If the next draw is red, the new proportion is \((R+c)/(T+c)\). If it is blue, the new proportion is \(R/(T+c)\). The conditional probabilities of these two cases are \(p\) and \(1-p\), respectively. Therefore

Here \(T>0\) and \(c>0\), so the divisions are valid. The calculation applies to every possible history, including a history with \(R=0\) or \(R=T\). Since \(X_n\) is adapted and integrable, the defining conditions for a martingale hold. \(\square\)

Worked One-Draw Calculations

Consequences of the Conditional Expectation Identity

The one-step identity gives an equality of unconditional expectations at every fixed time. This is a consequence of the martingale property and the defining averaging rule for conditional expectation, not a claim that the proportion stays fixed on each sample path.

Proof. At \(n=0\), \(X_0=a/(a+b)\) is deterministic, so the equality holds. Suppose \(\mathbb{E}[X_n]=X_0\). Since \(X_n\) is integrable and \(\mathbb{E}[X_{n+1}\mid\mathcal{F}_n]=X_n\), the tower property of conditional expectation gives

Induction proves the equality for all \(n\geq0\). \(\square\)

This proposition concerns the average proportion over repeated realizations of the urn experiment. It does not say that every realized proportion equals its initial value, or that the proportion is independent of the urn’s history. In the first worked example, a red draw changes the proportion from \(2/3\) to \(3/4\), while a blue draw changes it to \(1/2\). Those changes are different, but their conditional average is zero.

Why Equal Reinforcement Matters

The equal-reinforcement assumption is essential to the calculation. To see this, suppose instead that a red draw adds \(\alpha>0\) balls and a blue draw adds \(\beta>0\) balls. If the current counts are \(R\) red and \(B\) blue, with \(T=R+B>0\), the red-draw probability is \(p=R/T\), and the blue-draw probability is \(1-p\). The next total is now different depending on the color drawn.

Proof. Put \(p=R/T\), so \(0<p<1\). After a red draw the next proportion is \((R+\alpha)/(T+\alpha)\); after a blue draw it is \(R/(T+\beta)\). Subtracting the current proportion \(p\) from the conditional expectation gives

Because \(p(1-p)>0\), this difference is zero exactly when \(\alpha/(T+\alpha)=\beta/(T+\beta)\). The denominators are positive, so cross-multiplication gives \(\alpha(T+\beta)=\beta(T+\alpha)\), or \(T(\alpha-\beta)=0\). Since \(T>0\), this is equivalent to \(\alpha=\beta\). Conversely, when \(\alpha=\beta\), the displayed difference is zero, proving both directions. If one color is absent, then \(p\) is \(0\) or \(1\), the proportion remains fixed, and this necessity argument does not apply. \(\square\)

A Common Calculation Error

A frequent mistake is to average the two possible next proportions equally, as though red and blue draws had the same probability. In the first worked example, that incorrect calculation would be \(\tfrac12(3/4)+\tfrac12(1/2)=5/8\). The probabilities are not \(1/2\) and \(1/2\): with \(2\) red balls and \(1\) blue ball, they are \(2/3\) and \(1/3\). Weighting the outcomes by their actual probabilities gives \((2/3)(3/4)+(1/3)(1/2)=2/3\), as required. The conditional expectation must always use the probabilities given the current history.

The main practical lesson is to separate the random outcomes from their conditional weights. For equal reinforcement, both outcomes produce the same total \(T_n+c\), and weighting their red counts by the draw probabilities recovers the current red proportion. This one-step calculation proves the martingale property directly; it does not by itself assert a particular limiting distribution or describe the full distribution of future draws.