Generalized Urn Eigenvalues and Rate Regimes

Why Eigenvalues Set Urn Fluctuation Rates

In an adaptive allocation scheme represented by an urn, the current composition affects the next draw, and the draw affects the composition that follows. Consequently, composition fluctuations are not simply sums of independent increments. Their rates depend on how strongly the replacement mechanism amplifies or damps departures from its long-run composition. Eigenvalues provide a way to describe that behavior mode by mode.

The central comparison is between a nonleading eigenvalue’s real part and one half, after the replacement matrix has been normalized by the number of balls added per draw. This comparison identifies the natural scale of a composition mode; by itself, it does not establish the mode’s limiting distribution. The result is most direct for balanced urns with a simple leading eigenvalue and well-behaved replacement noise.

Model and Eigenvalue Conventions

Consider an urn with \(d\) colors. Write \(Z_n\) for the column vector of color counts after \(n\) draws, and \(T_n=\sum_{i=1}^{d}Z_{n,i}\) for the total number of balls. At each draw, a ball is selected with probability equal to its color’s proportion in the urn. It is returned, and a replacement vector is added. The replacement vector may depend on the color drawn; its conditional mean, given that color, is the corresponding column of a \(d\)-by-\(d\) matrix \(R\). In this convention, column \(j\) describes the mean replacement when color \(j\) is drawn.

Assume that the total number added is the same positive constant \(c\) at every draw. Thus \(T_n=T_0+nc\). The replacement vectors are assumed to be nonnegative and bounded, and the urn starts with positive counts. For the standard rate classification, also assume that the mean replacement matrix is irreducible and that its eigenvalue \(c\) is simple. These conditions ensure a unique positive leading composition direction. Less restrictive or unbalanced models require separate analysis.

A right eigenvector describes a direction in the color-count coordinates. For deviations from the leading composition, the relevant directions have total zero. A left eigenvector is useful for extracting the scalar coordinate of a deviation along a mode. In particular, if \(\ell^{T}A=\lambda\ell^{T}\), then applying \(\ell^{T}\) to the centered count vector isolates the mode associated with \(\lambda\).

Because the principal eigenvalue is \(1\), nonleading modes are compared with the threshold \(1/2\) on the normalized scale. Equivalently, for an eigenvalue \(\rho\) of the unnormalized matrix \(R\), compare \(\operatorname{Re}(\rho)\) with \(c/2\). For complex eigenvalues the real part, not the magnitude, determines the basic power rate.

From the Recursion to the Rate Threshold

The rate comparison follows from a simple linear recursion. Let \(Y_n=Z_n-T_n v\) denote the count deviation from the leading composition at the current total. Write \(\mathcal{F}_n\) for the information available after draw \(n\), and let \(\xi_{n+1}\) be the difference between the replacement vector at draw \(n+1\) and its conditional mean given \(\mathcal{F}_n\). Then \(E(\xi_{n+1}\mid\mathcal{F}_n)=0\). Since the probability of drawing each color is its current proportion, the conditional mean replacement is \(RZ_n/T_n\). Using \(Rv=cv\), the centered recursion is

To see this, substitute \(Z_n=Y_n+T_n v\) into the conditional mean increment. The mean replacement is \(RZ_n/T_n=cAY_n/T_n+cv\). The term \(cv\) is exactly the increase in \(T_n v\), leaving \(Y_n+cAY_n/T_n\); since \(T_n=c(n+a)\), the displayed recursion follows after adding the mean-zero noise.

Project the recursion onto a left eigenvector \(\ell\) with eigenvalue \(\lambda\), and set \(U_n=\ell^{T}Y_n\). Then

The product of the scalar multipliers from one step to \(n\) grows at order \(n^{\lambda}\). For a complex \(\lambda\), its magnitude grows at order \(n^{\operatorname{Re}(\lambda)}\). After dividing by that product, the contribution of the noise at step \(k\) is weighted at order \(k^{-\lambda}\). If the projected noise has nonzero, bounded variance, the accumulated variance is therefore governed by a sum of the form \(\sum_{k\le n} k^{-2\operatorname{Re}(\lambda)}\). That sum converges when the real part exceeds one half, grows logarithmically at one half, and grows at order \(n^{1-2\operatorname{Re}(\lambda)}\) below one half. This yields the rate classification below.

Worked Examples: Reading the Three Regimes

Conditions, Diagnostics, and Limits

The classification is useful only if the model and its spectral quantities are correctly specified. Check that total additions really are fixed at \(c\), that the matrix columns follow the stated convention, and that the matrix used in the threshold comparison is \(A=R/c\), not \(R\) itself. Verify that the eigenvalue \(1\) is the simple leading eigenvalue and that the remaining modes describe deviations rather than a second leading direction. In a numerical calculation, recompute the eigenvalues after normalizing the matrix and check that rounding has not moved a value across \(1/2\).

The noise also matters. The rate argument uses bounded or suitably controlled increments and nonzero variation in the projected noise direction. If the replacement mechanism produces no random variation in a mode, its noise-driven scale may not apply; the deterministic recursion or initial deviation can then be more important. Close to the threshold, finite samples can make the regimes difficult to distinguish: a value just below one half may show slow convergence, while a value just above it may resemble square-root behavior for a long time.

For a nonreal eigenvalue, the basic magnitude rate is controlled by its real part. The mode may also rotate as it grows or decays. If an eigenvalue has a nontrivial Jordan block, additional logarithmic factors can arise, so the simple power-rate summary is not a complete description. Likewise, if the urn is unbalanced, its total is not \(T_0+nc\), and the centered recursion and normalization must be reconsidered.

This eigenvalue view complements, rather than replaces, other descriptions. The earlier material on Pólya urn proportions and Dirichlet limits concerns a classical scheme with persistent randomness in its proportions; the simple-leading-eigenvalue rate calculation here does not apply unchanged when multiple directions share the leading eigenvalue. Linearization near an allocation target provides a related local-drift perspective, while the eigenvalue calculation organizes that drift into modes. Neither an eigenvalue classification nor a rate alone gives a complete distributional limit, a covariance formula, or a finite-sample guarantee.

Common Mistakes

• Comparing a raw eigenvalue with one half. The threshold applies to \(R/c\). For example, an eigenvalue \(6\) with \(c=10\) corresponds to \(0.6\), not 6, on the normalized scale.
• Using the eigenvalue’s magnitude for a complex mode. The basic power rate depends on \(\operatorname{Re}(\lambda)\), not \(|\lambda|\).
• Treating a rate as a distributional conclusion. A square-root scale does not, by itself, prove a Gaussian limit. That conclusion needs additional conditions and a limit theorem.
• Calling a mode above threshold when it is below, or vice versa. Check the normalized value explicitly against \(1/2\), including equality as the critical case.
• Ignoring degeneracy or model structure. Balance, a simple leading eigenvalue, and noise in the projected direction are substantive conditions, not automatic consequences of computing eigenvalues.