Critical Urn Eigenvalues and Logarithmic Normalization

Why the Critical Eigenvalue Needs a Different Scale

For a generalized urn, the dominant eigenvalue describes the overall growth of the urn. Other eigenvalues describe how deviations from the limiting composition evolve. When a subdominant eigenvalue is strictly below half the dominant one, its projected fluctuations typically have a square-root-of-\(n\) Gaussian scale. At the half-dominant threshold, the accumulated noise is just large enough to add a logarithmic factor. The resulting scale is \(\sqrt{n\log n}\), not \(\sqrt n\).

The logarithm comes from adding the squared contributions of many past innovations. At the critical threshold, the contribution from an innovation \(k\) steps into the process has squared weight proportional to \(n/k\). Summing these weights produces the harmonic sum \(\sum_{k=1}^n 1/k\), which grows like \(\log n\). This tutorial derives that argument for one projected fluctuation coordinate and explains exactly what it does—and does not—say about variance.

Model and Critical Coordinate

Consider a balanced generalized urn with a fixed number of colors. At each step one ball is drawn, and a random replacement vector specifies the balls added. Assume the total number of balls increases by one at each step. Let \(H\) be the mean replacement matrix, with columns indexed by the color drawn, and suppose its columns sum to one. The dominant eigenvalue is then one. Assume the proportions converge to an interior vector \(v\) satisfying \(Hv=v\).

Let \(u\) be a left eigenvector for a real subdominant eigenvalue \(\lambda\), so \(u^{T}H=\lambda u^{T}\), and take \(u^{T}v=0\). If \(Y_n\) is the vector of urn counts after \(n\) additions, the projected deviation is \(U_n=u^{T}Y_n\): the centering term in the direction \(v\) vanishes because \(u^{T}v=0\). The critical case is \(\lambda=1/2\), half the dominant eigenvalue.

The essential scalar recursion for this coordinate, up to an immaterial shift in the time index, is

where \(\xi_n\) is the projected replacement innovation. Let \(\mathcal F_{n-1}\) denote the information available before the \(n\)th draw. The innovations must satisfy \(E(\xi_n\mid\mathcal F_{n-1})=0\). For the Gaussian limit below, assume that their conditional variances converge in probability to a constant \(\sigma^2>0\), are uniformly bounded, and that a conditional Lindeberg condition holds. Bounded replacement vectors are a convenient sufficient condition for the latter. Also assume the critical eigenvalue is simple and there is no additional Jordan-block contribution in this coordinate.

Deriving the Logarithmic Normalization

Iterating the recursion expresses \(U_n\) as a weighted sum of its initial value and the martingale innovations. Define

Then \(U_n=a_{n,0}U_0+\sum_{k=1}^{n}a_{n,k}\xi_k\), with the initial factor interpreted according to the chosen starting index. For large \(k\), taking logarithms of the product and using \(\log(1+x)=x+O(x^2)\) gives

Thus \(a_{n,k}^2\) is asymptotic to \(n/k\) for large \(k\). The squared weight sum therefore has the order

The first, fixed number of terms do not change this leading order: each has squared weight of order \(n\), while \(n\log n\) is larger by a factor that diverges. The martingale innovations have asymptotic conditional variance \(\sigma^2\), so their weighted conditional variance, divided by \(n\log n\), converges in probability to \(\sigma^2\). Uniform boundedness of the conditional variances, together with convergence to \(\sigma^2\), justifies replacing the late conditional variances by that limit in the weighted sum; the finite early part is negligible after normalization.

The largest normalized weight tends to zero. For each fixed early \(k\), \(a_{n,k}/\sqrt{n\log n}\) is of order \(1/\sqrt{\log n}\), and later weights are no larger in order. The assumed conditional Lindeberg condition rules out a non-negligible contribution from unusually large innovations. These are the variance and no-large-increment requirements for the martingale central limit theorem.

The initial-value term divided by \(\sqrt{n\log n}\) tends to zero, so it does not shift this limit. The variance parameter \(\sigma^2\) is the variance of the limiting distribution. The distributional convergence alone does not establish that \(\operatorname{Var}(U_n)/(n\log n)\) converges to \(\sigma^2\). That stronger claim requires additional control, such as uniform integrability of the appropriately normalized squared sums, so that second moments converge as well.

Checking the Projection in a Two-Color Urn

The scalar recursion can be checked directly in a simple hypothetical urn. Suppose a draw of color 1 adds one color-1 ball with probability \(0.75\) and one color-2 ball otherwise. A draw of color 2 adds one color-1 ball with probability \(0.25\) and one color-2 ball otherwise. The mean replacement matrix and its eigenvalues are

The limiting composition is \(v=(0.5,0.5)^T\); for the second eigenvalue, take \(u=(1,-1)^T\). Then \(u^Tv=0\), and \(U_n=u^TY_n\) is the difference between the two color counts. If the current counts are \(Y_{n-1}\) and the total is \(n-1\), the probability of drawing color 1 is \(Y_{1,n-1}/(n-1)\). The conditional mean change in \(U_n\) is \(0.5\) after drawing color 1 and \(-0.5\) after drawing color 2. Averaging over the draw gives

Subtracting this conditional mean from the change defines the martingale innovation \(\xi_n\), yielding the critical recursion with a shifted index. For either drawn color, the projected added ball is \(+1\) or \(-1\), with probabilities \(0.75\) and \(0.25\) in one order or the other. Its conditional variance about its mean is \(4(0.75)(0.25)=0.75\). However, conditional on the pre-draw information, writing \(p=Y_{1,n-1}/(n-1)\), \(P(\Delta U_n=1\mid\mathcal F_{n-1})=0.25+0.5p\), so \(E(\Delta U_n\mid\mathcal F_{n-1})=p-0.5\) and \(\operatorname{Var}(\xi_n\mid\mathcal F_{n-1})=\operatorname{Var}(\Delta U_n\mid\mathcal F_{n-1})=1-(p-0.5)^2\). As the proportions converge to \((0.5,0.5)\), this variance converges to \(1\), not \(0.75\). The innovations are bounded, so the variance and Lindeberg requirements hold, and the theorem gives

This is a limit for the projected difference in counts. It is not by itself a statement about the distribution of every coordinate of the composition vector, nor a claim that the finite-\(n\) variance has the corresponding asymptotic value.

Diagnostics, Comparisons, and Limits

The critical normalization is one point in the rate classification for projected urn fluctuations. Relative to the dominant eigenvalue, an eigenvalue strictly below one half produces a square-root-\(n\) Gaussian regime under suitable conditions. At one half, the same order of accumulated noise acquires the logarithmic factor derived above. Above one half, early innovations can remain influential on a larger scale; the Gaussian critical theorem here does not cover that regime.

In applications, check the eigenvalue relative to the dominant growth rate, verify that the chosen coordinate is a genuine centered eigenprojection, and inspect the innovations. If replacement vectors are bounded and urn proportions converge to an interior target, the conditional variance often converges to a finite constant; the exact value must still be calculated for the projection being studied. Multiple or defective eigenvalues, a variance limit of zero, unbounded innovations without an appropriate Lindeberg condition, or failure of proportion convergence can invalidate this simple conclusion. A zero limiting innovation variance also means this theorem supplies no nondegenerate Gaussian limit on the stated scale.

A common error is to see a Gaussian limit with variance \(\sigma^2\) and immediately write \(\operatorname{Var}(U_n)\sim \sigma^2 n\log n\). Distributional convergence does not generally imply convergence of second moments: rare events can affect actual variances while having negligible effect on the limiting distribution. The correction is to state the result as \(U_n/\sqrt{n\log n}\xrightarrow{d}N(0,\sigma^2)\), and to claim the corresponding actual-variance asymptotic only when an additional condition, such as uniform integrability of the normalized squared sums, justifies it.