The Role of Generative AI (GenAI)
This paper is a collaborative effort between the author and GenAI. ChatGPT was extensively used in writing this manuscript. Most proofs were generated, corrected, and refined through iterative interactions between ChatGPT and the author. The author verified all results, organized and edited the paper, and takes full responsibility for the final content of the manuscript.
Introduction
Mean-field models provide tractable deterministic approximations for large stochastic systems and have been widely used in epidemic models, queueing and load-balancing systems, communication networks, and interacting particle systems. Consider M M M agents evolving on a common n n n -state space. Classical finite-time convergence results go back to Kurtz [5 , 6 ] . Using Stein’s method, Ying [7 ] established an O ( 1 / M ) O(1/M) O ( 1/ M ) bound on the steady-state mean-square approximation error for a broad class of homogeneous mean-field models. More recently, Ying [8 ] extended this result to fully heterogeneous systems under assumptions that include stability and uniform robustness of the occupancy dynamics.
This paper studies the second-order steady-state behavior of fully heterogeneous mean-field models. For homogeneous density-dependent population processes, Gast and Van Houdt [4 ] developed a refined mean-field approximation in steady state, in which the leading 1 / M 1/M 1/ M correction is characterized by the Jacobian and Hessian of the mean-field drift and the solution of a Lyapunov equation. Barbour, Luczak, and Xia [2 , 3 ] developed quantitative multivariate discrete-normal approximations for equilibrium distributions of density-dependent Markov jump processes. These results rely on a fixed-dimensional population-process representation. For fully heterogeneous systems, Allmeier and Gast [1 ] established mean-field and refined mean-field approximation results over finite time horizons. These finite-time results leave open the corresponding steady-state question when the dimension of the full mean-field system grows with the number of agents.
We address this problem by conditioning on the realized agent parameters and studying weighted occupancies. Let θ m \theta_m θ m denote the parameter of agent m m m , W m ( t ) ∈ R n − 1 \mathbf{W}_m(t) \in\mathbb{R}^{n-1} W m ( t ) ∈ R n − 1 its reduced one-hot state, and w m ∗ \mathbf{w}^{*}_m w m ∗ its component of the quenched mean-field equilibrium. For a fixed bounded weight function ϕ \phi ϕ , define X ϕ ( t ) = M − 1 ∑ m = 1 M ϕ ( θ m ) W m ( t ) \mathbf{X}_{\phi}(t) = M^{-1}\sum_{m=1}^{M}\phi(\theta_m)\mathbf{W}_m(t) X ϕ ( t ) = M − 1 ∑ m = 1 M ϕ ( θ m ) W m ( t ) , x ϕ ∗ = M − 1 ∑ m = 1 M ϕ ( θ m ) w m ∗ \mathbf{x}^{*}_{\phi} = M^{-1}\sum_{m=1}^{M}\phi(\theta_m)\mathbf{w}^{*}_m x ϕ ∗ = M − 1 ∑ m = 1 M ϕ ( θ m ) w m ∗ , and Y ϕ = M ( X ϕ ( ∞ ) − x ϕ ∗ ) \mathbf{Y}_{\phi} = \sqrt{M}\left(\mathbf{X}_{\phi}(\infty)-\mathbf{x}^{*}_{\phi}\right) Y ϕ = M ( X ϕ ( ∞ ) − x ϕ ∗ ) , where X ϕ ( ∞ ) \mathbf{X}_{\phi}(\infty) X ϕ ( ∞ ) denotes the stationary weighted occupancy. We linearize the heterogeneous mean-field system at its equilibrium and let Σ ‾ \overline{\Sigma} Σ denote the solution of the corresponding Lyapunov equation. With Γ ϕ \Gamma_{\phi} Γ ϕ denoting its weighted projection, we show, under assumptions A1–A8, that
∥ Cov ( Y ϕ ∣ θ ) − Γ ϕ ∥ o p = O ( M − 1 / 2 ) . (1) \left\lVert\operatorname{Cov}(\mathbf{Y}_{\phi}\mid\theta)-\Gamma_{\phi}\right\rVert_{\mathrm{op}} = O\left(M^{-1/2}\right). \tag*{(1)} ∥ Cov ( Y ϕ ∣ θ ) − Γ ϕ ∥ op = O ( M − 1/2 ) . (1)
Here θ = ( θ 1 , … , θ M ) \theta=(\theta_1,\ldots,\theta_M) θ = ( θ 1 , … , θ M ) is the realized parameter vector. Thus, although the full mean-field dimension grows linearly with M M M , the covariance matrix in (1) has size ( n − 1 ) × ( n − 1 ) (n-1)\times(n-1) ( n − 1 ) × ( n − 1 ) , independent of M M M . Equivalently, Γ ϕ / M \Gamma_{\phi}/M Γ ϕ / M approximates the covariance of the unscaled occupancy X ϕ ( ∞ ) \mathbf{X}_{\phi}(\infty) X ϕ ( ∞ ) with error O ( M − 3 / 2 ) O(M^{-3/2}) O ( M − 3/2 ) .
We further characterize the leading finite-size bias. Under the additional drift condition A9, any twice continuously differentiable function h : R n − 1 → R h:\mathbb{R}^{n-1}\to\mathbb{R} h : R n − 1 → R satisfies
E [ h ( X ϕ ( ∞ ) ) ∣ θ ] = h ( x ϕ ∗ ) + 1 M ( D h ( x ϕ ∗ ) [ β ϕ ] + 1 2 Tr ( D 2 h ( x ϕ ∗ ) Γ ϕ ) ) + o ( M − 1 ) . (2) \mathbb{E}\left[h\left(\mathbf{X}_{\phi}(\infty)\right)\mid\theta\right] = h\left(\mathbf{x}^{*}_{\phi}\right) + \frac{1}{M}\left(Dh\left(\mathbf{x}^{*}_{\phi}\right)[\beta_{\phi}] + \frac{1}{2}\operatorname{Tr}\left(D^{2}h\left(\mathbf{x}^{*}_{\phi}\right)\Gamma_{\phi}\right)\right) + o\left(M^{-1}\right). \tag*{(2)} E [ h ( X ϕ ( ∞ ) ) ∣ θ ] = h ( x ϕ ∗ ) + M 1 ( D h ( x ϕ ∗ ) [ β ϕ ] + 2 1 Tr ( D 2 h ( x ϕ ∗ ) Γ ϕ ) ) + o ( M − 1 ) . (2)
Here D h Dh D h and D 2 h D^{2}h D 2 h denote the first and second derivatives of h h h , respectively, Tr \operatorname{Tr} Tr denotes the matrix trace, and β ϕ ∈ R n − 1 \beta_{\phi}\in\mathbb{R}^{n-1} β ϕ ∈ R n − 1 is the mean-refinement vector for the weighted occupancy, determined by the Jacobian and Hessian of the mean-field drift and Σ ‾ \overline{\Sigma} Σ . The refined stationary mean x ϕ ∗ + β ϕ / M \mathbf{x}^{*}_{\phi}+\beta_{\phi}/M x ϕ ∗ + β ϕ / M has error o ( M − 1 ) o(M^{-1}) o ( M − 1 ) , which improves to O ( M − 3 / 2 ) O(M^{-3/2}) O ( M − 3/2 ) under the stronger drift remainder bound in A9. In the homogeneous density-dependent setting with ordinary occupancy (ϕ ≡ 1 \phi\equiv1 ϕ ≡ 1 ), the covariance approximation in (1) and the 1 / M 1/M 1/ M performance correction in (2) have the same form as in the classical steady-state refinement in [4 ] . The distributional approximations in [2 , 3 ] also provide bounds in total variation. Here we obtain the covariance and 1 / M 1/M 1/ M performance refinement directly in the fully heterogeneous, growing-dimensional setting.
The covariance and mean-refinement equations have the same structure as the finite-time refined mean-field equations in [1 ] . In [1 ] , the covariance correction satisfies a time-dependent Lyapunov equation, while the mean correction is driven by the Hessian of the mean-field drift contracted with this covariance. Formally setting the time derivatives to zero at the mean-field equilibrium yields the equations defining Σ ‾ \overline{\Sigma} Σ and the mean-refinement vector in this paper. The main theoretical results in [1 ] concern finite-time marginal state probabilities of individual heterogeneous agents. As discussed in [8 ] , dependence among agents can prevent the occupancy measure from concentrating even when the individual marginal probabilities are approximated accurately. We directly characterize the steady-state covariance and finite-size bias of weighted occupancies.
As a preliminary step toward these second-order results, we extend the first-order steady-state result of [8 ] from the ordinary occupancy to weighted occupancies. This provides the second-moment and bias estimates needed in the second-order analysis. We use a local coupling argument to establish a fourth-moment bound and give structural conditions on the drift and instantaneous covariance rate that can be checked from the transition rules and their smooth extensions. We verify the assumptions for heterogeneous power-of-two load balancing with buffer size two.
Models
Heterogeneous M M M -Agent CTMC
Consider a continuous-time Markov chain (CTMC) consisting of M M M heterogeneous agents. Each agent m m m is associated with a parameter θ m \theta_m θ m belonging to a bounded set Θ \Theta Θ . Throughout the paper, we analyze the system conditional on the realized parameter vector θ = ( θ 1 , … , θ M ) \boldsymbol{\theta} = (\theta_1,\ldots,\theta_M) θ = ( θ 1 , … , θ M ) .
Each agent evolves on the common finite state space S = { 0 , … , n − 1 } \mathcal{S} = \{0,\ldots,n-1\} S = { 0 , … , n − 1 } , where n n n is independent of M M M . Let e 1 , … , e n − 1 \boldsymbol{e}_1,\ldots,\boldsymbol{e}_{n-1} e 1 , … , e n − 1 denote the standard basis vectors of R n − 1 \mathbb{R}^{n-1} R n − 1 and let e 0 = 0 \boldsymbol{e}_0 = 0 e 0 = 0 . If agent m m m is in state i i i at time t t t , we represent its state by W m ( t ) = e i \boldsymbol{W}_m(t) = \boldsymbol{e}_i W m ( t ) = e i . Define the reduced simplex
D n − 1 = { w ∈ R + n − 1 : ∑ i = 1 n − 1 w i ≤ 1 } . (3) \mathcal{D}_{n-1} = \left\{\boldsymbol{w} \in\mathbb{R}_{+}^{n-1} : \sum_{i=1}^{n-1} w_i \le1\right\}. \tag*{(3)} D n − 1 = { w ∈ R + n − 1 : i = 1 ∑ n − 1 w i ≤ 1 } . (3)
Thus, W m ( t ) ∈ { e 0 , … , e n − 1 } ⊂ D n − 1 \boldsymbol{W}_m(t) \in\{\boldsymbol{e}_0,\ldots,\boldsymbol{e}_{n-1}\} \subset\mathcal{D}_{n-1} W m ( t ) ∈ { e 0 , … , e n − 1 } ⊂ D n − 1 . Let
W ⊆ { e 0 , … , e n − 1 } M (4) \mathcal{W} \subseteq\{\boldsymbol{e}_0,\ldots,\boldsymbol{e}_{n-1}\}^{M} \tag*{(4)} W ⊆ { e 0 , … , e n − 1 } M (4)
denote the finite admissible state space of the CTMC, which allows both unconstrained product state spaces and constrained state spaces. For W ∈ W \boldsymbol{W} \in\mathcal{W} W ∈ W , we stack it to a ( n − 1 ) M (n-1)M ( n − 1 ) M vector such that
W = ( W 1 T , … , W M T ) T ∈ R ( n − 1 ) M . (5) \boldsymbol{W} = \left(\boldsymbol{W}_1^{\mathsf{T}},\ldots,\boldsymbol{W}_M^{\mathsf{T}}\right)^{\mathsf{T}} \in\mathbb{R}^{(n-1)M}. \tag*{(5)} W = ( W 1 T , … , W M T ) T ∈ R ( n − 1 ) M . (5)
For a bounded weight function φ : Θ → R \varphi: \Theta\to\mathbb{R} φ : Θ → R , define the weighted empirical occupancy
X φ ( W ) = 1 M ∑ m = 1 M φ ( θ m ) W m . (6) X_{\varphi}(\boldsymbol{W}) = \frac{1}{M}\sum_{m=1}^{M} \varphi(\theta_m)\boldsymbol{W}_m. \tag*{(6)} X φ ( W ) = M 1 m = 1 ∑ M φ ( θ m ) W m . (6)
The interaction field is
Z ( W ) = Ψ ( X χ ( W ) ) , (7) \boldsymbol{Z}(\boldsymbol{W}) = \Psi(X_{\chi}(\boldsymbol{W})), \tag*{(7)} Z ( W ) = Ψ ( X χ ( W )) , (7)
where χ : Θ → R \chi: \Theta\to\mathbb{R} χ : Θ → R is a fixed bounded interaction weight satisfying 0 < ∣ χ ∣ ∞ < ∞ 0 < \lvert\chi\rvert_{\infty} < \infty 0 < ∣ χ ∣ ∞ < ∞ , and Ψ : R n − 1 → R d \Psi: \mathbb{R}^{n-1} \to\mathbb{R}^{d} Ψ : R n − 1 → R d . We assume that W ( t ) \boldsymbol{W}(t) W ( t ) is an irreducible CTMC on W \mathcal{W} W with generator G \mathcal{G} G . Its dynamics are described through a collection R \mathcal{R} R of transition types, which may depend on M M M but not on the current system state. For each r ∈ R r \in\mathcal{R} r ∈ R , let q r C T M C ( W ) q_{r}^{\mathrm{CTMC}}(\boldsymbol{W}) q r CTMC ( W ) denote the transition rate, with q r C T M C ( W ) = 0 q_{r}^{\mathrm{CTMC}}(\boldsymbol{W}) = 0 q r CTMC ( W ) = 0 whenever transition r r r is infeasible at W \boldsymbol{W} W , and let Δ r ∈ R ( n − 1 ) M \Delta_r \in\mathbb{R}^{(n-1)M} Δ r ∈ R ( n − 1 ) M denote the corresponding state change, which is independent of W \boldsymbol{W} W . For a test function g g g ,
( G g ) ( W ) = ∑ r ∈ R q r C T M C ( W ) ( g ( W + Δ r ) − g ( W ) ) . (8) (\mathcal{G}g)(\boldsymbol{W}) = \sum_{r\in\mathcal{R}} q_{r}^{\mathrm{CTMC}}(\boldsymbol{W})\left(g(\boldsymbol{W}+\Delta_r)-g(\boldsymbol{W})\right). \tag*{(8)} ( G g ) ( W ) = r ∈ R ∑ q r CTMC ( W ) ( g ( W + Δ r ) − g ( W ) ) . (8)
The infinitesimal drift and instantaneous covariance-rate matrix of the CTMC are
F C T M C ( W ) = ∑ r ∈ R q r C T M C ( W ) Δ r , Q C T M C ( W ) = ∑ r ∈ R q r C T M C ( W ) Δ r Δ r T . (9) \boldsymbol{F}^{\mathrm{CTMC}}(\boldsymbol{W}) = \sum_{r\in\mathcal{R}} q_{r}^{\mathrm{CTMC}}(\boldsymbol{W})\Delta_r,\qquad
\boldsymbol{Q}^{\mathrm{CTMC}}(\boldsymbol{W}) = \sum_{r\in\mathcal{R}} q_{r}^{\mathrm{CTMC}}(\boldsymbol{W})\Delta_r\Delta_r^{\mathsf{T}}. \tag*{(9)} F CTMC ( W ) = r ∈ R ∑ q r CTMC ( W ) Δ r , Q CTMC ( W ) = r ∈ R ∑ q r CTMC ( W ) Δ r Δ r T . (9)
Thus, conditional on W ( t ) = W W(t)=W W ( t ) = W ,
E [ d W ( t ) ∣ W ( t ) = W ] = F C T M C ( W ) d t + o ( d t ) , E [ d W ( t ) d W ( t ) T ∣ W ( t ) = W ] = Q C T M C ( W ) d t + o ( d t ) . (10) \mathbb{E}[dW(t)\mid W(t)=W]=F^{\mathrm{CTMC}}(W)\,dt+o(dt),\qquad\mathbb{E}[dW(t)dW(t)^{\mathsf{T}}\mid W(t)=W]=Q^{\mathrm{CTMC}}(W)\,dt+o(dt). \tag*{(10)} E [ d W ( t ) ∣ W ( t ) = W ] = F CTMC ( W ) d t + o ( d t ) , E [ d W ( t ) d W ( t ) T ∣ W ( t ) = W ] = Q CTMC ( W ) d t + o ( d t ) . (10)
This paper considers a special class of CTMCs in which each agent interacts with other agents only through the interaction field Z ( W ) Z(W) Z ( W ) . In particular, for each agent, the dependence of its infinitesimal drift on the other agents is through the interaction field and for every W ∈ W W\in\mathcal{W} W ∈ W and m = 1 , … , M m=1,\ldots,M m = 1 , … , M , the m m m th block of the CTMC drift satisfies
[ F C T M C ( W ) ] m = ( G W m ) ( W ) = f ( W m , Z ( W ) ; θ m ) . (11) \left[F^{\mathrm{CTMC}}(W)\right]_m=(\mathcal{G}W_m)(W)=f\left(W_m,Z(W);\theta_m\right). \tag*{(11)} [ F CTMC ( W ) ] m = ( G W m ) ( W ) = f ( W m , Z ( W ) ; θ m ) . (11)
Heterogeneous Mean-Field Model
For each realized parameter θ m \theta_m θ m , let w m ( t ) ∈ D n − 1 w_m(t)\in D_{n-1} w m ( t ) ∈ D n − 1 denote the mean-field state of agent m m m . It approximates the conditional mean of the reduced one-hot state, w m ( t ) ≈ E [ W m ( t ) ∣ θ ] w_m(t)\approx\mathbb{E}[W_m(t)\mid\theta] w m ( t ) ≈ E [ W m ( t ) ∣ θ ] . Equivalently, for 1 ≤ i ≤ n − 1 1\le i\le n-1 1 ≤ i ≤ n − 1 ,
w m , i ( t ) ≈ P ( W m ( t ) = e i ∣ θ ) , w m , 0 ( t ) = 1 − ∑ i = 1 n − 1 w m , i ( t ) . (12) w_{m,i}(t)\approx\mathbb{P}(W_m(t)=e_i\mid\theta),\qquad w_{m,0}(t)=1-\sum_{i=1}^{n-1}w_{m,i}(t). \tag*{(12)} w m , i ( t ) ≈ P ( W m ( t ) = e i ∣ θ ) , w m , 0 ( t ) = 1 − i = 1 ∑ n − 1 w m , i ( t ) . (12)
For a bounded weight φ \varphi φ , define
x φ ( w ) = 1 M ∑ m = 1 M φ ( θ m ) w m , x ( w ) = 1 M ∑ m = 1 M w m , z ( w ) = Ψ ( x χ ( w ) ) . (13) x_\varphi(w)=\frac{1}{M}\sum_{m=1}^{M}\varphi(\theta_m)w_m,\qquad x(w)=\frac{1}{M}\sum_{m=1}^{M}w_m,\qquad z(w)=\Psi\left(x_\chi(w)\right). \tag*{(13)} x φ ( w ) = M 1 m = 1 ∑ M φ ( θ m ) w m , x ( w ) = M 1 m = 1 ∑ M w m , z ( w ) = Ψ ( x χ ( w ) ) . (13)
For each M M M and realized θ \theta θ , let D \mathcal{D} D denote a compact convex admissible mean-field state space satisfying
W ⊆ D ⊆ D n − 1 × M . (14) \mathcal{W}\subseteq\mathcal{D}\subseteq\mathcal{D}_{n-1}^{\times M}. \tag*{(14)} W ⊆ D ⊆ D n − 1 × M . (14)
We assume that D \mathcal{D} D is forward invariant under the mean-field ODE defined below. The set D \mathcal{D} D may incorporate model-specific conservation constraints.
Conditional on θ \theta θ , the quenched mean-field system is
w ˙ m ( t ) = f ( w m ( t ) , z ( w ( t ) ) ; θ m ) , m = 1 , … , M , w ˙ ( t ) = F ( w ( t ) ) , (15) \dot{w}_m(t)=f\left(w_m(t),z(w(t));\theta_m\right),\qquad m=1,\ldots,M,\qquad\dot{w}(t)=F(w(t)), \tag*{(15)} w ˙ m ( t ) = f ( w m ( t ) , z ( w ( t )) ; θ m ) , m = 1 , … , M , w ˙ ( t ) = F ( w ( t )) , (15)
where the mean-field drift F ( w ( t ) ) F(w(t)) F ( w ( t )) is defined by its blocks F m ( w ( t ) ) = f ( w m ( t ) , z ( w ( t ) ) ; θ m ) F_m(w(t))=f\left(w_m(t),z(w(t));\theta_m\right) F m ( w ( t )) = f ( w m ( t ) , z ( w ( t )) ; θ m ) . Note that F ( W ) = F C T M C ( W ) F(W)=F^{\mathrm{CTMC}}(W) F ( W ) = F CTMC ( W ) for every W ∈ W W\in\mathcal{W} W ∈ W by construction.
For an initial condition w ˉ ∈ D \bar{w}\in\mathcal{D} w ˉ ∈ D , let w ( t ; w ˉ ) w(t;\bar{w}) w ( t ; w ˉ ) denote the solution of (15), and let
w ∗ = ( ( w 1 ∗ ) T , … , ( w M ∗ ) T ) T ∈ D (16) w^*=\left((w_1^*)^{\mathsf{T}},\ldots,(w_M^*)^{\mathsf{T}}\right)^{\mathsf{T}}\in\mathcal{D} \tag*{(16)} w ∗ = ( ( w 1 ∗ ) T , … , ( w M ∗ ) T ) T ∈ D (16)
denote its equilibrium. Define
x φ ∗ = 1 M ∑ m = 1 M φ ( θ m ) w m ∗ , z ∗ = Ψ ( x χ ∗ ) , f ( w m ∗ , z ∗ ; θ m ) = 0 , m = 1 , … , M . (17) x_\varphi^*=\frac{1}{M}\sum_{m=1}^{M}\varphi(\theta_m)w_m^*,\qquad z^*=\Psi(x_\chi^*),\qquad f(w_m^*,z^*;\theta_m)=0,\qquad m=1,\ldots,M. \tag*{(17)} x φ ∗ = M 1 m = 1 ∑ M φ ( θ m ) w m ∗ , z ∗ = Ψ ( x χ ∗ ) , f ( w m ∗ , z ∗ ; θ m ) = 0 , m = 1 , … , M . (17)
For a full-state vector u = ( u 1 T , … , u M T ) T u=(u_1^{\mathsf{T}},\ldots,u_M^{\mathsf{T}})^{\mathsf{T}} u = ( u 1 T , … , u M T ) T , define
∥ u ∥ M 2 = 1 M ∑ m = 1 M ∥ u m ∥ 2 , ∥ u ∥ max = max 1 ≤ m ≤ M ∥ u m ∥ . (18) \lVert u\rVert_M^2=\frac{1}{M}\sum_{m=1}^{M}\lVert u_m\rVert^2,\qquad\lVert u\rVert_{\max}=\max_{1\le m\le M}\lVert u_m\rVert. \tag*{(18)} ∥ u ∥ M 2 = M 1 m = 1 ∑ M ∥ u m ∥ 2 , ∥ u ∥ m a x = 1 ≤ m ≤ M max ∥ u m ∥ . (18)
All O ( ⋅ ) O(\cdot) O ( ⋅ ) and o ( ⋅ ) o(\cdot) o ( ⋅ ) statements below are uniform over realized parameter vectors and admissible domains satisfying the stated assumptions.
First-Order Approximation
The first-order analysis in [8 ] is based on bounded rates and jumps, smoothness, stability, and occupancy robustness. In this paper, we further strengthen the robustness condition (A5) to control both the first and second variations of the full mean-field trajectory in a normalized block-ℓ 1 \ell_1 ℓ 1 norm with respect to the initial condition. This strengthened condition will result in an approximation error of O ( M − 1 ) O(M^{-1}) O ( M − 1 ) in Proposition 1 for any bounded weight φ \varphi φ with constants that may depend on φ \varphi φ .
Let
K χ = { x ∈ R n − 1 : ∥ x ∥ 1 ≤ ∥ χ ∥ ∞ } , ∥ u ∥ 1 , M = 1 M ∑ m = 1 M ∥ u m ∥ , (19) \mathcal{K}_{\chi} = \left\{x \in\mathbb{R}^{n-1}: \|x\|_1 \le\|\chi\|_{\infty}\right\}, \qquad\|u\|_{1,M} = \frac{1}{M}\sum_{m=1}^{M}\|u_m\|, \tag*{(19)} K χ = { x ∈ R n − 1 : ∥ x ∥ 1 ≤ ∥ χ ∥ ∞ } , ∥ u ∥ 1 , M = M 1 m = 1 ∑ M ∥ u m ∥ , (19)
where u = ( u 1 T , … , u M T ) T u=(u_1^{\mathsf{T}},\ldots,u_M^{\mathsf{T}})^{\mathsf{T}} u = ( u 1 T , … , u M T ) T . The set K χ \mathcal{K}_{\chi} K χ is compact, independent of M M M and θ \theta θ , and contains x χ ( w ) x_{\chi}(w) x χ ( w ) for every w ∈ D w \in\mathcal{D} w ∈ D .
Assumption 1 (First Order Assumptions). The following conditions hold.
∑ r ∈ R q r C T M C ( W ) ≤ c M (20) \sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W)\le cM \tag*{(20)} r ∈ R ∑ q r CTMC ( W ) ≤ c M (20) uniformly over all W ∈ W W\in\mathcal{W} W ∈ W .
A3 – Smoothness condition. The maps Ψ \Psi Ψ and f ( ⋅ , ⋅ ; θ ) f(\cdot,\cdot;\theta) f ( ⋅ , ⋅ ; θ ) are twice continuously differentiable in their state arguments. Their first and second derivatives are uniformly bounded on K χ \mathcal{K}_{\chi} K χ and D n − 1 × Ψ ( K χ ) \mathcal{D}^{n-1}\times\Psi(\mathcal{K}_{\chi}) D n − 1 × Ψ ( K χ ) , respectively, uniformly over θ ∈ Θ \theta\in\Theta θ ∈ Θ .
A4 – Uniform exponential stability. There exist C , γ > 0 C,\gamma>0 C , γ > 0 , independent of M M M and θ \theta θ , such that
∥ w ( t ; w ^ ) − w ∗ ∥ M ≤ C e − γ t ∥ w ^ − w ∗ ∥ M , w ^ ∈ D , t ≥ 0. (21) \|w(t;\widehat{w})-w^*\|_M\le Ce^{-\gamma t}\|\widehat{w}-w^*\|_M,\qquad\widehat{w}\in\mathcal{D},\quad t\ge0. \tag*{(21)} ∥ w ( t ; w ) − w ∗ ∥ M ≤ C e − γ t ∥ w − w ∗ ∥ M , w ∈ D , t ≥ 0. (21) A5 – Local perturbation robustness. There exist constants C 1 , C 2 < ∞ C_1,C_2<\infty C 1 , C 2 < ∞ , independent of M M M , θ \theta θ , the system state, the transition type r r r , and s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] , such that for every feasible CTMC transition W → W + Δ r W\to W+\Delta_r W → W + Δ r and every
w ^ = W + s Δ r , s ∈ [ 0 , 1 ] , (22) \widehat{w}=W+s\Delta_r,\qquad s\in[0,1], \tag*{(22)} w = W + s Δ r , s ∈ [ 0 , 1 ] , (22) the first and second flow variations in direction Δ r \Delta_r Δ r satisfy1
∫ 0 ∞ ∥ D w ^ w ( t ; w ^ ) [ Δ r ] ∥ 1 , M 2 d t ≤ C 1 M 2 , ∫ 0 ∞ ∥ D w ^ 2 w ( t ; w ^ ) [ Δ r , Δ r ] ∥ 1 , M d t ≤ C 2 M 2 . (23) \int_{0}^{\infty}\left\|D_{\widehat{w}}w(t;\widehat{w})[\Delta_r]\right\|_{1,M}^{2}\,dt\le\frac{C_1}{M^2},\qquad
\int_{0}^{\infty}\left\|D_{\widehat{w}}^{2}w(t;\widehat{w})[\Delta_r,\Delta_r]\right\|_{1,M}\,dt\le\frac{C_2}{M^2}. \tag*{(23)} ∫ 0 ∞ ∥ D w w ( t ; w ) [ Δ r ] ∥ 1 , M 2 d t ≤ M 2 C 1 , ∫ 0 ∞ D w 2 w ( t ; w ) [ Δ r , Δ r ] 1 , M d t ≤ M 2 C 2 . (23)
Proposition 1 (First-order approximation error of a weighted occupancy). Assume A1–A5 and fix a bounded observation weight φ : Θ → R \varphi: \Theta\to\mathbb{R} φ : Θ → R . Recall X φ \mathbf{X}_{\varphi} X φ and x φ ∗ \mathbf{x}_{\varphi}^{*} x φ ∗ from Section 2. Let h : R n − 1 → R h : \mathbb{R}^{n-1} \to\mathbb{R} h : R n − 1 → R be twice continuously differentiable on a neighborhood of
K φ = { y ∈ R n − 1 : ∥ y ∥ 1 ≤ ∥ φ ∥ ∞ } . (24) \mathcal{K}_{\varphi} = \left\{ y \in\mathbb{R}^{n-1} : \lVert y \rVert_{1} \le\lVert\varphi\rVert_{\infty} \right\}. \tag*{(24)} K φ = { y ∈ R n − 1 : ∥ y ∥ 1 ≤ ∥ φ ∥ ∞ } . (24) Then
∣ E [ h ( X φ ( ∞ ) ) ∣ θ ] − h ( x φ ∗ ) ∣ = O ( M − 1 ) , (25) \left| \mathbb{E}\left[h\left(\mathbf{X}_{\varphi}(\infty)\right) \mid\theta\right] - h\left(\mathbf{x}_{\varphi}^{*}\right) \right| = O\left(M^{-1}\right), \tag*{(25)} E [ h ( X φ ( ∞ ) ) ∣ θ ] − h ( x φ ∗ ) = O ( M − 1 ) , (25) where the constant may depend on h h h and φ \varphi φ but is independent of M M M and θ \theta θ .
Proof. Condition on θ \theta θ and suppress this conditioning from the notation. Write x φ ( t ; w ~ ) = x φ ( w ( t ; w ~ ) ) x_{\varphi}(t;\widetilde{w})=x_{\varphi}(w(t;\widetilde{w})) x φ ( t ; w ) = x φ ( w ( t ; w )) . For every v = ( v 1 T , … , v M T ) T ∈ D \mathbf{v}=(v_{1}^{\mathsf{T}},\ldots,v_{M}^{\mathsf{T}})^{\mathsf{T}}\in\mathcal{D} v = ( v 1 T , … , v M T ) T ∈ D ,
∥ 1 M ∑ m = 1 M φ ( θ m ) v m ∥ 1 ≤ 1 M ∑ m = 1 M ∣ φ ( θ m ) ∣ ∥ v m ∥ 1 ≤ ∥ φ ∥ ∞ . (26) \left\lVert\frac{1}{M}\sum_{m=1}^{M}\varphi(\theta_{m})v_{m}\right\rVert_{1}
\le\frac{1}{M}\sum_{m=1}^{M}|\varphi(\theta_{m})|\lVert v_{m}\rVert_{1}
\le\lVert\varphi\rVert_{\infty}. \tag*{(26)} M 1 m = 1 ∑ M φ ( θ m ) v m 1 ≤ M 1 m = 1 ∑ M ∣ φ ( θ m ) ∣ ∥ v m ∥ 1 ≤ ∥ φ ∥ ∞ . (26)
Hence X φ ( W ) \mathbf{X}_{\varphi}(\mathbf{W}) X φ ( W ) , x φ ( t ; w ~ ) x_{\varphi}(t;\widetilde{w}) x φ ( t ; w ) , and x φ ∗ \mathbf{x}_{\varphi}^{*} x φ ∗ belong to K φ \mathcal{K}_{\varphi} K φ . Define the following two constants based on the operator norm induced by the Euclidean norm:
B 1 , h = sup y ∈ K φ ∥ D h ( y ) ∥ o p = sup y ∈ K φ ∥ ∇ h ( y ) ∥ 2 , B 2 , h = sup y ∈ K φ ∥ D 2 h ( y ) ∥ o p . (27) B_{1,h}=\sup_{y\in\mathcal{K}_{\varphi}}\lVert Dh(y)\rVert_{\mathrm{op}}
=\sup_{y\in\mathcal{K}_{\varphi}}\lVert\nabla h(y)\rVert_{2},
\qquad
B_{2,h}=\sup_{y\in\mathcal{K}_{\varphi}}\lVert D^{2}h(y)\rVert_{\mathrm{op}}. \tag*{(27)} B 1 , h = y ∈ K φ sup ∥ D h ( y ) ∥ op = y ∈ K φ sup ∥ ∇ h ( y ) ∥ 2 , B 2 , h = y ∈ K φ sup ∥ D 2 h ( y ) ∥ op . (27)
These constants are finite.
Define the infinite-horizon Stein function
g ( w ~ ) = − ∫ 0 ∞ [ h ( x φ ( t ; w ~ ) ) − h ( x φ ∗ ) ] d t . (28) g(\widetilde{w})=-\int_{0}^{\infty}\left[h\left(x_{\varphi}(t;\widetilde{w})\right)-h\left(\mathbf{x}_{\varphi}^{*}\right)\right]\,\mathrm{d}t. \tag*{(28)} g ( w ) = − ∫ 0 ∞ [ h ( x φ ( t ; w ) ) − h ( x φ ∗ ) ] d t . (28)
By the definition of x φ x_{\varphi} x φ , Cauchy–Schwarz, and A4,
∥ x φ ( t ; w ~ ) − x φ ∗ ∥ ≤ ∥ φ ∥ ∞ ∥ w ( t ; w ~ ) − w ∗ ∥ M ≤ C ∥ φ ∥ ∞ e − γ t ∥ w ~ − w ∗ ∥ M . (29) \left\lVert x_{\varphi}(t;\widetilde{w})-\mathbf{x}_{\varphi}^{*}\right\rVert
\le\lVert\varphi\rVert_{\infty}\left\lVert w(t;\widetilde{w})-w^{*}\right\rVert_{M}
\le C\lVert\varphi\rVert_{\infty}e^{-\gamma t}\left\lVert\widetilde{w}-w^{*}\right\rVert_{M}. \tag*{(29)} x φ ( t ; w ) − x φ ∗ ≤ ∥ φ ∥ ∞ ∥ w ( t ; w ) − w ∗ ∥ M ≤ C ∥ φ ∥ ∞ e − γ t ∥ w − w ∗ ∥ M . (29)
Thus (28) is finite and g g g is bounded on D \mathcal{D} D . The flow property gives
g ( w ( s ; w ~ ) ) = − ∫ s ∞ [ h ( x φ ( t ; w ~ ) ) − h ( x φ ∗ ) ] d t , (30) g(w(s;\widetilde{w}))=-\int_{s}^{\infty}\left[h\left(x_{\varphi}(t;\widetilde{w})\right)-h\left(\mathbf{x}_{\varphi}^{*}\right)\right]\,\mathrm{d}t, \tag*{(30)} g ( w ( s ; w )) = − ∫ s ∞ [ h ( x φ ( t ; w ) ) − h ( x φ ∗ ) ] d t , (30)
and differentiating at s = 0 s=0 s = 0 yields the Poisson equation
D g ( w ~ ) [ F ( w ~ ) ] = h ( x φ ( 0 ; w ~ ) ) − h ( x φ ∗ ) . (31) Dg(\widetilde{w})[F(\widetilde{w})]
=h\left(x_{\varphi}(0;\widetilde{w})\right)-h\left(\mathbf{x}_{\varphi}^{*}\right). \tag*{(31)} D g ( w ) [ F ( w )] = h ( x φ ( 0 ; w ) ) − h ( x φ ∗ ) . (31)
At a discrete CTMC state W \mathbf{W} W , x φ ( 0 ; W ) = 1 M ∑ m = 1 M φ ( θ m ) W m = X φ ( W ) x_{\varphi}(0;\mathbf{W})=\frac{1}{M}\sum_{m=1}^{M}\varphi(\theta_{m})W_{m}=\mathbf{X}_{\varphi}(\mathbf{W}) x φ ( 0 ; W ) = M 1 ∑ m = 1 M φ ( θ m ) W m = X φ ( W ) . Since W ( ∞ ) \mathbf{W}(\infty) W ( ∞ ) is stationary and g g g is bounded,
E [ ( G g ) ( W ( ∞ ) ) ] = 0 , E [ h ( X φ ( ∞ ) ) − h ( x φ ∗ ) ] = E [ D g ( W ( ∞ ) ) [ F ( W ( ∞ ) ) ] − ( G g ) ( W ( ∞ ) ) ] . (32) \mathbb{E}[(\mathcal{G}g)(\mathbf{W}(\infty))]=0,\qquad
\mathbb{E}\left[h(\mathbf{X}_{\varphi}(\infty))-h(\mathbf{x}_{\varphi}^{*})\right]
=\mathbb{E}\left[Dg(\mathbf{W}(\infty))[F(\mathbf{W}(\infty))]-(\mathcal{G}g)(\mathbf{W}(\infty))\right]. \tag*{(32)} E [( G g ) ( W ( ∞ ))] = 0 , E [ h ( X φ ( ∞ )) − h ( x φ ∗ ) ] = E [ D g ( W ( ∞ )) [ F ( W ( ∞ ))] − ( G g ) ( W ( ∞ )) ] . (32)
Fix a feasible CTMC transition W → W + Δ r \mathbf{W}\to\mathbf{W}+\Delta_{r} W → W + Δ r and a point w ~ = W + s Δ r \widetilde{w}=\mathbf{W}+s\Delta_{r} w = W + s Δ r on its segment. Write v ( t ) = D w ~ w ( t ; w ~ ) [ Δ r ] \mathbf{v}(t)=D_{\widetilde{w}}w(t;\widetilde{w})[\Delta_{r}] v ( t ) = D w w ( t ; w ) [ Δ r ] and r ( t ) = D w ~ 2 w ( t ; w ~ ) [ Δ r , Δ r ] \mathbf{r}(t)=D_{\widetilde{w}}^{2}w(t;\widetilde{w})[\Delta_{r},\Delta_{r}] r ( t ) = D w 2 w ( t ; w ) [ Δ r , Δ r ] . Differentiating the finite sum defining x φ x_{\varphi} x φ gives
D w ~ x φ ( t ; w ~ ) [ Δ r ] = 1 M ∑ m = 1 M φ ( θ m ) v m ( t ) , D w ~ 2 x φ ( t ; w ~ ) [ Δ r , Δ r ] = 1 M ∑ m = 1 M φ ( θ m ) r m ( t ) . (33) D_{\widetilde{w}}x_{\varphi}(t;\widetilde{w})[\Delta_{r}]
=\frac{1}{M}\sum_{m=1}^{M}\varphi(\theta_{m})v_{m}(t),
\qquad
D_{\widetilde{w}}^{2}x_{\varphi}(t;\widetilde{w})[\Delta_{r},\Delta_{r}]
=\frac{1}{M}\sum_{m=1}^{M}\varphi(\theta_{m})r_{m}(t). \tag*{(33)} D w x φ ( t ; w ) [ Δ r ] = M 1 m = 1 ∑ M φ ( θ m ) v m ( t ) , D w 2 x φ ( t ; w ) [ Δ r , Δ r ] = M 1 m = 1 ∑ M φ ( θ m ) r m ( t ) . (33)
Therefore, by the triangle inequality,
∥ D w ~ x φ ( t ; w ~ ) [ Δ r ] ∥ ≤ ∥ φ ∥ ∞ ∥ v ( t ) ∥ 1 , M , ∥ D w ~ 2 x φ ( t ; w ~ ) [ Δ r , Δ r ] ∥ ≤ ∥ φ ∥ ∞ ∥ r ( t ) ∥ 1 , M . (34) \left\|D_{\widetilde{w}}x_{\varphi}(t;\widetilde{w})[\Delta_r]\right\| \le\|\varphi\|_{\infty}\|v(t)\|_{1,M}, \qquad\left\|D_{\widetilde{w}}^2x_{\varphi}(t;\widetilde{w})[\Delta_r,\Delta_r]\right\| \le\|\varphi\|_{\infty}\|r(t)\|_{1,M}. \tag*{(34)} ∥ D w x φ ( t ; w ) [ Δ r ] ∥ ≤ ∥ φ ∥ ∞ ∥ v ( t ) ∥ 1 , M , D w 2 x φ ( t ; w ) [ Δ r , Δ r ] ≤ ∥ φ ∥ ∞ ∥ r ( t ) ∥ 1 , M . (34)
Squaring the first inequality, integrating, and applying A5 yield
∫ 0 ∞ ∥ D w ~ x φ ( t ; w ~ ) [ Δ r ] ∥ 2 d t ≤ C 1 ∥ φ ∥ ∞ 2 M 2 , ∫ 0 ∞ ∥ D w ~ 2 x φ ( t ; w ~ ) [ Δ r , Δ r ] ∥ d t ≤ C 2 ∥ φ ∥ ∞ M 2 . (35) \int_{0}^{\infty}\left\|D_{\widetilde{w}}x_{\varphi}(t;\widetilde{w})[\Delta_r]\right\|^2\,dt \le\frac{C_1\|\varphi\|_{\infty}^2}{M^2}, \qquad\int_{0}^{\infty}\left\|D_{\widetilde{w}}^2x_{\varphi}(t;\widetilde{w})[\Delta_r,\Delta_r]\right\|\,dt \le\frac{C_2\|\varphi\|_{\infty}}{M^2}. \tag*{(35)} ∫ 0 ∞ ∥ D w x φ ( t ; w ) [ Δ r ] ∥ 2 d t ≤ M 2 C 1 ∥ φ ∥ ∞ 2 , ∫ 0 ∞ D w 2 x φ ( t ; w ) [ Δ r , Δ r ] d t ≤ M 2 C 2 ∥ φ ∥ ∞ . (35)
Let W \mathbf{W} W be a discrete CTMC state and let Δ r \Delta_r Δ r be a feasible transition increment at W \mathbf{W} W . Since D \mathcal{D} D is convex and both W \mathbf{W} W and W + Δ r \mathbf{W}+\Delta_r W + Δ r belong to W ⊆ D \mathcal{W}\subseteq\mathcal{D} W ⊆ D , the segment between them remains in D \mathcal{D} D . Taylor’s theorem gives
g ( W + Δ r ) = g ( W ) + D g ( W ) [ Δ r ] + R ( W , Δ r ) , R ( W , Δ r ) = ∫ 0 1 ( 1 − s ) D 2 g ( W + s Δ r ) [ Δ r , Δ r ] d s . (36) g(\mathbf{W}+\Delta_r)=g(\mathbf{W})+Dg(\mathbf{W})[\Delta_r]+R(\mathbf{W},\Delta_r), \qquad R(\mathbf{W},\Delta_r)=\int_{0}^{1}(1-s)D^2g(\mathbf{W}+s\Delta_r)[\Delta_r,\Delta_r]\,ds. \tag*{(36)} g ( W + Δ r ) = g ( W ) + D g ( W ) [ Δ r ] + R ( W , Δ r ) , R ( W , Δ r ) = ∫ 0 1 ( 1 − s ) D 2 g ( W + s Δ r ) [ Δ r , Δ r ] d s . (36)
By A3, the first and second flow variations exist, and the integrability bounds in A5 justify differentiation under the integral in (28) . Hence
D 2 g ( w ~ ) [ Δ r , Δ r ] = − ∫ 0 ∞ D 2 h ( x φ ( t ; w ~ ) ) [ D w ~ x φ ( t ; w ~ ) [ Δ r ] , D w ~ x φ ( t ; w ~ ) [ Δ r ] ] d t − ∫ 0 ∞ D h ( x φ ( t ; w ~ ) ) [ D w ~ 2 x φ ( t ; w ~ ) [ Δ r , Δ r ] ] d t . (37) D^2g(\widetilde{w})[\Delta_r,\Delta_r]=-\int_{0}^{\infty}D^2h\left(x_{\varphi}(t;\widetilde{w})\right)\left[D_{\widetilde{w}}x_{\varphi}(t;\widetilde{w})[\Delta_r],D_{\widetilde{w}}x_{\varphi}(t;\widetilde{w})[\Delta_r]\right]\,dt
-\int_{0}^{\infty}Dh\left(x_{\varphi}(t;\widetilde{w})\right)\left[D_{\widetilde{w}}^2x_{\varphi}(t;\widetilde{w})[\Delta_r,\Delta_r]\right]\,dt. \tag*{(37)} D 2 g ( w ) [ Δ r , Δ r ] = − ∫ 0 ∞ D 2 h ( x φ ( t ; w ) ) [ D w x φ ( t ; w ) [ Δ r ] , D w x φ ( t ; w ) [ Δ r ] ] d t − ∫ 0 ∞ D h ( x φ ( t ; w ) ) [ D w 2 x φ ( t ; w ) [ Δ r , Δ r ] ] d t . (37)
Using (35) ,
∣ D 2 g ( w ~ ) [ Δ r , Δ r ] ∣ ≤ B 2 , h C 1 ∥ φ ∥ ∞ 2 + B 1 , h C 2 ∥ φ ∥ ∞ M 2 = C h , φ M 2 . (38) \left|D^2g(\widetilde{w})[\Delta_r,\Delta_r]\right| \le\frac{B_{2,h}C_1\|\varphi\|_{\infty}^2+B_{1,h}C_2\|\varphi\|_{\infty}}{M^2}=\frac{C_{h,\varphi}}{M^2}. \tag*{(38)} D 2 g ( w ) [ Δ r , Δ r ] ≤ M 2 B 2 , h C 1 ∥ φ ∥ ∞ 2 + B 1 , h C 2 ∥ φ ∥ ∞ = M 2 C h , φ . (38)
Substituting the bound above into (36) yields ∣ R ( W , Δ r ) ∣ ≤ C h , φ / ( 2 M 2 ) \lvert R(\mathbf{W},\Delta_r)\rvert\le C_{h,\varphi}/(2M^2) ∣ R ( W , Δ r )∣ ≤ C h , φ / ( 2 M 2 ) uniformly over feasible transitions. Note that at every discrete CTMC state W \mathbf{W} W , we have
( G g ) ( W ) = ∑ r ∈ R q r C T M C ( W ) ( g ( W + Δ r ) − g ( W ) ) = D g ( W ) [ F ( W ) ] + ∑ r ∈ R q r C T M C ( W ) R ( W , Δ r ) , (39) (\mathcal{G}g)(\mathbf{W})=\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(\mathbf{W})\left(g(\mathbf{W}+\Delta_r)-g(\mathbf{W})\right)=Dg(\mathbf{W})[F(\mathbf{W})]+\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(\mathbf{W})R(\mathbf{W},\Delta_r), \tag*{(39)} ( G g ) ( W ) = r ∈ R ∑ q r CTMC ( W ) ( g ( W + Δ r ) − g ( W ) ) = D g ( W ) [ F ( W )] + r ∈ R ∑ q r CTMC ( W ) R ( W , Δ r ) , (39)
which implies that
∣ ( G g ) ( W ) − D g ( W ) [ F ( W ) ] ∣ ≤ c C h , φ 2 M , (40) \left|(\mathcal{G}g)(\mathbf{W})-Dg(\mathbf{W})[F(\mathbf{W})]\right|\le\frac{cC_{h,\varphi}}{2M}, \tag*{(40)} ∣ ( G g ) ( W ) − D g ( W ) [ F ( W )] ∣ ≤ 2 M c C h , φ , (40)
where the inequality follows directly from A1 and (38) . Substituting (40) into (32) and restoring the conditioning on θ \theta θ proves (25) .
Corollary 1. (Weighted occupancy second-moment and bias bounds.) Under A1–A5, for every fixed bounded observation weight φ \varphi φ ,
E [ ∥ X φ ( ∞ ) − x φ ∗ ∥ 2 ∣ θ ] = O ( M − 1 ) , ∥ E [ X φ ( ∞ ) − x φ ∗ ∣ θ ] ∥ = O ( M − 1 ) . (41) \mathbb{E}\left[\left\|X_{\varphi}(\infty)-x_{\varphi}^{*}\right\|^2\mid\theta\right]=O(M^{-1}), \qquad\left\|\mathbb{E}\left[X_{\varphi}(\infty)-x_{\varphi}^{*}\mid\theta\right]\right\|=O(M^{-1}). \tag*{(41)} E [ X φ ( ∞ ) − x φ ∗ 2 ∣ θ ] = O ( M − 1 ) , E [ X φ ( ∞ ) − x φ ∗ ∣ θ ] = O ( M − 1 ) . (41) Equivalently, with Y φ = M ( X φ ( ∞ ) − x φ ∗ ) Y_{\varphi}=\sqrt{M}\left(X_{\varphi}(\infty)-x_{\varphi}^{*}\right) Y φ = M ( X φ ( ∞ ) − x φ ∗ ) , we have
E [ ∥ Y φ ∥ 2 ∣ θ ] = O ( 1 ) , ∥ E [ Y φ ∣ θ ] ∥ = O ( M − 1 / 2 ) . (42) \mathbb{E}\left[\|Y_{\varphi}\|^2\mid\theta\right]=O(1), \qquad\left\|\mathbb{E}[Y_{\varphi}\mid\theta]\right\|=O(M^{-1/2}). \tag*{(42)} E [ ∥ Y φ ∥ 2 ∣ θ ] = O ( 1 ) , ∥ E [ Y φ ∣ θ ] ∥ = O ( M − 1/2 ) . (42)
Proof. For the first statement in (41) , apply Proposition 1 to h θ ( y ) = ∥ y − x φ ∗ ∥ 2 h_{\theta}(y)=\|y-x_{\varphi}^{*}\|^2 h θ ( y ) = ∥ y − x φ ∗ ∥ 2 . Its first and second derivatives are uniformly bounded on K φ \mathcal{K}_{\varphi} K φ , independently of M M M and θ \theta θ . For the bias statement, apply Proposition 1 to the coordinate functions h i ( y ) = y i h_i(y)=y_i h i ( y ) = y i , i = 1 , … , n − 1 i=1,\ldots,n-1 i = 1 , … , n − 1 . Since n n n is fixed, the resulting coordinatewise O ( M − 1 ) O(M^{-1}) O ( M − 1 ) bounds imply the second statement in (41) . Equation (42) follows by the definition of Y φ Y_{\varphi} Y φ .
Second-Order Covariance Approximation and Mean Refinement
For the second-order analysis, let Q Q Q be a symmetric positive semidefinite matrix-valued function on D \mathcal{D} D satisfying Q ( W ) = Q C T M C ( W ) Q(W)=Q^{\mathrm{CTMC}}(W) Q ( W ) = Q CTMC ( W ) for every W ∈ W W\in\mathcal{W} W ∈ W , where Q C T M C Q^{\mathrm{CTMC}} Q CTMC is defined in (9) . Define
J = D F ( w ∗ ) , Q ‾ = Q ( w ∗ ) , R F ( w ) = F ( w ) − J ( w − w ∗ ) . (43) J=DF(w^*), \qquad\overline{Q}=Q(w^*), \qquad R_F(w)=F(w)-J(w-w^*). \tag*{(43)} J = D F ( w ∗ ) , Q = Q ( w ∗ ) , R F ( w ) = F ( w ) − J ( w − w ∗ ) . (43)
For a deterministic block vector a = ( a 1 ⊤ , … , a M ⊤ ) ⊤ a=(a_1^\top,\ldots,a_M^\top)^\top a = ( a 1 ⊤ , … , a M ⊤ ) ⊤ , define the scaled vector
L a = 1 M ( a 1 ⊤ ⋯ a M ⊤ ) . L_a=\frac{1}{\sqrt{M}}(a_1^\top\ \cdots\ a_M^\top). L a = M 1 ( a 1 ⊤ ⋯ a M ⊤ ) .
For a fixed bounded observation weight φ : Θ → R \varphi:\Theta\to\mathbb{R} φ : Θ → R , define
L φ = 1 M ( φ ( θ 1 ) I n − 1 ⋯ φ ( θ M ) I n − 1 ) , Y φ = L φ ( W ( ∞ ) − w ∗ ) = M ( X φ ( ∞ ) − x φ ∗ ) . (44) L_\varphi=\frac{1}{\sqrt{M}}\left(\varphi(\theta_1)I_{n-1}\ \cdots\ \varphi(\theta_M)I_{n-1}\right), \qquad Y_\varphi=L_\varphi(W(\infty)-w^*)=\sqrt{M}\left(X_\varphi(\infty)-x_\varphi^*\right). \tag*{(44)} L φ = M 1 ( φ ( θ 1 ) I n − 1 ⋯ φ ( θ M ) I n − 1 ) , Y φ = L φ ( W ( ∞ ) − w ∗ ) = M ( X φ ( ∞ ) − x φ ∗ ) . (44)
Whenever J J J is Hurwitz, let Σ ‾ \overline{\Sigma} Σ denote the unique symmetric solution of the Lyapunov equation
J Σ ‾ + Σ ‾ J ⊤ + Q ‾ = 0 (45) J\overline{\Sigma}+\overline{\Sigma}J^\top+\overline{Q}=0 \tag*{(45)} J Σ + Σ J ⊤ + Q = 0 (45)
such that
Σ ‾ = ∫ 0 ∞ e J t Q ‾ e J ⊤ t d t . (46) \overline{\Sigma}=\int_0^\infty e^{Jt}\overline{Q}e^{J^\top t}\,dt. \tag*{(46)} Σ = ∫ 0 ∞ e J t Q e J ⊤ t d t . (46)
We further define
Γ φ = L φ Σ ‾ L φ ⊤ , U = W ( ∞ ) − w ∗ , Σ = E [ U U ⊤ ∣ θ ] . (47) \Gamma_\varphi=L_\varphi\overline{\Sigma}L_\varphi^\top,\qquad U=W(\infty)-w^*,\qquad\Sigma=\mathbb{E}[UU^\top\mid\theta]. \tag*{(47)} Γ φ = L φ Σ L φ ⊤ , U = W ( ∞ ) − w ∗ , Σ = E [ U U ⊤ ∣ θ ] . (47)
For a symmetric matrix A ∈ R N × N A\in\mathbb{R}^{N\times N} A ∈ R N × N , where N = ( n − 1 ) M N=(n-1)M N = ( n − 1 ) M , we define the Hessian contraction of the mean-field drift at equilibrium by
[ H ( A ) ] i = ∑ a , b = 1 N ∂ 2 F i ∂ w a ∂ w b ( w ∗ ) A a b , i = 1 , … , N . (48) [H(A)]_i=\sum_{a,b=1}^{N}\frac{\partial^2F_i}{\partial w_a\partial w_b}(w^*)A_{ab},\qquad i=1,\ldots,N. \tag*{(48)} [ H ( A ) ] i = a , b = 1 ∑ N ∂ w a ∂ w b ∂ 2 F i ( w ∗ ) A ab , i = 1 , … , N . (48)
Equivalently, for any u , v ∈ R N u,v\in\mathbb{R}^N u , v ∈ R N ,
D 2 F ( w ∗ ) [ u , v ] = H ( u v ⊤ + v u ⊤ 2 ) . (49) D^2F(w^*)[u,v]=H\left(\frac{uv^\top+vu^\top}{2}\right). \tag*{(49)} D 2 F ( w ∗ ) [ u , v ] = H ( 2 u v ⊤ + v u ⊤ ) . (49)
The second-order results below are under additional assumptions A6–A9. A6 controls the linearized dynamics, while A7 provides the stationary concentration used in Lemma 1. A8 quantifies the nonlinear-drift and state-dependent-noise errors needed for the covariance approximation, and A9 quantifies the quadratic drift structure and post-quadratic remainder needed for the refined mean. Thus Theorem 1 uses A1–A8, whereas Theorem 2 uses A1–A9. The theorem statements do not require a particular structural representation of the drift or noise. In Section 4.1, we introduce S1–S2 as convenient structural conditions that, together with A1–A7, imply A8–A9 through Lemma 2.
Assumption 2 (Second-order conditions). The following conditions hold.
Stability and concentration.
A6 – Uniform exponential stability of the linearized system. There exist constants C s , γ s > 0 C_s,\gamma_s>0 C s , γ s > 0 , independent of M M M and θ \boldsymbol{\theta} θ , such that
∥ e J t u ∥ 1 , M ≤ C s e − γ s t ∥ u ∥ 1 , M , u ∈ R N , t ≥ 0. (50) \lVert e^{Jt}u\rVert_{1,M}\le C_s e^{-\gamma_s t}\lVert u\rVert_{1,M},\qquad u\in\mathbb{R}^{N},\quad t\ge0. \tag*{(50)} ∥ e J t u ∥ 1 , M ≤ C s e − γ s t ∥ u ∥ 1 , M , u ∈ R N , t ≥ 0. (50)
In particular, J J J is Hurwitz.
A7 – Uniform local coupling contraction. Recall that W \mathcal{W} W is the finite state space of the CTMC. Call two distinct states w , w ~ ∈ W w,\widetilde{w}\in\mathcal{W} w , w ∈ W neighboring, written w ∼ w ~ w\sim\widetilde{w} w ∼ w , if one can be obtained from the other by one feasible CTMC transition, in either direction. There is a metric d d d on W \mathcal{W} W and constants D e , κ c > 0 D_e,\kappa_c>0 D e , κ c > 0 , independent of M M M and θ \boldsymbol{\theta} θ , such that
1 ≤ d ( w , w ~ ) ≤ D e if w ∼ w ~ (51) 1\le d(w,\widetilde{w})\le D_e\quad\text{if }w\sim\widetilde{w} \tag*{(51)} 1 ≤ d ( w , w ) ≤ D e if w ∼ w (51)
and every pair w , w ~ ∈ W w,\widetilde{w}\in\mathcal{W} w , w ∈ W can be joined by a neighboring path w = w ( 0 ) , … , w ( L ) = w ~ w=w^{(0)},\ldots,w^{(L)}=\widetilde{w} w = w ( 0 ) , … , w ( L ) = w satisfying
d ( w , w ~ ) = ∑ ℓ = 1 L d ( w ( ℓ − 1 ) , w ( ℓ ) ) . (52) d(w,\widetilde{w})=\sum_{\ell=1}^{L}d\left(w^{(\ell-1)},w^{(\ell)}\right). \tag*{(52)} d ( w , w ) = ℓ = 1 ∑ L d ( w ( ℓ − 1 ) , w ( ℓ ) ) . (52)
For every neighboring pair there exists a coupling of two copies of the finite CTMC, started from w ∼ w ~ w\sim\widetilde{w} w ∼ w , whose coupled generator G c \mathcal{G}^{c} G c satisfies
( G c d ) ( w , w ~ ) ≤ − κ c d ( w , w ~ ) . (53) (\mathcal{G}^{c}d)(w,\widetilde{w})\le-\kappa_c d(w,\widetilde{w}). \tag*{(53)} ( G c d ) ( w , w ) ≤ − κ c d ( w , w ) . (53)
E R = E [ R F ( W ( ∞ ) ) U T + U R F ( W ( ∞ ) ) T ∣ θ ] , E Q = E [ Q ( W ( ∞ ) ) − Q ‾ ∣ θ ] . (54) E_R=\mathbb{E}\left[R_F(W(\infty))U^{\mathsf T}+UR_F(W(\infty))^{\mathsf T}\mid\boldsymbol{\theta}\right],\qquad E_Q=\mathbb{E}\left[Q(W(\infty))-\overline{Q}\mid\boldsymbol{\theta}\right]. \tag*{(54)} E R = E [ R F ( W ( ∞ )) U T + U R F ( W ( ∞ ) ) T ∣ θ ] , E Q = E [ Q ( W ( ∞ )) − Q ∣ θ ] . (54)
Then
sup ∥ b ∥ max ≤ 1 1 M ∣ b T E R b ∣ = O ( M − 1 / 2 ) , sup ∥ b ∥ max ≤ 1 1 M ∣ b T E Q b ∣ = O ( M − 1 / 2 ) . (55) \sup_{\lVert b\rVert_{\max}\le1}\frac{1}{M}\left|b^{\mathsf T}E_Rb\right|=O(M^{-1/2}),\qquad
\sup_{\lVert b\rVert_{\max}\le1}\frac{1}{M}\left|b^{\mathsf T}E_Qb\right|=O(M^{-1/2}). \tag*{(55)} ∥ b ∥ m a x ≤ 1 sup M 1 b T E R b = O ( M − 1/2 ) , ∥ b ∥ m a x ≤ 1 sup M 1 b T E Q b = O ( M − 1/2 ) . (55)
A9 – Mean-refinement error control. There exist constants K H , C H < ∞ K_H,C_H<\infty K H , C H < ∞ , independent of M M M and θ \boldsymbol{\theta} θ , such that for every ∥ b ∥ max ≤ 1 \lVert b\rVert_{\max}\le1 ∥ b ∥ m a x ≤ 1 and every symmetric matrix A A A , there are block vectors r k , b , s k , b r_{k,b},s_{k,b} r k , b , s k , b satisfying
max 1 ≤ k ≤ K H { ∥ r k , b ∥ max , ∥ s k , b ∥ max } ≤ C H , ∣ b T H ( A ) ∣ ≤ C H ∑ k = 1 K H ∣ L r k , b A L s k , b T ∣ . (56) \max_{1\le k\le K_H}\left\{\lVert r_{k,b}\rVert_{\max},\lVert s_{k,b}\rVert_{\max}\right\}\le C_H,\qquad
\left|b^{\mathsf T}H(A)\right|\le C_H\sum_{k=1}^{K_H}\left|L_{r_{k,b}}AL_{s_{k,b}}^{\mathsf T}\right|. \tag*{(56)} 1 ≤ k ≤ K H max { ∥ r k , b ∥ m a x , ∥ s k , b ∥ m a x } ≤ C H , b T H ( A ) ≤ C H k = 1 ∑ K H L r k , b A L s k , b T . (56)
Moreover, with
T F ( w ) = R F ( w ) − 1 2 H ( ( w − w ∗ ) ( w − w ∗ ) T ) , (57) T_F(w)=R_F(w)-\frac{1}{2}H\left((w-w^*)(w-w^*)^{\mathsf T}\right), \tag*{(57)} T F ( w ) = R F ( w ) − 2 1 H ( ( w − w ∗ ) ( w − w ∗ ) T ) , (57)
we have
sup ∥ b ∥ max ≤ 1 ∣ b T E [ T F ( W ( ∞ ) ) ∣ θ ] ∣ = o ( 1 ) . (58) \sup_{\lVert b\rVert_{\max}\le1}\left|b^{\mathsf T}\mathbb{E}\left[T_F(W(\infty))\mid\boldsymbol{\theta}\right]\right|=o(1). \tag*{(58)} ∥ b ∥ m a x ≤ 1 sup b T E [ T F ( W ( ∞ )) ∣ θ ] = o ( 1 ) . (58)
For the sharper mean-refinement rate, assume the left-hand side of (58) is O ( M − 1 / 2 ) O(M^{-1/2}) O ( M − 1/2 ) . A6–A7 are analytical conditions controlling the linearized dynamics and stationary concentration, while A8–A9 are the second-order error conditions used directly in Theorems 1 and 2. Section 4.1 gives structural sufficient conditions S1–S2 for verifying A8–A9. The local coupling condition A7 is only one way to obtain the concentration bounds below; any alternative argument yielding the same uniform moment bounds can be substituted for A7.
Recall that N = M ( n − 1 ) N=M(n-1) N = M ( n − 1 ) denotes the dimension of the full-state vector. For a deterministic block vector a = ( a 1 ⊤ , … , a M ⊤ ) ⊤ a=(a_1^\top,\ldots,a_M^\top)^\top a = ( a 1 ⊤ , … , a M ⊤ ) ⊤ , define
x a ( w ) = 1 M a ⊤ w , x a ∗ = x a ( w ∗ ) , x ˉ a ( w ) = x a ( w ) − x a ∗ . (59) x_a(w)=\frac{1}{M}a^\top w,\qquad x_a^*=x_a(w^*),\qquad\bar{x}_a(w)=x_a(w)-x_a^*. \tag*{(59)} x a ( w ) = M 1 a ⊤ w , x a ∗ = x a ( w ∗ ) , x ˉ a ( w ) = x a ( w ) − x a ∗ . (59)
The coefficient vector a a a may depend on the realized θ \theta θ , but is deterministic after conditioning on θ \theta θ .
Lemma 1 (Uniform block moment bounds). Under A 1 A_1 A 1 –A 7 A_7 A 7 , there exists C < ∞ C<\infty C < ∞ , independent of M M M , θ \theta θ , and a a a , such that
sup ∥ a ∥ max ≤ 1 ∣ E [ x ˉ a ( W ( ∞ ) ) ∣ θ ] ∣ ≤ C M , sup ∥ a ∥ max ≤ 1 E [ ∣ x ˉ a ( W ( ∞ ) ) ∣ 2 ∣ θ ] ≤ C M , sup ∥ a ∥ max ≤ 1 E [ ∣ x ˉ a ( W ( ∞ ) ) ∣ 4 ∣ θ ] ≤ C M 2 . (60) \sup_{\lVert a\rVert_{\max}\leq1}\left|\mathbb{E}[\bar{x}_a(W(\infty))\mid\theta]\right|\leq\frac{C}{M},
\qquad
\sup_{\lVert a\rVert_{\max}\leq1}\mathbb{E}\left[|\bar{x}_a(W(\infty))|^2\mid\theta\right]\leq\frac{C}{M},
\qquad
\sup_{\lVert a\rVert_{\max}\leq1}\mathbb{E}\left[|\bar{x}_a(W(\infty))|^4\mid\theta\right]\leq\frac{C}{M^2}. \tag*{(60)} ∥ a ∥ m a x ≤ 1 sup ∣ E [ x ˉ a ( W ( ∞ )) ∣ θ ] ∣ ≤ M C , ∥ a ∥ m a x ≤ 1 sup E [ ∣ x ˉ a ( W ( ∞ )) ∣ 2 ∣ θ ] ≤ M C , ∥ a ∥ m a x ≤ 1 sup E [ ∣ x ˉ a ( W ( ∞ )) ∣ 4 ∣ θ ] ≤ M 2 C . (60)
Proof. Condition on θ \theta θ and suppress this conditioning and consider ∥ a ∥ max ≤ 1. W e f i r s t p r o v e t h e b i a s b o u n d u s i n g \lVert a\rVert_{\max}\leq1. We first prove the bias bound using ∥ a ∥ m a x ≤ 1. W e f i r s tp r o v e t h e bia s b o u n d u s in g A_1$–A 5 A_5 A 5 . The proof is similar to the proof of Proposition 1 but needs to establish a bound uniform over all block vectors a a a satisfying the stated block-max norm restriction. Define
x a ( t ; w ^ ) = 1 M ∑ m = 1 M a m ⊤ w m ( t ; w ^ ) , g a ( w ^ ) = − ∫ 0 ∞ ( x a ( t ; w ^ ) − x a ∗ ) d t . (61) x_a(t;\widehat{w})=\frac{1}{M}\sum_{m=1}^{M}a_m^\top w_m(t;\widehat{w}),\qquad
g_a(\widehat{w})=-\int_0^\infty\left(x_a(t;\widehat{w})-x_a^*\right)\,\mathrm{d}t. \tag*{(61)} x a ( t ; w ) = M 1 m = 1 ∑ M a m ⊤ w m ( t ; w ) , g a ( w ) = − ∫ 0 ∞ ( x a ( t ; w ) − x a ∗ ) d t . (61)
By A4 the integral is finite. Arguing as in the proof of Proposition 1, A3 and A5 justify differentiation under the integral along every feasible jump segment. Since x a x_a x a is linear, for every feasible CTMC transition W → W + Δ r W\to W+\Delta_r W → W + Δ r and every w ^ = W + s Δ r \widehat{w}=W+s\Delta_r w = W + s Δ r , s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] ,
∣ D 2 g a ( w ^ ) [ Δ r , Δ r ] ∣ ≤ ∫ 0 ∞ ∥ D 2 w ^ ( t ; w ^ ) [ Δ r , Δ r ] ∥ 1 , M d t ≤ C 2 M 2 , (62) \left|D^2g_a(\widehat{w})[\Delta_r,\Delta_r]\right|
\leq\int_0^\infty\left\|D^2\widehat{w}(t;\widehat{w})[\Delta_r,\Delta_r]\right\|_{1,M}\,\mathrm{d}t
\leq\frac{C_2}{M^2}, \tag*{(62)} D 2 g a ( w ) [ Δ r , Δ r ] ≤ ∫ 0 ∞ D 2 w ( t ; w ) [ Δ r , Δ r ] 1 , M d t ≤ M 2 C 2 , (62)
where the last inequality holds due to A5. The Poisson equation gives
D g a ( w ^ ) [ F ( w ^ ) ] = x a ( w ^ ) − x a ∗ = x ˉ a ( w ^ ) . (63) Dg_a(\widehat{w})[F(\widehat{w})]=x_a(\widehat{w})-x_a^*=\bar{x}_a(\widehat{w}). \tag*{(63)} D g a ( w ) [ F ( w )] = x a ( w ) − x a ∗ = x ˉ a ( w ) . (63)
For a feasible transition W → W + Δ r W\to W+\Delta_r W → W + Δ r , Taylor’s theorem gives
g a ( W + Δ r ) − g a ( W ) = D g a ( W ) [ Δ r ] + R r ( W ) , (64) g_a(W+\Delta_r)-g_a(W)=Dg_a(W)[\Delta_r]+R_r(W), \tag*{(64)} g a ( W + Δ r ) − g a ( W ) = D g a ( W ) [ Δ r ] + R r ( W ) , (64)
R r ( W ) = ∫ 0 1 ( 1 − s ) D 2 g a ( W + s Δ r ) [ Δ r , Δ r ] d s . (65) R_r(W)=\int_0^1(1-s)D^2g_a(W+s\Delta_r)[\Delta_r,\Delta_r]\,\mathrm{d}s. \tag*{(65)} R r ( W ) = ∫ 0 1 ( 1 − s ) D 2 g a ( W + s Δ r ) [ Δ r , Δ r ] d s . (65)
By (65) and (62),
∣ R r ( W ) ∣ ≤ C 2 2 M 2 . (66) |R_r(W)|\leq\frac{C_2}{2M^2}. \tag*{(66)} ∣ R r ( W ) ∣ ≤ 2 M 2 C 2 . (66)
Hence, at every discrete CTMC state W W W ,
( G g a ) ( W ) = ∑ r ∈ R q r C T M C ( W ) ( D g a ( W ) [ Δ r ] + R r ( W ) ) = D g a ( W ) [ F ( W ) ] + ∑ r ∈ R q r C T M C ( W ) R r ( W ) , (67) \begin{aligned}
(\mathcal{G}g_a)(W)=\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W)\left(Dg_a(W)[\Delta_r]+R_r(W)\right) \\
&=Dg_a(W)[F(W)]+\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W)R_r(W), \tag*{(67)}
\end{aligned} ( G g a ) ( W ) = r ∈ R ∑ q r CTMC ( W ) ( D g a ( W ) [ Δ r ] + R r ( W ) ) = D g a ( W ) [ F ( W )] + r ∈ R ∑ q r CTMC ( W ) R r ( W ) , (67)
where we used F ( W ) = ∑ r ∈ R q r C T M C ( W ) Δ r F(W)=\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W)\Delta_r F ( W ) = ∑ r ∈ R q r CTMC ( W ) Δ r on the discrete state space. Since W ( ∞ ) W(\infty) W ( ∞ ) is stationary,
E [ ( G g a ) ( W ( ∞ ) ) ] = 0. (68) \mathbb{E}[(\mathcal{G}_{g_a})(W(\infty))]=0. \tag*{(68)} E [( G g a ) ( W ( ∞ ))] = 0. (68)
Combining (63) , (67) , and (68) yields
E [ x ‾ a ( W ( ∞ ) ) ] = − E [ ∑ r ∈ R q r C T M C ( W ( ∞ ) ) R r ( W ( ∞ ) ) ] . (69) \mathbb{E}[\overline{x}_a(W(\infty))]=-\mathbb{E}\left[\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W(\infty))R_r(W(\infty))\right]. \tag*{(69)} E [ x a ( W ( ∞ ))] = − E [ r ∈ R ∑ q r CTMC ( W ( ∞ )) R r ( W ( ∞ )) ] . (69)
Therefore, by (66) and A1,
∣ E [ x ‾ a ( W ( ∞ ) ) ] ∣ ≤ C 2 2 M 2 E [ ∑ r ∈ R q r C T M C ( W ( ∞ ) ) ] ≤ c C 2 2 M . (70) \left|\mathbb{E}[\overline{x}_a(W(\infty))]\right|\leq\frac{C_2}{2M^2}\mathbb{E}\left[\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W(\infty))\right]\leq\frac{cC_2}{2M}. \tag*{(70)} ∣ E [ x a ( W ( ∞ ))] ∣ ≤ 2 M 2 C 2 E [ r ∈ R ∑ q r CTMC ( W ( ∞ )) ] ≤ 2 M c C 2 . (70)
We next use A7 to bound the second and fourth moments. Adding and subtracting E [ x a ( W ( ∞ ) ) ] \mathbb{E}[x_a(W(\infty))] E [ x a ( W ( ∞ ))] therefore gives the exact decomposition
x ‾ a ( W ( ∞ ) ) = x a ( W ( ∞ ) ) − E [ x a ( W ( ∞ ) ) ] ⏟ centered fluctuation + E [ x a ( W ( ∞ ) ) ] − x a ∗ ⏟ E [ x ‾ a ( W ( ∞ ) ) ] . (71) \overline{x}_a(W(\infty))=\underbrace{x_a(W(\infty))-\mathbb{E}[x_a(W(\infty))]}_{\text{centered fluctuation}}+\underbrace{\mathbb{E}[x_a(W(\infty))]-x_a^*}_{\mathbb{E}[\overline{x}_a(W(\infty))]}. \tag*{(71)} x a ( W ( ∞ )) = centered fluctuation x a ( W ( ∞ )) − E [ x a ( W ( ∞ ))] + E [ x a ( W ( ∞ ))] E [ x a ( W ( ∞ ))] − x a ∗ . (71)
Hence, for p ∈ { 2 , 4 } p\in\{2,4\} p ∈ { 2 , 4 } , the inequality ∣ x + y ∣ p ≤ 2 p − 1 ( ∣ x ∣ p + ∣ y ∣ p ) \lvert x+y\rvert^p\leq2^{p-1}(\lvert x\rvert^p+\lvert y\rvert^p) ∣ x + y ∣ p ≤ 2 p − 1 (∣ x ∣ p + ∣ y ∣ p ) yields
E ∣ x ‾ a ( W ( ∞ ) ) ∣ p ≤ 2 p − 1 E [ ∣ x a ( W ( ∞ ) ) − E [ x a ( W ( ∞ ) ) ] ∣ p ] + 2 p − 1 ∣ E [ x ‾ a ( W ( ∞ ) ) ] ∣ p . (72) \mathbb{E}\left|\overline{x}_a(W(\infty))\right|^p\leq2^{p-1}\mathbb{E}\left[\left|x_a(W(\infty))-\mathbb{E}[x_a(W(\infty))]\right|^p\right]+2^{p-1}\left|\mathbb{E}[\overline{x}_a(W(\infty))]\right|^p. \tag*{(72)} E ∣ x a ( W ( ∞ )) ∣ p ≤ 2 p − 1 E [ ∣ x a ( W ( ∞ )) − E [ x a ( W ( ∞ ))] ∣ p ] + 2 p − 1 ∣ E [ x a ( W ( ∞ ))] ∣ p . (72)
By (70) , the second term in (72) is O ( M − 2 ) O(M^{-2}) O ( M − 2 ) for p = 2 p=2 p = 2 and O ( M − 4 ) O(M^{-4}) O ( M − 4 ) for p = 4 p=4 p = 4 , both smaller than the corresponding bounds required in the lemma. Therefore it remains only to prove
E [ ∣ x a ( W ( ∞ ) ) − E [ x a ( W ( ∞ ) ) ] ∣ 2 ] ≤ C M , E [ ∣ x a ( W ( ∞ ) ) − E [ x a ( W ( ∞ ) ) ] ∣ 4 ] ≤ C M 2 . (73) \mathbb{E}\left[\left|x_a(W(\infty))-\mathbb{E}[x_a(W(\infty))]\right|^2\right]\leq\frac{C}{M},\qquad
\mathbb{E}\left[\left|x_a(W(\infty))-\mathbb{E}[x_a(W(\infty))]\right|^4\right]\leq\frac{C}{M^2}. \tag*{(73)} E [ ∣ x a ( W ( ∞ )) − E [ x a ( W ( ∞ ))] ∣ 2 ] ≤ M C , E [ ∣ x a ( W ( ∞ )) − E [ x a ( W ( ∞ ))] ∣ 4 ] ≤ M 2 C . (73)
Let P t = e t G P_t=e^{t\mathcal{G}} P t = e t G denote the time-t t t transition matrix of the CTMC. For any function f : W → R f:\mathcal{W}\to\mathbb{R} f : W → R ,
( P t f ) ( w ) = E [ f ( W ( t ) ) ∣ W ( 0 ) = w ] , P s + t = P s P t . (74) (P_tf)(w)=\mathbb{E}[f(W(t))\mid W(0)=w],\qquad P_{s+t}=P_sP_t. \tag*{(74)} ( P t f ) ( w ) = E [ f ( W ( t )) ∣ W ( 0 ) = w ] , P s + t = P s P t . (74)
Fix T > 0 T>0 T > 0 and start the chain in stationarity. Then W ( T ) W(T) W ( T ) has the same distribution as W ( ∞ ) W(\infty) W ( ∞ ) , and
x a ( W ( T ) ) − E [ x a ( W ( ∞ ) ) ] = x a ( W ( T ) ) − P T x a ( W ( 0 ) ) ⏟ prediction error + P T x a ( W ( 0 ) ) − E [ x a ( W ( ∞ ) ) ] ⏟ mixing error . (75) x_a(W(T))-\mathbb{E}[x_a(W(\infty))]=\underbrace{x_a(W(T))-P_Tx_a(W(0))}_{\text{prediction error}}+\underbrace{P_Tx_a(W(0))-\mathbb{E}[x_a(W(\infty))]}_{\text{mixing error}}. \tag*{(75)} x a ( W ( T )) − E [ x a ( W ( ∞ ))] = prediction error x a ( W ( T )) − P T x a ( W ( 0 )) + mixing error P T x a ( W ( 0 )) − E [ x a ( W ( ∞ ))] . (75)
Hence, for p ∈ { 2 , 4 } p\in\{2,4\} p ∈ { 2 , 4 } and any T > 0 T>0 T > 0 ,
E [ ∣ x a ( W ( ∞ ) ) − E [ x a ( W ( ∞ ) ) ] ∣ p ] ≤ 2 p − 1 E [ ∣ x a ( W ( T ) ) − P T x a ( W ( 0 ) ) ∣ p ] + 2 p − 1 sup w ∈ W ∣ P T x a ( w ) − E [ x a ( W ( ∞ ) ) ] ∣ p . (76) \mathbb{E}\left[\left|x_a(W(\infty))-\mathbb{E}[x_a(W(\infty))]\right|^p\right]\leq2^{p-1}\mathbb{E}\left[\left|x_a(W(T))-P_Tx_a(W(0))\right|^p\right]+2^{p-1}\sup_{w\in\mathcal{W}}\left|P_Tx_a(w)-\mathbb{E}[x_a(W(\infty))]\right|^p. \tag*{(76)} E [ ∣ x a ( W ( ∞ )) − E [ x a ( W ( ∞ ))] ∣ p ] ≤ 2 p − 1 E [ ∣ x a ( W ( T )) − P T x a ( W ( 0 )) ∣ p ] + 2 p − 1 w ∈ W sup ∣ P T x a ( w ) − E [ x a ( W ( ∞ ))] ∣ p . (76)
We control the two terms on the right-hand side of (76) separately. We first use A7 to show that the mixing error vanishes exponentially in T T T . We then bound the second and fourth moments of the prediction error uniformly in T T T and the initial state.
We begin with the mixing error. For t ≥ 0 t\geq0 t ≥ 0 , define
K a ( t ) = sup w ∼ w ~ ∣ P t x a ( w ) − P t x a ( w ~ ) ∣ d ( w , w ~ ) . (77) K_a(t)=\sup_{w\sim\widetilde{w}}\frac{\left|P_tx_a(w)-P_tx_a(\widetilde{w})\right|}{d(w,\widetilde{w})}. \tag*{(77)} K a ( t ) = w ∼ w sup d ( w , w ) ∣ P t x a ( w ) − P t x a ( w ) ∣ . (77)
We first extend this neighboring-pair bound to arbitrary pairs. Fix w , w ~ ∈ W w,\widetilde{w}\in\mathcal{W} w , w ∈ W . By A7, there exists a neighboring path w = w ( 0 ) , … , w ( L ) = w ~ w=w^{(0)},\ldots,w^{(L)}=\widetilde{w} w = w ( 0 ) , … , w ( L ) = w such that
d ( w , w ~ ) = ∑ ℓ = 1 L d ( w ( ℓ − 1 ) , w ( ℓ ) ) . (78) d(w,\widetilde{w})=\sum_{\ell=1}^{L}d\left(w^{(\ell-1)},w^{(\ell)}\right). \tag*{(78)} d ( w , w ) = ℓ = 1 ∑ L d ( w ( ℓ − 1 ) , w ( ℓ ) ) . (78)
For each edge on this path, the definition of K a ( t ) K_a(t) K a ( t ) gives
∣ P t x a ( w ( ℓ − 1 ) ) − P t x a ( w ( ℓ ) ) ∣ ≤ K a ( t ) d ( w ( ℓ − 1 ) , w ( ℓ ) ) , ℓ = 1 , … , L . (79) \left|P_t x_a\left(w^{(\ell-1)}\right)-P_t x_a\left(w^{(\ell)}\right)\right|\leq K_a(t)d\left(w^{(\ell-1)},w^{(\ell)}\right),\qquad\ell=1,\ldots,L. \tag*{(79)} P t x a ( w ( ℓ − 1 ) ) − P t x a ( w ( ℓ ) ) ≤ K a ( t ) d ( w ( ℓ − 1 ) , w ( ℓ ) ) , ℓ = 1 , … , L . (79)
Therefore, by telescoping, the triangle inequality, and (78),
∣ P t x a ( w ) − P t x a ( w ~ ) ∣ ≤ K a ( t ) d ( w , w ~ ) . (80) \left|P_t x_a(w)-P_t x_a(\widetilde{w})\right|\leq K_a(t)d(w,\widetilde{w}). \tag*{(80)} ∣ P t x a ( w ) − P t x a ( w ) ∣ ≤ K a ( t ) d ( w , w ) . (80)
Fix a neighboring pair w ∼ w ~ w\sim\widetilde{w} w ∼ w . Let W w W^w W w and W w ~ W^{\widetilde{w}} W w denote the two copies of the CTMC under the coupling in A7, started from w w w and w ~ \widetilde{w} w , respectively. The expansion of the coupled-generator, denoted by G c \mathcal{G}^c G c , gives
E [ d ( W w ( h ) , W w ~ ( h ) ) ] = d ( w , w ~ ) + h ( G c d ) ( w , w ~ ) + o ( h ) ≤ ( 1 − κ c h ) d ( w , w ~ ) + o ( h ) . (81) \begin{aligned}
\mathbb{E}\left[d\left(W^w(h),W^{\widetilde{w}}(h)\right)\right]=d(w,\widetilde{w})+h(\mathcal{G}^c d)(w,\widetilde{w})+o(h) \\
&\leq(1-\kappa_c h)d(w,\widetilde{w})+o(h). \tag*{(81)}
\end{aligned} E [ d ( W w ( h ) , W w ( h ) ) ] = d ( w , w ) + h ( G c d ) ( w , w ) + o ( h ) ≤ ( 1 − κ c h ) d ( w , w ) + o ( h ) . (81)
For each fixed M M M , there are finitely many neighboring pairs, so the o ( h ) o(h) o ( h ) term can be chosen uniformly over them. Since d ( w , w ~ ) ≥ 1 d(w,\widetilde{w})\geq1 d ( w , w ) ≥ 1 for neighboring pairs, there exists ε ( h ) → 0 \varepsilon(h)\to0 ε ( h ) → 0 as h ↓ 0 h\downarrow0 h ↓ 0 such that
E [ d ( W w ( h ) , W w ~ ( h ) ) ] ≤ ( 1 − κ c h + h ε ( h ) ) d ( w , w ~ ) . (82) \mathbb{E}\left[d\left(W^w(h),W^{\widetilde{w}}(h)\right)\right]\leq(1-\kappa_c h+h\varepsilon(h))d(w,\widetilde{w}). \tag*{(82)} E [ d ( W w ( h ) , W w ( h ) ) ] ≤ ( 1 − κ c h + h ε ( h )) d ( w , w ) . (82)
By the Markov property, P t + h = P h P t P_{t+h}=P_hP_t P t + h = P h P t . Since the coupling in A7 has CTMCs started from w w w and w ~ \widetilde{w} w as its two marginals,
P t + h x a ( w ) = E [ P t x a ( W w ( h ) ) ] , P t + h x a ( w ~ ) = E [ P t x a ( W w ~ ( h ) ) ] . (83) P_{t+h}x_a(w)=\mathbb{E}\left[P_t x_a\left(W^w(h)\right)\right],\qquad P_{t+h}x_a(\widetilde{w})=\mathbb{E}\left[P_t x_a\left(W^{\widetilde{w}}(h)\right)\right]. \tag*{(83)} P t + h x a ( w ) = E [ P t x a ( W w ( h ) ) ] , P t + h x a ( w ) = E [ P t x a ( W w ( h ) ) ] . (83)
Hence, by (80) and (82), the following inequality holds for any w ∼ w ~ w\sim\widetilde{w} w ∼ w
∣ P t + h x a ( w ) − P t + h x a ( w ~ ) ∣ ≤ ( 1 − κ c h + h ε ( h ) ) K a ( t ) d ( w , w ~ ) , (84) \left|P_{t+h}x_a(w)-P_{t+h}x_a(\widetilde{w})\right|\leq(1-\kappa_c h+h\varepsilon(h))K_a(t)d(w,\widetilde{w}), \tag*{(84)} ∣ P t + h x a ( w ) − P t + h x a ( w ) ∣ ≤ ( 1 − κ c h + h ε ( h )) K a ( t ) d ( w , w ) , (84)
and therefore
K a ( t + h ) ≤ ( 1 − κ c h + h ε ( h ) ) K a ( t ) . (85) K_a(t+h)\leq(1-\kappa_c h+h\varepsilon(h))K_a(t). \tag*{(85)} K a ( t + h ) ≤ ( 1 − κ c h + h ε ( h )) K a ( t ) . (85)
The explicit linear form of x a x_a x a and A2 give the initial bound. For a neighboring pair w ∼ w ~ w\sim\widetilde{w} w ∼ w , define
I ( w , w ~ ) = { m : w m ≠ w ~ m } . (86) \mathcal{I}(w,\widetilde{w})=\{m:w_m\ne\widetilde{w}_m\}. \tag*{(86)} I ( w , w ) = { m : w m = w m } . (86)
Since P 0 x a = x a P_0x_a=x_a P 0 x a = x a , the exact initial value is
K a ( 0 ) = 1 M sup w ∼ w ~ ∣ ∑ m ∈ I ( w , w ~ ) a m T ( w m − w ~ m ) ∣ d ( w , w ~ ) . (87) K_a(0)=\frac{1}{M}\sup_{w\sim\widetilde{w}}\frac{\left|\sum_{m\in\mathcal{I}(w,\widetilde{w})}a_m^{\mathsf{T}}(w_m-\widetilde{w}_m)\right|}{d(w,\widetilde{w})}. \tag*{(87)} K a ( 0 ) = M 1 w ∼ w sup d ( w , w ) ∑ m ∈ I ( w , w ) a m T ( w m − w m ) . (87)
By A2 _2 2 , ∣ I ( w , w ~ ) ∣ ≤ c e \lvert\mathcal{I}(w,\widetilde{w})\rvert\le c_e ∣ I ( w , w )∣ ≤ c e . Since each block is a reduced one-hot state, any two block states satisfy ∥ w m − w ~ m ∥ ≤ 2 \lVert w_m-\widetilde{w}_m\rVert\le\sqrt{2} ∥ w m − w m ∥ ≤ 2 . Therefore, for ∥ a ∥ max ≤ 1 \lVert a\rVert_{\max}\le1 ∥ a ∥ m a x ≤ 1 ,
∣ ∑ m ∈ I ( w , w ~ ) a m T ( w m − w ~ m ) ∣ ≤ ∑ m ∈ I ( w , w ~ ) ∥ a m ∥ ∥ w m − w ~ m ∥ ≤ 2 c e . (88) \left\lvert\sum_{m\in\mathcal{I}(w,\widetilde{w})} a_m^{\mathsf{T}}(w_m-\widetilde{w}_m)\right\rvert\le\sum_{m\in\mathcal{I}(w,\widetilde{w})}\lVert a_m\rVert\lVert w_m-\widetilde{w}_m\rVert\le\sqrt{2}c_e. \tag*{(88)} m ∈ I ( w , w ) ∑ a m T ( w m − w m ) ≤ m ∈ I ( w , w ) ∑ ∥ a m ∥ ∥ w m − w m ∥ ≤ 2 c e . (88)
Since A7 _7 7 gives d ( w , w ~ ) ≥ 1 d(w,\widetilde{w})\ge1 d ( w , w ) ≥ 1 for neighboring states, (87) yields
K a ( 0 ) ≤ 2 c e M . (89) K_a(0)\le\frac{\sqrt{2}c_e}{M}. \tag*{(89)} K a ( 0 ) ≤ M 2 c e . (89)
Fix t > 0 t>0 t > 0 and take h = t / k h=t/k h = t / k . For all sufficiently large k k k , iterating (85) k k k times gives
K a ( t ) ≤ ( 1 − κ c t k + t k ε ( t / k ) ) k K a ( 0 ) . (90) K_a(t)\le\left(1-\frac{\kappa_c t}{k}+\frac{t}{k}\varepsilon(t/k)\right)^k K_a(0). \tag*{(90)} K a ( t ) ≤ ( 1 − k κ c t + k t ε ( t / k ) ) k K a ( 0 ) . (90)
Since ε ( t / k ) → 0 \varepsilon(t/k)\to0 ε ( t / k ) → 0 , the right-hand side of (90) converges to e − κ c t K a ( 0 ) e^{-\kappa_c t}K_a(0) e − κ c t K a ( 0 ) . Since the left-hand side does not depend on k k k , taking k → ∞ k\to\infty k → ∞ yields
K a ( t ) ≤ e − κ c t K a ( 0 ) . (91) K_a(t)\le e^{-\kappa_c t}K_a(0). \tag*{(91)} K a ( t ) ≤ e − κ c t K a ( 0 ) . (91)
Combining (80) , (89) , and (91) ,
∣ P t x a ( w ) − P t x a ( w ~ ) ∣ ≤ 2 c e M e − κ c t d ( w , w ~ ) , t ≥ 0. (92) \lvert P_t x_a(w)-P_t x_a(\widetilde{w})\rvert\le\frac{\sqrt{2}c_e}{M}e^{-\kappa_c t}d(w,\widetilde{w}),\qquad t\ge0. \tag*{(92)} ∣ P t x a ( w ) − P t x a ( w )∣ ≤ M 2 c e e − κ c t d ( w , w ) , t ≥ 0. (92)
The contraction in (92) now controls the mixing error in (76) . By stationarity,
E [ P t x a ( W ( ∞ ) ) ] = E [ x a ( W ( ∞ ) ) ] . (93) \mathbb{E}[P_t x_a(W(\infty))]=\mathbb{E}[x_a(W(\infty))]. \tag*{(93)} E [ P t x a ( W ( ∞ ))] = E [ x a ( W ( ∞ ))] . (93)
Therefore, by (92) and A7 _7 7 ,
∣ P t x a ( w ) − E [ x a ( W ( ∞ ) ) ] ∣ = ∣ P t x a ( w ) − E [ P t x a ( W ( ∞ ) ) ] ∣ ≤ E [ ∣ P t x a ( w ) − P t x a ( W ( ∞ ) ) ∣ ] ≤ 2 c e M e − κ c t E [ d ( w , W ( ∞ ) ) ] , (94) \begin{aligned}
\lvert P_t x_a(w)-\mathbb{E}[x_a(W(\infty))]\rvert
&=\lvert P_t x_a(w)-\mathbb{E}[P_t x_a(W(\infty))]\rvert\\
&\le\mathbb{E}[\lvert P_t x_a(w)-P_t x_a(W(\infty))\rvert]\\
&\le\frac{\sqrt{2}c_e}{M}e^{-\kappa_c t}\mathbb{E}[d(w,W(\infty))], \tag*{(94)}
\end{aligned} ∣ P t x a ( w ) − E [ x a ( W ( ∞ ))]∣ = ∣ P t x a ( w ) − E [ P t x a ( W ( ∞ ))]∣ ≤ E [∣ P t x a ( w ) − P t x a ( W ( ∞ ))∣] ≤ M 2 c e e − κ c t E [ d ( w , W ( ∞ ))] , (94)
which implies that
sup w ∈ W ∣ P T x a ( w ) − E [ x a ( W ( ∞ ) ) ] ∣ ≤ 2 c e M diam ( W ) e − κ c T . (95) \sup_{w\in\mathcal{W}}\lvert P_Tx_a(w)-\mathbb{E}[x_a(W(\infty))]\rvert\le\frac{\sqrt{2}c_e}{M}\operatorname{diam}(\mathcal{W})e^{-\kappa_cT}. \tag*{(95)} w ∈ W sup ∣ P T x a ( w ) − E [ x a ( W ( ∞ ))]∣ ≤ M 2 c e diam ( W ) e − κ c T . (95)
By (95) , the second term in (76) vanishes exponentially as T → ∞ T\to\infty T → ∞ . Therefore, it remains to prove, uniformly in T T T and the initial state,
E [ ∣ x a ( W ( T ) ) − P T x a ( W ( 0 ) ) ∣ 2 ] ≤ C M , E [ ∣ x a ( W ( T ) ) − P T x a ( W ( 0 ) ) ∣ 4 ] ≤ C M 2 . (96) \mathbb{E}\left[\lvert x_a(W(T))-P_Tx_a(W(0))\rvert^2\right]\le\frac{C}{M},\qquad
\mathbb{E}\left[\lvert x_a(W(T))-P_Tx_a(W(0))\rvert^4\right]\le\frac{C}{M^2}. \tag*{(96)} E [ ∣ x a ( W ( T )) − P T x a ( W ( 0 )) ∣ 2 ] ≤ M C , E [ ∣ x a ( W ( T )) − P T x a ( W ( 0 )) ∣ 4 ] ≤ M 2 C . (96)
To establish (96) , fix T > 0 T>0 T > 0 and an arbitrary initial state, and let F t \mathcal{F}_t F t be the history of the CTMC up to time t t t . Define the conditional prediction
M t = E [ x a ( W ( T ) ) ∣ F t ] = P T − t x a ( W ( t ) ) , 0 ≤ t ≤ T . (97) \mathcal{M}_t=\mathbb{E}[x_a(W(T))\mid\mathcal{F}_t]=P_{T-t}x_a(W(t)),\qquad0\le t\le T. \tag*{(97)} M t = E [ x a ( W ( T )) ∣ F t ] = P T − t x a ( W ( t )) , 0 ≤ t ≤ T . (97)
The second equality follows from the Markov property. Thus M t \mathcal{M}_t M t is the conditional prediction, at time t t t , of the terminal value x a ( W ( T ) ) x_a(W(T)) x a ( W ( T )) . For $0 \le s \le t \le T$, the tower property gives
E [ M t ∣ F s ] = E [ E [ x a ( W ( T ) ) ∣ F t ] | F s ] = E [ x a ( W ( T ) ) ∣ F s ] = M s . (98) \mathbb{E}[\mathcal{M}_t \mid\mathcal{F}_s] = \mathbb{E}\left[\mathbb{E}[x_a(W(T)) \mid\mathcal{F}_t] \,\middle|\, \mathcal{F}_s\right] = \mathbb{E}[x_a(W(T)) \mid\mathcal{F}_s] = \mathcal{M}_s. \tag*{(98)} E [ M t ∣ F s ] = E [ E [ x a ( W ( T )) ∣ F t ] ∣ F s ] = E [ x a ( W ( T )) ∣ F s ] = M s . (98)
Hence ( M t ) 0 ≤ t ≤ T (\mathcal{M}_t)_{0\le t\le T} ( M t ) 0 ≤ t ≤ T is a martingale. Define the centered conditional prediction
Z t = M t − M 0 , 0 ≤ t ≤ T . (99) Z_t = \mathcal{M}_t - \mathcal{M}_0, \qquad0 \le t \le T. \tag*{(99)} Z t = M t − M 0 , 0 ≤ t ≤ T . (99)
Then Z t Z_t Z t is a martingale and Z 0 = 0 Z_0 = 0 Z 0 = 0 .
If a feasible transition of type r r r occurs from state w w w at time t t t , we further define
δ r ( t , w ) = P T − t x a ( w + Δ r ) − P T − t x a ( w ) . (100) \delta_r(t,w) = P_{T-t}x_a(w+\Delta_r) - P_{T-t}x_a(w). \tag*{(100)} δ r ( t , w ) = P T − t x a ( w + Δ r ) − P T − t x a ( w ) . (100)
Since the two states are neighboring, (92) and A7 imply
∣ δ r ( t , w ) ∣ ≤ 2 c e D e M e − κ c ( T − t ) . (101) \lvert\delta_r(t,w)\rvert\le\frac{\sqrt{2}c_eD_e}{M}e^{-\kappa_c(T-t)}. \tag*{(101)} ∣ δ r ( t , w )∣ ≤ M 2 c e D e e − κ c ( T − t ) . (101)
Since Z t Z_t Z t is F t \mathcal{F}_t F t -measurable, expanding the square and conditioning on F t \mathcal{F}_t F t gives
E [ Z t + h 2 − Z t 2 ∣ F t ] = 2 Z t E [ Z t + h − Z t ∣ F t ] + E [ ( Z t + h − Z t ) 2 ∣ F t ] = E [ ( Z t + h − Z t ) 2 ∣ F t ] , (102) \begin{aligned}
\mathbb{E}[Z_{t+h}^2-Z_t^2\mid\mathcal{F}_t] = 2Z_t\mathbb{E}[Z_{t+h}-Z_t\mid\mathcal{F}_t] + \mathbb{E}[(Z_{t+h}-Z_t)^2\mid\mathcal{F}_t] \\
&= \mathbb{E}[(Z_{t+h}-Z_t)^2\mid\mathcal{F}_t], \tag*{(102)}
\end{aligned} E [ Z t + h 2 − Z t 2 ∣ F t ] = 2 Z t E [ Z t + h − Z t ∣ F t ] + E [( Z t + h − Z t ) 2 ∣ F t ] = E [( Z t + h − Z t ) 2 ∣ F t ] , (102)
where the last equality holds because Z t Z_t Z t is a martingale. For sufficiently small h > 0 h>0 h > 0 , we have
E [ Z t + h 2 − Z t 2 ∣ F t ] = h ∑ r ∈ R q r C T M C ( W ( t ) ) δ r ( t , W ( t ) ) 2 + o ( h ) . (103) \mathbb{E}[Z_{t+h}^2-Z_t^2\mid\mathcal{F}_t] = h\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W(t))\delta_r(t,W(t))^2+o(h). \tag*{(103)} E [ Z t + h 2 − Z t 2 ∣ F t ] = h r ∈ R ∑ q r CTMC ( W ( t )) δ r ( t , W ( t ) ) 2 + o ( h ) . (103)
Taking expectations and using the tower property,
E [ Z t + h 2 ] − E [ Z t 2 ] = h E [ ∑ r ∈ R q r C T M C ( W ( t ) ) δ r ( t , W ( t ) ) 2 ] + o ( h ) (104) \mathbb{E}[Z_{t+h}^2]-\mathbb{E}[Z_t^2] = h\mathbb{E}\left[\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W(t))\delta_r(t,W(t))^2\right]+o(h) \tag*{(104)} E [ Z t + h 2 ] − E [ Z t 2 ] = h E [ r ∈ R ∑ q r CTMC ( W ( t )) δ r ( t , W ( t ) ) 2 ] + o ( h ) (104)
where the remainder remains o ( h ) o(h) o ( h ) after taking expectation because the remainder in (103) can be chosen to be uniform over the finite state space. Dividing by h h h gives
E [ Z t + h 2 ] − E [ Z t 2 ] h = E [ ∑ r ∈ R q r C T M C ( W ( t ) ) δ r ( t , W ( t ) ) 2 ] + o ( 1 ) . (105) \frac{\mathbb{E}[Z_{t+h}^2]-\mathbb{E}[Z_t^2]}{h} = \mathbb{E}\left[\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W(t))\delta_r(t,W(t))^2\right]+o(1). \tag*{(105)} h E [ Z t + h 2 ] − E [ Z t 2 ] = E [ r ∈ R ∑ q r CTMC ( W ( t )) δ r ( t , W ( t ) ) 2 ] + o ( 1 ) . (105)
Moreover, by A1 and (101) , for every w ∈ W w\in\mathcal{W} w ∈ W ,
∑ r ∈ R q r C T M C ( w ) δ r ( t , w ) 2 ≤ ( ∑ r ∈ R q r C T M C ( w ) ) K 2 M 2 e − 2 κ c ( T − t ) ≤ c K 2 M e − 2 κ c ( T − t ) = : a 2 ( t ) , (106) \begin{aligned}
\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(w)\delta_r(t,w)^2 \le\left(\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(w)\right)\frac{K^2}{M^2}e^{-2\kappa_c(T-t)} \\
&\le\frac{cK^2}{M}e^{-2\kappa_c(T-t)}=:a_2(t), \tag*{(106)}
\end{aligned} r ∈ R ∑ q r CTMC ( w ) δ r ( t , w ) 2 ≤ ( r ∈ R ∑ q r CTMC ( w ) ) M 2 K 2 e − 2 κ c ( T − t ) ≤ M c K 2 e − 2 κ c ( T − t ) =: a 2 ( t ) , (106)
where K = 2 c e D e K=\sqrt{2}c_eD_e K = 2 c e D e . Letting h ↓ 0 h\downarrow0 h ↓ 0 in (105) and using (106) ,
d d t E [ Z t 2 ] = E [ ∑ r ∈ R q r C T M C ( W ( t ) ) δ r ( t , W ( t ) ) 2 ] ≤ a 2 ( t ) . (107) \frac{d}{dt}\mathbb{E}[Z_t^2]=\mathbb{E}\left[\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W(t))\delta_r(t,W(t))^2\right]\le a_2(t). \tag*{(107)} d t d E [ Z t 2 ] = E [ r ∈ R ∑ q r CTMC ( W ( t )) δ r ( t , W ( t ) ) 2 ] ≤ a 2 ( t ) . (107)
Since Z 0 = 0 Z_0 = 0 Z 0 = 0 ,
E [ Z t 2 ] ≤ ∫ 0 t a 2 ( s ) d s ≤ c K 2 2 κ c M ′ , 0 ≤ t ≤ T . (108) \mathbb{E}[Z_t^2] \le\int_0^t a_2(s)\,\mathrm{d}s \le\frac{cK^2}{2\kappa_c M'}, \qquad0 \le t \le T. \tag*{(108)} E [ Z t 2 ] ≤ ∫ 0 t a 2 ( s ) d s ≤ 2 κ c M ′ c K 2 , 0 ≤ t ≤ T . (108)
For the fourth moment, we can similarly obtain
d d t E [ Z t 4 ] = E [ ∑ r ∈ R q r C T M C ( W ( t ) ) ( 6 Z t 2 δ r 2 + 4 Z t δ r 3 + δ r 4 ) ] , (109) \frac{\mathrm{d}}{\mathrm{d}t}\mathbb{E}[Z_t^4] = \mathbb{E}\left[\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W(t))\left(6Z_t^2\delta_r^2+4Z_t\delta_r^3+\delta_r^4\right)\right], \tag*{(109)} d t d E [ Z t 4 ] = E [ r ∈ R ∑ q r CTMC ( W ( t )) ( 6 Z t 2 δ r 2 + 4 Z t δ r 3 + δ r 4 ) ] , (109)
where δ r = δ r ( t , W ( t ) ) \delta_r = \delta_r(t,W(t)) δ r = δ r ( t , W ( t )) . Since 4 ∣ x ∣ ∣ y ∣ 3 ≤ 2 x 2 y 2 + 2 y 4 4|x||y|^3 \le2x^2y^2 + 2y^4 4∣ x ∣∣ y ∣ 3 ≤ 2 x 2 y 2 + 2 y 4 ,
d d t E [ Z t 4 ] ≤ 8 a 2 ( t ) E [ Z t 2 ] + 3 a 4 ( t ) , a 4 ( t ) = c K 4 M 3 e − 4 κ c ( T − t ) . (110) \frac{\mathrm{d}}{\mathrm{d}t}\mathbb{E}[Z_t^4] \le8a_2(t)\mathbb{E}[Z_t^2] + 3a_4(t), \qquad a_4(t)=\frac{cK^4}{M^3}e^{-4\kappa_c(T-t)}. \tag*{(110)} d t d E [ Z t 4 ] ≤ 8 a 2 ( t ) E [ Z t 2 ] + 3 a 4 ( t ) , a 4 ( t ) = M 3 c K 4 e − 4 κ c ( T − t ) . (110)
Integrating (110) from 0 to t ≤ T t \le T t ≤ T and using (108) ,
E [ Z t 4 ] ≤ 8 sup 0 ≤ s ≤ t E [ Z s 2 ] ∫ 0 t a 2 ( s ) d s + 3 ∫ 0 t a 4 ( s ) d s ≤ C M 2 , 0 ≤ t ≤ T . (111) \mathbb{E}[Z_t^4] \le8\sup_{0\le s\le t}\mathbb{E}[Z_s^2]\int_0^t a_2(s)\,\mathrm{d}s+3\int_0^t a_4(s)\,\mathrm{d}s\le\frac{C}{M^2}, \qquad0\le t\le T. \tag*{(111)} E [ Z t 4 ] ≤ 8 0 ≤ s ≤ t sup E [ Z s 2 ] ∫ 0 t a 2 ( s ) d s + 3 ∫ 0 t a 4 ( s ) d s ≤ M 2 C , 0 ≤ t ≤ T . (111)
Thus
E [ Z t 2 ] ≤ C M ′ , E [ Z t 4 ] ≤ C M 2 , 0 ≤ t ≤ T . (112) \mathbb{E}[Z_t^2]\le\frac{C}{M'}, \qquad\mathbb{E}[Z_t^4]\le\frac{C}{M^2}, \qquad0\le t\le T. \tag*{(112)} E [ Z t 2 ] ≤ M ′ C , E [ Z t 4 ] ≤ M 2 C , 0 ≤ t ≤ T . (112)
We observe that
Z T = x a ( W ( T ) ) − P T x a ( W ( 0 ) ) . (113) Z_T=x_a(W(T))-P_Tx_a(W(0)). \tag*{(113)} Z T = x a ( W ( T )) − P T x a ( W ( 0 )) . (113)
Setting t = T t=T t = T in (112) therefore gives, uniformly over the initial state,
E [ ∣ Z T ∣ 2 ] = E [ ∣ x a ( W ( T ) ) − P T x a ( W ( 0 ) ) ∣ 2 ] ≤ C M ′ , E [ ∣ Z T ∣ 4 ] = E [ ∣ x a ( W ( T ) ) − P T x a ( W ( 0 ) ) ∣ 4 ] ≤ C M 2 . (114) \mathbb{E}[|Z_T|^2]=\mathbb{E}\left[\left|x_a(W(T))-P_Tx_a(W(0))\right|^2\right]\le\frac{C}{M'}, \qquad\mathbb{E}[|Z_T|^4]=\mathbb{E}\left[\left|x_a(W(T))-P_Tx_a(W(0))\right|^4\right]\le\frac{C}{M^2}. \tag*{(114)} E [ ∣ Z T ∣ 2 ] = E [ ∣ x a ( W ( T )) − P T x a ( W ( 0 )) ∣ 2 ] ≤ M ′ C , E [ ∣ Z T ∣ 4 ] = E [ ∣ x a ( W ( T )) − P T x a ( W ( 0 )) ∣ 4 ] ≤ M 2 C . (114)
Returning to the stationary chain, substitute (114) into (76) and let T → ∞ T\to\infty T → ∞ . The mixing term vanishes by (95) , so
E [ ∣ x a ( W ( ∞ ) ) − E [ x a ( W ( ∞ ) ) ] ∣ 2 ] ≤ C M ′ , E [ ∣ x a ( W ( ∞ ) ) − E [ x a ( W ( ∞ ) ) ] ∣ 4 ] ≤ C M 2 . (115) \mathbb{E}\left[\left|x_a(W(\infty))-\mathbb{E}[x_a(W(\infty))]\right|^2\right]\le\frac{C}{M'}, \qquad\mathbb{E}\left[\left|x_a(W(\infty))-\mathbb{E}[x_a(W(\infty))]\right|^4\right]\le\frac{C}{M^2}. \tag*{(115)} E [ ∣ x a ( W ( ∞ )) − E [ x a ( W ( ∞ ))] ∣ 2 ] ≤ M ′ C , E [ ∣ x a ( W ( ∞ )) − E [ x a ( W ( ∞ ))] ∣ 4 ] ≤ M 2 C . (115)
The bounds in (115) establish (73) . So the second- and fourth-moment bounds in the lemma hold.
Structural Modeling Conditions for A8-A9
A8-A9 are not easy to directly verify. Next, we will identify structural properties of the CTMC that guarantee A8-A9. These structural conditions concern only the functional form of the drift and the instantaneous covariance-rate matrix and can therefore be verified directly from the transition rules and the selected off-lattice extension. We verify these conditions for the power-of-two-choices model in § 6 .
S1 – Local approximately affine drift. There exist constants η A > 0 \eta_A > 0 η A > 0 and 1 ≤ C A < ∞ 1 \le C_A < \infty 1 ≤ C A < ∞ , independent of M M M and the realized parameter vector θ \theta θ , and moduli ω A ( s ) ↓ 0 \omega_A(s) \downarrow0 ω A ( s ) ↓ 0 and ω r ( s ) ↓ 0 \omega_r(s) \downarrow0 ω r ( s ) ↓ 0 as s ↓ 0 s \downarrow0 s ↓ 0 , such that the following holds. For each realized equilibrium interaction input x χ ∗ x_\chi^* x χ ∗ , there exist a matrix-valued function A ( x ; θ ) ∈ R ( n − 1 ) × ( n − 1 ) A(x;\theta) \in\mathbb{R}^{(n-1)\times(n-1)} A ( x ; θ ) ∈ R ( n − 1 ) × ( n − 1 ) , a vector-valued function a ( x ; θ ) ∈ R n − 1 a(x;\theta) \in\mathbb{R}^{n-1} a ( x ; θ ) ∈ R n − 1 , and a residual r ( v , x ; θ ) ∈ R n − 1 r(v,x;\theta) \in\mathbb{R}^{n-1} r ( v , x ; θ ) ∈ R n − 1 such that, for every v ∈ D n − 1 v \in D_{n-1} v ∈ D n − 1 , θ ∈ Θ \theta\in\Theta θ ∈ Θ , and x ∈ K χ x \in K_\chi x ∈ K χ satisfying ∥ x − x χ ∗ ∥ ≤ η A \lVert x-x_\chi^*\rVert\le\eta_A ∥ x − x χ ∗ ∥ ≤ η A ,
f ( v , Ψ ( x ) ; θ ) = A ( x ; θ ) v + a ( x ; θ ) + r ( v , x ; θ ) . (116) f(v,\Psi(x);\theta)=A(x;\theta)v+a(x;\theta)+r(v,x;\theta). \tag*{(116)} f ( v , Ψ ( x ) ; θ ) = A ( x ; θ ) v + a ( x ; θ ) + r ( v , x ; θ ) . (116)
The first and second derivatives of A A A and a a a with respect to x x x satisfy
sup θ ∈ Θ , x ∈ K χ ∥ x − x χ ∗ ∥ ≤ η A ( ∥ D A ( x ; θ ) ∥ + ∥ D 2 A ( x ; θ ) ∥ + ∥ D a ( x ; θ ) ∥ + ∥ D 2 a ( x ; θ ) ∥ ) ≤ C A . (117) \sup_{\substack{\theta\in\Theta,\ x\in K_\chi\\ \lVert x-x_\chi^*\rVert\le\eta_A}}
\left(\lVert DA(x;\theta)\rVert+\lVert D^2A(x;\theta)\rVert+\lVert Da(x;\theta)\rVert+\lVert D^2a(x;\theta)\rVert\right)\le C_A. \tag*{(117)} θ ∈ Θ , x ∈ K χ ∥ x − x χ ∗ ∥ ≤ η A sup ( ∥ D A ( x ; θ )∥ + ∥ D 2 A ( x ; θ )∥ + ∥ D a ( x ; θ )∥ + ∥ D 2 a ( x ; θ )∥ ) ≤ C A . (117)
and their second derivatives satisfy the common modulus-of-continuity bound
sup θ ∈ Θ , x , y ∈ K χ ∥ x − x χ ∗ ∥ , ∥ y − x χ ∗ ∥ ≤ η A ∥ x − y ∥ ≤ s ( ∥ D 2 A ( x ; θ ) − D 2 A ( y ; θ ) ∥ + ∥ D 2 a ( x ; θ ) − D 2 a ( y ; θ ) ∥ ) ≤ ω A ( s ) . (118) \sup_{\substack{\theta\in\Theta,\ x,y\in K_\chi\\ \lVert x-x_\chi^*\rVert,\lVert y-x_\chi^*\rVert\le\eta_A\\ \lVert x-y\rVert\le s}}
\left(\lVert D^2A(x;\theta)-D^2A(y;\theta)\rVert+\lVert D^2a(x;\theta)-D^2a(y;\theta)\rVert\right)\le\omega_A(s). \tag*{(118)} θ ∈ Θ , x , y ∈ K χ ∥ x − x χ ∗ ∥ , ∥ y − x χ ∗ ∥ ≤ η A ∥ x − y ∥ ≤ s sup ( ∥ D 2 A ( x ; θ ) − D 2 A ( y ; θ )∥ + ∥ D 2 a ( x ; θ ) − D 2 a ( y ; θ )∥ ) ≤ ω A ( s ) . (118)
Moreover, for every x ∈ K χ x \in K_\chi x ∈ K χ satisfying ∥ x − x χ ∗ ∥ ≤ η A \lVert x-x_\chi^*\rVert\le\eta_A ∥ x − x χ ∗ ∥ ≤ η A ,
sup v ∈ D n − 1 , θ ∈ Θ ∥ r ( v , x ; θ ) ∥ ≤ ω r ( ∥ x − x χ ∗ ∥ ) ∥ x − x χ ∗ ∥ 2 . (119) \sup_{v\in D_{n-1},\ \theta\in\Theta}\lVert r(v,x;\theta)\rVert\le\omega_r(\lVert x-x_\chi^*\rVert)\lVert x-x_\chi^*\rVert^2. \tag*{(119)} v ∈ D n − 1 , θ ∈ Θ sup ∥ r ( v , x ; θ )∥ ≤ ω r (∥ x − x χ ∗ ∥) ∥ x − x χ ∗ ∥ 2 . (119)
Sharper condition: For the sharper mean-refinement rate, assume in addition that
ω A ( s ) + ω r ( s ) ≤ C A s , 0 ≤ s ≤ η A . (120) \omega_A(s)+\omega_r(s)\le C_As,\qquad0\le s\le\eta_A. \tag*{(120)} ω A ( s ) + ω r ( s ) ≤ C A s , 0 ≤ s ≤ η A . (120)
V b ( w ) = 1 M b ⊤ Q ( w ) b (121) V_b(w)=\frac{1}{M}b^\top Q(w)b \tag*{(121)} V b ( w ) = M 1 b ⊤ Q ( w ) b (121)
There exist constants K Q , C Q < ∞ K_Q,C_Q<\infty K Q , C Q < ∞ and η Q > 0 \eta_Q>0 η Q > 0 , independent of M M M and θ \theta θ , such that for every ∥ b ∥ max ≤ 1 \lVert b\rVert_{\max}\le1 ∥ b ∥ m a x ≤ 1 there are block vectors c 1 , b , … , c K Q , b c_{1,b},\ldots,c_{K_Q,b} c 1 , b , … , c K Q , b and a twice continuously differentiable function V ^ b : R K Q → R \widehat V_b:\mathbb{R}^{K_Q}\to\mathbb{R} V b : R K Q → R satisfying
V b ( w ) = V ^ b ( x ˉ c 1 , b ( w ) , … , x ˉ c K Q , b ( w ) ) (122) V_b(w)=\widehat V_b\left(\bar x_{c_{1,b}}(w),\ldots,\bar x_{c_{K_Q,b}}(w)\right) \tag*{(122)} V b ( w ) = V b ( x ˉ c 1 , b ( w ) , … , x ˉ c K Q , b ( w ) ) (122)
whenever max k ∣ x ˉ c k , b ( w ) ∣ ≤ η Q \max_k|\bar x_{c_{k,b}}(w)|\le\eta_Q max k ∣ x ˉ c k , b ( w ) ∣ ≤ η Q and
max 1 ≤ k ≤ K Q ∥ c k , b ∥ max + ∣ V ^ b ( 0 ) ∣ + sup ∥ z ∥ ∞ ≤ η Q ( ∥ D V ^ b ( z ) ∥ + ∥ D 2 V ^ b ( z ) ∥ ) ≤ C Q . (123) \max_{1\le k\le K_Q}\lVert c_{k,b}\rVert_{\max}+|\widehat V_b(0)|+
\sup_{\lVert z\rVert_\infty\le\eta_Q}
\left(\lVert D\widehat V_b(z)\rVert+\lVert D^2\widehat V_b(z)\rVert\right)\le C_Q. \tag*{(123)} 1 ≤ k ≤ K Q max ∥ c k , b ∥ m a x + ∣ V b ( 0 ) ∣ + ∥ z ∥ ∞ ≤ η Q sup ( ∥ D V b ( z )∥ + ∥ D 2 V b ( z )∥ ) ≤ C Q . (123)
The vectors c k , b c_{k,b} c k , b and the function V ^ b \widehat V_b V b may depend on M M M , θ \theta θ , and b b b , but K Q K_Q K Q , C Q C_Q C Q , and η Q \eta_Q η Q are uniform.
Remark 1. S1 does not make the full mean-field system linear. Rather, it requires the local drift to be affine in the state of one agent when the interaction input is fixed at its equilibrium value; the full system can remain nonlinear through x χ ( w ) x_\chi(w) x χ ( w ) . S2 is the analogous structural condition for the noise: near equilibrium, the instantaneous variance rate in any bounded macroscopic direction depends smoothly on only O ( 1 ) O(1) O ( 1 ) weighted occupancy deviations.
Lemma 2 (Verification of A8–A9 from structural conditions). Under A 1 A1 A 1 –A 7 A7 A 7 and the structural modeling conditions S 1 S1 S 1 –S 2 S2 S 2 , A 8 A8 A 8 and A 9 A9 A 9 hold. If the sharper condition in S 1 S1 S 1 holds, then the O ( M − 1 / 2 ) O(M^{-1/2}) O ( M − 1/2 ) version of the remainder bound in A 9 A9 A 9 also holds.
Proof. Condition on θ \theta θ and suppress this conditioning. We verify A 8 A8 A 8 and A 9 A9 A 9 in turn. Throughout, C C C denotes a finite generic constant, independent of M M M , θ \theta θ , and b b b , whose value may change from line to line. Write A m ( x ) = A ( x ; θ m ) A_m(x)=A(x;\theta_m) A m ( x ) = A ( x ; θ m ) , a m ( x ) = a ( x ; θ m ) a_m(x)=a(x;\theta_m) a m ( x ) = a ( x ; θ m ) , and r m ( v , x ) = r ( v , x ; θ m ) r_m(v,x)=r(v,x;\theta_m) r m ( v , x ) = r ( v , x ; θ m ) . Define the interaction-occupancy deviation
x ˉ χ ( w ) = x χ ( w ) − x χ ∗ . (124) \bar{x}_{\chi}(w)=x_{\chi}(w)-x_{\chi}^{*}. \tag*{(124)} x ˉ χ ( w ) = x χ ( w ) − x χ ∗ . (124)
Lemma 1 gives
E ∥ x ˉ χ ( W ( ∞ ) ) ∥ 2 = O ( M − 1 ) , E ∥ x ˉ χ ( W ( ∞ ) ) ∥ 4 = O ( M − 2 ) . (125) \mathbb{E}\lVert\bar{x}_{\chi}(W(\infty))\rVert^{2}=O(M^{-1}),\qquad\mathbb{E}\lVert\bar{x}_{\chi}(W(\infty))\rVert^{4}=O(M^{-2}). \tag*{(125)} E ∥ x ˉ χ ( W ( ∞ )) ∥ 2 = O ( M − 1 ) , E ∥ x ˉ χ ( W ( ∞ )) ∥ 4 = O ( M − 2 ) . (125)
Define the local S 1 S1 S 1 event
B A = { ∥ x ˉ χ ( W ( ∞ ) ) ∥ ≤ η A } . (126) \mathcal{B}_{A}=\{\lVert\bar{x}_{\chi}(W(\infty))\rVert\le\eta_{A}\}. \tag*{(126)} B A = {∥ x ˉ χ ( W ( ∞ ))∥ ≤ η A } . (126)
By (125) and Markov’s inequality,
P ( B A c ) ≤ E ∥ x ˉ χ ( W ( ∞ ) ) ∥ 4 η A 4 = O ( M − 2 ) . (127) \mathbb{P}(\mathcal{B}_{A}^{c})\le\frac{\mathbb{E}\lVert\bar{x}_{\chi}(W(\infty))\rVert^{4}}{\eta_{A}^{4}}=O(M^{-2}). \tag*{(127)} P ( B A c ) ≤ η A 4 E ∥ x ˉ χ ( W ( ∞ )) ∥ 4 = O ( M − 2 ) . (127)
We first show that the residual r ( v , x ; θ ) r(v,x;\theta) r ( v , x ; θ ) does not affect the equilibrium linearization or Hessian. Write w ˉ = w − w ∗ \bar{w}=w-w^{*} w ˉ = w − w ∗ and w ˉ m = w m − w m ∗ \bar{w}_{m}=w_{m}-w_{m}^{*} w ˉ m = w m − w m ∗ . By A 3 A3 A 3 and S 1 S1 S 1 , r m r_m r m is twice continuously differentiable in ( v , x ) (v,x) ( v , x ) . For every fixed v ∈ D n − 1 v\in D_{n-1} v ∈ D n − 1 , the residual bound in S 1 S1 S 1 gives
∥ r m ( v , x χ ∗ + h ) ∥ ∥ h ∥ 2 ≤ ω r ( ∥ h ∥ ) ⟶ 0 , h → 0. (128) \frac{\lVert r_m(v,x_{\chi}^{*}+h)\rVert}{\lVert h\rVert^{2}}\le\omega_r(\lVert h\rVert)\longrightarrow0,\qquad h\to0. \tag*{(128)} ∥ h ∥ 2 ∥ r m ( v , x χ ∗ + h )∥ ≤ ω r (∥ h ∥) ⟶ 0 , h → 0. (128)
Since ∥ χ ∥ ∞ > 0 \lVert\chi\rVert_{\infty}>0 ∥ χ ∥ ∞ > 0 , the convex set K χ K_{\chi} K χ has nonempty interior. Taking the limit through x χ ∗ + h ∈ K χ x_{\chi}^{*}+h\in K_{\chi} x χ ∗ + h ∈ K χ , Taylor expansion therefore implies that r m ( v , x χ ∗ ) r_m(v,x_{\chi}^{*}) r m ( v , x χ ∗ ) and its first two derivatives with respect to x x x vanish. Since r m ( v , x χ ∗ ) = 0 r_m(v,x_{\chi}^{*})=0 r m ( v , x χ ∗ ) = 0 for every v v v , its first two v v v -derivatives also vanish; and since D x r m ( v , x χ ∗ ) = 0 D_xr_m(v,x_{\chi}^{*})=0 D x r m ( v , x χ ∗ ) = 0 for every v v v , the mixed second derivatives vanish as well. Thus, with D D D denoting differentiation with respect to the pair ( v , x ) (v,x) ( v , x ) ,
r m ( v , x χ ∗ ) = 0 , D r m ( v , x χ ∗ ) = 0 , D 2 r m ( v , x χ ∗ ) = 0. (129) r_m(v,x_{\chi}^{*})=0,\qquad Dr_m(v,x_{\chi}^{*})=0,\qquad D^{2}r_m(v,x_{\chi}^{*})=0. \tag*{(129)} r m ( v , x χ ∗ ) = 0 , D r m ( v , x χ ∗ ) = 0 , D 2 r m ( v , x χ ∗ ) = 0. (129)
Consequently, the residual contributes neither to the equilibrium identity, the Jacobian J J J , nor the Hessian contraction H H H . In particular, A m ( x χ ∗ ) w m ∗ + a m ( x χ ∗ ) = 0 A_m(x_{\chi}^{*})w_m^{*}+a_m(x_{\chi}^{*})=0 A m ( x χ ∗ ) w m ∗ + a m ( x χ ∗ ) = 0 , and
[ J w ˉ ] m = A m ( x χ ∗ ) w ˉ m + D A m ( x χ ∗ ) [ x ˉ χ ( w ) ] w m ∗ + D a m ( x χ ∗ ) [ x ˉ χ ( w ) ] . (130) [J\bar{w}]_m=A_m(x_{\chi}^{*})\bar{w}_m+DA_m(x_{\chi}^{*})[\bar{x}_{\chi}(w)]w_m^{*}+Da_m(x_{\chi}^{*})[\bar{x}_{\chi}(w)]. \tag*{(130)} [ J w ˉ ] m = A m ( x χ ∗ ) w ˉ m + D A m ( x χ ∗ ) [ x ˉ χ ( w )] w m ∗ + D a m ( x χ ∗ ) [ x ˉ χ ( w )] . (130)
On B A \mathcal{B}_{A} B A , S 1 S1 S 1 gives
F m ( W ( ∞ ) ) = A m ( x χ ( W ( ∞ ) ) ) W m ( ∞ ) + a m ( x χ ( W ( ∞ ) ) ) + r m ( W m ( ∞ ) , x χ ( W ( ∞ ) ) ) . (131) F_m(W(\infty))=A_m(x_{\chi}(W(\infty)))W_m(\infty)+a_m(x_{\chi}(W(\infty)))+r_m(W_m(\infty),x_{\chi}(W(\infty))). \tag*{(131)} F m ( W ( ∞ )) = A m ( x χ ( W ( ∞ ))) W m ( ∞ ) + a m ( x χ ( W ( ∞ ))) + r m ( W m ( ∞ ) , x χ ( W ( ∞ ))) . (131)
More generally, for any w w w satisfying ∥ x ˉ χ ( w ) ∥ ≤ η A \lVert\bar{x}_{\chi}(w)\rVert\le\eta_A ∥ x ˉ χ ( w )∥ ≤ η A , define the first-order Taylor remainders
R A , m ( w ) = A m ( x χ ∗ + x ˉ χ ( w ) ) − A m ( x χ ∗ ) − D A m ( x χ ∗ ) [ x ˉ χ ( w ) ] , R a , m ( w ) = a m ( x χ ∗ + x ˉ χ ( w ) ) − a m ( x χ ∗ ) − D a m ( x χ ∗ ) [ x ˉ χ ( w ) ] . (132) \begin{aligned}
R_{A,m}(w)&=A_m(x_{\chi}^{*}+\bar{x}_{\chi}(w))-A_m(x_{\chi}^{*})-DA_m(x_{\chi}^{*})[\bar{x}_{\chi}(w)],\\
R_{a,m}(w)&=a_m(x_{\chi}^{*}+\bar{x}_{\chi}(w))-a_m(x_{\chi}^{*})-Da_m(x_{\chi}^{*})[\bar{x}_{\chi}(w)]. \tag*{(132)}
\end{aligned} R A , m ( w ) R a , m ( w ) = A m ( x χ ∗ + x ˉ χ ( w )) − A m ( x χ ∗ ) − D A m ( x χ ∗ ) [ x ˉ χ ( w )] , = a m ( x χ ∗ + x ˉ χ ( w )) − a m ( x χ ∗ ) − D a m ( x χ ∗ ) [ x ˉ χ ( w )] . (132)
Taylor’s theorem with integral remainder gives
R A , m ( w ) = ∫ 0 1 ( 1 − s ) D 2 A m ( x χ ∗ + s x ˉ χ ( w ) ) [ x ˉ χ ( w ) , x ˉ χ ( w ) ] d s , R_{A,m}(w)=\int_{0}^{1}(1-s)D^{2}A_m\left(x_\chi^*+s\bar{x}_\chi(w)\right)\left[\bar{x}_\chi(w),\bar{x}_\chi(w)\right]\,ds, R A , m ( w ) = ∫ 0 1 ( 1 − s ) D 2 A m ( x χ ∗ + s x ˉ χ ( w ) ) [ x ˉ χ ( w ) , x ˉ χ ( w ) ] d s ,
R a , m ( w ) = ∫ 0 1 ( 1 − s ) D 2 a m ( x χ ∗ + s x ˉ χ ( w ) ) [ x ˉ χ ( w ) , x ˉ χ ( w ) ] d s . (133) R_{a,m}(w)=\int_{0}^{1}(1-s)D^{2}a_m\left(x_\chi^*+s\bar{x}_\chi(w)\right)\left[\bar{x}_\chi(w),\bar{x}_\chi(w)\right]\,ds. \tag*{(133)} R a , m ( w ) = ∫ 0 1 ( 1 − s ) D 2 a m ( x χ ∗ + s x ˉ χ ( w ) ) [ x ˉ χ ( w ) , x ˉ χ ( w ) ] d s . (133)
Since the segment from x χ ∗ x_\chi^* x χ ∗ to x χ ∗ + x ˉ χ ( w ) x_\chi^*+\bar{x}_\chi(w) x χ ∗ + x ˉ χ ( w ) stays inside the local S1 neighborhood, the uniform second-derivative bound in (117) of S1 implies
∥ R A , m ( w ) ∥ + ∥ R a , m ( w ) ∥ ≤ C ∥ x ˉ χ ( w ) ∥ 2 . (134) \left\|R_{A,m}(w)\right\|+\left\|R_{a,m}(w)\right\|\leq C\left\|\bar{x}_\chi(w)\right\|^2. \tag*{(134)} ∥ R A , m ( w ) ∥ + ∥ R a , m ( w ) ∥ ≤ C ∥ x ˉ χ ( w ) ∥ 2 . (134)
for C = C A / 2 C=C_A/2 C = C A /2 . Recall w ˉ m = w m − w m ∗ \bar{w}_m=w_m-w_m^* w ˉ m = w m − w m ∗ . Substituting (132) into the S1 decomposition and using A m ( x χ ∗ ) w m ∗ + a m ( x χ ∗ ) = 0 A_m(x_\chi^*)w_m^*+a_m(x_\chi^*)=0 A m ( x χ ∗ ) w m ∗ + a m ( x χ ∗ ) = 0 yields
[ R F ( w ) ] m = D A m ( x χ ∗ ) [ x ˉ χ ( w ) ] w ˉ m + R A , m ( w ) w m + R a , m ( w ) + r m ( w m , x χ ∗ + x ˉ χ ( w ) ) . (135) [R_F(w)]_m=DA_m(x_\chi^*)[\bar{x}_\chi(w)]\bar{w}_m+R_{A,m}(w)w_m+R_{a,m}(w)+r_m(w_m,x_\chi^*+\bar{x}_\chi(w)). \tag*{(135)} [ R F ( w ) ] m = D A m ( x χ ∗ ) [ x ˉ χ ( w )] w ˉ m + R A , m ( w ) w m + R a , m ( w ) + r m ( w m , x χ ∗ + x ˉ χ ( w )) . (135)
For 1 ≤ i ≤ n − 1 1\leq i\leq n-1 1 ≤ i ≤ n − 1 and ∥ b ∥ max ≤ 1 \|b\|_{\max}\leq1 ∥ b ∥ m a x ≤ 1 , define the block vector c i , b R c^R_{i,b} c i , b R by c i , b , m R = ( D i A m ( x χ ∗ ) ) ⊤ b m c^R_{i,b,m}=(D_iA_m(x_\chi^*))^\top b_m c i , b , m R = ( D i A m ( x χ ∗ ) ) ⊤ b m . By (117) in S1 and x χ ∗ ∈ K χ x_\chi^*\in K_\chi x χ ∗ ∈ K χ ,
max 1 ≤ i ≤ n − 1 sup 1 ≤ m ≤ M ∥ D i A m ( x χ ∗ ) ∥ o p ≤ C A , ∥ c i , b R ∥ max ≤ C A . (136) \max_{1\leq i\leq n-1}\sup_{1\leq m\leq M}\left\|D_iA_m(x_\chi^*)\right\|_{\mathrm{op}}\leq C_A,\qquad\left\|c^R_{i,b}\right\|_{\max}\leq C_A. \tag*{(136)} 1 ≤ i ≤ n − 1 max 1 ≤ m ≤ M sup D i A m ( x χ ∗ ) op ≤ C A , c i , b R m a x ≤ C A . (136)
Define c i , b R = c i , b R / C A c^R_{i,b}=c^R_{i,b}/C_A c i , b R = c i , b R / C A . Then ∥ c i , b R ∥ max ≤ 1 \|c^R_{i,b}\|_{\max}\leq1 ∥ c i , b R ∥ m a x ≤ 1 and x ˉ c i , b R ( W ( ∞ ) ) = C A x ˉ c i , b R C A ( W ( ∞ ) ) \bar{x}_{c^R_{i,b}}(W(\infty))=C_A\bar{x}_{\frac{c^R_{i,b}}{C_A}}(W(\infty)) x ˉ c i , b R ( W ( ∞ )) = C A x ˉ C A c i , b R ( W ( ∞ )) . Hence Lemma 1 gives, uniformly in i i i and b b b ,
∣ E [ x ˉ c i , b R ( W ( ∞ ) ) ] ∣ ≤ C M , E ∣ x ˉ c i , b R ( W ( ∞ ) ) ∣ 2 ≤ C M , E ∣ x ˉ c i , b R ( W ( ∞ ) ) ∣ 4 ≤ C M 2 . (137) \left|\mathbb{E}\left[\bar{x}_{c^R_{i,b}}(W(\infty))\right]\right|\leq\frac{C}{M},\qquad
\mathbb{E}\left|\bar{x}_{c^R_{i,b}}(W(\infty))\right|^2\leq\frac{C}{M},\qquad
\mathbb{E}\left|\bar{x}_{c^R_{i,b}}(W(\infty))\right|^4\leq\frac{C}{M^2}. \tag*{(137)} E [ x ˉ c i , b R ( W ( ∞ )) ] ≤ M C , E x ˉ c i , b R ( W ( ∞ )) 2 ≤ M C , E x ˉ c i , b R ( W ( ∞ )) 4 ≤ M 2 C . (137)
By (134) , the residual bound in S1, and boundedness of the single-agent state space, on B A \mathcal{B}_A B A we have
1 M ∣ b ⊤ R F ( W ( ∞ ) ) ∣ ≤ C ( ∥ x ˉ χ ( W ( ∞ ) ) ∥ ∑ i = 1 n − 1 ∣ x ˉ c i , b R ( W ( ∞ ) ) ∣ + [ 1 + ω r ( ∥ x ˉ χ ( W ( ∞ ) ) ∥ ) ] ∥ x ˉ χ ( W ( ∞ ) ) ∥ 2 ) . (138) \frac{1}{M}\left|b^\top R_F(W(\infty))\right|\leq C\left(\left\|\bar{x}_\chi(W(\infty))\right\|\sum_{i=1}^{n-1}\left|\bar{x}_{c^R_{i,b}}(W(\infty))\right|+\left[1+\omega_r\left(\left\|\bar{x}_\chi(W(\infty))\right\|\right)\right]\left\|\bar{x}_\chi(W(\infty))\right\|^2\right). \tag*{(138)} M 1 b ⊤ R F ( W ( ∞ )) ≤ C ( ∥ x ˉ χ ( W ( ∞ )) ∥ i = 1 ∑ n − 1 x ˉ c i , b R ( W ( ∞ )) + [ 1 + ω r ( ∥ x ˉ χ ( W ( ∞ )) ∥ ) ] ∥ x ˉ χ ( W ( ∞ )) ∥ 2 ) . (138)
Since η A \eta_A η A is fixed, ω r \omega_r ω r is bounded on [ 0 , η A ] [0,\eta_A] [ 0 , η A ] , so the factor ω r ( ∥ x ˉ χ ( W ( ∞ ) ) ∥ ) \omega_r(\|\bar{x}_\chi(W(\infty))\|) ω r ( ∥ x ˉ χ ( W ( ∞ )) ∥ ) can be absorbed into C C C on B A \mathcal{B}_A B A .
Since b ⊤ U = M x ˉ b ( W ( ∞ ) ) b^\top U=M\bar{x}_b(W(\infty)) b ⊤ U = M x ˉ b ( W ( ∞ )) , separating the expectation over B A \mathcal{B}_A B A and B A c \mathcal{B}_A^c B A c gives
1 M ∣ b ⊤ E R b ∣ ≤ 2 ∣ E [ ( b ⊤ R F ) x ˉ b ( W ( ∞ ) ) 1 B A ] ∣ + 2 E [ ∣ b ⊤ R F ∣ ∣ x ˉ b ( W ( ∞ ) ) ∣ 1 B A c ] . (139) \frac{1}{M}\left|b^\top\mathbb{E}R_b\right|\leq2\left|\mathbb{E}\left[(b^\top R_F)\bar{x}_b(W(\infty))\mathbf{1}_{\mathcal{B}_A}\right]\right|+2\mathbb{E}\left[|b^\top R_F|\,|\bar{x}_b(W(\infty))|\mathbf{1}_{\mathcal{B}_A^c}\right]. \tag*{(139)} M 1 b ⊤ E R b ≤ 2 E [ ( b ⊤ R F ) x ˉ b ( W ( ∞ )) 1 B A ] + 2 E [ ∣ b ⊤ R F ∣ ∣ x ˉ b ( W ( ∞ )) ∣ 1 B A c ] . (139)
For the first term, (138) , (125) , (137) , Lemma 1 applied to b b b , and Hölder’s inequality give
M E [ ∥ x ˉ χ ( W ( ∞ ) ) ∥ ∣ x ˉ c i , b R ( W ( ∞ ) ) ∣ ∣ x ˉ b ( W ( ∞ ) ) ∣ ] ≤ M ( E ∣ x ˉ χ ( W ( ∞ ) ) ∣ 4 ) 1 / 4 ( E ∣ x ˉ c i , b R ( W ( ∞ ) ) ∣ 4 ) 1 / 4 ( E ∣ x ˉ b ( W ( ∞ ) ) ∣ 2 ) 1 / 2 = O ( M − 1 / 2 ) , \begin{aligned}
M\mathbb{E}\left[\|\bar{x}_\chi(W(\infty))\|\,|\bar{x}_{c^R_{i,b}}(W(\infty))|\,|\bar{x}_b(W(\infty))|\right] \\
&\leq M\left(\mathbb{E}|\bar{x}_\chi(W(\infty))|^4\right)^{1/4}\left(\mathbb{E}|\bar{x}_{c^R_{i,b}}(W(\infty))|^4\right)^{1/4}\left(\mathbb{E}|\bar{x}_b(W(\infty))|^2\right)^{1/2}=O(M^{-1/2}),
\end{aligned} M E [ ∥ x ˉ χ ( W ( ∞ )) ∥ ∣ x ˉ c i , b R ( W ( ∞ )) ∣ ∣ x ˉ b ( W ( ∞ )) ∣ ] ≤ M ( E ∣ x ˉ χ ( W ( ∞ )) ∣ 4 ) 1/4 ( E ∣ x ˉ c i , b R ( W ( ∞ )) ∣ 4 ) 1/4 ( E ∣ x ˉ b ( W ( ∞ )) ∣ 2 ) 1/2 = O ( M − 1/2 ) ,
M E [ ∥ x ˉ χ ( W ( ∞ ) ) ∥ 2 ∣ x ˉ b ( W ( ∞ ) ) ∣ ] ≤ M ( E ∣ x ˉ χ ( W ( ∞ ) ) ∣ 4 ) 1 / 2 ( E ∣ x ˉ b ( W ( ∞ ) ) ∣ 2 ) 1 / 2 = O ( M − 1 / 2 ) . (140) \begin{aligned}
M\mathbb{E}\left[\|\bar{x}_\chi(W(\infty))\|^2|\bar{x}_b(W(\infty))|\right] \\
&\leq M\left(\mathbb{E}|\bar{x}_\chi(W(\infty))|^4\right)^{1/2}\left(\mathbb{E}|\bar{x}_b(W(\infty))|^2\right)^{1/2}=O(M^{-1/2}). \tag*{(140)}
\end{aligned} M E [ ∥ x ˉ χ ( W ( ∞ )) ∥ 2 ∣ x ˉ b ( W ( ∞ )) ∣ ] ≤ M ( E ∣ x ˉ χ ( W ( ∞ )) ∣ 4 ) 1/2 ( E ∣ x ˉ b ( W ( ∞ )) ∣ 2 ) 1/2 = O ( M − 1/2 ) . (140)
For the contribution on B A c \mathcal{B}_A^c B A c , recall that x χ x_\chi x χ is linear and F m ( w ∗ ) = 0 F_m(w^*)=0 F m ( w ∗ ) = 0 . Thus [ R F ( w ) ] m [R_F(w)]_m [ R F ( w ) ] m is the first-order Taylor remainder of ( v , x ) ↦ f ( v , Ψ ( x ) ; θ m ) (v,x)\mapsto f(v,\Psi(x);\theta_m) ( v , x ) ↦ f ( v , Ψ ( x ) ; θ m ) about ( w m ∗ , x χ ∗ ) (w_m^*,x_\chi^*) ( w m ∗ , x χ ∗ ) , evaluated at ( w m , x χ ( w ) ) (w_m,x_\chi(w)) ( w m , x χ ( w )) . By A3, the second derivatives of this map are uniformly bounded on the fixed bounded convex set D n − 1 × K χ \mathcal{D}_{n-1} \times\mathcal{K}_{\chi} D n − 1 × K χ . Hence ∥ [ R F ( w ) ] m ∥ ≤ C \lVert[R_F(w)]_m \rVert\le C ∥[ R F ( w ) ] m ∥ ≤ C uniformly in m m m , M M M , θ \theta θ , and w ∈ D w \in\mathcal{D} w ∈ D .
For ∥ b ∥ max ≤ 1 \lVert b \rVert_{\max} \le1 ∥ b ∥ m a x ≤ 1 , summing over m m m gives ∣ b T R F ( w ) ∣ ≤ C M \lvert b^{\mathsf{T}} R_F(w) \rvert\le CM ∣ b T R F ( w )∣ ≤ C M . The simplex constraint also gives ∣ x ˉ b ( w ) ∣ ≤ M − 1 ∑ m = 1 M ∥ w m − w m ∗ ∥ ≤ 2 \lvert\bar{x}_b(w) \rvert\le M^{-1} \sum_{m=1}^{M} \lVert w_m - w_m^* \rVert\le2 ∣ x ˉ b ( w )∣ ≤ M − 1 ∑ m = 1 M ∥ w m − w m ∗ ∥ ≤ 2 . Since P ( B A c ) = O ( M − 2 ) \mathbb{P}(\mathcal{B}_A^c) = O(M^{-2}) P ( B A c ) = O ( M − 2 ) , we obtain
E [ ∣ b T R F ( W ( ∞ ) ) ∣ ∣ x ˉ b ( W ( ∞ ) ) ∣ 1 B A c ] ≤ 2 C M P ( B A c ) = O ( M − 1 ) . (141) \mathbb{E}\left[\left\lvert b^{\mathsf{T}}R_F(W(\infty))\right\rvert\left\lvert\bar{x}_b(W(\infty))\right\rvert\mathbf{1}_{\mathcal{B}_A^c}\right]\le2CM\mathbb{P}(\mathcal{B}_A^c)=O(M^{-1}). \tag*{(141)} E [ b T R F ( W ( ∞ )) ∣ x ˉ b ( W ( ∞ )) ∣ 1 B A c ] ≤ 2 C M P ( B A c ) = O ( M − 1 ) . (141)
Combining (139)–(141) verifies the E R E_R E R bound in A8.
We next verify the E Q E_Q E Q bound in A8. For ∥ b ∥ max ≤ 1 \lVert b \rVert_{\max} \le1 ∥ b ∥ m a x ≤ 1 , every feasible jump changes at most c e c_e c e blocks, and the distance between two reduced one-hot states in one block is at most 2 \sqrt{2} 2 . Hence ∣ b T Δ r ∣ ≤ 2 c e \lvert b^{\mathsf{T}}\Delta_r\rvert\le\sqrt{2}c_e ∣ b T Δ r ∣ ≤ 2 c e , and A1 gives
0 ≤ V b ( W ) = 1 M ∑ r ∈ R q r C T M C ( W ) ( b T Δ r ) 2 ≤ 2 c e 2 , W ∈ W . (142) 0 \le V_b(W)=\frac{1}{M}\sum_{r\in\mathcal{R}}q_r^{\mathrm{CTMC}}(W)(b^{\mathsf{T}}\Delta_r)^2\le2c_e^2,\qquad W\in\mathcal{W}. \tag*{(142)} 0 ≤ V b ( W ) = M 1 r ∈ R ∑ q r CTMC ( W ) ( b T Δ r ) 2 ≤ 2 c e 2 , W ∈ W . (142)
At equilibrium, S2 gives
V b ( w ∗ ) = V ^ b ( 0 ) , sup ∥ b ∥ max ≤ 1 ∣ V b ( w ∗ ) ∣ ≤ C Q . (143) V_b(w^*)=\widehat{V}_b(0),\qquad\sup_{\lVert b\rVert_{\max}\le1}\lvert V_b(w^*)\rvert\le C_Q. \tag*{(143)} V b ( w ∗ ) = V b ( 0 ) , ∥ b ∥ m a x ≤ 1 sup ∣ V b ( w ∗ )∣ ≤ C Q . (143)
For fixed b b b , let c 1 , b , … , c K Q , b c_{1,b},\ldots,c_{K_Q,b} c 1 , b , … , c K Q , b and V ^ b \widehat{V}_b V b be given by S2, and define event
B b = { max 1 ≤ k ≤ K Q ∣ x ˉ c k , b ( W ( ∞ ) ) ∣ ≤ η Q } . (144) \mathcal{B}_b=\left\{\max_{1\le k\le K_Q}\left\lvert\bar{x}_{c_{k,b}}(W(\infty))\right\rvert\le\eta_Q\right\}. \tag*{(144)} B b = { 1 ≤ k ≤ K Q max x ˉ c k , b ( W ( ∞ )) ≤ η Q } . (144)
We will use shorthand notation x ˉ c k , b = x ˉ c k , b ( W ( ∞ ) ) \bar{x}_{c_{k,b}}=\bar{x}_{c_{k,b}}(W(\infty)) x ˉ c k , b = x ˉ c k , b ( W ( ∞ )) in the rest of the proof. Separating the expectation over B b \mathcal{B}_b B b and B b c \mathcal{B}_b^c B b c , we obtain
1 M ∣ b T E Q b ∣ = ∣ E [ V b ( W ( ∞ ) ) − V b ( w ∗ ) ] ∣ ≤ ∣ E [ ( V b ( W ( ∞ ) ) − V b ( w ∗ ) ) 1 B b ] ∣ + E [ ∣ V b ( W ( ∞ ) ) − V b ( w ∗ ) ∣ 1 B b c ] . \frac{1}{M}\lvert b^{\mathsf{T}}E_Qb\rvert=\left\lvert\mathbb{E}\left[V_b(W(\infty))-V_b(w^*)\right]\right\rvert
\le\left\lvert\mathbb{E}\left[(V_b(W(\infty))-V_b(w^*))\mathbf{1}_{\mathcal{B}_b}\right]\right\rvert+\mathbb{E}\left[\lvert V_b(W(\infty))-V_b(w^*)\rvert\mathbf{1}_{\mathcal{B}_b^c}\right]. M 1 ∣ b T E Q b ∣ = ∣ E [ V b ( W ( ∞ )) − V b ( w ∗ ) ] ∣ ≤ ∣ E [ ( V b ( W ( ∞ )) − V b ( w ∗ )) 1 B b ] ∣ + E [ ∣ V b ( W ( ∞ )) − V b ( w ∗ )∣ 1 B b c ] .
On B b \mathcal{B}_b B b , define z b = ( x ˉ c 1 , b , … , x ˉ c K Q , b ) T z_b=(\bar{x}_{c_{1,b}},\ldots,\bar{x}_{c_{K_Q,b}})^{\mathsf{T}} z b = ( x ˉ c 1 , b , … , x ˉ c K Q , b ) T . Then ∥ z b ∥ ∞ ≤ η Q \lVert z_b\rVert_\infty\le\eta_Q ∥ z b ∥ ∞ ≤ η Q , so the S2 representation is valid at W ( ∞ ) W(\infty) W ( ∞ ) . Moreover, ∥ s z b ∥ ∞ ≤ η Q \lVert sz_b\rVert_\infty\le\eta_Q ∥ s z b ∥ ∞ ≤ η Q for every s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] , so the S2 bound on D 2 V ^ b D^2\widehat{V}_b D 2 V b holds along the entire segment from 0 0 0 to z b z_b z b . Since x ˉ c k , b ( w ∗ ) = 0 \bar{x}_{c_{k,b}}(w^*)=0 x ˉ c k , b ( w ∗ ) = 0 for every k k k , V b ( w ∗ ) = V ^ b ( 0 ) V_b(w^*)=\widehat{V}_b(0) V b ( w ∗ ) = V b ( 0 ) . Taylor’s theorem at 0 therefore gives
V b ( W ( ∞ ) ) − V b ( w ∗ ) = V ^ b ( z b ) − V ^ b ( 0 ) = ∑ k = 1 K Q κ k , b x ˉ c k , b + R b , (145) V_b(W(\infty))-V_b(w^*)=\widehat{V}_b(z_b)-\widehat{V}_b(0)=\sum_{k=1}^{K_Q}\kappa_{k,b}\bar{x}_{c_{k,b}}+R_b, \tag*{(145)} V b ( W ( ∞ )) − V b ( w ∗ ) = V b ( z b ) − V b ( 0 ) = k = 1 ∑ K Q κ k , b x ˉ c k , b + R b , (145)
where
κ k , b = ∂ V ^ b ∂ z k ( 0 ) and R b = ∫ 0 1 ( 1 − s ) z b T D 2 V ^ b ( s z b ) z b d s . (146) \kappa_{k,b}=\frac{\partial\widehat{V}_b}{\partial z_k}(0)\qquad\text{and}\qquad R_b=\int_0^1(1-s)z_b^{\mathsf{T}}D^2\widehat{V}_b(sz_b)z_b\,\mathrm{d}s. \tag*{(146)} κ k , b = ∂ z k ∂ V b ( 0 ) and R b = ∫ 0 1 ( 1 − s ) z b T D 2 V b ( s z b ) z b d s . (146)
On B b c \mathcal{B}_b^c B b c , (142)–(143) give a uniform bound on ∣ V b ( W ( ∞ ) ) − V b ( w ∗ ) ∣ \lvert V_b(W(\infty))-V_b(w^*)\rvert ∣ V b ( W ( ∞ )) − V b ( w ∗ )∣ . By Lemma 1, the uniform block-max bound in S2, a union bound, and Markov’s inequality applied to ∣ x ˉ c k , b ∣ 4 \lvert\bar{x}_{c_{k,b}}\rvert^4 ∣ x ˉ c k , b ∣ 4 ,
P ( B b c ) ≤ ∑ k = 1 K Q P ( ∣ x ˉ c k , b ∣ > η Q ) ≤ ∑ k = 1 K Q E ∣ x ˉ c k , b ∣ 4 η Q 4 = O ( M − 2 ) . (147) \mathbb{P}(\mathcal{B}_b^c)\le\sum_{k=1}^{K_Q}\mathbb{P}\left(\lvert\bar{x}_{c_{k,b}}\rvert>\eta_Q\right)\le\sum_{k=1}^{K_Q}\frac{\mathbb{E}\lvert\bar{x}_{c_{k,b}}\rvert^4}{\eta_Q^4}=O(M^{-2}). \tag*{(147)} P ( B b c ) ≤ k = 1 ∑ K Q P ( ∣ x ˉ c k , b ∣ > η Q ) ≤ k = 1 ∑ K Q η Q 4 E ∣ x ˉ c k , b ∣ 4 = O ( M − 2 ) . (147)
Therefore, we have
1 M ∣ b T E Q b ∣ ≤ ∑ k = 1 K Q ∣ κ k , b ∣ ∣ E [ x ˉ c k , b 1 B b ] ∣ + E [ ∣ R b ∣ 1 B b ] + O ( M − 2 ) . (148) \frac{1}{M}\left|b^{\mathsf T}E_Qb\right| \le\sum_{k=1}^{K_Q}|\kappa_{k,b}|\left|\mathbb{E}\left[\bar{x}_{c_k,b}\mathbf{1}_{B_b}\right]\right|+\mathbb{E}\left[|R_b|\mathbf{1}_{B_b}\right]+O(M^{-2}). \tag*{(148)} M 1 b T E Q b ≤ k = 1 ∑ K Q ∣ κ k , b ∣ ∣ E [ x ˉ c k , b 1 B b ] ∣ + E [ ∣ R b ∣ 1 B b ] + O ( M − 2 ) . (148)
Next, by S2,
∣ κ k , b ∣ = ∣ ∂ V ^ b ∂ z k ( 0 ) ∣ ≤ ∥ D V ^ b ( 0 ) ∥ ≤ C Q , 1 ≤ k ≤ K Q . (149) |\kappa_{k,b}|=\left|\frac{\partial\widehat{V}_b}{\partial z_k}(0)\right|\le\left\|D\widehat{V}_b(0)\right\|\le C_Q,\qquad1\le k\le K_Q. \tag*{(149)} ∣ κ k , b ∣ = ∂ z k ∂ V b ( 0 ) ≤ D V b ( 0 ) ≤ C Q , 1 ≤ k ≤ K Q . (149)
Moreover, by Lemma 1 and (147),
∣ E [ x ˉ c k , b 1 B b ] ∣ ≤ ∣ E x ˉ c k , b ∣ + ( E ∣ x ˉ c k , b ∣ 2 ) 1 / 2 P ( B b c ) 1 / 2 = O ( M − 1 ) . (150) \left|\mathbb{E}\left[\bar{x}_{c_k,b}\mathbf{1}_{B_b}\right]\right|\le\left|\mathbb{E}\bar{x}_{c_k,b}\right|+\left(\mathbb{E}|\bar{x}_{c_k,b}|^2\right)^{1/2}\mathbb{P}(B_b^c)^{1/2}=O(M^{-1}). \tag*{(150)} ∣ E [ x ˉ c k , b 1 B b ] ∣ ≤ ∣ E x ˉ c k , b ∣ + ( E ∣ x ˉ c k , b ∣ 2 ) 1/2 P ( B b c ) 1/2 = O ( M − 1 ) . (150)
From the definition of R b R_b R b , we have
∣ R b ∣ ≤ C Q 2 ∑ k = 1 K Q ∣ x ˉ c k , b ∣ 2 . (151) |R_b|\le\frac{C_Q}{2}\sum_{k=1}^{K_Q}|\bar{x}_{c_k,b}|^2. \tag*{(151)} ∣ R b ∣ ≤ 2 C Q k = 1 ∑ K Q ∣ x ˉ c k , b ∣ 2 . (151)
By (146) and Lemma 1,
E [ ∣ R b ∣ 1 B b ] ≤ C Q 2 ∑ k = 1 K Q E [ ∣ x ˉ c k , b ∣ 2 1 B b ] ≤ C Q 2 ∑ k = 1 K Q E ∣ x ˉ c k , b ∣ 2 = O ( M − 1 ) . (152) \mathbb{E}\left[|R_b|\mathbf{1}_{B_b}\right]\le\frac{C_Q}{2}\sum_{k=1}^{K_Q}\mathbb{E}\left[|\bar{x}_{c_k,b}|^2\mathbf{1}_{B_b}\right]\le\frac{C_Q}{2}\sum_{k=1}^{K_Q}\mathbb{E}|\bar{x}_{c_k,b}|^2=O(M^{-1}). \tag*{(152)} E [ ∣ R b ∣ 1 B b ] ≤ 2 C Q k = 1 ∑ K Q E [ ∣ x ˉ c k , b ∣ 2 1 B b ] ≤ 2 C Q k = 1 ∑ K Q E ∣ x ˉ c k , b ∣ 2 = O ( M − 1 ) . (152)
Combining the results above, we conclude that
1 M ∣ b T E Q b ∣ = O ( M − 1 ) . (153) \frac{1}{M}\left|b^{\mathsf T}E_Qb\right|=O(M^{-1}). \tag*{(153)} M 1 b T E Q b = O ( M − 1 ) . (153)
uniformly over ∥ b ∥ max ≤ 1 \|b\|_{\max}\le1 ∥ b ∥ m a x ≤ 1 . This is in fact the stronger O ( M − 1 ) O(M^{-1}) O ( M − 1 ) estimate for E Q E_Q E Q , and hence verifies the O ( M − 1 / 2 ) O(M^{-1/2}) O ( M − 1/2 ) bound required in A8. Thus A8 holds.
We next verify the Hessian-control requirement in A9 using two full-state directions u , v ∈ R N u,v\in\mathbb{R}^N u , v ∈ R N . By (129), the residual makes no contribution to the Hessian contraction H H H . Since x χ x_\chi x χ is linear, for every full-state direction u u u ,
D x χ [ u ] = 1 M ∑ m = 1 M χ ( θ m ) u m . (154) Dx_\chi[u]=\frac{1}{M}\sum_{m=1}^{M}\chi(\theta_m)u_m. \tag*{(154)} D x χ [ u ] = M 1 m = 1 ∑ M χ ( θ m ) u m . (154)
Differentiating the local S1 decomposition twice at equilibrium gives
D 2 F m ( w ∗ ) [ u , v ] = D A m ( x χ ∗ ) [ D x χ [ u ] ] v m + D A m ( x χ ∗ ) [ D x χ [ v ] ] u m + D 2 A m ( x χ ∗ ) [ D x χ [ u ] , D x χ [ v ] ] w m ∗ + D 2 a m ( x χ ∗ ) [ D x χ [ u ] , D x χ [ v ] ] . (155) \begin{aligned}
D^2F_m(w^*)[u,v]
={}&DA_m(x_\chi^*)[Dx_\chi[u]]v_m+DA_m(x_\chi^*)[Dx_\chi[v]]u_m\\
&+D^2A_m(x_\chi^*)[Dx_\chi[u],Dx_\chi[v]]w_m^*+D^2a_m(x_\chi^*)[Dx_\chi[u],Dx_\chi[v]]. \tag*{(155)}
\end{aligned} D 2 F m ( w ∗ ) [ u , v ] = D A m ( x χ ∗ ) [ D x χ [ u ]] v m + D A m ( x χ ∗ ) [ D x χ [ v ]] u m + D 2 A m ( x χ ∗ ) [ D x χ [ u ] , D x χ [ v ]] w m ∗ + D 2 a m ( x χ ∗ ) [ D x χ [ u ] , D x χ [ v ]] . (155)
For 1 ≤ i , j ≤ n − 1 1\le i,j\le n-1 1 ≤ i , j ≤ n − 1 , define d ( i ) d^{(i)} d ( i ) to be a block vector such that its m m m th block is d m ( i ) = χ ( θ m ) e i d_m^{(i)}=\chi(\theta_m)e_i d m ( i ) = χ ( θ m ) e i and define
r i , b , m = ( D i A m ( x χ ∗ ) ) T b m , ρ i j , b = 1 M ∑ m = 1 M b m T ( D i j 2 A m ( x χ ∗ ) w m ∗ + D i j 2 a m ( x χ ∗ ) ) . (156) r_{i,b,m}=(D_iA_m(x_\chi^*))^{\mathsf T}b_m,\qquad\rho_{ij,b}=\frac{1}{M}\sum_{m=1}^{M}b_m^{\mathsf T}\left(D_{ij}^2A_m(x_\chi^*)w_m^*+D_{ij}^2a_m(x_\chi^*)\right). \tag*{(156)} r i , b , m = ( D i A m ( x χ ∗ ) ) T b m , ρ ij , b = M 1 m = 1 ∑ M b m T ( D ij 2 A m ( x χ ∗ ) w m ∗ + D ij 2 a m ( x χ ∗ ) ) . (156)
Recall that L a = M − 1 / 2 a T L_a=M^{-1/2}a^{\mathsf T} L a = M − 1/2 a T . Hence
D x χ , i [ u ] = M − 1 ( d ( i ) ) T u = M − 1 / 2 L d ( i ) u , ( r i , b ) T u = M L r i , b u . (157) Dx_{\chi,i}[u]=M^{-1}(d^{(i)})^{\mathsf T}u=M^{-1/2}L_{d^{(i)}}u,\qquad(r_{i,b})^{\mathsf T}u=\sqrt{M}L_{r_{i,b}}u. \tag*{(157)} D x χ , i [ u ] = M − 1 ( d ( i ) ) T u = M − 1/2 L d ( i ) u , ( r i , b ) T u = M L r i , b u . (157)
Thus, summing (155) against b b b gives
b ⊤ D 2 F ( w ∗ ) [ u , v ] = ∑ i = 1 n − 1 [ ( L d ( i ) u ) ( L r i , b v ) + ( L d ( i ) v ) ( L r i , b u ) ] + ∑ i , j = 1 n − 1 ρ i j , b ( L d ( i ) u ) ( L d ( j ) v ) . (158) b^{\top}D^{2}F(w^{*})[u,v]=\sum_{i=1}^{n-1}\left[(L_{d^{(i)}}u)(L_{r_{i,b}}v)+(L_{d^{(i)}}v)(L_{r_{i,b}}u)\right]+\sum_{i,j=1}^{n-1}\rho_{ij,b}(L_{d^{(i)}}u)(L_{d^{(j)}}v). \tag*{(158)} b ⊤ D 2 F ( w ∗ ) [ u , v ] = i = 1 ∑ n − 1 [ ( L d ( i ) u ) ( L r i , b v ) + ( L d ( i ) v ) ( L r i , b u ) ] + i , j = 1 ∑ n − 1 ρ ij , b ( L d ( i ) u ) ( L d ( j ) v ) . (158)
The symmetry of the second derivatives implies ρ i j , b = ρ j i , b \rho_{ij,b}=\rho_{ji,b} ρ ij , b = ρ j i , b . Now set
B = 1 2 ( u v ⊤ + v u ⊤ ) . (159) B=\frac{1}{2}\left(uv^{\top}+vu^{\top}\right). \tag*{(159)} B = 2 1 ( u v ⊤ + v u ⊤ ) . (159)
By the componentwise definition of the Hessian contraction H H H , symmetry of the component Hessians gives H ( B ) = D 2 F ( w ∗ ) [ u , v ] H(B)=D^{2}F(w^{*})[u,v] H ( B ) = D 2 F ( w ∗ ) [ u , v ] . Thus (158) becomes
b ⊤ H ( B ) = 2 ∑ i = 1 n − 1 L r i , b B L d ( i ) ⊤ + ∑ i , j = 1 n − 1 ρ i j , b L d ( i ) B L d ( j ) ⊤ . (160) b^{\top}H(B)=2\sum_{i=1}^{n-1}L_{r_{i,b}}BL_{d^{(i)}}^{\top}+\sum_{i,j=1}^{n-1}\rho_{ij,b}L_{d^{(i)}}BL_{d^{(j)}}^{\top}. \tag*{(160)} b ⊤ H ( B ) = 2 i = 1 ∑ n − 1 L r i , b B L d ( i ) ⊤ + i , j = 1 ∑ n − 1 ρ ij , b L d ( i ) B L d ( j ) ⊤ . (160)
Every symmetric matrix is a linear combination of matrices of the form u u ⊤ uu^{\top} u u ⊤ . Since both sides of (160) are linear in B B B , the identity therefore holds for every symmetric B B B .
We now put (160) in the form required by A9. By S1, ∥ b ∥ max ≤ 1 \lVert b\rVert_{\max}\le1 ∥ b ∥ m a x ≤ 1 , boundedness of χ \chi χ , and w m ∗ ∈ D n − 1 w_m^{*}\in D_{n-1} w m ∗ ∈ D n − 1 , there exists C 0 < ∞ C_0<\infty C 0 < ∞ , independent of M M M , θ \theta θ , and b b b , such that
max 1 ≤ i ≤ n − 1 { ∥ r i , b ∥ max , ∥ d ( i ) ∥ max } + max 1 ≤ i , j ≤ n − 1 ∣ ρ i j , b ∣ ≤ C 0 . (161) \max_{1\le i\le n-1}\left\{\lVert r_{i,b}\rVert_{\max},\lVert d^{(i)}\rVert_{\max}\right\}+\max_{1\le i,j\le n-1}|\rho_{ij,b}|\le C_0. \tag*{(161)} 1 ≤ i ≤ n − 1 max { ∥ r i , b ∥ m a x , ∥ d ( i ) ∥ m a x } + 1 ≤ i , j ≤ n − 1 max ∣ ρ ij , b ∣ ≤ C 0 . (161)
Specifically, the first two bounds follow from the uniform bound on D A DA D A in S1 and ∥ d ( i ) ∥ max ≤ ∥ χ ∥ ∞ \lVert d^{(i)}\rVert_{\max}\le\lVert\chi\rVert_{\infty} ∥ d ( i ) ∥ m a x ≤ ∥ χ ∥ ∞ , while
∣ ρ i j , b ∣ ≤ 1 M ∑ m = 1 M ∥ b m ∥ ( ∥ D i j 2 A m ( x χ ∗ ) ∥ ∥ w m ∗ ∥ + ∥ D i j 2 a m ( x χ ∗ ) ∥ ) ≤ C 0 (162) |\rho_{ij,b}|\le\frac{1}{M}\sum_{m=1}^{M}\lVert b_m\rVert\left(\lVert D_{ij}^{2}A_m(x_{\chi}^{*})\rVert\lVert w_m^{*}\rVert+\lVert D_{ij}^{2}a_m(x_{\chi}^{*})\rVert\right)\le C_0 \tag*{(162)} ∣ ρ ij , b ∣ ≤ M 1 m = 1 ∑ M ∥ b m ∥ ( ∥ D ij 2 A m ( x χ ∗ )∥ ∥ w m ∗ ∥ + ∥ D ij 2 a m ( x χ ∗ )∥ ) ≤ C 0 (162)
by the uniform second-derivative bounds in S1.
There are ( n − 1 ) (n-1) ( n − 1 ) terms in the first sum of (160) and ( n − 1 ) 2 (n-1)^2 ( n − 1 ) 2 terms in the second. Set K H = ( n − 1 ) + ( n − 1 ) 2 = n ( n − 1 ) K_H=(n-1)+(n-1)^2=n(n-1) K H = ( n − 1 ) + ( n − 1 ) 2 = n ( n − 1 ) and relabel the corresponding pairs of block vectors as
( r k , b , s k , b ) ∈ { ( r i , b , d ( i ) ) : 1 ≤ i ≤ n − 1 } ∪ { ( d ( i ) , d ( j ) ) : 1 ≤ i , j ≤ n − 1 } . (163) (r_{k,b},s_{k,b})\in\left\{(r_{i,b},d^{(i)}):1\le i\le n-1\right\}\cup\left\{(d^{(i)},d^{(j)}):1\le i,j\le n-1\right\}. \tag*{(163)} ( r k , b , s k , b ) ∈ { ( r i , b , d ( i ) ) : 1 ≤ i ≤ n − 1 } ∪ { ( d ( i ) , d ( j ) ) : 1 ≤ i , j ≤ n − 1 } . (163)
Then (160) and the triangle inequality imply
∣ b ⊤ H ( B ) ∣ ≤ 2 ∑ i = 1 n − 1 ∣ L r i , b B L d ( i ) ⊤ ∣ + C 0 ∑ i , j = 1 n − 1 ∣ L d ( i ) B L d ( j ) ⊤ ∣ ≤ C H ∑ k = 1 K H ∣ L r k , b B L s k , b ⊤ ∣ , max 1 ≤ k ≤ K H { ∥ r k , b ∥ max , ∥ s k , b ∥ max } ≤ C H , (164) \begin{aligned}
\lvert b^{\top}H(B)\rvert\le2\sum_{i=1}^{n-1}\left\lvert L_{r_{i,b}}BL_{d^{(i)}}^{\top}\right\rvert+C_0\sum_{i,j=1}^{n-1}\left\lvert L_{d^{(i)}}BL_{d^{(j)}}^{\top}\right\rvert\\
&\le C_H\sum_{k=1}^{K_H}\left\lvert L_{r_{k,b}}BL_{s_{k,b}}^{\top}\right\rvert,\qquad\max_{1\le k\le K_H}\left\{\lVert r_{k,b}\rVert_{\max},\lVert s_{k,b}\rVert_{\max}\right\}\le C_H, \tag*{(164)}
\end{aligned} ∣ b ⊤ H ( B )∣ ≤ 2 i = 1 ∑ n − 1 L r i , b B L d ( i ) ⊤ + C 0 i , j = 1 ∑ n − 1 L d ( i ) B L d ( j ) ⊤ ≤ C H k = 1 ∑ K H L r k , b B L s k , b ⊤ , 1 ≤ k ≤ K H max { ∥ r k , b ∥ m a x , ∥ s k , b ∥ m a x } ≤ C H , (164)
for a constant C H < ∞ C_H<\infty C H < ∞ independent of M M M , θ \theta θ , and b b b . This verifies the Hessian-control requirement in A9.
It remains to verify the post-quadratic drift-remainder requirement in A9. The following argument is used only on B A B_A B A , where the local S1 representation is valid. For w ∈ D w\in D w ∈ D satisfying ∥ x ˉ χ ( w ) ∥ ≤ η A \lVert\bar{x}_{\chi}(w)\rVert\le\eta_A ∥ x ˉ χ ( w )∥ ≤ η A , Taylor expansion of A m A_m A m and a m a_m a m about x χ ∗ x_{\chi}^{*} x χ ∗ gives
A m ( x χ ( w ) ) = A m ( x χ ∗ ) + D A m ( x χ ∗ ) [ x ˉ χ ( w ) ] + 1 2 D 2 A m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w ) ] + R ~ A , m ( w ) , A_m(x_{\chi}(w))=A_m(x_{\chi}^{*})+DA_m(x_{\chi}^{*})[\bar{x}_{\chi}(w)]+\frac{1}{2}D^{2}A_m(x_{\chi}^{*})[\bar{x}_{\chi}(w),\bar{x}_{\chi}(w)]+\widetilde{R}_{A,m}(w), A m ( x χ ( w )) = A m ( x χ ∗ ) + D A m ( x χ ∗ ) [ x ˉ χ ( w )] + 2 1 D 2 A m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w )] + R A , m ( w ) ,
a m ( x χ ( w ) ) = a m ( x χ ∗ ) + D a m ( x χ ∗ ) [ x ˉ χ ( w ) ] + 1 2 D 2 a m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w ) ] + R ~ a , m ( w ) . (165) a_m(x_{\chi}(w))=a_m(x_{\chi}^{*})+Da_m(x_{\chi}^{*})[\bar{x}_{\chi}(w)]+\frac{1}{2}D^{2}a_m(x_{\chi}^{*})[\bar{x}_{\chi}(w),\bar{x}_{\chi}(w)]+\widetilde{R}_{a,m}(w). \tag*{(165)} a m ( x χ ( w )) = a m ( x χ ∗ ) + D a m ( x χ ∗ ) [ x ˉ χ ( w )] + 2 1 D 2 a m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w )] + R a , m ( w ) . (165)
For ∥ x ˉ χ ( w ) ∥ ≤ η A \lVert\bar{x}_{\chi}(w)\rVert\leq\eta_A ∥ x ˉ χ ( w )∥ ≤ η A , apply Taylor’s integral remainder formula to A m A_m A m and a m a_m a m along the segment from x χ ∗ x_{\chi}^{*} x χ ∗ to x ˉ χ ( w ) \bar{x}_{\chi}(w) x ˉ χ ( w ) . The common modulus bound in S 1 \mathrm{S}_1 S 1 and ∫ 0 1 ( 1 − s ) d s = 1 / 2 \int_{0}^{1}(1-s)\,ds=1/2 ∫ 0 1 ( 1 − s ) d s = 1/2 give
∥ R ~ A , m ( w ) ∥ + ∥ R ~ a , m ( w ) ∥ ≤ 1 2 ω A ( ∥ x ˉ χ ( w ) ∥ ) ∥ x ˉ χ ( w ) ∥ 2 . (166) \lVert\widetilde{R}_{A,m}(w)\rVert+\lVert\widetilde{R}_{a,m}(w)\rVert\leq\frac{1}{2}\omega_A(\lVert\bar{x}_{\chi}(w)\rVert)\lVert\bar{x}_{\chi}(w)\rVert^2. \tag*{(166)} ∥ R A , m ( w )∥ + ∥ R a , m ( w )∥ ≤ 2 1 ω A (∥ x ˉ χ ( w )∥) ∥ x ˉ χ ( w ) ∥ 2 . (166)
Let w ˉ = w − w ∗ \bar{w}=w-w^{*} w ˉ = w − w ∗ . Taking the derivative at w ∗ w^{*} w ∗ in the direction w ˉ = w − w ∗ \bar{w}=w-w^{*} w ˉ = w − w ∗ gives
D x χ [ w ˉ ] = d d t x χ ( w ∗ + t w ˉ ) ∣ t = 0 = 1 M ∑ m = 1 M χ ( θ m ) ( w m − w m ∗ ) = x χ ( w ) − x χ ( w ∗ ) = x ˉ χ ( w ) . (167) \begin{aligned}
D x_{\chi}[\bar{w}]=\left.\frac{d}{dt}x_{\chi}(w^{*}+t\bar{w})\right|_{t=0}=\frac{1}{M}\sum_{m=1}^{M}\chi(\theta_m)(w_m-w_m^{*}) \\
&=x_{\chi}(w)-x_{\chi}(w^{*})=\bar{x}_{\chi}(w). \tag*{(167)}
\end{aligned} D x χ [ w ˉ ] = d t d x χ ( w ∗ + t w ˉ ) t = 0 = M 1 m = 1 ∑ M χ ( θ m ) ( w m − w m ∗ ) = x χ ( w ) − x χ ( w ∗ ) = x ˉ χ ( w ) . (167)
Using D x χ [ w ˉ ] = x ˉ χ ( w ) D x_{\chi}[\bar{w}]=\bar{x}_{\chi}(w) D x χ [ w ˉ ] = x ˉ χ ( w ) in D 2 F m ( w ∗ ) [ w ˉ , w ˉ ] D^{2}F_m(w^{*})[\bar{w},\bar{w}] D 2 F m ( w ∗ ) [ w ˉ , w ˉ ] gives
1 2 [ H ( w ˉ w ˉ T ) ] m = D A m ( x χ ∗ ) [ x ˉ χ ( w ) ] w ˉ m + 1 2 D 2 A m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w ) ] w m ∗ + 1 2 D 2 a m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w ) ] . (168) \frac{1}{2}\left[H(\bar{w}\bar{w}^{\mathsf{T}})\right]_m=D A_m(x_{\chi}^{*})[\bar{x}_{\chi}(w)]\bar{w}_m+\frac{1}{2}D^{2}A_m(x_{\chi}^{*})[\bar{x}_{\chi}(w),\bar{x}_{\chi}(w)]w_m^{*}+\frac{1}{2}D^{2}a_m(x_{\chi}^{*})[\bar{x}_{\chi}(w),\bar{x}_{\chi}(w)]. \tag*{(168)} 2 1 [ H ( w ˉ w ˉ T ) ] m = D A m ( x χ ∗ ) [ x ˉ χ ( w )] w ˉ m + 2 1 D 2 A m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w )] w m ∗ + 2 1 D 2 a m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w )] . (168)
In the block formula for R F ( w ) R_F(w) R F ( w ) , expand R A , m ( w ) R_{A,m}(w) R A , m ( w ) and R a , m ( w ) R_{a,m}(w) R a , m ( w ) using (165). Subtracting (168) cancels the D A m D A_m D A m and D 2 a m D^{2}a_m D 2 a m terms and leaves w m − w m ∗ = w ˉ m w_m-w_m^{*}=\bar{w}_m w m − w m ∗ = w ˉ m in the D 2 A m D^{2}A_m D 2 A m term. By the definition of T F T_F T F , we obtain
[ T F ( w ) ] m = 1 2 D 2 A m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w ) ] w ˉ m + R ~ A , m ( w ) w m + R ~ a , m ( w ) + r m ( w m , x χ ( w ) ) . (169) [T_F(w)]_m=\frac{1}{2}D^{2}A_m(x_{\chi}^{*})[\bar{x}_{\chi}(w),\bar{x}_{\chi}(w)]\bar{w}_m+\widetilde{R}_{A,m}(w)w_m+\widetilde{R}_{a,m}(w)+r_m(w_m,x_{\chi}(w)). \tag*{(169)} [ T F ( w ) ] m = 2 1 D 2 A m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w )] w ˉ m + R A , m ( w ) w m + R a , m ( w ) + r m ( w m , x χ ( w )) . (169)
Fix a block vector b b b with ∥ b ∥ max ≤ 1 \lVert b\rVert_{\max}\leq1 ∥ b ∥ m a x ≤ 1 . Let x ˉ χ , i ( w ) \bar{x}_{\chi,i}(w) x ˉ χ , i ( w ) denote the i i i th coordinate of x ˉ χ ( w ) \bar{x}_{\chi}(w) x ˉ χ ( w ) . For 1 ≤ i , j ≤ n − 1 1\leq i,j\leq n-1 1 ≤ i , j ≤ n − 1 , define the block vector c ~ i j , b \widetilde{c}_{ij,b} c ij , b by c ~ i j , b , m = ( D i j 2 A m ( x χ ∗ ) ) T b m \widetilde{c}_{ij,b,m}=(D^{2}_{ij}A_m(x_{\chi}^{*}))^{\mathsf{T}}b_m c ij , b , m = ( D ij 2 A m ( x χ ∗ ) ) T b m . The second-derivative bound in S 1 \mathrm{S}_1 S 1 gives ∥ c ~ i j , b ∥ max ≤ C A \lVert\widetilde{c}_{ij,b}\rVert_{\max}\leq C_A ∥ c ij , b ∥ m a x ≤ C A . Expanding the Hessian in coordinates and using x ˉ c ( w ) = M − 1 ∑ m = 1 M c m T w ˉ \bar{x}_c(w)=M^{-1}\sum_{m=1}^{M}c_m^{\mathsf{T}}\bar{w} x ˉ c ( w ) = M − 1 ∑ m = 1 M c m T w ˉ yields
1 2 M ∑ m = 1 M b m T D 2 A m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w ) ] w ˉ m = 1 2 ∑ i , j = 1 n − 1 x ˉ χ , i ( w ) x ˉ χ , j ( w ) x ˉ c ~ i j , b ( w ) . (170) \frac{1}{2M}\sum_{m=1}^{M}b_m^{\mathsf{T}}D^{2}A_m(x_{\chi}^{*})[\bar{x}_{\chi}(w),\bar{x}_{\chi}(w)]\bar{w}_m=\frac{1}{2}\sum_{i,j=1}^{n-1}\bar{x}_{\chi,i}(w)\bar{x}_{\chi,j}(w)\bar{x}_{\widetilde{c}_{ij,b}}(w). \tag*{(170)} 2 M 1 m = 1 ∑ M b m T D 2 A m ( x χ ∗ ) [ x ˉ χ ( w ) , x ˉ χ ( w )] w ˉ m = 2 1 i , j = 1 ∑ n − 1 x ˉ χ , i ( w ) x ˉ χ , j ( w ) x ˉ c ij , b ( w ) . (170)
Set ω ( s ) = ω A ( s ) + ω r ( s ) \omega(s)=\omega_A(s)+\omega_r(s) ω ( s ) = ω A ( s ) + ω r ( s ) . By (166), the residual bound in S 1 \mathrm{S}_1 S 1 , and ∥ w m ∥ ≤ 1 \lVert w_m\rVert\leq1 ∥ w m ∥ ≤ 1 , the sum of the norms of the last three terms in (169) is at most ω ( ∥ x ˉ χ ( w ) ∥ ) ∥ x ˉ χ ( w ) ∥ 2 \omega(\lVert\bar{x}_{\chi}(w)\rVert)\lVert\bar{x}_{\chi}(w)\rVert^2 ω (∥ x ˉ χ ( w )∥) ∥ x ˉ χ ( w ) ∥ 2 . Using ∣ x ˉ χ , i ( w ) x ˉ χ , j ( w ) ∣ ≤ ∥ x ˉ χ ( w ) ∥ 2 |\bar{x}_{\chi,i}(w)\bar{x}_{\chi,j}(w)|\leq\lVert\bar{x}_{\chi}(w)\rVert^2 ∣ x ˉ χ , i ( w ) x ˉ χ , j ( w ) ∣ ≤ ∥ x ˉ χ ( w ) ∥ 2 in (170), we obtain, for ∥ x ˉ χ ( w ) ∥ ≤ η A \lVert\bar{x}_{\chi}(w)\rVert\leq\eta_A ∥ x ˉ χ ( w )∥ ≤ η A ,
1 M ∣ b T T F ( w ) ∣ ≤ ∥ x ˉ χ ( w ) ∥ 2 ( 1 2 ∑ i , j = 1 n − 1 ∣ x ˉ c ~ i j , b ( w ) ∣ + ω ( ∥ x ˉ χ ( w ) ∥ ) ) . (171) \frac{1}{M}|b^{\mathsf{T}}T_F(w)|\leq\lVert\bar{x}_{\chi}(w)\rVert^2\left(\frac{1}{2}\sum_{i,j=1}^{n-1}|\bar{x}_{\widetilde{c}_{ij,b}}(w)|+\omega(\lVert\bar{x}_{\chi}(w)\rVert)\right). \tag*{(171)} M 1 ∣ b T T F ( w ) ∣ ≤ ∥ x ˉ χ ( w ) ∥ 2 ( 2 1 i , j = 1 ∑ n − 1 ∣ x ˉ c ij , b ( w ) ∣ + ω (∥ x ˉ χ ( w )∥) ) . (171)
On B A \mathcal{B}_A B A , evaluate (171) at w = W ( ∞ ) w=W(\infty) w = W ( ∞ ) . Conditional on θ \theta θ , the coefficient vector c ~ i j , b \widetilde{c}_{ij,b} c ij , b is deterministic. Applying Lemma 1 to c ~ i j , b / C A \widetilde{c}_{ij,b}/C_A c ij , b / C A gives E ∣ x ˉ c ~ i j , b ( W ( ∞ ) ) ∣ 2 ≤ C / M \mathbb{E}|\bar{x}_{\widetilde{c}_{ij,b}}(W(\infty))|^2\leq C/M E ∣ x ˉ c ij , b ( W ( ∞ )) ∣ 2 ≤ C / M uniformly in i , j , b i,j,b i , j , b . By Cauchy–Schwarz and the fourth-moment bound for x ˉ χ ( W ( ∞ ) ) \bar{x}_{\chi}(W(\infty)) x ˉ χ ( W ( ∞ )) ,
M E [ ∥ x ˉ χ ( W ( ∞ ) ) ∥ 2 ∣ x ˉ c ~ i j , b ( W ( ∞ ) ) ∣ 1 B A ] ≤ M ( E ∥ x ˉ χ ( W ( ∞ ) ) ∥ 4 ) 1 / 2 ( E ∣ x ˉ c ~ i j , b ( W ( ∞ ) ) ∣ 2 ) 1 / 2 = O ( M − 1 / 2 ) . (172) \begin{aligned}
M\mathbb{E}\left[\lVert\bar{x}_{\chi}(W(\infty))\rVert^2|\bar{x}_{\widetilde{c}_{ij,b}}(W(\infty))|\mathbf{1}_{\mathcal{B}_A}\right] \\
&\leq M\left(\mathbb{E}\lVert\bar{x}_{\chi}(W(\infty))\rVert^4\right)^{1/2}\left(\mathbb{E}|\bar{x}_{\widetilde{c}_{ij,b}}(W(\infty))|^2\right)^{1/2}=O(M^{-1/2}). \tag*{(172)}
\end{aligned} M E [ ∥ x ˉ χ ( W ( ∞ )) ∥ 2 ∣ x ˉ c ij , b ( W ( ∞ )) ∣ 1 B A ] ≤ M ( E ∥ x ˉ χ ( W ( ∞ )) ∥ 4 ) 1/2 ( E ∣ x ˉ c ij , b ( W ( ∞ )) ∣ 2 ) 1/2 = O ( M − 1/2 ) . (172)
There are only ( n − 1 ) 2 (n-1)^2 ( n − 1 ) 2 terms, so their sum has the same order.
For the modulus term, fix 0 < η < η A 0<\eta<\eta_A 0 < η < η A and split B A \mathcal{B}_A B A according to whether ∥ x ˉ χ ( W ( ∞ ) ) ∥ ≤ η \lVert\bar{x}_{\chi}(W(\infty))\rVert\leq\eta ∥ x ˉ χ ( W ( ∞ ))∥ ≤ η . When this norm exceeds η \eta η , we have ∥ x ˉ χ ( W ( ∞ ) ) ∥ 2 ≤ η − 2 ∥ x ˉ χ ( W ( ∞ ) ) ∥ 4 \lVert\bar{x}_{\chi}(W(\infty))\rVert^2\leq\eta^{-2}\lVert\bar{x}_{\chi}(W(\infty))\rVert^4 ∥ x ˉ χ ( W ( ∞ )) ∥ 2 ≤ η − 2 ∥ x ˉ χ ( W ( ∞ )) ∥ 4 . The second- and fourth-moment bounds therefore give
M E [ ω ( ∥ x ˉ χ ( W ( ∞ ) ) ∥ ) ∥ x ˉ χ ( W ( ∞ ) ) ∥ 2 1 B A ] ≤ M ω ( η ) E ∥ x ˉ χ ( W ( ∞ ) ) ∥ 2 + M ω ( η A ) η 2 E ∥ x ˉ χ ( W ( ∞ ) ) ∥ 4 ≤ C ω ( η ) + C M η 2 . (173) \begin{aligned}
M\mathbb{E}\left[\omega(\lVert\bar{x}_{\chi}(W(\infty))\rVert)\lVert\bar{x}_{\chi}(W(\infty))\rVert^2\mathbf{1}_{\mathcal{B}_A}\right] \\
&\leq M\omega(\eta)\mathbb{E}\lVert\bar{x}_{\chi}(W(\infty))\rVert^2+\frac{M\omega(\eta_A)}{\eta^2}\mathbb{E}\lVert\bar{x}_{\chi}(W(\infty))\rVert^4\leq C\omega(\eta)+\frac{C}{M\eta^2}. \tag*{(173)}
\end{aligned} M E [ ω (∥ x ˉ χ ( W ( ∞ ))∥) ∥ x ˉ χ ( W ( ∞ )) ∥ 2 1 B A ] ≤ M ω ( η ) E ∥ x ˉ χ ( W ( ∞ )) ∥ 2 + η 2 M ω ( η A ) E ∥ x ˉ χ ( W ( ∞ )) ∥ 4 ≤ C ω ( η ) + M η 2 C . (173)
Letting M → ∞ M \to\infty M → ∞ and then η ↓ 0 \eta\downarrow0 η ↓ 0 shows that the left-hand side of (173) is o ( 1 ) o(1) o ( 1 ) . Under the sharper condition in S1, ω ( s ) ≤ C A s \omega(s) \le C_A s ω ( s ) ≤ C A s for 0 ≤ s ≤ η A 0 \le s \le\eta_A 0 ≤ s ≤ η A , so the fourth-moment bound gives
M E [ ω ( ∥ x ˉ χ ( W ( ∞ ) ) ∥ ) ∥ x ˉ χ ( W ( ∞ ) ) ∥ 2 1 B A ] ≤ C A M E ∥ x ˉ χ ( W ( ∞ ) ) ∥ 3 ≤ C A M ( E ∥ x ˉ χ ( W ( ∞ ) ) ∥ 4 ) 3 / 4 = O ( M − 1 / 2 ) . (174) M\mathbb{E}\left[\omega\left(\left\|\bar{x}_{\chi}(W(\infty))\right\|\right)\left\|\bar{x}_{\chi}(W(\infty))\right\|^2 1_{B_A}\right]
\le C_A M\mathbb{E}\left\|\bar{x}_{\chi}(W(\infty))\right\|^3
\le C_A M\left(\mathbb{E}\left\|\bar{x}_{\chi}(W(\infty))\right\|^4\right)^{3/4}
= O(M^{-1/2}). \tag*{(174)} M E [ ω ( ∥ x ˉ χ ( W ( ∞ )) ∥ ) ∥ x ˉ χ ( W ( ∞ )) ∥ 2 1 B A ] ≤ C A M E ∥ x ˉ χ ( W ( ∞ )) ∥ 3 ≤ C A M ( E ∥ x ˉ χ ( W ( ∞ )) ∥ 4 ) 3/4 = O ( M − 1/2 ) . (174)
On B A c B_A^c B A c , use the bound ∥ [ R F ( w ) ] m ∥ ≤ C \left\|[R_F(w)]_m\right\| \le C ∥ [ R F ( w ) ] m ∥ ≤ C on D \mathcal{D} D established in the verification of A8. All derivatives in (168) are evaluated at x χ ∗ x_\chi^* x χ ∗ , where S1 bounds them uniformly. Since ∣ w ˉ m ∣ ≤ 2 \left|\bar{w}_m\right| \le2 ∣ w ˉ m ∣ ≤ 2 and ∥ x ˉ χ ( w ) ∥ ≤ 2 ∥ χ ∥ ∞ \left\|\bar{x}_{\chi}(w)\right\| \le2\|\chi\|_\infty ∥ x ˉ χ ( w ) ∥ ≤ 2∥ χ ∥ ∞ , the quadratic term is also uniformly bounded on D \mathcal{D} D . Thus ∥ [ T F ( w ) ] m ∥ ≤ C \left\|[T_F(w)]_m\right\| \le C ∥ [ T F ( w ) ] m ∥ ≤ C , and summing over m m m gives ∣ b T T F ( w ) ∣ ≤ C M \left|b^\mathsf{T}T_F(w)\right| \le CM b T T F ( w ) ≤ C M . Since P ( B A c ) = O ( M − 2 ) \mathbb{P}(B_A^c)=O(M^{-2}) P ( B A c ) = O ( M − 2 ) , we have
E [ ∣ b T T F ( W ( ∞ ) ) ∣ 1 B A c ] ≤ C M P ( B A c ) = O ( M − 1 ) . (175) \mathbb{E}\left[\left|b^\mathsf{T}T_F(W(\infty))\right|1_{B_A^c}\right]
\le CM\mathbb{P}(B_A^c)=O(M^{-1}). \tag*{(175)} E [ b T T F ( W ( ∞ )) 1 B A c ] ≤ C M P ( B A c ) = O ( M − 1 ) . (175)
The estimates (171)–(175) are uniform in b b b . Taking the supremum after splitting the expectation over B A B_A B A and B A c B_A^c B A c gives
sup ∥ b ∥ max ≤ 1 ∣ b T E [ T F ( W ( ∞ ) ) ∣ θ ] ∣ = o ( 1 ) . (176) \sup_{\|b\|_{\max}\le1}\left|b^\mathsf{T}\mathbb{E}[T_F(W(\infty))\mid\theta]\right|=o(1). \tag*{(176)} ∥ b ∥ m a x ≤ 1 sup b T E [ T F ( W ( ∞ )) ∣ θ ] = o ( 1 ) . (176)
Under the sharper condition in S1, (172), (174), and (175) improve the bound in (176) to O ( M − 1 / 2 ) O(M^{-1/2}) O ( M − 1/2 ) . This proves the remaining requirement of A9 and completes the proof.
Covariance Approximation and Mean Refinement
Recall that
Γ φ = L φ Σ ˉ L φ T and Σ = E [ ( W ( ∞ ) − w ∗ ) ( W ( ∞ ) − w ∗ ) T ∣ θ ] . \Gamma_\varphi=L_\varphi\bar{\Sigma}L_\varphi^\mathsf{T}
\quad\text{and}\quad
\Sigma=\mathbb{E}\left[(W(\infty)-w^*)(W(\infty)-w^*)^\mathsf{T}\mid\theta\right]. Γ φ = L φ Σ ˉ L φ T and Σ = E [ ( W ( ∞ ) − w ∗ ) ( W ( ∞ ) − w ∗ ) T ∣ θ ] .
We have the following theorem.
Theorem 1 (Second-order covariance approximation). Assuming A1–A8 , we have
sup ∥ a ∥ max ≤ 1 ∥ c ∥ max ≤ 1 ∣ L a ( Σ − Σ ˉ ) L c T ∣ = O ( M − 1 / 2 ) . (177) \sup_{\substack{\|a\|_{\max}\le1\\\|c\|_{\max}\le1}}
\left|L_a(\Sigma-\bar{\Sigma})L_c^\mathsf{T}\right|=O(M^{-1/2}). \tag*{(177)} ∥ a ∥ m a x ≤ 1 ∥ c ∥ m a x ≤ 1 sup L a ( Σ − Σ ˉ ) L c T = O ( M − 1/2 ) . (177) Consequently, for every fixed bounded observation weight φ \varphi φ ,
∥ Cov ( Y φ ∣ θ ) − Γ φ ∥ o p = O ( M − 1 / 2 ) . (178) \left\|\operatorname{Cov}(Y_\varphi\mid\theta)-\Gamma_\varphi\right\|_{\mathrm{op}}=O(M^{-1/2}). \tag*{(178)} ∥ Cov ( Y φ ∣ θ ) − Γ φ ∥ op = O ( M − 1/2 ) . (178)
Proof. Condition on θ \theta θ and suppress this conditioning. Stationarity applied componentwise to ( w − w ∗ ) ( w − w ∗ ) T (w-w^*)(w-w^*)^\mathsf{T} ( w − w ∗ ) ( w − w ∗ ) T gives
J Σ + Σ J T + Q ˉ = − ( E R + E Q ) . (179) J\Sigma+\Sigma J^\mathsf{T}+\bar{Q}=-(E_R+E_Q). \tag*{(179)} J Σ + Σ J T + Q ˉ = − ( E R + E Q ) . (179)
Thus,
Σ − Σ ˉ = ∫ 0 ∞ e J t ( E R + E Q ) e J T t d t . (180) \Sigma-\bar{\Sigma}=\int_0^\infty e^{Jt}(E_R+E_Q)e^{J^\mathsf{T}t}\,dt. \tag*{(180)} Σ − Σ ˉ = ∫ 0 ∞ e J t ( E R + E Q ) e J T t d t . (180)
Let
δ R = sup ∥ b ∥ max ≤ 1 1 M ∣ b T E R b ∣ , δ Q = sup ∥ b ∥ max ≤ 1 1 M ∣ b T E Q b ∣ . (181) \delta_R=\sup_{\|b\|_{\max}\le1}\frac{1}{M}\left|b^\mathsf{T}E_Rb\right|,
\qquad
\delta_Q=\sup_{\|b\|_{\max}\le1}\frac{1}{M}\left|b^\mathsf{T}E_Qb\right|. \tag*{(181)} δ R = ∥ b ∥ m a x ≤ 1 sup M 1 b T E R b , δ Q = ∥ b ∥ m a x ≤ 1 sup M 1 b T E Q b . (181)
By A8, δ R = O ( M − 1 / 2 ) \delta_R = O(M^{-1/2}) δ R = O ( M − 1/2 ) and δ Q = O ( M − 1 / 2 ) \delta_Q = O(M^{-1/2}) δ Q = O ( M − 1/2 ) . Fix E ∈ { E R , E Q } E \in\{E_R,E_Q\} E ∈ { E R , E Q } and let δ E \delta_E δ E denote the corresponding supremum. First suppose that ∥ a ∥ max , ∥ c ∥ max ≤ 1 \lVert a\rVert_{\max}, \lVert c\rVert_{\max} \le1 ∥ a ∥ m a x , ∥ c ∥ m a x ≤ 1 . Set b ± = ( a ± c ) / 2 b_{\pm} = (a \pm c)/2 b ± = ( a ± c ) /2 , so that ∥ b ± ∥ max ≤ 1 \lVert b_{\pm}\rVert_{\max} \le1 ∥ b ± ∥ m a x ≤ 1 . Expanding the difference b + T E b + − b − T E b − b_+^{\mathsf{T}}Eb_+ - b_-^{\mathsf{T}}Eb_- b + T E b + − b − T E b − gives 1 2 ( a T E c + c T E a ) = a T E c \frac{1}{2}(a^{\mathsf{T}}Ec+c^{\mathsf{T}}Ea)=a^{\mathsf{T}}Ec 2 1 ( a T E c + c T E a ) = a T E c by symmetry of E E E . Each quadratic form in the difference has absolute value at most M δ E M\delta_E M δ E . Thus M − 1 ∣ a T E c ∣ ≤ 2 δ E M^{-1}|a^{\mathsf{T}}Ec| \le2\delta_E M − 1 ∣ a T E c ∣ ≤ 2 δ E . For nonzero a a a and c c c , applying this estimate to a / ∥ a ∥ max a/\lVert a\rVert_{\max} a / ∥ a ∥ m a x and c / ∥ c ∥ max c/\lVert c\rVert_{\max} c / ∥ c ∥ m a x gives the following bound, which also holds if either vector is zero. Therefore, we have
1 M ∣ a T E c ∣ ≤ 2 δ E ∥ a ∥ max ∥ c ∥ max . (182) \frac{1}{M}|a^{\mathsf{T}}Ec| \le2\delta_E\lVert a\rVert_{\max}\lVert c\rVert_{\max}. \tag*{(182)} M 1 ∣ a T E c ∣ ≤ 2 δ E ∥ a ∥ m a x ∥ c ∥ m a x . (182)
The dual norm of ∥ ⋅ ∥ 1 , M \lVert\cdot\rVert_{1,M} ∥ ⋅ ∥ 1 , M is M ∥ ⋅ ∥ max M\lVert\cdot\rVert_{\max} M ∥ ⋅ ∥ m a x , so A6 gives
∥ e J T t a ∥ max ≤ C s e − γ s t ∥ a ∥ max . (183) \lVert e^{J^{\mathsf{T}}t}a\rVert_{\max} \le C_s e^{-\gamma_s t}\lVert a\rVert_{\max}. \tag*{(183)} ∥ e J T t a ∥ m a x ≤ C s e − γ s t ∥ a ∥ m a x . (183)
Combining (180) –(183) ,
sup ∥ a ∥ max ≤ 1 ∥ c ∥ max ≤ 1 ∣ L a ( Σ − Σ ˉ ) L c T ∣ ≤ C s 2 γ s ( δ R + δ Q ) = O ( M − 1 / 2 ) , (184) \sup_{\substack{\lVert a\rVert_{\max}\le1\\\lVert c\rVert_{\max}\le1}}
\left|L_a(\Sigma-\bar{\Sigma})L_c^{\mathsf{T}}\right|
\le\frac{C_s^2}{\gamma_s}(\delta_R+\delta_Q)=O(M^{-1/2}), \tag*{(184)} ∥ a ∥ m a x ≤ 1 ∥ c ∥ m a x ≤ 1 sup L a ( Σ − Σ ˉ ) L c T ≤ γ s C s 2 ( δ R + δ Q ) = O ( M − 1/2 ) , (184)
which proves (177) .
For i = 1 , … , n − 1 i=1,\ldots,n-1 i = 1 , … , n − 1 , let a ( i ) a^{(i)} a ( i ) have block a m ( i ) = φ ( θ m ) e i a_m^{(i)}=\varphi(\theta_m)e_i a m ( i ) = φ ( θ m ) e i . Since n n n is fixed and ∥ a ( i ) ∥ max ≤ ∥ φ ∥ ∞ \lVert a^{(i)}\rVert_{\max}\le\lVert\varphi\rVert_{\infty} ∥ a ( i ) ∥ m a x ≤ ∥ φ ∥ ∞ , (177) gives
∥ L φ ( Σ − Σ ˉ ) L φ T ∥ o p = O ( M − 1 / 2 ) . (185) \left\lVert L_{\varphi}(\Sigma-\bar{\Sigma})L_{\varphi}^{\mathsf{T}}\right\rVert_{\mathrm{op}}=O(M^{-1/2}). \tag*{(185)} L φ ( Σ − Σ ˉ ) L φ T op = O ( M − 1/2 ) . (185)
By Corollary 1, the outer product of the conditional mean of Y φ Y_{\varphi} Y φ with itself has operator norm O ( M − 1 ) O(M^{-1}) O ( M − 1 ) . Since
Cov ( Y φ ∣ θ ) = L φ Σ L φ T − E [ Y φ ∣ θ ] E [ Y φ ∣ θ ] T , (186) \operatorname{Cov}(Y_{\varphi}\mid\theta)=L_{\varphi}\Sigma L_{\varphi}^{\mathsf{T}}-\mathbb{E}[Y_{\varphi}\mid\theta]\mathbb{E}[Y_{\varphi}\mid\theta]^{\mathsf{T}}, \tag*{(186)} Cov ( Y φ ∣ θ ) = L φ Σ L φ T − E [ Y φ ∣ θ ] E [ Y φ ∣ θ ] T , (186)
the preceding bound and (186) prove the covariance approximation in Theorem 1. □
We next turn to the refined stationary mean. Define
μ = − 1 2 J − 1 H ( Σ ˉ ) , β φ = M L φ μ . (187) \mu=-\frac{1}{2}J^{-1}H(\bar{\Sigma}),\qquad\beta_{\varphi}=\sqrt{M}L_{\varphi}\mu. \tag*{(187)} μ = − 2 1 J − 1 H ( Σ ˉ ) , β φ = M L φ μ . (187)
Theorem 2 (Second-order performance refinement). Assume A1–A9 and fix a bounded observation weight φ : Θ → R \varphi:\Theta\to\mathbb{R} φ : Θ → R . Then
∥ E [ X φ ( ∞ ) ∣ θ ] − x φ ∗ − β φ M ∥ = o ( M − 1 ) , ∥ Cov ( X φ ( ∞ ) ∣ θ ) − Γ φ M ∥ o p = O ( M − 3 / 2 ) . (188) \left\lVert\mathbb{E}[X_{\varphi}(\infty)\mid\theta]-x_{\varphi}^{*}-\frac{\beta_{\varphi}}{M}\right\rVert=o(M^{-1}),\qquad
\left\lVert\operatorname{Cov}(X_{\varphi}(\infty)\mid\theta)-\frac{\Gamma_{\varphi}}{M}\right\rVert_{\mathrm{op}}=O(M^{-3/2}). \tag*{(188)} E [ X φ ( ∞ ) ∣ θ ] − x φ ∗ − M β φ = o ( M − 1 ) , Cov ( X φ ( ∞ ) ∣ θ ) − M Γ φ op = O ( M − 3/2 ) . (188) If the sharper O ( M − 1 / 2 ) O(M^{-1/2}) O ( M − 1/2 ) remainder bound in A9 holds, then the mean error in (188) is O ( M − 3 / 2 ) O(M^{-3/2}) O ( M − 3/2 ) . Moreover, if h : R n − 1 → R h:\mathbb{R}^{n-1}\to\mathbb{R} h : R n − 1 → R is twice continuously differentiable on a neighborhood of K φ = { y ∈ R n − 1 : ∥ y ∥ 1 ≤ ∥ φ ∥ ∞ } K_{\varphi}=\{y\in\mathbb{R}^{n-1}:\lVert y\rVert_1\le\lVert\varphi\rVert_{\infty}\} K φ = { y ∈ R n − 1 : ∥ y ∥ 1 ≤ ∥ φ ∥ ∞ } , then
E [ h ( X φ ( ∞ ) ) ∣ θ ] = h ( x φ ∗ ) + 1 M ( D h ( x φ ∗ ) [ β φ ] + 1 2 Tr ( D 2 h ( x φ ∗ ) Γ φ ) ) + o ( M − 1 ) . (189) \mathbb{E}[h(X_{\varphi}(\infty))\mid\theta]
=h(x_{\varphi}^{*})+\frac{1}{M}\left(Dh(x_{\varphi}^{*})[\beta_{\varphi}]+\frac{1}{2}\operatorname{Tr}\left(D^2h(x_{\varphi}^{*})\Gamma_{\varphi}\right)\right)+o(M^{-1}). \tag*{(189)} E [ h ( X φ ( ∞ )) ∣ θ ] = h ( x φ ∗ ) + M 1 ( D h ( x φ ∗ ) [ β φ ] + 2 1 Tr ( D 2 h ( x φ ∗ ) Γ φ ) ) + o ( M − 1 ) . (189)
Proof. Condition on θ \theta θ and suppress this conditioning. Let
m = E [ W ( ∞ ) − w ∗ ] , D = Σ − Σ ‾ . (190) \begin{aligned}
m &= \mathbb{E}[W(\infty)-w^*], \qquad D = \Sigma-\overline{\Sigma}. \tag*{(190)}
\end{aligned} m = E [ W ( ∞ ) − w ∗ ] , D = Σ − Σ . (190)
By stationarity, J m + E [ R F ( W ( ∞ ) ) ] = 0 Jm+\mathbb{E}[R_F(W(\infty))]=0 J m + E [ R F ( W ( ∞ ))] = 0 . Using the definition of T F T_F T F in A9 and the linearity of H H H ,
E [ R F ( W ( ∞ ) ) ] − 1 2 H ( Σ ‾ ) = E [ T F ( W ( ∞ ) ) ] + 1 2 H ( D ) = : E H . (191) \mathbb{E}[R_F(W(\infty))]-\frac{1}{2}H(\overline{\Sigma})=\mathbb{E}[T_F(W(\infty))]+\frac{1}{2}H(D)=:E_H. \tag*{(191)} E [ R F ( W ( ∞ ))] − 2 1 H ( Σ ) = E [ T F ( W ( ∞ ))] + 2 1 H ( D ) =: E H . (191)
We first bound E H E_H E H . By the Hessian-control part of A9 and Theorem 1, uniformly over ∥ b ∥ max ≤ 1 \lVert b\rVert_{\max}\le1 ∥ b ∥ m a x ≤ 1 ,
∣ b T H ( D ) ∣ ≤ C H ∑ k = 1 K H ∣ L r k , b , D L s k , b T ∣ = O ( M − 1 / 2 ) , (192) \left|b^{\mathsf T}H(D)\right|\le C_H\sum_{k=1}^{K_H}\left|L_{r_{k,b},D}L_{s_{k,b}}^{\mathsf T}\right|=O(M^{-1/2}), \tag*{(192)} b T H ( D ) ≤ C H k = 1 ∑ K H L r k , b , D L s k , b T = O ( M − 1/2 ) , (192)
where we used ∥ r k , b ∥ max , ∥ s k , b ∥ max ≤ C H \lVert r_{k,b}\rVert_{\max},\lVert s_{k,b}\rVert_{\max}\le C_H ∥ r k , b ∥ m a x , ∥ s k , b ∥ m a x ≤ C H and rescaled the coefficient vectors when applying Theorem 1. Together with the post-quadratic remainder bound in A9, (191) therefore gives
δ H : = sup ∥ b ∥ max ≤ 1 ∣ b T E H ∣ = o ( 1 ) . (193) \delta_H:=\sup_{\lVert b\rVert_{\max}\le1}\left|b^{\mathsf T}E_H\right|=o(1). \tag*{(193)} δ H := ∥ b ∥ m a x ≤ 1 sup b T E H = o ( 1 ) . (193)
If the sharper O ( M − 1 / 2 ) O(M^{-1/2}) O ( M − 1/2 ) remainder bound in A9 holds, then
δ H = O ( M − 1 / 2 ) . (194) \delta_H=O(M^{-1/2}). \tag*{(194)} δ H = O ( M − 1/2 ) . (194)
Recall μ = − 1 2 J − 1 H ( Σ ‾ ) \mu=-\frac{1}{2}J^{-1}H(\overline{\Sigma}) μ = − 2 1 J − 1 H ( Σ ) , so J μ + 1 2 H ( Σ ‾ ) = 0 J\mu+\frac{1}{2}H(\overline{\Sigma})=0 J μ + 2 1 H ( Σ ) = 0 . Combining this identity with stationarity and (191) gives
m − μ = ∫ 0 ∞ e J t E H d t . (195) m-\mu=\int_{0}^{\infty}e^{Jt}E_H\,dt. \tag*{(195)} m − μ = ∫ 0 ∞ e J t E H d t . (195)
For any a ∈ R n − 1 a\in\mathbb{R}^{n-1} a ∈ R n − 1 with ∥ a ∥ = 1 \lVert a\rVert=1 ∥ a ∥ = 1 , A6 and duality imply
∣ a T L φ ( m − μ ) ∣ ≤ ∫ 0 ∞ ∥ e J T t L φ T a ∥ max δ H d t ≤ C s ∥ φ ∥ ∞ γ s M δ H . (196) \left|a^{\mathsf T}L_{\varphi}(m-\mu)\right|\le\int_{0}^{\infty}\left\lVert e^{J^{\mathsf T}t}L_{\varphi}^{\mathsf T}a\right\rVert_{\max}\delta_H\,dt\le\frac{C_s\lVert\varphi\rVert_{\infty}}{\gamma_s\sqrt{M}}\delta_H. \tag*{(196)} a T L φ ( m − μ ) ≤ ∫ 0 ∞ e J T t L φ T a m a x δ H d t ≤ γ s M C s ∥ φ ∥ ∞ δ H . (196)
Since E [ X φ ( ∞ ) ] − x φ ∗ = M − 1 / 2 L φ m \mathbb{E}[X_{\varphi}(\infty)]-x_{\varphi}^*=M^{-1/2}L_{\varphi}m E [ X φ ( ∞ )] − x φ ∗ = M − 1/2 L φ m and β φ / M = M − 1 / 2 L φ μ \beta_{\varphi}/M=M^{-1/2}L_{\varphi}\mu β φ / M = M − 1/2 L φ μ , (193)–(196) yield
∥ E [ X φ ( ∞ ) ] − x φ ∗ − β φ M ∥ = o ( M − 1 ) . (197) \left\lVert\mathbb{E}[X_{\varphi}(\infty)]-x_{\varphi}^*-\frac{\beta_{\varphi}}{M}\right\rVert=o(M^{-1}). \tag*{(197)} E [ X φ ( ∞ )] − x φ ∗ − M β φ = o ( M − 1 ) . (197)
Under the sharper version of A9, (194) gives the sharper bound O ( M − 3 / 2 ) O(M^{-3/2}) O ( M − 3/2 ) in (197). For the covariance, Theorem 1 gives
∥ L φ ( Σ − Σ ‾ ) L φ T ∥ o p = O ( M − 1 / 2 ) . (198) \left\lVert L_{\varphi}(\Sigma-\overline{\Sigma})L_{\varphi}^{\mathsf T}\right\rVert_{\mathrm{op}}=O(M^{-1/2}). \tag*{(198)} L φ ( Σ − Σ ) L φ T op = O ( M − 1/2 ) . (198)
Moreover, by Corollary 1, the outer product of the conditional mean of Y φ Y_{\varphi} Y φ with itself has operator norm O ( M − 1 ) O(M^{-1}) O ( M − 1 ) . Hence
∥ Cov ( Y φ ∣ θ ) − Γ φ ∥ o p = O ( M − 1 / 2 ) , ∥ Cov ( X φ ( ∞ ) ∣ θ ) − Γ φ M ∥ o p = O ( M − 3 / 2 ) . (199) \left\lVert\operatorname{Cov}(Y_{\varphi}\mid\theta)-\Gamma_{\varphi}\right\rVert_{\mathrm{op}}=O(M^{-1/2}),\qquad
\left\lVert\operatorname{Cov}(X_{\varphi}(\infty)\mid\theta)-\frac{\Gamma_{\varphi}}{M}\right\rVert_{\mathrm{op}}=O(M^{-3/2}). \tag*{(199)} ∥ Cov ( Y φ ∣ θ ) − Γ φ ∥ op = O ( M − 1/2 ) , Cov ( X φ ( ∞ ) ∣ θ ) − M Γ φ op = O ( M − 3/2 ) . (199)
For the performance expansion, Taylor’s theorem at x φ ∗ x_\varphi^* x φ ∗ gives
h ( X φ ( ∞ ) ) = h ( x φ ∗ ) + D h ( x φ ∗ ) [ X φ ( ∞ ) − x φ ∗ ] + 1 2 D 2 h ( x φ ∗ ) [ X φ ( ∞ ) − x φ ∗ , X φ ( ∞ ) − x φ ∗ ] + R h ( X φ ( ∞ ) ) . (200) h(X_\varphi(\infty)) = h(x_\varphi^*) + Dh(x_\varphi^*)[X_\varphi(\infty)-x_\varphi^*] + \frac{1}{2}D^2h(x_\varphi^*)[X_\varphi(\infty)-x_\varphi^*,X_\varphi(\infty)-x_\varphi^*] + R_h(X_\varphi(\infty)). \tag*{(200)} h ( X φ ( ∞ )) = h ( x φ ∗ ) + D h ( x φ ∗ ) [ X φ ( ∞ ) − x φ ∗ ] + 2 1 D 2 h ( x φ ∗ ) [ X φ ( ∞ ) − x φ ∗ , X φ ( ∞ ) − x φ ∗ ] + R h ( X φ ( ∞ )) . (200)
By (197) and (199) ,
D h ( x φ ∗ ) [ E [ X φ ( ∞ ) ] − x φ ∗ ] = 1 M D h ( x φ ∗ ) [ β φ ] + o ( M − 1 ) , Dh(x_\varphi^*)[\mathbb{E}[X_\varphi(\infty)]-x_\varphi^*] = \frac{1}{M}Dh(x_\varphi^*)[\beta_\varphi] + o(M^{-1}), D h ( x φ ∗ ) [ E [ X φ ( ∞ )] − x φ ∗ ] = M 1 D h ( x φ ∗ ) [ β φ ] + o ( M − 1 ) ,
E [ D 2 h ( x φ ∗ ) [ X φ ( ∞ ) − x φ ∗ , X φ ( ∞ ) − x φ ∗ ] ] = 1 M Tr ( D 2 h ( x φ ∗ ) Γ φ ) + o ( M − 1 ) . (201) \mathbb{E}\left[D^2h(x_\varphi^*)[X_\varphi(\infty)-x_\varphi^*,X_\varphi(\infty)-x_\varphi^*]\right] = \frac{1}{M}\operatorname{Tr}(D^2h(x_\varphi^*)\Gamma_\varphi) + o(M^{-1}). \tag*{(201)} E [ D 2 h ( x φ ∗ ) [ X φ ( ∞ ) − x φ ∗ , X φ ( ∞ ) − x φ ∗ ] ] = M 1 Tr ( D 2 h ( x φ ∗ ) Γ φ ) + o ( M − 1 ) . (201)
In the second equality, the outer product of E [ X φ ( ∞ ) ] − x φ ∗ \mathbb{E}[X_\varphi(\infty)]-x_\varphi^* E [ X φ ( ∞ )] − x φ ∗ with itself has operator norm O ( M − 2 ) O(M^{-2}) O ( M − 2 ) by Corollary 1.
Applying Lemma 1 coordinatewise gives
E ∥ X φ ( ∞ ) − x φ ∗ ∥ 2 ≤ C φ M , E ∥ X φ ( ∞ ) − x φ ∗ ∥ 4 ≤ C φ M 2 . (202) \mathbb{E}\|X_\varphi(\infty)-x_\varphi^*\|^2 \le\frac{C_\varphi}{M}, \qquad\mathbb{E}\|X_\varphi(\infty)-x_\varphi^*\|^4 \le\frac{C_\varphi}{M^2}. \tag*{(202)} E ∥ X φ ( ∞ ) − x φ ∗ ∥ 2 ≤ M C φ , E ∥ X φ ( ∞ ) − x φ ∗ ∥ 4 ≤ M 2 C φ . (202)
Let
ω h ( r ) = sup y , z ∈ K φ ∥ y − z ∥ ≤ r ∥ D 2 h ( y ) − D 2 h ( z ) ∥ o p , B h = sup y ∈ K φ ∥ D 2 h ( y ) ∥ o p . (203) \omega_h(r) = \sup_{\substack{y,z\in K_\varphi\\ \|y-z\|\le r}}\|D^2h(y)-D^2h(z)\|_{\mathrm{op}}, \qquad B_h = \sup_{y\in K_\varphi}\|D^2h(y)\|_{\mathrm{op}}. \tag*{(203)} ω h ( r ) = y , z ∈ K φ ∥ y − z ∥ ≤ r sup ∥ D 2 h ( y ) − D 2 h ( z ) ∥ op , B h = y ∈ K φ sup ∥ D 2 h ( y ) ∥ op . (203)
The Taylor remainder satisfies ∣ R h ( X φ ( ∞ ) ) ∣ ≤ 1 2 ω h ( ∥ X φ ( ∞ ) − x φ ∗ ∥ ) ∥ X φ ( ∞ ) − x φ ∗ ∥ 2 |R_h(X_\varphi(\infty))| \le\frac{1}{2}\omega_h(\|X_\varphi(\infty)-x_\varphi^*\|)\|X_\varphi(\infty)-x_\varphi^*\|^2 ∣ R h ( X φ ( ∞ )) ∣ ≤ 2 1 ω h ( ∥ X φ ( ∞ ) − x φ ∗ ∥ ) ∥ X φ ( ∞ ) − x φ ∗ ∥ 2 . For fixed η > 0 \eta>0 η > 0 , split the expectation over { ∥ X φ ( ∞ ) − x φ ∗ ∥ ≤ η } \{\|X_\varphi(\infty)-x_\varphi^*\|\le\eta\} { ∥ X φ ( ∞ ) − x φ ∗ ∥ ≤ η } and its complement. Using ω h ( r ) ≤ 2 B h \omega_h(r)\le2B_h ω h ( r ) ≤ 2 B h and (202) gives
M E ∣ R h ( X φ ( ∞ ) ) ∣ ≤ C φ 2 ω h ( η ) + C φ B h M η 2 . (204) M\mathbb{E}|R_h(X_\varphi(\infty))| \le\frac{C_\varphi}{2}\omega_h(\eta) + \frac{C_\varphi B_h}{M\eta^2}. \tag*{(204)} M E ∣ R h ( X φ ( ∞ )) ∣ ≤ 2 C φ ω h ( η ) + M η 2 C φ B h . (204)
Since D 2 h D^2h D 2 h is uniformly continuous on K φ K_\varphi K φ , ω h ( η ) → 0 \omega_h(\eta)\to0 ω h ( η ) → 0 as η ↓ 0 \eta\downarrow0 η ↓ 0 . Taking M → ∞ M\to\infty M → ∞ and then η ↓ 0 \eta\downarrow0 η ↓ 0 in (204) yields
E ∣ R h ( X φ ( ∞ ) ) ∣ = o ( M − 1 ) . (205) \mathbb{E}|R_h(X_\varphi(\infty))| = o(M^{-1}). \tag*{(205)} E ∣ R h ( X φ ( ∞ )) ∣ = o ( M − 1 ) . (205)
Taking expectations in (200) and using (201) and (205) proves the performance expansion.
Application: Heterogeneous Power-of-Two Choices with B = 2 B=2 B = 2
We consider a heterogeneous power-of-two-choices system with M M M servers and buffer size B = 2 B=2 B = 2 , including the job in service. Server m m m has service rate μ m \mu_m μ m , where
0 < μ ‾ ≤ μ m ≤ μ ‾ < ∞ , m = 1 , … , M . (206) 0 < \underline{\mu}\le\mu_m\le\overline{\mu}<\infty,\qquad m=1,\ldots,M. \tag*{(206)} 0 < μ ≤ μ m ≤ μ < ∞ , m = 1 , … , M . (206)
The arrival-rate parameter λ > 0 \lambda>0 λ > 0 is fixed independently of M M M . Jobs arrive according to a Poisson process of rate λ M \lambda M λ M . Each arrival samples two servers independently and uniformly with replacement and is routed to the server with the shorter queue; ties are broken uniformly. An arrival is discarded if both sampled servers contain two jobs. Throughout this section, we condition on the realized service-rate vector μ = ( μ 1 , … , μ M ) T \boldsymbol{\mu}=(\mu_1,\ldots,\mu_M)^\mathsf{T} μ = ( μ 1 , … , μ M ) T . Let Q m ( t ) ∈ { 0 , 1 , 2 } Q_m(t) \in\{0,1,2\} Q m ( t ) ∈ { 0 , 1 , 2 } be the queue length of server m m m and use the following state representation
W m ( t ) = ( W m , 1 ( t ) W m , 2 ( t ) ) = ( 1 { Q m ( t ) ≥ 1 } 1 { Q m ( t ) = 2 } ) ∈ S = { ( 0 0 ) , ( 1 0 ) , ( 1 1 ) } . (207) W_m(t)=\begin{pmatrix}W_{m,1}(t)\\ W_{m,2}(t)\end{pmatrix}
=\begin{pmatrix}\mathbb{1}\{Q_m(t)\ge1\}\\ \mathbb{1}\{Q_m(t)=2\}\end{pmatrix}
\in\mathcal{S}=\left\{\begin{pmatrix}0\\0\end{pmatrix},\begin{pmatrix}1\\0\end{pmatrix},\begin{pmatrix}1\\1\end{pmatrix}\right\}. \tag*{(207)} W m ( t ) = ( W m , 1 ( t ) W m , 2 ( t ) ) = ( 1 { Q m ( t ) ≥ 1 } 1 { Q m ( t ) = 2 } ) ∈ S = { ( 0 0 ) , ( 1 0 ) , ( 1 1 ) } . (207)
This is an invertible linear transformation of the reduced one-hot representation. Specifically, if W ~ m = ( 1 { Q m = 1 } , 1 { Q m = 2 } ) T \widetilde{W}_m=(\mathbb{1}\{Q_m=1\},\mathbb{1}\{Q_m=2\})^{\mathsf{T}} W m = ( 1 { Q m = 1 } , 1 { Q m = 2 } ) T , then
W m = ( 1 1 0 1 ) W ~ m . (208) W_m=\begin{pmatrix}1&1\\0&1\end{pmatrix}\widetilde{W}_m. \tag*{(208)} W m = ( 1 0 1 1 ) W m . (208)
Since the transformation and its inverse have fixed operator norms, the assumptions and conclusions of § 4 and § 5 carry over with constants independent of M M M . In tail coordinates, the single-server mean-field state lies in the triangle in (212) , the empirical tail occupancy lies in the triangle in (215) , and the weighted tail occupancy lies in the box in (258) .
Define the empirical tail occupancies
X i ( W ) = 1 M ∑ m = 1 M W m , i , i = 1 , 2. (209) X_i(W)=\frac{1}{M}\sum_{m=1}^{M}W_{m,i},\qquad i=1,2. \tag*{(209)} X i ( W ) = M 1 m = 1 ∑ M W m , i , i = 1 , 2. (209)
This model fits the framework of § 3 with θ m = μ m \theta_m=\mu_m θ m = μ m , χ ≡ 1 \chi\equiv1 χ ≡ 1 , and Ψ \Psi Ψ equal to the identity map on R 2 \mathbb{R}^2 R 2 , so the interaction field is Z ( W ) = ( X 1 ( W ) , X 2 ( W ) ) T Z(W)=(X_1(W),X_2(W))^{\mathsf{T}} Z ( W ) = ( X 1 ( W ) , X 2 ( W ) ) T . The transition rates of server m m m are
( 0 0 ) ⟶ ( 1 0 ) at rate λ ( 1 + X 1 ) , ( 1 0 ) ⟶ ( 1 1 ) at rate λ ( X 1 + X 2 ) , \begin{pmatrix}0\\0\end{pmatrix}\longrightarrow\begin{pmatrix}1\\0\end{pmatrix}\quad\text{at rate }\lambda(1+X_1),\qquad
\begin{pmatrix}1\\0\end{pmatrix}\longrightarrow\begin{pmatrix}1\\1\end{pmatrix}\quad\text{at rate }\lambda(X_1+X_2), ( 0 0 ) ⟶ ( 1 0 ) at rate λ ( 1 + X 1 ) , ( 1 0 ) ⟶ ( 1 1 ) at rate λ ( X 1 + X 2 ) ,
\begin{pmatrix}1\\0\end{pmatrix}\longrightarrow\begin{pmatrix}0\\0\end{pmatrix}\quad\text{at rate }\mu_m,\qquad
\begin{pmatrix}1\\1\end{pmatrix}\longrightarrow\begin{pmatrix}1\\0\end{pmatrix}\quad\text{at rate }\mu_m. \tag*{(210)}\end{pmatrix}
Because λ > 0 \lambda>0 λ > 0 , μ m > 0 \mu_m>0 μ m > 0 , and sampling is with replacement, the finite CTMC is irreducible and therefore has a unique stationary distribution. For w m = ( w m , 1 , w m , 2 ) T w_m=(w_{m,1},w_{m,2})^{\mathsf{T}} w m = ( w m , 1 , w m , 2 ) T and x i ( w ) = M − 1 ∑ m w m , i x_i(w)=M^{-1}\sum_m w_{m,i} x i ( w ) = M − 1 ∑ m w m , i , the mean-field drift is
F m , 1 ( w ) = λ ( 1 + x 1 ) ( 1 − w m , 1 ) − μ m ( w m , 1 − w m , 2 ) , F m , 2 ( w ) = λ ( x 1 + x 2 ) ( w m , 1 − w m , 2 ) − μ m w m , 2 . (211) \begin{aligned}
F_{m,1}(w)&=\lambda(1+x_1)(1-w_{m,1})-\mu_m(w_{m,1}-w_{m,2}),\\
F_{m,2}(w)&=\lambda(x_1+x_2)(w_{m,1}-w_{m,2})-\mu_m w_{m,2}. \tag*{(211)}
\end{aligned} F m , 1 ( w ) F m , 2 ( w ) = λ ( 1 + x 1 ) ( 1 − w m , 1 ) − μ m ( w m , 1 − w m , 2 ) , = λ ( x 1 + x 2 ) ( w m , 1 − w m , 2 ) − μ m w m , 2 . (211)
The admissible state space of one mean-field block is
D p o 2 = { ( w 1 , w 2 ) T ∈ R 2 : 0 ≤ w 2 ≤ w 1 ≤ 1 } . (212) \mathcal{D}_{\mathrm{po2}}=\left\{(w_1,w_2)^{\mathsf{T}}\in\mathbb{R}^2:0\le w_2\le w_1\le1\right\}. \tag*{(212)} D po2 = { ( w 1 , w 2 ) T ∈ R 2 : 0 ≤ w 2 ≤ w 1 ≤ 1 } . (212)
For this application, we take the full admissible mean-field domain in § 3 to be D = D p o 2 × M \mathcal{D}=\mathcal{D}_{\mathrm{po2}}^{\times M} D = D po2 × M , which is compact, convex, and forward invariant under (211).
For fixed ( x 1 , x 2 ) (x_1,x_2) ( x 1 , x 2 ) , let
a = λ ( 1 + x 1 ) , b = λ ( x 1 + x 2 ) , D m = μ m 2 + μ m a + a b . (213) a=\lambda(1+x_1),\qquad b=\lambda(x_1+x_2),\qquad D_m=\mu_m^2+\mu_m a+ab. \tag*{(213)} a = λ ( 1 + x 1 ) , b = λ ( x 1 + x 2 ) , D m = μ m 2 + μ m a + ab . (213)
The stationary tail probabilities of the corresponding three-state birth–death chain are
w m , 1 = a ( μ m + b ) D m , w m , 2 = a b D m . (214) w_{m,1}=\frac{a(\mu_m+b)}{D_m},\qquad w_{m,2}=\frac{ab}{D_m}. \tag*{(214)} w m , 1 = D m a ( μ m + b ) , w m , 2 = D m ab . (214)
Consequently, (214) defines a continuous map from
K = { ( x 1 , x 2 ) T ∈ R 2 : 0 ≤ x 2 ≤ x 1 ≤ 1 } (215) \mathcal{K}=\left\{(x_1,x_2)^{\mathsf{T}}\in\mathbb{R}^2:0\le x_2\le x_1\le1\right\} \tag*{(215)} K = { ( x 1 , x 2 ) T ∈ R 2 : 0 ≤ x 2 ≤ x 1 ≤ 1 } (215)
into itself by averaging over m m m . Brouwer’s fixed-point theorem therefore gives at least one equilibrium w ∗ w^* w ∗ . Its uniqueness follows from the incremental stability proved below.
Verification of S1–S2
We first verify S1. For v = ( v 1 , v 2 ) ⊤ v=(v_1,v_2)^\top v = ( v 1 , v 2 ) ⊤ and x = ( x 1 , x 2 ) ⊤ x=(x_1,x_2)^\top x = ( x 1 , x 2 ) ⊤ , define
A ( x ; μ ) = ( − λ ( 1 + x 1 ) − μ μ λ ( x 1 + x 2 ) − λ ( x 1 + x 2 ) − μ ) , a ( x ; μ ) = ( λ ( 1 + x 1 ) 0 ) . (216) A(x;\mu)=\begin{pmatrix}
-\lambda(1+x_1)-\mu& \mu\\
\lambda(x_1+x_2) & -\lambda(x_1+x_2)-\mu
\end{pmatrix},\qquad
a(x;\mu)=\begin{pmatrix}
\lambda(1+x_1) \\
0
\end{pmatrix}. \tag*{(216)} A ( x ; μ ) = ( − λ ( 1 + x 1 ) − μ λ ( x 1 + x 2 ) μ − λ ( x 1 + x 2 ) − μ ) , a ( x ; μ ) = ( λ ( 1 + x 1 ) 0 ) . (216)
Then the drift in (211) can be written as
f ( v , x ; μ ) = A ( x ; μ ) v + a ( x ; μ ) . (217) f(v,x;\mu)=A(x;\mu)v+a(x;\mu). \tag*{(217)} f ( v , x ; μ ) = A ( x ; μ ) v + a ( x ; μ ) . (217)
Thus the new local approximately affine condition S1 holds with residual r ≡ 0 r\equiv0 r ≡ 0 . In fact, (217) holds globally on D p o 2 × K \mathcal{D}_{\mathrm{po}2}\times\mathcal{K} D po 2 × K , so any fixed local radius η A > 0 \eta_A>0 η A > 0 allowed by the interaction domain may be used. Moreover, A A A and a a a are affine in x x x , their first derivatives are uniformly bounded under (206) , and their second derivatives vanish identically. Hence one may take ω A ≡ ω r ≡ 0 \omega_A\equiv\omega_r\equiv0 ω A ≡ ω r ≡ 0 , so both S1 and its sharper version hold. In particular, the drift is exactly quadratic in the full mean-field state and the post-quadratic remainder T F T_F T F vanishes identically.
We next verify S2. Each transition changes exactly one tail coordinate by ± 1 \pm1 ± 1 , so
Q ( w ) = diag ( q 1 , 1 ( w ) , q 1 , 2 ( w ) , … , q M , 1 ( w ) , q M , 2 ( w ) ) , (218) Q(w)=\operatorname{diag}\bigl(q_{1,1}(w),q_{1,2}(w),\ldots,q_{M,1}(w),q_{M,2}(w)\bigr), \tag*{(218)} Q ( w ) = diag ( q 1 , 1 ( w ) , q 1 , 2 ( w ) , … , q M , 1 ( w ) , q M , 2 ( w ) ) , (218)
where
q m , 1 ( w ) = λ ( 1 − w m , 1 ) ( 1 + x 1 ) + μ m ( w m , 1 − w m , 2 ) , q m , 2 ( w ) = λ ( w m , 1 − w m , 2 ) ( x 1 + x 2 ) + μ m w m , 2 . (219) \begin{aligned}
q_{m,1}(w)&=\lambda(1-w_{m,1})(1+x_1)+\mu_m(w_{m,1}-w_{m,2}),\\
q_{m,2}(w)&=\lambda(w_{m,1}-w_{m,2})(x_1+x_2)+\mu_m w_{m,2}. \tag*{(219)}
\end{aligned} q m , 1 ( w ) q m , 2 ( w ) = λ ( 1 − w m , 1 ) ( 1 + x 1 ) + μ m ( w m , 1 − w m , 2 ) , = λ ( w m , 1 − w m , 2 ) ( x 1 + x 2 ) + μ m w m , 2 . (219)
Fix b b b with ∥ b ∥ max ≤ 1 \lVert b\rVert_{\max}\le1 ∥ b ∥ m a x ≤ 1 , and define e ( 1 ) , e ( + ) ∈ R 2 M e^{(1)},e^{(+)}\in\mathbb{R}^{2M} e ( 1 ) , e ( + ) ∈ R 2 M by
e m ( 1 ) = ( 1 , 0 ) ⊤ , e m ( + ) = ( 1 , 1 ) ⊤ . (220) e_m^{(1)}=(1,0)^\top,\qquad e_m^{(+)}=(1,1)^\top. \tag*{(220)} e m ( 1 ) = ( 1 , 0 ) ⊤ , e m ( + ) = ( 1 , 1 ) ⊤ . (220)
Also define
a b , m = ( b m , 1 2 ( μ m − λ ( 1 + x 1 ∗ ) ) + b m , 2 2 λ ( x 1 ∗ + x 2 ∗ ) − b m , 1 2 μ m + b m , 2 2 ( μ m − λ ( x 1 ∗ + x 2 ∗ ) ) ) , d b , m ( 1 ) = ( b m , 1 2 , 0 ) ⊤ , d b , m ( 2 ) = ( b m , 2 2 , − b m , 2 2 ) ⊤ , ρ 1 , b = λ M ∑ m = 1 M b m , 1 2 ( 1 − w m , 1 ∗ ) , ρ 2 , b = λ M ∑ m = 1 M b m , 2 2 ( w m , 1 ∗ − w m , 2 ∗ ) . (221) \begin{aligned}
a_{b,m}&=\begin{pmatrix}
b_{m,1}^{2}\bigl(\mu_m-\lambda(1+x_1^*)\bigr)+b_{m,2}^{2}\lambda(x_1^*+x_2^*)\\
-b_{m,1}^{2}\mu_m+b_{m,2}^{2}\bigl(\mu_m-\lambda(x_1^*+x_2^*)\bigr)
\end{pmatrix},\\
d_{b,m}^{(1)}&=(b_{m,1}^{2},0)^\top,\qquad
d_{b,m}^{(2)}=(b_{m,2}^{2},-b_{m,2}^{2})^\top,\\
\rho_{1,b}&=\frac{\lambda}{M}\sum_{m=1}^{M}b_{m,1}^{2}(1-w_{m,1}^{*}),\qquad
\rho_{2,b}=\frac{\lambda}{M}\sum_{m=1}^{M}b_{m,2}^{2}(w_{m,1}^{*}-w_{m,2}^{*}). \tag*{(221)}
\end{aligned} a b , m d b , m ( 1 ) ρ 1 , b = ( b m , 1 2 ( μ m − λ ( 1 + x 1 ∗ ) ) + b m , 2 2 λ ( x 1 ∗ + x 2 ∗ ) − b m , 1 2 μ m + b m , 2 2 ( μ m − λ ( x 1 ∗ + x 2 ∗ ) ) ) , = ( b m , 1 2 , 0 ) ⊤ , d b , m ( 2 ) = ( b m , 2 2 , − b m , 2 2 ) ⊤ , = M λ m = 1 ∑ M b m , 1 2 ( 1 − w m , 1 ∗ ) , ρ 2 , b = M λ m = 1 ∑ M b m , 2 2 ( w m , 1 ∗ − w m , 2 ∗ ) . (221)
Expanding (219) around w ∗ w^* w ∗ gives the exact identity
V b ( w ) = V b ( w ∗ ) + x ˉ a b ( w ) + ρ 1 , b x ˉ e ( 1 ) ( w ) + ρ 2 , b x ˉ e ( + ) ( w ) − λ x ˉ d b ( 1 ) ( w ) x ˉ e ( 1 ) ( w ) + λ x ˉ d b ( 2 ) ( w ) x ˉ e ( + ) ( w ) . (222) \begin{aligned}
V_b(w)={}&V_b(w^*)+\bar{x}_{a_b}(w)+\rho_{1,b}\bar{x}_{e^{(1)}}(w)+\rho_{2,b}\bar{x}_{e^{(+)}}(w)\\
&-\lambda\bar{x}_{d_{b}^{(1)}}(w)\bar{x}_{e^{(1)}}(w)+\lambda\bar{x}_{d_{b}^{(2)}}(w)\bar{x}_{e^{(+)}}(w). \tag*{(222)}
\end{aligned} V b ( w ) = V b ( w ∗ ) + x ˉ a b ( w ) + ρ 1 , b x ˉ e ( 1 ) ( w ) + ρ 2 , b x ˉ e ( + ) ( w ) − λ x ˉ d b ( 1 ) ( w ) x ˉ e ( 1 ) ( w ) + λ x ˉ d b ( 2 ) ( w ) x ˉ e ( + ) ( w ) . (222)
Thus S2 has a direct finite weighted-occupancy representation. Specifically, take K Q = 5 K_Q=5 K Q = 5 with
c 1 , b = a b , c 2 , b = e ( 1 ) , c 3 , b = e ( + ) , c 4 , b = d b ( 1 ) , c 5 , b = d b ( 2 ) . (223) c_{1,b}=a_b,\qquad c_{2,b}=e^{(1)},\qquad c_{3,b}=e^{(+)},\qquad c_{4,b}=d_b^{(1)},\qquad c_{5,b}=d_b^{(2)}. \tag*{(223)} c 1 , b = a b , c 2 , b = e ( 1 ) , c 3 , b = e ( + ) , c 4 , b = d b ( 1 ) , c 5 , b = d b ( 2 ) . (223)
For z = ( z 1 , … , z 5 ) ⊤ z=(z_1,\ldots,z_5)^\top z = ( z 1 , … , z 5 ) ⊤ , define
V ^ b ( z ) = V b ( w ∗ ) + z 1 + ρ 1 , b z 2 + ρ 2 , b z 3 − λ z 4 z 2 + λ z 5 z 3 . (224) \widehat{V}_b(z)=V_b(w^*)+z_1+\rho_{1,b}z_2+\rho_{2,b}z_3-\lambda z_4z_2+\lambda z_5z_3. \tag*{(224)} V b ( z ) = V b ( w ∗ ) + z 1 + ρ 1 , b z 2 + ρ 2 , b z 3 − λ z 4 z 2 + λ z 5 z 3 . (224)
Then (222) is exactly
V b ( w ) = V ^ b ( x ˉ c 1 , b ( w ) , … , x ˉ c 5 , b ( w ) ) . (225) V_b(\mathbf{w})=\widehat{V}_b\left(\bar{x}_{c_{1,b}}(\mathbf{w}),\ldots,\bar{x}_{c_{5,b}}(\mathbf{w})\right). \tag*{(225)} V b ( w ) = V b ( x ˉ c 1 , b ( w ) , … , x ˉ c 5 , b ( w ) ) . (225)
All vectors in (223) have uniformly bounded block-max norms, and ∣ ρ 1 , b ∣ + ∣ ρ 2 , b ∣ ≤ 2 λ |\rho_{1,b}|+|\rho_{2,b}|\le2\lambda ∣ ρ 1 , b ∣ + ∣ ρ 2 , b ∣ ≤ 2 λ . Moreover, for every w ∈ D p o 2 × M \mathbf{w}\in D_{\mathrm{po2}}^{\times M} w ∈ D po2 × M ,
q m , 1 ( w ) + q m , 2 ( w ) ≤ 2 λ ( ( 1 − w m , 1 ) + ( w m , 1 − w m , 2 ) ) + μ m w m , 1 ≤ 2 λ + μ ˉ . (226) q_{m,1}(\mathbf{w})+q_{m,2}(\mathbf{w})\le2\lambda\left((1-w_{m,1})+(w_{m,1}-w_{m,2})\right)+\mu_mw_{m,1}\le2\lambda+\bar{\mu}. \tag*{(226)} q m , 1 ( w ) + q m , 2 ( w ) ≤ 2 λ ( ( 1 − w m , 1 ) + ( w m , 1 − w m , 2 ) ) + μ m w m , 1 ≤ 2 λ + μ ˉ . (226)
Therefore, since b m , i 2 ≤ 1 b_{m,i}^{2}\le1 b m , i 2 ≤ 1 ,
0 ≤ V b ( w ∗ ) ≤ 1 M ∑ m = 1 M ( q m , 1 ( w ∗ ) + q m , 2 ( w ∗ ) ) ≤ 2 λ + μ ˉ . (227) 0\le V_b(\mathbf{w}^{*})\le\frac{1}{M}\sum_{m=1}^{M}\left(q_{m,1}(\mathbf{w}^{*})+q_{m,2}(\mathbf{w}^{*})\right)\le2\lambda+\bar{\mu}. \tag*{(227)} 0 ≤ V b ( w ∗ ) ≤ M 1 m = 1 ∑ M ( q m , 1 ( w ∗ ) + q m , 2 ( w ∗ ) ) ≤ 2 λ + μ ˉ . (227)
Finally, V ^ b \widehat{V}_b V b in (224) is a quadratic polynomial. Hence, for any fixed η Q > 0 \eta_Q>0 η Q > 0 , V ^ b \widehat{V}_b V b and its first two derivatives are uniformly bounded on { ∥ z ∥ ∞ ≤ η Q } \{\lVert\mathbf{z}\rVert_{\infty}\le\eta_Q\} {∥ z ∥ ∞ ≤ η Q } , with constants depending only on λ \lambda λ , μ ˉ \bar{\mu} μ ˉ , and η Q \eta_Q η Q . Therefore S2 holds uniformly in M M M , μ \mu μ , and b b b .
Verification of A1–A6
Set
ϑ = min { 1 , μ 4 λ } , c = 1 + ϑ , β = ϑ μ 1 + ϑ > 0. (228) \vartheta=\min\left\{1,\frac{\mu}{4\lambda}\right\},\qquad c=1+\vartheta,\qquad\beta=\frac{\vartheta\mu}{1+\vartheta}>0. \tag*{(228)} ϑ = min { 1 , 4 λ μ } , c = 1 + ϑ , β = 1 + ϑ ϑ μ > 0. (228)
Lemma 3. Under (206) , the heterogeneous power-of-two-choices model with B = 2 B=2 B = 2 satisfies A1–A6 for every fixed λ > 0 \lambda>0 λ > 0 .
Proof. A1 follows because the total accepted-arrival rate is at most λ M \lambda M λ M and the total service rate is at most μ ˉ M \bar{\mu}M μ ˉ M . A2 holds because every transition changes the state of one server. A3 follows from (211) , whose entries are quadratic polynomials with derivatives uniformly bounded on D p o 2 × M D_{\mathrm{po2}}^{\times M} D po2 × M .
We first establish a weighted 1-norm contraction. Let J ( w ) = D F ( w ) J(\mathbf{w})=DF(\mathbf{w}) J ( w ) = D F ( w ) and let p ∈ R 2 M \mathbf{p}\in\mathbb{R}^{2M} p ∈ R 2 M have every block equal to ( 1 , c ) T (1,c)^{\mathsf{T}} ( 1 , c ) T . Since J ( w ) J(\mathbf{w}) J ( w ) is Metzler, it suffices to bound its weighted column sums. Summing the two drift coordinates with weights 1 and c c c gives
∑ m = 1 M ( F m , 1 ( w ) + c F m , 2 ( w ) ) = λ M ( 1 + ϑ x 1 2 − c x 2 2 ) − ∑ m = 1 M μ m w m , 1 − ϑ ∑ m = 1 M μ m w m , 2 . (229) \sum_{m=1}^{M}\left(F_{m,1}(\mathbf{w})+cF_{m,2}(\mathbf{w})\right)=\lambda M(1+\vartheta x_1^2-cx_2^2)-\sum_{m=1}^{M}\mu_mw_{m,1}-\vartheta\sum_{m=1}^{M}\mu_mw_{m,2}. \tag*{(229)} m = 1 ∑ M ( F m , 1 ( w ) + c F m , 2 ( w ) ) = λ M ( 1 + ϑ x 1 2 − c x 2 2 ) − m = 1 ∑ M μ m w m , 1 − ϑ m = 1 ∑ M μ m w m , 2 . (229)
Differentiating (229) with respect to w j , 1 w_{j,1} w j , 1 and w j , 2 w_{j,2} w j , 2 yields
( p T J ( w ) ) j , 1 = − μ j + 2 λ ϑ x 1 ≤ − μ + 2 λ ϑ ≤ − μ 2 ≤ − β , (\mathbf{p}^{\mathsf{T}}J(\mathbf{w}))_{j,1}=-\mu_j+2\lambda\vartheta x_1\le-\mu+2\lambda\vartheta\le-\frac{\mu}{2}\le-\beta, ( p T J ( w ) ) j , 1 = − μ j + 2 λ ϑ x 1 ≤ − μ + 2 λ ϑ ≤ − 2 μ ≤ − β ,
( p T J ( w ) ) j , 2 = − ϑ μ j − 2 c λ x 2 ≤ − ϑ μ = − β c . (230) (\mathbf{p}^{\mathsf{T}}J(\mathbf{w}))_{j,2}=-\vartheta\mu_j-2c\lambda x_2\le-\vartheta\mu=-\beta c. \tag*{(230)} ( p T J ( w ) ) j , 2 = − ϑ μ j − 2 c λ x 2 ≤ − ϑ μ = − β c . (230)
For any two mean-field trajectories w ( t ) \mathbf{w}(t) w ( t ) and w ~ ( t ) \widetilde{\mathbf{w}}(t) w ( t ) , their difference u ( t ) = w ( t ) − w ~ ( t ) \mathbf{u}(t)=\mathbf{w}(t)-\widetilde{\mathbf{w}}(t) u ( t ) = w ( t ) − w ( t ) satisfies
u ˙ ( t ) = J ( t ) u ( t ) , J ( t ) = ∫ 0 1 J ( w ~ ( t ) + s u ( t ) ) d s . (231) \dot{\mathbf{u}}(t)=J(t)\mathbf{u}(t),\qquad J(t)=\int_{0}^{1}J\left(\widetilde{\mathbf{w}}(t)+s\mathbf{u}(t)\right)\,\mathrm{d}s. \tag*{(231)} u ˙ ( t ) = J ( t ) u ( t ) , J ( t ) = ∫ 0 1 J ( w ( t ) + s u ( t ) ) d s . (231)
The matrix J ( t ) J(t) J ( t ) is Metzler and satisfies (230) . Therefore, with
V ( t ) = 1 M ∑ m = 1 M ( ∣ u m , 1 ( t ) ∣ + c ∣ u m , 2 ( t ) ∣ ) , (232) V(t)=\frac{1}{M}\sum_{m=1}^{M}\left(|u_{m,1}(t)|+c|u_{m,2}(t)|\right), \tag*{(232)} V ( t ) = M 1 m = 1 ∑ M ( ∣ u m , 1 ( t ) ∣ + c ∣ u m , 2 ( t ) ∣ ) , (232)
the upper-right Dini derivative satisfies
D + V ( t ) ≤ − β V ( t ) , V ( t ) ≤ e − β t V ( 0 ) . (233) D^{+}V(t) \le-\beta V(t), \qquad V(t) \le e^{-\beta t}V(0). \tag*{(233)} D + V ( t ) ≤ − β V ( t ) , V ( t ) ≤ e − β t V ( 0 ) . (233)
We next prove A4 in the normalized Euclidean norm. Set u ˉ i = M − 1 ∑ m u m , i \bar{u}_i=M^{-1}\sum_m u_{m,i} u ˉ i = M − 1 ∑ m u m , i . Direct subtraction of the two mean-field systems gives
u ˙ m , 1 = − ( μ m + λ ( 1 + x 1 ) ) u m , 1 + μ m u m , 2 + λ ( 1 − w ~ m , 1 ) u ˉ 1 , u ˙ m , 2 = λ ( x 1 + x 2 ) u m , 1 − ( μ m + λ ( x 1 + x 2 ) ) u m , 2 + λ ( w ~ m , 1 − w ~ m , 2 ) ( u ˉ 1 + u ˉ 2 ) . (234) \begin{aligned}
\dot{u}_{m,1} &= -\left(\mu_m+\lambda(1+x_1)\right)u_{m,1}+\mu_m u_{m,2}+\lambda(1-\widetilde{w}_{m,1})\bar{u}_1,\\
\dot{u}_{m,2} &= \lambda(x_1+x_2)u_{m,1}-\left(\mu_m+\lambda(x_1+x_2)\right)u_{m,2}+\lambda(\widetilde{w}_{m,1}-\widetilde{w}_{m,2})(\bar{u}_1+\bar{u}_2). \tag*{(234)}
\end{aligned} u ˙ m , 1 u ˙ m , 2 = − ( μ m + λ ( 1 + x 1 ) ) u m , 1 + μ m u m , 2 + λ ( 1 − w m , 1 ) u ˉ 1 , = λ ( x 1 + x 2 ) u m , 1 − ( μ m + λ ( x 1 + x 2 ) ) u m , 2 + λ ( w m , 1 − w m , 2 ) ( u ˉ 1 + u ˉ 2 ) . (234)
where x i = M − 1 ∑ m w m , i x_i=M^{-1}\sum_m w_{m,i} x i = M − 1 ∑ m w m , i refers to the first trajectory. The local homogeneous matrix in (234) is
B m ( t ) = ( − μ m − λ ( 1 + x 1 ( t ) ) μ m λ ( x 1 ( t ) + x 2 ( t ) ) − μ m − λ ( x 1 ( t ) + x 2 ( t ) ) ) . (235) B_m(t)=\begin{pmatrix}
-\mu_m-\lambda(1+x_1(t)) & \mu_m\\
\lambda(x_1(t)+x_2(t)) & -\mu_m-\lambda(x_1(t)+x_2(t))
\end{pmatrix}. \tag*{(235)} B m ( t ) = ( − μ m − λ ( 1 + x 1 ( t )) λ ( x 1 ( t ) + x 2 ( t )) μ m − μ m − λ ( x 1 ( t ) + x 2 ( t )) ) . (235)
Its row sums are − λ ( 1 + x 1 ( t ) ) ≤ − λ -\lambda(1+x_1(t))\le-\lambda − λ ( 1 + x 1 ( t )) ≤ − λ and − μ m ≤ − μ -\mu_m\le-\mu − μ m ≤ − μ . Hence, with a 0 = min { λ , μ } a_0=\min\{\lambda,\mu\} a 0 = min { λ , μ } , the evolution operator Φ m ( t , s ) \Phi_m(t,s) Φ m ( t , s ) of v ˙ = B m ( t ) v \dot{v}=B_m(t)v v ˙ = B m ( t ) v satisfies
∥ Φ m ( t , s ) ∥ ∞ ≤ e − a 0 ( t − s ) , ∥ Φ m ( t , s ) ∥ o p ≤ 2 e − a 0 ( t − s ) . (236) \lVert\Phi_m(t,s)\rVert_{\infty}\le e^{-a_0(t-s)}, \qquad\lVert\Phi_m(t,s)\rVert_{\mathrm{op}}\le\sqrt{2}e^{-a_0(t-s)}. \tag*{(236)} ∥ Φ m ( t , s ) ∥ ∞ ≤ e − a 0 ( t − s ) , ∥ Φ m ( t , s ) ∥ op ≤ 2 e − a 0 ( t − s ) . (236)
The forcing term in (234) has Euclidean norm at most 2 λ V ( t ) 2\lambda V(t) 2 λV ( t ) . Therefore, by variation of constants, Minkowski’s inequality, (233) , and V ( 0 ) ≤ 1 + c 2 ∥ u ( 0 ) ∥ M V(0)\le\sqrt{1+c^2}\lVert u(0)\rVert_M V ( 0 ) ≤ 1 + c 2 ∥ u ( 0 ) ∥ M ,
∥ u ( t ) ∥ M ≤ 2 e − a 0 t ∥ u ( 0 ) ∥ M + 2 2 λ 1 + c 2 ∥ u ( 0 ) ∥ M ∫ 0 t e − a 0 ( t − s ) e − β s d s ≤ C 0 e − γ 0 t ∥ u ( 0 ) ∥ M , γ 0 = 1 2 min { a 0 , β } , (237) \begin{aligned}
\lVert u(t)\rVert_M &\le\sqrt{2}e^{-a_0t}\lVert u(0)\rVert_M+2\sqrt{2}\lambda\sqrt{1+c^2}\lVert u(0)\rVert_M\int_0^t e^{-a_0(t-s)}e^{-\beta s}\,ds\\
&\le C_0e^{-\gamma_0t}\lVert u(0)\rVert_M,\qquad\gamma_0=\frac{1}{2}\min\{a_0,\beta\}, \tag*{(237)}
\end{aligned} ∥ u ( t ) ∥ M ≤ 2 e − a 0 t ∥ u ( 0 ) ∥ M + 2 2 λ 1 + c 2 ∥ u ( 0 ) ∥ M ∫ 0 t e − a 0 ( t − s ) e − β s d s ≤ C 0 e − γ 0 t ∥ u ( 0 ) ∥ M , γ 0 = 2 1 min { a 0 , β } , (237)
where C 0 < ∞ C_0<\infty C 0 < ∞ depends only on λ \lambda λ , μ \mu μ , and μ ˉ \bar{\mu} μ ˉ . Taking w ~ ( t ) = w ∗ \widetilde{w}(t)=w^* w ( t ) = w ∗ proves A4 and also proves uniqueness of the equilibrium.
For A5, fix a feasible CTMC transition W → W + Δ r W\to W+\Delta_r W → W + Δ r and a point w ^ = W + s Δ r \widehat{w}=W+s\Delta_r w = W + s Δ r , s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] , on the corresponding jump segment. Define the first and second variations
v ( t ) = D w ^ w ( t ; w ^ ) [ Δ r ] , r ( t ) = D w ^ 2 w ( t ; w ^ ) [ Δ r , Δ r ] , (238) v(t)=D_{\widehat{w}}w(t;\widehat{w})[\Delta_r],\qquad r(t)=D_{\widehat{w}}^2w(t;\widehat{w})[\Delta_r,\Delta_r], \tag*{(238)} v ( t ) = D w w ( t ; w ) [ Δ r ] , r ( t ) = D w 2 w ( t ; w ) [ Δ r , Δ r ] , (238)
and
V 1 ( t ) = 1 M ∑ m = 1 M ( ∣ v m , 1 ( t ) ∣ + c ∣ v m , 2 ( t ) ∣ ) , V 2 ( t ) = 1 M ∑ m = 1 M ( ∣ r m , 1 ( t ) ∣ + c ∣ r m , 2 ( t ) ∣ ) . (239) V_1(t)=\frac{1}{M}\sum_{m=1}^{M}\left(|v_{m,1}(t)|+c|v_{m,2}(t)|\right),\qquad V_2(t)=\frac{1}{M}\sum_{m=1}^{M}\left(|r_{m,1}(t)|+c|r_{m,2}(t)|\right). \tag*{(239)} V 1 ( t ) = M 1 m = 1 ∑ M ( ∣ v m , 1 ( t ) ∣ + c ∣ v m , 2 ( t ) ∣ ) , V 2 ( t ) = M 1 m = 1 ∑ M ( ∣ r m , 1 ( t ) ∣ + c ∣ r m , 2 ( t ) ∣ ) . (239)
The first variation satisfies the linearized equation along the trajectory, so (230) gives
V 1 ( t ) ≤ e − β t V 1 ( 0 ) ≤ c M e − β t . (240) V_1(t)\le e^{-\beta t}V_1(0)\le\frac{c}{M}e^{-\beta t}. \tag*{(240)} V 1 ( t ) ≤ e − β t V 1 ( 0 ) ≤ M c e − β t . (240)
The Hessian forcing in the second-variation equation is
D 2 F m , 1 ( w ) [ v , v ] = − 2 λ v m , 1 v ˉ 1 , D 2 F m , 2 ( w ) [ v , v ] = 2 λ ( v ˉ 1 + v ˉ 2 ) ( v m , 1 − v m , 2 ) , (241) D^2F_{m,1}(w)[v,v]=-2\lambda v_{m,1}\bar{v}_1,\qquad D^2F_{m,2}(w)[v,v]=2\lambda(\bar{v}_1+\bar{v}_2)(v_{m,1}-v_{m,2}), \tag*{(241)} D 2 F m , 1 ( w ) [ v , v ] = − 2 λ v m , 1 v ˉ 1 , D 2 F m , 2 ( w ) [ v , v ] = 2 λ ( v ˉ 1 + v ˉ 2 ) ( v m , 1 − v m , 2 ) , (241)
where v ˉ i = M − 1 ∑ m v m , i \bar{v}_i=M^{-1}\sum_m v_{m,i} v ˉ i = M − 1 ∑ m v m , i . Consequently,
1 M ∑ m = 1 M ( ∣ D 2 F m , 1 [ v , v ] ∣ + c ∣ D 2 F m , 2 [ v , v ] ∣ ) ≤ 2 λ ( 1 + c ) V 1 ( t ) 2 . (242) \frac{1}{M}\sum_{m=1}^{M}\left(|D^2F_{m,1}[v,v]|+c|D^2F_{m,2}[v,v]|\right)\le2\lambda(1+c)V_1(t)^2. \tag*{(242)} M 1 m = 1 ∑ M ( ∣ D 2 F m , 1 [ v , v ] ∣ + c ∣ D 2 F m , 2 [ v , v ] ∣ ) ≤ 2 λ ( 1 + c ) V 1 ( t ) 2 . (242)
Since r ( 0 ) = 0 r(0)=0 r ( 0 ) = 0 , (240) –(242) imply
V 2 ( t ) ≤ 2 λ ( 1 + c ) ∫ 0 t e − β ( t − s ) V 1 ( s ) 2 d s ≤ 2 λ ( 1 + c ) c 2 β M 2 e − β t . (243) V_2(t) \le2\lambda(1+c)\int_0^t e^{-\beta(t-s)}V_1(s)^2\,ds \le\frac{2\lambda(1+c)c^2}{\beta M^2}e^{-\beta t}. \tag*{(243)} V 2 ( t ) ≤ 2 λ ( 1 + c ) ∫ 0 t e − β ( t − s ) V 1 ( s ) 2 d s ≤ β M 2 2 λ ( 1 + c ) c 2 e − β t . (243)
Because ∥ v ( t ) ∥ 1 , M ≤ V 1 ( t ) \lVert v(t)\rVert_{1,M}\le V_1(t) ∥ v ( t ) ∥ 1 , M ≤ V 1 ( t ) and ∥ r ( t ) ∥ 1 , M ≤ V 2 ( t ) \lVert r(t)\rVert_{1,M}\le V_2(t) ∥ r ( t ) ∥ 1 , M ≤ V 2 ( t ) ,
∫ 0 ∞ ∥ v ( t ) ∥ 1 , M 2 d t ≤ c 2 2 β M 2 , ∫ 0 ∞ ∥ r ( t ) ∥ 1 , M d t ≤ 2 λ ( 1 + c ) c 2 β 2 M 2 , (244) \int_0^\infty\lVert v(t)\rVert_{1,M}^2\,dt \le\frac{c^2}{2\beta M^2},\qquad\int_0^\infty\lVert r(t)\rVert_{1,M}\,dt \le\frac{2\lambda(1+c)c^2}{\beta^2M^2}, \tag*{(244)} ∫ 0 ∞ ∥ v ( t ) ∥ 1 , M 2 d t ≤ 2 β M 2 c 2 , ∫ 0 ∞ ∥ r ( t ) ∥ 1 , M d t ≤ β 2 M 2 2 λ ( 1 + c ) c 2 , (244)
which proves A 5 A_5 A 5 uniformly along every feasible jump segment.
Finally, the equilibrium Jacobian J = D F ( w ∗ ) J=DF(w^*) J = D F ( w ∗ ) satisfies the same weighted column-sum bound. Define
∥ v ∥ c , 1 , M = 1 M ∑ m = 1 M ( ∣ v m , 1 ∣ + c ∣ v m , 2 ∣ ) . (245) \lVert v\rVert_{c,1,M}=\frac{1}{M}\sum_{m=1}^M\left(|v_{m,1}|+c|v_{m,2}|\right). \tag*{(245)} ∥ v ∥ c , 1 , M = M 1 m = 1 ∑ M ( ∣ v m , 1 ∣ + c ∣ v m , 2 ∣ ) . (245)
Then
∥ v ∥ 1 , M ≤ ∥ v ∥ c , 1 , M ≤ 1 + c 2 ∥ v ∥ 1 , M . (246) \lVert v\rVert_{1,M}\le\lVert v\rVert_{c,1,M}\le\sqrt{1+c^2}\lVert v\rVert_{1,M}. \tag*{(246)} ∥ v ∥ 1 , M ≤ ∥ v ∥ c , 1 , M ≤ 1 + c 2 ∥ v ∥ 1 , M . (246)
Hence, using the weighted contraction for the linearized system,
∥ e J t v ∥ 1 , M ≤ ∥ e J t v ∥ c , 1 , M ≤ e − β t ∥ v ∥ c , 1 , M ≤ 1 + c 2 e − β t ∥ v ∥ 1 , M , t ≥ 0 , (247) \lVert e^{Jt}v\rVert_{1,M}\le\lVert e^{Jt}v\rVert_{c,1,M}\le e^{-\beta t}\lVert v\rVert_{c,1,M}\le\sqrt{1+c^2}e^{-\beta t}\lVert v\rVert_{1,M},\qquad t\ge0, \tag*{(247)} ∥ e J t v ∥ 1 , M ≤ ∥ e J t v ∥ c , 1 , M ≤ e − β t ∥ v ∥ c , 1 , M ≤ 1 + c 2 e − β t ∥ v ∥ 1 , M , t ≥ 0 , (247)
so A 6 A_6 A 6 holds.
Verification of A 7 A_7 A 7
Define the single-server level function
ℓ ( 0 ) = 0 , ℓ ( 1 ) = 1 , ℓ ( 2 ) = 2 + ϑ , (248) \ell(0)=0,\qquad\ell(1)=1,\qquad\ell(2)=2+\vartheta, \tag*{(248)} ℓ ( 0 ) = 0 , ℓ ( 1 ) = 1 , ℓ ( 2 ) = 2 + ϑ , (248)
and the additive metric on { 0 , 1 , 2 } M \{0,1,2\}^M { 0 , 1 , 2 } M by
d ( q , q ~ ) = ∑ m = 1 M ∣ ℓ ( q m ) − ℓ ( q ~ m ) ∣ . (249) d(q,\widetilde q)=\sum_{m=1}^M\left|\ell(q_m)-\ell(\widetilde q_m)\right|. \tag*{(249)} d ( q , q ) = m = 1 ∑ M ∣ ℓ ( q m ) − ℓ ( q m ) ∣ . (249)
Two states are neighboring in the sense of A 7 A_7 A 7 precisely when they differ by one queue level at one server. Such an edge has length 1 1 1 for a 0 ↔ 1 0\leftrightarrow1 0 ↔ 1 move and c = 1 + ϑ c=1+\vartheta c = 1 + ϑ for a 1 ↔ 2 1\leftrightarrow2 1 ↔ 2 move. Moreover, any two states can be connected by changing the queue lengths one server at a time along 0 ↔ 1 ↔ 2 0\leftrightarrow1\leftrightarrow2 0 ↔ 1 ↔ 2 . Therefore, (249) is the corresponding shortest-path metric and
1 ≤ d ( q , q ~ ) ≤ c , q ∼ q ~ , sup q , q ~ ∈ { 0 , 1 , 2 } M d ( q , q ~ ) ≤ ( 2 + ϑ ) M . (250) 1\le d(q,\widetilde q)\le c,\qquad q\sim\widetilde q,\qquad\sup_{q,\widetilde q\in\{0,1,2\}^M}d(q,\widetilde q)\le(2+\vartheta)M. \tag*{(250)} 1 ≤ d ( q , q ) ≤ c , q ∼ q , q , q ∈ { 0 , 1 , 2 } M sup d ( q , q ) ≤ ( 2 + ϑ ) M . (250)
Lemma 4 (Local coupling contraction). Under (206), A 7 A_7 A 7 holds with D e = c D_e=c D e = c and κ c = β \kappa_c=\beta κ c = β .
Proof. By (250) , it remains only to verify the local coupled-generator inequality in A 7 A_7 A 7 . By symmetry, there are two types of neighboring pairs. Couple arrivals by using the same arrival clock, the same ordered sampled pair, and the same tie-breaking random variable in both systems. Couple services by using the same rate-μ j \mu_j μ j potential-service clock at each server j j j in both systems. Suppose first that the two states differ only by q m = 0 q_m=0 q m = 0 and q ~ m = 1 \widetilde{q}_m=1 q m = 1 . A service completion at server m m m coalesces the two states and decreases the distance by 1. If an arrival does not sample server m m m , the two systems make the same routing decision and the distance is unchanged. If an arrival samples server m m m , the post-arrival discrepancy is either another 0 ↔ 1 0\leftrightarrow1 0 ↔ 1 discrepancy or a 1 ↔ 2 1\leftrightarrow2 1 ↔ 2 discrepancy, so the distance can increase by at most ϑ \vartheta ϑ . The rate at which an arrival samples server m m m at least once is
λ M [ 1 − ( 1 − 1 M ) 2 ] = λ ( 2 − 1 M ) ≤ 2 λ . (251) \lambda M\left[1-\left(1-\frac{1}{M}\right)^2\right]=\lambda\left(2-\frac{1}{M}\right)\le2\lambda. \tag*{(251)} λ M [ 1 − ( 1 − M 1 ) 2 ] = λ ( 2 − M 1 ) ≤ 2 λ . (251)
Hence the coupled generator satisfies
( G c d ) ( q , q ~ ) ≤ − μ m + 2 λ ϑ ≤ − μ 2 ≤ − β d ( q , q ~ ) . (252) (\mathcal{G}^{c}d)(q,\widetilde{q})\le-\mu_m+2\lambda\vartheta\le-\frac{\mu}{2}\le-\beta d(q,\widetilde{q}). \tag*{(252)} ( G c d ) ( q , q ) ≤ − μ m + 2 λ ϑ ≤ − 2 μ ≤ − β d ( q , q ) . (252)
Suppose next that the states differ only by q m = 1 q_m=1 q m = 1 and q ~ m = 2 \widetilde{q}_m=2 q m = 2 . Arrivals cannot increase the distance under the synchronous routing coupling: they either leave the discrepancy unchanged, move the same 1 ↔ 2 1\leftrightarrow2 1 ↔ 2 discrepancy to another sampled server, or coalesce the two systems. A service completion at server m m m changes the discrepancy from 1 ↔ 2 1\leftrightarrow2 1 ↔ 2 to 0 ↔ 1 0\leftrightarrow1 0 ↔ 1 , decreasing the distance by ϑ \vartheta ϑ . Therefore,
( G c d ) ( q , q ~ ) ≤ − μ m ϑ ≤ − ϑ μ 1 + ϑ d ( q , q ~ ) = − β d ( q , q ~ ) . (253) (\mathcal{G}^{c}d)(q,\widetilde{q})\le-\mu_m\vartheta\le-\frac{\vartheta\mu}{1+\vartheta}d(q,\widetilde{q})=-\beta d(q,\widetilde{q}). \tag*{(253)} ( G c d ) ( q , q ) ≤ − μ m ϑ ≤ − 1 + ϑ ϑ μ d ( q , q ) = − β d ( q , q ) . (253)
Thus the local contraction in A7 holds for every neighboring pair. Together with (250) and the shortest-path property of (249), this verifies A7.
Second-Order Consequences
For a fixed bounded weight φ \varphi φ , define
Y φ = M ( X φ ( W ( ∞ ) ) − x φ ∗ ) , L φ = 1 M ( φ ( μ 1 ) I 2 ⋯ φ ( μ M ) I 2 ) . (254) Y_\varphi=\sqrt{M}\left(X_\varphi(W(\infty))-x_\varphi^*\right),\qquad L_\varphi=\frac{1}{\sqrt{M}}\left(\varphi(\mu_1)I_2\cdots\varphi(\mu_M)I_2\right). \tag*{(254)} Y φ = M ( X φ ( W ( ∞ )) − x φ ∗ ) , L φ = M 1 ( φ ( μ 1 ) I 2 ⋯ φ ( μ M ) I 2 ) . (254)
Let Σ ‾ \overline{\Sigma} Σ solve
J Σ ‾ + Σ ‾ J T + Q ( w ∗ ) = 0. (255) J\overline{\Sigma}+\overline{\Sigma}J^{\mathsf{T}}+Q(w^*)=0. \tag*{(255)} J Σ + Σ J T + Q ( w ∗ ) = 0. (255)
Corollary 2 (Second-order approximation for heterogeneous power-of-two choices with B = 2 B=2 B = 2 ). Under (206), for every fixed λ > 0 \lambda>0 λ > 0 , conditions A1–A9 hold. For every fixed bounded observation weight φ \varphi φ , define
Γ φ = L φ Σ ‾ L φ T , β φ = − M 2 L φ J − 1 H ( Σ ‾ ) . (256) \Gamma_\varphi=L_\varphi\overline{\Sigma}L_\varphi^{\mathsf{T}},\qquad\beta_\varphi=-\frac{\sqrt{M}}{2}L_\varphi J^{-1}H(\overline{\Sigma}). \tag*{(256)} Γ φ = L φ Σ L φ T , β φ = − 2 M L φ J − 1 H ( Σ ) . (256)
Then
∥ Cov ( Y φ ∣ μ ) − Γ φ ∥ op = O ( M − 1 / 2 ) , ∥ E [ X φ ( W ( ∞ ) ) ∣ μ ] − x φ ∗ − β φ M ∥ = O ( M − 3 / 2 ) . (257) \left\|\operatorname{Cov}(Y_\varphi\mid\mu)-\Gamma_\varphi\right\|_{\operatorname{op}}=O(M^{-1/2}),\qquad\left\|\mathbb{E}[X_\varphi(W(\infty))\mid\mu]-x_\varphi^*-\frac{\beta_\varphi}{M}\right\|=O(M^{-3/2}). \tag*{(257)} ∥ Cov ( Y φ ∣ μ ) − Γ φ ∥ op = O ( M − 1/2 ) , E [ X φ ( W ( ∞ )) ∣ μ ] − x φ ∗ − M β φ = O ( M − 3/2 ) . (257)
Moreover, let
K φ = { y ∈ R 2 : ∣ y i ∣ ≤ ∥ φ ∥ ∞ , i = 1 , 2 } . (258) \mathcal{K}_\varphi=\{y\in\mathbb{R}^2:|y_i|\le\|\varphi\|_\infty,\ i=1,2\}. \tag*{(258)} K φ = { y ∈ R 2 : ∣ y i ∣ ≤ ∥ φ ∥ ∞ , i = 1 , 2 } . (258)
For every h : R 2 → R h:\mathbb{R}^2\to\mathbb{R} h : R 2 → R that is twice continuously differentiable on a neighborhood of K φ \mathcal{K}_\varphi K φ ,
E [ h ( X φ ( W ( ∞ ) ) ) ∣ μ ] = h ( x φ ∗ ) + 1 M ( D h ( x φ ∗ ) [ β φ ] + 1 2 Tr ( D 2 h ( x φ ∗ ) Γ φ ) ) + o ( M − 1 ) . (259) \mathbb{E}[h(X_\varphi(W(\infty)))\mid\mu]=h(x_\varphi^*)+\frac{1}{M}\left(Dh(x_\varphi^*)[\beta_\varphi]+\frac{1}{2}\operatorname{Tr}\left(D^2h(x_\varphi^*)\Gamma_\varphi\right)\right)+o(M^{-1}). \tag*{(259)} E [ h ( X φ ( W ( ∞ ))) ∣ μ ] = h ( x φ ∗ ) + M 1 ( D h ( x φ ∗ ) [ β φ ] + 2 1 Tr ( D 2 h ( x φ ∗ ) Γ φ ) ) + o ( M − 1 ) . (259)
Proof. Lemmas 3 and 4 establish A1–A7. Section 5.1 verifies S1–S2, so Lemma 2 gives A8–A9. Hence the covariance and performance conclusions follow from Theorems 1–2. Moreover, here r ≡ 0 r\equiv0 r ≡ 0 and D 2 A = D 2 a = 0 D^2A=D^2a=0 D 2 A = D 2 a = 0 , so the post-quadratic drift remainder vanishes identically and the sharper A9 bound holds. The O ( M − 3 / 2 ) O(M^{-3/2}) O ( M − 3/2 ) refined-mean rate therefore follows as well.
Conclusion
We characterize the steady-state covariance and bias of weighted occupancies in fully heterogeneous mean-field models conditional on the realized agent parameters. The matrix Γ φ / M \Gamma_{\varphi}/M Γ φ / M obtained from the Lyapunov equation approximates the occupancy covariance with error O ( M − 3 / 2 ) O(M^{-3/2}) O ( M − 3/2 ) . Under the additional drift condition A9, we obtain an explicit 1 / M 1/M 1/ M correction for stationary expectations of twice continuously differentiable functions of the occupancy, with residual error o ( M − 1 ) o(M^{-1}) o ( M − 1 ) . We verify the assumptions for heterogeneous power-of-two load balancing with buffer size two.