Random Limits in Classical Urn Schemes

Why Reinforcement Can Preserve Randomness

In a fixed-probability sequence of independent draws, long-run proportions tend to settle near the common draw probability. Reinforcement changes that logic: the next draw probability depends on the urn's current composition, and each early draw changes the probabilities that govern all later draws. A useful way to see the consequence is to track the current proportion and ask what its conditional expectation will be after the next draw.

Consider a classical two-color urn. It begins with \(a\) red balls and \(b\) blue balls, where \(a,b\) are positive integers. At each step, one ball is drawn uniformly, returned to the urn, and joined by one additional ball of the same color. Let \(R_n\) be the number of red balls added in the first \(n\) draws, and let \(M_n\) be the red proportion in the urn after those draws. The total number of balls then is \(s+n\), where \(s=a+b\).

Definition: For this urn, \(M_n=(a+R_n)/(s+n)\) is the red proportion after \(n\) draws. Let \(\mathcal F_n\) denote all the information from the initial urn and the first \(n\) draws. The classical reinforcement rule says that, conditional on \(\mathcal F_n\), the next draw is red with probability \(M_n\).

The initial proportion is \(M_0=a/s\). The question is not merely whether \(M_n\) has an average that remains stable. It is whether the realized proportion approaches a fixed number or a limit that depends on the random sequence of draws.

The Proportion Is a Martingale

Let \(X_{n+1}\) equal 1 if draw \(n+1\) is red and 0 otherwise. The urn adds a red ball precisely when \(X_{n+1}=1\), so

M_{n+1} =\frac{a+R_n+X_{n+1}}{s+n+1} =M_n+\frac{X_{n+1}-M_n}{s+n+1}.

By the urn rule, \(E[X_{n+1}\mid\mathcal F_n]=M_n\). Taking conditional expectations in the update therefore gives

E[M_{n+1}\mid\mathcal F_n] =M_n+\frac{E[X_{n+1}\mid\mathcal F_n]-M_n}{s+n+1} =M_n.

Thus \((M_n,\mathcal F_n)\) is a martingale: at every step, the expected next proportion conditional on the entire observed history equals the current proportion. Also \(0\leq M_n\leq1\), so it is bounded.

Theorem: A bounded martingale converges almost surely and in \(L^1\) to an integrable random variable. Since \(0\leq M_n\leq1\), there is a random variable \(M_\infty\) such that \(M_n\to M_\infty\) almost surely and in \(L^1\). In particular, \(E[M_\infty]=E[M_0]=a/s\).

This theorem establishes convergence, but convergence alone does not say whether the limit is random. A constant limit is also a random variable in the formal sense. To distinguish these possibilities, we need to show that the limiting proportion has positive variance. The following calculation does so without requiring the distribution of \(M_\infty\).

Why the Limit Is Not a Fixed Constant

The change in the proportion is a martingale difference. Given the current urn, \(X_{n+1}\) is Bernoulli with probability \(M_n\), so

E[(M_{n+1}-M_n)^2\mid\mathcal F_n] =\frac{M_n(1-M_n)}{(s+n+1)^2}.

For a complete variance calculation, write \(q_n=E[M_n(1-M_n)]\) and \(p=a/s\). The mean of \(M_n\) remains \(p\). Squaring the update and conditioning on \(\mathcal F_n\) shows that \(E[M_{n+1}^2]=E[M_n^2]+q_n/(s+n+1)^2\). Consequently,

q_{n+1}=p-E[M_{n+1}^2] =q_n\left(1-\frac{1}{(s+n+1)^2}\right).

Starting from \(q_0=p(1-p)=ab/s^2\), the product in this recursion telescopes:

q_n =\frac{ab}{s^2}\prod_{j=1}^{n}\left(1-\frac{1}{(s+j)^2}\right) =\frac{ab(s+n+1)}{s(s+1)(s+n)}.

Martingale increments at different times have expectation-zero cross-products, so the variance at time \(n\) is the sum of their expected squared sizes. Substituting the expression for \(q_j\) and telescoping the reciprocal terms gives

\begin{aligned} \operatorname{Var}(M_n) &=\sum_{j=0}^{n-1}\frac{q_j}{(s+j+1)^2}\\ &=\frac{ab}{s(s+1)} \sum_{j=0}^{n-1}\frac{1}{(s+j)(s+j+1)}\\ &=\frac{ab}{s(s+1)} \left(\frac{1}{s}-\frac{1}{s+n}\right) =\frac{ab\,n}{s^2(s+1)(s+n)}. \end{aligned}

Because the proportions are bounded and converge almost surely, they also converge in \(L^2\): dominated convergence applies to \((M_n-M_\infty)^2\). Their variances therefore converge to the variance of the limit. Taking \(n\) to infinity in the expression above yields

E[M_\infty]=\frac{a}{s}, \qquad \operatorname{Var}(M_\infty)=\frac{ab}{s^2(s+1)}>0.

The positive variance is the key conclusion. Although the expected limiting red proportion equals the starting red proportion, the realized long-run proportion is not forced to equal that number. The starting composition determines the mean of the limit, not a common value shared by every urn history.

Worked Example: Quantifying the Remaining Variability

Suppose a hypothetical urn starts with \(a=2\) red balls and \(b=3\) blue balls. The urn is run under the replacement-and-reinforcement rule above. Find the mean and variance of the limiting red proportion.

Here \(s=a+b=5\), and the initial red proportion is \(2/5=0.4000\). The limit formulas give

E[M_\infty]=\frac{2}{5}=0.4000, \qquad \operatorname{Var}(M_\infty) =\frac{(2)(3)}{5^2(6)} =\frac{6}{150}=0.04000.

The limiting proportion has standard deviation \(\sqrt{0.04000}=0.2000\), in proportion units. The mean is 0.4000, but the positive variance shows that the limit is not a fixed 0.4000. These two summaries do not specify the full distribution of the limit.

Conditional Expectations Reveal Path Dependence

The martingale identity has a stronger interpretation than preservation of the unconditional mean. For any fixed \(n\), the expected limiting proportion conditional on the history through draw \(n\) is the current proportion:

E[M_\infty\mid\mathcal F_n]=M_n.

To justify the identity, use \(E[M_k\mid\mathcal F_n]=M_n\) for every \(k\geq n\), which follows by repeatedly applying the martingale property. Then let \(k\) tend to infinity. The bounded convergence theorem for conditional expectations applies because \(0\leq M_k\leq1\) and \(M_k\to M_\infty\) almost surely.

So different observed histories can imply different conditional expectations for the final proportion. This is not a claim that the current value predicts the limit without uncertainty: it says the current value is the conditional mean of that limit. Reinforcement makes early histories matter because they shift the proportion that subsequent draws preserve in expectation.

Worked Example: Two Possible First Draws

Start a hypothetical urn with one red and one blue ball. Its initial red proportion is \(M_0=1/2\). After one draw, there are three balls in the urn.

If the first draw is red, the urn has two red and one blue ball, so \(M_1=2/3\). If the first draw is blue, it has one red and two blue balls, so \(M_1=1/3\). Each first-draw outcome has probability \(1/2\), since the initial urn is balanced.

The conditional expectation identity gives

E[M_\infty\mid\text{first draw red}]=\frac{2}{3}, \qquad E[M_\infty\mid\text{first draw blue}]=\frac{1}{3}.

A constant limit would have the same conditional expectation on both events. These distinct values therefore exhibit path dependence; they do not assert that the limit must equal either \(1/3\) or \(2/3\). Averaging the two conditional expectations gives the unconditional mean \((1/2)(2/3)+(1/2)(1/3)=1/2\), as required.

Worked Example: Updating the Conditional Mean After a History

Return to a hypothetical urn that starts with two red and three blue balls. Suppose that after ten draws, seven have been red and three blue. This history has added seven red balls and three blue balls, so the current composition is nine red and six blue out of fifteen. Its red proportion is

M_{10}=\frac{2+7}{2+3+10}=\frac{9}{15}=0.6000.

Conditional on this history, \(E[M_\infty\mid\mathcal F_{10}]=0.6000\). Before observing the ten draws, the expected limiting proportion was \(2/5=0.4000\). The history has shifted the conditional mean upward, even though the unconditional expectation remains 0.4000 across all possible histories. The value 0.6000 is a conditional expectation, not a guarantee about this urn's eventual proportion.

Comparisons, Diagnostics, and Limits of the Argument

The difference from a fixed-probability model is structural. With independent draws that each have the same red probability \(p\), the sample red fraction converges to \(p\) by the law of large numbers. In the reinforced urn, the probability of the next red draw is \(M_n\), and a draw changes that probability by changing the urn composition. The limiting proportion can therefore vary between realized histories.

Feature	Classical reinforced urn	Independent fixed-probability draws
Probability of next red draw	Current urn proportion \(M_n\)	Same fixed probability \(p\)
Effect of an early draw	Changes the composition and future draw probabilities	Does not change the probability of later draws
Long-run proportion	Almost-sure limit with positive variance when \(a,b>0\)	Converges almost surely to \(p\)

A deterministic target analysis asks whether the allocation fraction approaches a prescribed or dynamically stable value. That is a different question from whether a particular reinforced urn has a martingale proportion. Here the conditional expectation is exactly the current proportion, and the positive limiting variance rules out convergence to one common fixed constant. The martingale argument does not, by itself, describe a Gaussian fluctuation around a target.

The conclusion depends on the stated urn mechanism. It applies because each draw is made uniformly from the current urn, the drawn ball is returned, exactly one same-color ball is added, and both starting counts are positive. If balls are removed, additions depend on a different rule, or draw probabilities are not the current proportions, the displayed update may fail to be a martingale. One must verify the conditional expectation from the actual transition rule rather than transfer the conclusion by analogy.

In practice, check the model's conditional draw probabilities and composition update before invoking martingale convergence. Then check boundedness (here \(M_n\) always lies between zero and one) and assess whether the desired conclusion is convergence, a limit's mean, or its full distribution. The calculation above proves a nondegenerate limit but does not provide its distribution, quantiles, or a finite-sample guarantee that a particular run is close to its eventual value.

Common Mistake

Wrong reasoning: “The expected proportion is always \(a/s\), so every urn must converge to \(a/s\).” This confuses an expectation over possible urn histories with the outcome of one history.
Correction: The martingale property preserves the mean, while the positive limiting variance \(ab/[s^2(s+1)]\) shows that the limit is not constant. Conditional on an observed history, the expected limit is the current proportion, which can differ across histories.
Wrong reasoning: “Convergence to a limit means the limit is deterministic.” Almost-sure convergence only says that a limit exists for almost every path; it does not say all paths have the same limit.
Correction: Establish whether the limit is constant by examining its variability or its conditional expectations. In this urn, both calculations show that the limit retains randomness.

Key takeaway: In the classical two-color reinforcement urn, the red proportion is a bounded martingale, so it converges almost surely. Its limiting mean is the initial red proportion, but its variance is positive when both colors begin in the urn. Reinforcement therefore produces a path-dependent random limit, not a fixed target.

Check Your Understanding

Answer each question, then compare with the solutions below.

For an urn starting with \(a=3\) red and \(b=1\) blue ball, what is the expected limiting red proportion?
In the same urn, is the limiting red proportion constant? Justify using its variance.
An urn starts with two red and two blue balls. After one red draw, what is the conditional expectation of the eventual red proportion?
Why does the martingale convergence theorem apply to the urn proportions?
What model feature distinguishes this urn from independent draws with one fixed red probability?

Solutions. (1) The initial total is \(s=4\), so \(E[M_\infty]=a/s=3/4=0.7500\). (2) Its variance is \(ab/[s^2(s+1)]=(3)(1)/[4^2(5)]=3/80=0.03750\), which is positive; the limit is not constant. (3) After the red draw, the urn has three red and two blue balls, so \(M_1=3/5=0.6000\). The conditional expectation identity gives \(E[M_\infty\mid\mathcal F_1]=0.6000\). (4) The conditional expectation of the next proportion equals the current proportion, making the sequence a martingale, and every proportion lies in \([0,1]\), making it bounded. (5) In the urn, each draw changes the composition and hence the probability of later draws; under the independent fixed-probability model, earlier draws do not change the probability \(p\) of a later red draw.