Gaussian Limits for Urns With Subdominant Eigenvalues

Why the Eigenvalue Threshold Matters

A generalized urn changes its composition after every draw: the color drawn affects which balls are added, and the current composition determines the next draw probabilities. The resulting proportions are dependent over time. Their fluctuations therefore reflect both the randomness of each replacement and the way the urn’s composition feeds back into later draws.

The replacement matrix describes this feedback. Its leading eigenvalue sets the overall growth rate, while the other eigenvalues describe how perturbations in different composition directions evolve. When every nonleading eigenvalue is strictly less than half the leading eigenvalue in real part, the composition proportions have a square-root-scale Gaussian limit. This tutorial states that result, derives its covariance, and shows how to check it.

Definition: Consider a balanced $d$-color urn. Write $Z_n$ for its column vector of color counts after $n$ draws, and $P_n=Z_n/(\mathbf{1}^T Z_n)$ for its vector of proportions. On each draw, a ball of color $i$ is selected with probability equal to its current proportion, and a replacement vector $\xi$ is added. Assume the total number added is the same positive constant $\gamma$ on every draw. The replacement matrix $A$ has as its $i$th column the mean replacement vector conditional on drawing color $i$. Thus $\mathbf{1}^T A=\gamma\mathbf{1}^T$. Here $\mathbf{1}$ denotes the vector of ones.

The Gaussian Fluctuation Result

Assume the expected replacement matrix $A$ is irreducible, so its leading eigenvalue $\gamma$ is simple and has a positive right eigenvector. Normalize that eigenvector $v$ so that $\mathbf{1}^T v=1$. In this balanced setting, $v$ is the limiting target proportion vector. Assume also that replacement vectors have finite moments of order $2+\delta$ for some $\delta>0$, and that the urn starts with a fixed, nonzero composition.

For a replacement made when the urn proportions are near $v$, the mean replacement vector is $Av=\gamma v$. Define the covariance of the replacement noise at that limiting composition by averaging over the color drawn and the replacement randomness:

\Gamma=\sum_{i=1}^d v_i\,\mathbb{E}\left[(\xi_i-\gamma v)(\xi_i-\gamma v)^T\right],

where $\xi_i$ has the replacement distribution conditional on drawing color $i$. The term $\gamma v$ is the unconditional mean replacement at the limiting composition. Thus $\Gamma$ accounts for variation both in which color is drawn and in the replacement made for that color. Balance implies $\mathbf{1}^T(\xi_i-\gamma v)=0$, so the noise and its covariance lie in directions that preserve the total proportion.

Theorem: Suppose the balanced urn satisfies the assumptions above and every eigenvalue $\lambda\ne\gamma$ of $A$ satisfies $\operatorname{Re}(\lambda)<\gamma/2$. Then $$ \sqrt{n}(P_n-v)\ \xrightarrow{d}\ N(0,\Sigma), $$ where the covariance is defined on the proportion-preserving subspace $\{x:\mathbf{1}^T x=0\}$ by $$ \Sigma=\frac{1}{\gamma^2}\int_0^\infty e^{(A/\gamma-I/2)t}\,\Gamma\,e^{(A^T/\gamma-I/2)t}\,dt. $$

The strict inequality is the subdominant-eigenvalue condition. On the proportion-preserving subspace, each eigen-direction contracts quickly enough for its accumulated replacement noise to have a finite covariance at the square-root scale. The theorem does not claim a nonsingular covariance: the proportions sum to one, so their fluctuations also sum to zero.

Why This Covariance Appears

The covariance formula can be understood from the one-step proportion update. Ignoring the fixed initial total, the urn total after $n$ draws is approximately $\gamma n$. A replacement changes the proportion vector by its replacement vector minus the current mean composition increment, divided by a total of order $\gamma n$. Conditional on the current proportions, the mean replacement is $AP_n$. Consequently, the first-order drift of $P_n-v$ is governed by $A/\gamma-I$, while the replacement noise is scaled by $1/\gamma$.

For a fluctuation multiplied by $\sqrt n$, the effective drift on the proportion-preserving subspace is $A/\gamma-I/2$: the additional $I/2$ adjustment comes from the square-root normalization. The one-step noise covariance contributes $\Gamma/\gamma^2$. Accumulating these contributions over past draws gives the integral in the theorem. More explicitly, if $F=A/\gamma-I/2$ on that subspace, then the covariance is

\Sigma=\int_0^\infty e^{Ft}\frac{\Gamma}{\gamma^2}e^{F^Tt}\,dt.

The spectral condition makes every eigenvalue of $F$ have negative real part on this subspace. Therefore the matrix exponential decays there, the integral is finite, and differentiating its integrand yields the equivalent Lyapunov equation:

F\Sigma+\Sigma F^T=-\frac{\Gamma}{\gamma^2}.

This equation is often a convenient way to calculate the covariance. The integral also shows its meaning: it is the sum of the noise covariance transported forward by the urn’s linearized dynamics.

Worked Example: A Two-Color Urn With Random Replacements

Consider a hypothetical urn with two colors. A draw adds two balls. If color 1 is drawn, add two balls of color 1 with probability $0.3$, or one ball of each color with probability $0.7$. If color 2 is drawn, use the color-reversed rule. Each replacement adds exactly two balls, so $\gamma=2$, and the replacement matrix is

A= \begin{pmatrix} 1.3&0.7\\ 0.7&1.3 \end{pmatrix}.

The columns sum to 2, and the eigenvalues are $2$ and $0.6$. The leading eigenvector normalized to sum to one is $v=(0.5,0.5)^T$. The nonleading eigenvalue meets the required condition because $0.6<2/2=1$.

At $v$, the mean replacement is $\gamma v=(1,1)^T$. For either color drawn, the replacement differs from this mean by $(1,-1)^T$ with probability $0.3$, and is equal to the mean with probability $0.7$, with signs reversed for the other color. Hence

\Gamma=0.3 \begin{pmatrix} 1&-1\\ -1&1 \end{pmatrix}.

On the contrast direction $(1,-1)^T$, the matrix $A/\gamma-I/2$ has eigenvalue $0.6/2-0.5=-0.2$. The covariance integral on this direction therefore has scalar factor $\int_0^\infty e^{-0.4t}\,dt=2.5$. Including the noise scaling $1/\gamma^2=1/4$, the limiting covariance is

\Sigma=\frac{2.5}{4}\Gamma =0.1875 \begin{pmatrix} 1&-1\\ -1&1 \end{pmatrix}.

Thus the asymptotic variance of $\sqrt n(P_{n,1}-0.5)$ is $0.1875$. The negative covariance between the two proportions is required because they sum to one.

Worked Example: Checking a Three-Color Urn

Suppose a hypothetical three-color urn adds three balls per draw. After drawing color $i$, it adds three balls of color $i$ with probability $0.2$, and one ball of each color with probability $0.8$. Each column of the mean replacement matrix has $1.4$ in the drawn color’s row and $0.8$ in each other row:

A= \begin{pmatrix} 1.4&0.8&0.8\\ 0.8&1.4&0.8\\ 0.8&0.8&1.4 \end{pmatrix}.

The column sums are 3, so $\gamma=3$. The equal-proportion vector $v=(1/3,1/3,1/3)^T$ is the leading eigenvector. The eigenvalues are $3,0.6,0.6$: the leading direction is the all-ones direction, and both contrast directions have eigenvalue $1.4-0.8=0.6$. Since $0.6<1.5$, the spectral condition holds.

At the limiting proportions, the mean replacement is $(1,1,1)^T$. Conditional on drawing color $i$, the replacement differs from this mean by $3e_i-\mathbf{1}$ with probability $0.2$, and by zero otherwise. Averaging the three equally likely colors gives

\Gamma= \begin{pmatrix} 0.4&-0.2&-0.2\\ -0.2&0.4&-0.2\\ -0.2&-0.2&0.4 \end{pmatrix}.

On each contrast direction, $A/\gamma-I/2$ has eigenvalue $0.6/3-0.5=-0.3$. The integral contributes $\int_0^\infty e^{-0.6t}\,dt=1/0.6$, and the noise scaling is $1/9$. Therefore $\Sigma=\Gamma/(9\times0.6)$. For each color proportion, the limiting variance is $0.4/5.4=0.07407$; each pair of distinct proportions has covariance $-0.2/5.4=-0.03704$. The rows of this covariance matrix sum to zero, as they must.

Worked Example: Translating the Limit Into a Proportion Scale

Consider another hypothetical two-color urn. Each draw adds four balls. For a draw of either color, add four balls of that color with probability $0.2$, or two of each color with probability $0.8$. Its replacement matrix is

A= \begin{pmatrix} 2.4&1.6\\ 1.6&2.4 \end{pmatrix}.

Here $\gamma=4$, $v=(0.5,0.5)^T$, and the eigenvalues are $4$ and $0.8$. The condition holds because $0.8<2$. At $v$, a replacement differs from the mean $(2,2)^T$ by $(2,-2)^T$ with probability $0.2$, or by its reversal for the other color, and otherwise has zero difference. It follows that

\Gamma=0.8 \begin{pmatrix} 1&-1\\ -1&1 \end{pmatrix}.

The contrast-direction drift eigenvalue is $0.8/4-0.5=-0.3$, so the integral contributes $1/0.6$. Thus $\Sigma=\Gamma/(16\times0.6)$, and the first proportion has asymptotic variance $0.8/9.6=0.08333$ after multiplication by $\sqrt n$. At $n=100$, this gives the first-order approximation $\operatorname{SD}(P_{n,1})\approx\sqrt{0.08333/100}=0.02887$. This is an asymptotic standard deviation, not an exact finite-sample standard error.

Diagnostics, Alternatives, and Limitations

Before applying the result, check the model as well as the eigenvalues. The replacement rule must match the stated urn mechanism; the total added must be constant; the columns of $A$ must have the common sum $\gamma$; and $v$ must be the normalized positive leading right eigenvector. The noise covariance must be calculated from the actual replacement distributions, not just from the mean matrix. A mean replacement matrix alone does not determine $\Gamma$.

The main alternative is to analyze a different eigenvalue regime rather than force this Gaussian approximation. If a nonleading eigenvalue reaches the half-dominant threshold, the strict condition used to establish the integral’s convergence fails; if it exceeds that threshold, the square-root normalization need not describe the fluctuations. A direct simulation can help explore finite urn behavior, but it does not establish a limiting law or replace verification of the assumptions. The theorem is also an asymptotic result: it does not guarantee an accurate normal approximation for a small number of draws.

A useful diagnostic is whether the proposed covariance respects the constraints of the problem. In a balanced urn, every draw adds the same total, so proportions sum to one at every time. The covariance must consequently assign zero variance to the sum of the proportion fluctuations. A covariance matrix whose rows do not sum to zero indicates an error in the noise calculation, scaling, or linear algebra.

Common pitfall: It is incorrect to check only that every nonleading eigenvalue is smaller than $\gamma$. The Gaussian result requires $\operatorname{Re}(\lambda)<\gamma/2$, a stricter condition. For example, the eigenvalue $0.8$ in the preceding example is below $\gamma=4$, but it is the half-dominant comparison $0.8<2$ that verifies the theorem’s condition. Also, the covariance depends on replacement randomness through $\Gamma$, not solely on the eigenvalues of $A$.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions below.

A balanced urn has dominant eigenvalue $\gamma=6$ and nonleading eigenvalues $2.4$ and $3.1$. Does the subdominant-eigenvalue condition hold?
Why does the limiting covariance of the proportions have zero row sums?
For a two-color urn with $\gamma=4$, the contrast eigenvalue is $1$. What is the eigenvalue of $A/\gamma-I/2$ in that direction, and is it stable?
Can the mean replacement matrix by itself determine the limiting covariance? Explain.

Solutions. (1) Yes. The threshold is $\gamma/2=3$, and both $2.4<3$ and $3.1<3$. (2) The proportions sum to one, so their centered fluctuations also sum to zero; the covariance therefore has zero variance in the all-ones direction, which gives zero row sums. (3) The value is $1/4-1/2=-0.25$, which is negative and hence stable in that contrast direction. (4) No. The covariance also uses $\Gamma$, which depends on the conditional distributions of the replacement vectors, not just their conditional means.

Gaussian Limits for Urns With Subdominant Eigenvalues

What You'll Learn