Near-decomposability: spectral gap and two-timescale aggregation

Parent: derivations

0. Claim and contribution

For a general nearly-decomposable (NCD) stochastic system $P_\varepsilon=P_0+\varepsilon C$:

1. $P_0$'s eigenvalue $1$ is $K$-fold semisimple, the rest separated by $\rho<1$ (Lem 1).
2. Perturbation splits $1$ into one eigenvalue still $=1$ (global stationary) plus $K-1$ slow eigenvalues $1+\varepsilon\mu_j+o(\varepsilon)$, $\mu_j$ the spectrum of a $K\times K$ aggregated matrix $\hat C$; fast eigenvalues stay $\le\rho+O(\varepsilon)$ (Thm 1).
3. Hence two-timescale aggregation: in an intermediate window each block reaches internal equilibrium and the block aggregates evolve slowly under $\hat C$ (Thm 2). The general theorem is proved (degenerate perturbation + identification of $\hat C$); the symmetric $4\times4$ is only a numerical check.

1. Model

$K$ blocks; block $i$ has $n_i$ states. (A1) $P_0=\mathrm{diag}(B_1,\dots,B_K)$, each $B_i$ a primitive (irreducible aperiodic) stochastic matrix. (A2) $P_\varepsilon=P_0+\varepsilon C\ge0$ row-stochastic, so $C\mathbf 1_n=0$, off-block $C\ge0$. Let $\mathbf 1_i$ = indicator of block $i$; $\pi_i$ = stationary row vector of $B_i$ ($\pi_iB_i=\pi_i$, $\pi_i\mathbf 1=1$) zero-extended. Set $R=[\mathbf 1_1\cdots\mathbf 1_K]$, $L=[\pi_1;\dots;\pi_K]$.

2. Lemma 1 ($P_0$'s spectrum)

Lemma 1

$P_0$'s eigenvalue $1$ has algebraic & geometric multiplicity $K$ (semisimple), with $P_0R=R$, $LP_0=L$, $LR=I_K$; the rest satisfy $|\lambda|\le\rho:=\max_i\rho_2(B_i)<1$.

Proof

$P_0$ block-diagonal ⇒ spectrum = $\bigcup_i\mathrm{spec}(B_i)$. By Perron–Frobenius, each primitive stochastic $B_i$ has a simple eigenvalue $1$ (right $\mathbf 1$, left $\pi_i>0$) and the rest of modulus $<1$. So $1$ has multiplicity $K$, with $K$ independent eigenvectors $\mathbf 1_i$ ⇒ semisimple. $(LR)_{ij}=\pi_i\mathbf 1_j=\delta_{ij}$.

3. Lemma 2 (first-order degenerate perturbation) — computation proved, validity cited

Lemma 2

Claim. $A(\varepsilon)=A_0+\varepsilon C$, $A_0$ with semisimple eigenvalue $\lambda_0$ of multiplicity $K$, bases $R,L$, $LR=I_K$. Then the $K$ eigenvalues approaching $\lambda_0$ are $\lambda_0+\varepsilon\mu_j+o(\varepsilon)$, $\mu_j\in\mathrm{spec}(\hat C)$, $\hat C:=LCR$.

Remark

Validity (cited): the first-order expansion exists with coefficients $\mathrm{spec}(LCR)$ — Lidskii's theorem / Kato, Perturbation Theory, Ch. II.

Proof

Coefficient (proved). Expand $A(\varepsilon)v=\lambda v$, $\lambda=\lambda_0+\varepsilon\mu+o$, $v=v_0+\varepsilon v_1+o$, $v_0\in\mathrm{ran}\,R$. Order $\varepsilon^1$: $(A_0-\lambda_0I)v_1=(\mu I-C)v_0$. Left-multiply by $L$; $L(A_0-\lambda_0I)=0$ kills the left side: $0=\mu Lv_0-LCv_0$. With $v_0=Rc$ and $LR=I$: $LCRc=\mu c$, i.e. $\hat C c=\mu c$.

4. Theorem 1 (spectral gap)

Theorem 1

$\hat C=LCR$ satisfies $\hat C\mathbf 1_K=0$ and is generator-type (off-diagonal $\ge0$, zero row sums). For small $\varepsilon$, $P_\varepsilon$'s spectrum is three clusters: $\{1\}$ (global stationary); a slow cluster $1+\varepsilon\mu_j$, $j=2,\dots,K$, $\mu_j\in\mathrm{spec}(\hat C)\setminus\{0\}$ with $\mathrm{Re}\,\mu_j<0$ (so $O(\varepsilon)$ below 1); a fast cluster of modulus $\le\rho+O(\varepsilon)<1$.

Proof

Apply Lemma 2 with $A_0=P_0,\lambda_0=1$. Row sums: $\hat C\mathbf 1_K=LCR\mathbf 1_K=LC\mathbf 1_n=0$ (using $R\mathbf 1_K=\mathbf 1_n$, $C\mathbf 1_n=0$). Off-diagonals $\hat C_{ij}=\pi_iC\mathbf 1_j\ge0$ ($i\ne j$). So $\hat C$ is a Q-matrix: $\mu=0$ (right vector $\mathbf 1_K$, the global stationary stays at 1), others $\mathrm{Re}\,\mu_j\le0$ by Gershgorin. Fast cluster: continuity of eigenvalues (char-poly roots) keeps $|\lambda|\le\rho+O(\varepsilon)$.

Remark

Identification. $\hat C_{ij}=\pi_iC\mathbf 1_j$ = the $\pi_i$-weighted total leak rate from block $i$ to $j$ — the aggregated transition matrix on the $K$ blocks.

5. Theorem 2 (two-timescale aggregation)

Theorem 2

Let $y(t)=Lx(t)\in\mathbb R^K$ (block aggregates).

(i) Exact recursion: $y(t+1)=y(t)+\varepsilon LC\,x(t)$ (from $LP_0=L$).

(ii) In the window $\frac{1}{\log(1/\rho)}\ll t\ll\frac1\varepsilon$, write $x(t)=Ry(t)+e(t)$ with $\|e(t)\|\le\rho^t\|e(0)\|+O(\varepsilon)$; then

$$y(t+1)=(I+\varepsilon\hat C)y(t)+O(\varepsilon^2)+O(\varepsilon\rho^t),$$

i.e. within each block equilibrium $\propto\pi_i$, between blocks slow evolution by $\hat C$ — the system reduces to $K$ states.

Proof

(i) $y(t+1)=L(P_0+\varepsilon C)x(t)=Lx(t)+\varepsilon LCx(t)$. (ii) Split $x(0)=Ry(0)+w(0)$, $w(0)\in\ker L$ ($P_0$-invariant fast subspace), $\|P_0^tw(0)\|\le\rho^t\|w(0)\|$; the $\varepsilon C$ leakage between subspaces is $O(\varepsilon)$, so $\|w(t)\|\le\rho^t\|w(0)\|+O(\varepsilon)$ (standard singular-perturbation / Tikhonov bound). Then $LCx(t)=\hat Cy(t)+O(\varepsilon)$.

6. Numerical check (symmetric 4×4, verification only)

$P_\varepsilon=\begin{pmatrix}a&b&e&e\\b&a&e&e\\e&e&a&b\\e&e&b&a\end{pmatrix}$, $a+b+2e=1$; take $e=0.01,a=0.6,b=0.38$. Sign-vectors give the exact spectrum $\{1,0.96,0.22,0.22\}$. Theory: $\pi_i=(\tfrac12,\tfrac12)$, $\hat C=\begin{pmatrix}-2e&2e\\2e&-2e\end{pmatrix}$, $\mathrm{spec}=\{0,-4e\}\Rightarrow1+\varepsilon\mu\in\{1,0.96\}$ ✓; fast $a-b=0.22\le\rho$ ✓. Window $3\ll t\ll100$. This verifies; the proof is §3–5, for any $K$ and any blocks.

7. Scope

Semisimplicity is required (a defective $1$ gives $\varepsilon^{1/m}$ Puiseux splitting — excluded by primitivity (A1)); the $O(\varepsilon)$ leakage constant in §5(ii) depends on the gap $1-\rho$ and $\|C\|$ (cited Tikhonov-type bound); block primitivity needed; continuous-time $\dot x=(P_0+\varepsilon C)x$ is parallel (slow rates are the $\mu_j$ themselves).

8. Cited vs proved

Proved: $P_0$ spectrum and $R,L,LR=I$; the first-order coefficient $=\mathrm{spec}(LCR)$; $\hat C$ generator structure and the three clusters; aggregation recursion and window bound. Cited: Perron–Frobenius; Lidskii/Kato (existence of the semisimple first-order expansion); continuity of char-poly roots; Tikhonov-type constants.