betaFeedback

WorksMathematics

Second-Order Steady-State Approximation of Heterogeneous Mean-Field Models

Abstract

Mean-field models provide tractable approximations for large stochastic systems, but second-order steady-state results are largely limited to homogeneous or fixed-dimensional population processes. This paper develops a second-order steady-state approximation for fully heterogeneous mean-field models. Conditioning on the realized agent parameters, we study fixed-dimensional weighted occupancies even though the dimension of the full heterogeneous mean-field system grows linearly with the number of agents MM. We first establish an O(M−1)O(M^{-1}) bound on the mean-field approximation error for stationary expectations of twice continuously differentiable functions of these occupancies. We then characterize the leading term in this error in terms of the stationary mean bias and covariance of the weighted occupancies. A Lyapunov equation for the linearized dynamics yields an approximation to the stationary covariance of the unscaled weighted occupancy with error O(M−3/2)O(M^{-3/2}). Its solution, together with the drift derivatives at equilibrium, also gives an explicit 1/M1/M correction to the mean-field prediction of the stationary mean. The corrected mean has error o(M−1)o(M^{-1}), which improves to O(M−3/2)O(M^{-3/2}) under a stronger bound on the drift remainder. The resulting covariance and mean-refinement equations have the same structure as the finite-time heterogeneous refined mean-field equations, but our results directly provide steady-state guarantees for weighted occupancies rather than marginal state probabilities of individual agents. The results are illustrated through a heterogeneous power-of-two load-balancing model with buffer size two.

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 MM agents evolving on a common nn-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) 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/M1/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 denote the parameter of agent mm, Wm(t)∈Rn−1\mathbf{W}_m(t) \in\mathbb{R}^{n-1} its reduced one-hot state, and wm∗\mathbf{w}^{*}_m its component of the quenched mean-field equilibrium. For a fixed bounded weight function ϕ\phi, define Xϕ(t)=M−1∑m=1Mϕ(θm)Wm(t)\mathbf{X}_{\phi}(t) = M^{-1}\sum_{m=1}^{M}\phi(\theta_m)\mathbf{W}_m(t), xϕ∗=M−1∑m=1Mϕ(θm)wm∗\mathbf{x}^{*}_{\phi} = M^{-1}\sum_{m=1}^{M}\phi(\theta_m)\mathbf{w}^{*}_m, and Yϕ=M(Xϕ(∞)−xϕ∗)\mathbf{Y}_{\phi} = \sqrt{M}\left(\mathbf{X}_{\phi}(\infty)-\mathbf{x}^{*}_{\phi}\right), where Xϕ(∞)\mathbf{X}_{\phi}(\infty) 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ϕ∣θ)−Γϕ∥op=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)}

Here θ=(θ1,…,θM)\theta=(\theta_1,\ldots,\theta_M) is the realized parameter vector. Thus, although the full mean-field dimension grows linearly with MM, the covariance matrix in (1) has size (n−1)×(n−1)(n-1)\times(n-1), independent of MM. Equivalently, Γϕ/M\Gamma_{\phi}/M approximates the covariance of the unscaled occupancy Xϕ(∞)\mathbf{X}_{\phi}(\infty) with error 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:Rn−1→Rh:\mathbb{R}^{n-1}\to\mathbb{R} satisfies

E[h(Xϕ(∞))∣θ]=h(xϕ∗)+1M(Dh(xϕ∗)[βϕ]+12Tr⁡(D2h(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)}

Here DhDh and D2hD^{2}h denote the first and second derivatives of hh, respectively, Tr⁡\operatorname{Tr} denotes the matrix trace, and βϕ∈Rn−1\beta_{\phi}\in\mathbb{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 has error o(M−1)o(M^{-1}), which improves to 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), the covariance approximation in (1) and the 1/M1/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/M1/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 MM-Agent CTMC

Consider a continuous-time Markov chain (CTMC) consisting of MM heterogeneous agents. Each agent mm is associated with a parameter θm\theta_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).

Each agent evolves on the common finite state space S={0,…,n−1}\mathcal{S} = \{0,\ldots,n-1\}, where nn is independent of MM. Let e1,…,en−1\boldsymbol{e}_1,\ldots,\boldsymbol{e}_{n-1} denote the standard basis vectors of Rn−1\mathbb{R}^{n-1} and let e0=0\boldsymbol{e}_0 = 0. If agent mm is in state ii at time tt, we represent its state by Wm(t)=ei\boldsymbol{W}_m(t) = \boldsymbol{e}_i. Define the reduced simplex

Dn−1={w∈R+n−1:∑i=1n−1wi≤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)}

Thus, Wm(t)∈{e0,…,en−1}⊂Dn−1\boldsymbol{W}_m(t) \in\{\boldsymbol{e}_0,\ldots,\boldsymbol{e}_{n-1}\} \subset\mathcal{D}_{n-1}. Let

W⊆{e0,…,en−1}M(4)\mathcal{W} \subseteq\{\boldsymbol{e}_0,\ldots,\boldsymbol{e}_{n-1}\}^{M} \tag*{(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}, we stack it to a (n−1)M(n-1)M vector such that

W=(W1T,…,WMT)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)}

For a bounded weight function φ:Θ→R\varphi: \Theta\to\mathbb{R}, define the weighted empirical occupancy

Xφ(W)=1M∑m=1Mφ(θm)Wm.(6)X_{\varphi}(\boldsymbol{W}) = \frac{1}{M}\sum_{m=1}^{M} \varphi(\theta_m)\boldsymbol{W}_m. \tag*{(6)}

The interaction field is

Z(W)=Ψ(Xχ(W)),(7)\boldsymbol{Z}(\boldsymbol{W}) = \Psi(X_{\chi}(\boldsymbol{W})), \tag*{(7)}

where χ:Θ→R\chi: \Theta\to\mathbb{R} is a fixed bounded interaction weight satisfying 0<∣χ∣∞<∞0 < \lvert\chi\rvert_{\infty} < \infty, and Ψ:Rn−1→Rd\Psi: \mathbb{R}^{n-1} \to\mathbb{R}^{d}. We assume that W(t)\boldsymbol{W}(t) is an irreducible CTMC on W\mathcal{W} with generator G\mathcal{G}. Its dynamics are described through a collection R\mathcal{R} of transition types, which may depend on MM but not on the current system state. For each r∈Rr \in\mathcal{R}, let qrCTMC(W)q_{r}^{\mathrm{CTMC}}(\boldsymbol{W}) denote the transition rate, with qrCTMC(W)=0q_{r}^{\mathrm{CTMC}}(\boldsymbol{W}) = 0 whenever transition rr is infeasible at W\boldsymbol{W}, and let Δr∈R(n−1)M\Delta_r \in\mathbb{R}^{(n-1)M} denote the corresponding state change, which is independent of W\boldsymbol{W}. For a test function gg,

(Gg)(W)=∑r∈RqrCTMC(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)}

The infinitesimal drift and instantaneous covariance-rate matrix of the CTMC are

FCTMC(W)=∑r∈RqrCTMC(W)Δr,QCTMC(W)=∑r∈RqrCTMC(W)ΔrΔrT.(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)}

Thus, conditional on W(t)=WW(t)=W,

E[dW(t)∣W(t)=W]=FCTMC(W) dt+o(dt),E[dW(t)dW(t)T∣W(t)=W]=QCTMC(W) dt+o(dt).(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)}

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). In particular, for each agent, the dependence of its infinitesimal drift on the other agents is through the interaction field and for every W∈WW\in\mathcal{W} and m=1,…,Mm=1,\ldots,M, the mmth block of the CTMC drift satisfies

[FCTMC(W)]m=(GWm)(W)=f(Wm,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)}

Heterogeneous Mean-Field Model

References

  1. [1]Sebastian Allmeier and Nicolas Gast. Mean field and refined mean field approximations for heterogeneous systems: It works! In Proc. Ann. ACM SIGMETRICS Conf., Mumbai, India, 2022.
  2. [2]Andrew D. Barbour, Malwina J. Luczak, and Aihua Xia. Multivariate Approximation in Total Variation, I: Equilibrium Distributions of Markov Jump Processes. Ann. Probab., 46(3):1351–1404, 2018.arxiv.org/abs/1512.07400
  3. [3]Andrew D. Barbour, Malwina J. Luczak, and Aihua Xia. Multivariate Approximation in Total Variation, II: Discrete Normal Approximation. Ann. Probab., 46(3):1405–1440, 2018.arxiv.org/abs/1612.07519
  4. [4]Nicolas Gast and Benny Van Houdt. A refined mean field approximation. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1–28, 2017.
  5. [5]Thomas G Kurtz. Limit theorems for sequences of jump Markov processes approximating ordinary differential processes. J. Appl. Probab., 8(2):344–356, 1971.DOI
  6. [6]Thomas G Kurtz. Approximation of population processes, volume 36. SIAM, 1981.
  7. [7]Lei Ying. On the approximation error of mean-field models. In Proc. Ann. ACM SIGMETRICS Conf., Antibes Juan-les-Pins, France, June 2016.
  8. [8]Lei Ying. Steady-state approximation error of heterogeneous mean-field models. arXiv preprint arXiv:2606.09022, 2026.arxiv.org/abs/2606.09022

Paper details

vlnc:W_6qa3b6ae
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents