Theoretical analysis of a Stochastic Approximation approach for computing Quasi-Stationary distributions

José Blanchet, Peter W. Glynn, Shuheng Zheng

Abstract

This paper investigates a sampling-based method, originally proposed in physics literature, for estimating Quasi-Stationary Distributions (QSDs). Unlike traditional eigenvector estimation techniques, this method avoids explicit transition matrix manipulation, making it suitable for high-dimensional systems. By re-casting the algorithm as a Robbins-Monro stochastic approximation, we provide a rigorous proof of its convergence and establish its rate of convergence. Furthermore, we identify scenarios where the standard algorithm exhibits slow convergence and propose an improved version utilizing Polyak-Ruppert averaging. Numerical experiments demonstrate that this improved method significantly enhances performance in complex systems.

Introduction: The Challenge of Pseudo-Equilibrium

In many stochastic systems, such as the spread of an epidemic or the dynamics of a queue, the system is eventually absorbed into a terminal state (e.g., the extinction of a virus or an empty queue). However, before absorption occurs, these systems often exhibit a long-lived "pseudo-equilibrium" known as a Quasi-Stationary Distribution (QSD).

Mathematically, the QSD is the principal left-eigenvector of a substochastic transition matrix. While conceptually straightforward, computing this distribution for Interacting Particle Systems (IPS) is often impossible due to the curse of dimensionality. In these cases, the state space is too vast to construct or manipulate the transition matrix explicitly. To circumvent this, physicists developed heuristic sampling methods to estimate the QSD. This paper provides the mathematical foundation for these heuristics, proving their validity and optimizing their efficiency.

Methods: Bridging Physics and Optimization

We analyze the sampling heuristic by framing it within the framework of Stochastic Approximation, specifically the Robbins-Monro algorithm. This allows us to treat the sampling process as a recursive update rule:

$$\mu_{n+1} = \mu_n + \epsilon_n W_n$$

By applying the "ODE method," we prove that the algorithm’s trajectory tracks a continuous dynamical system that converges to the unique QSD with probability 1. To ensure the robustness of this approach, we introduce several technical refinements:

  • Projection-Variant: We incorporate a projection step to ensure the estimated distribution remains within the probability simplex, maintaining non-negative components that sum to one.
  • Doeblinization: This technique accelerates the simulation of the Markov chain toward absorption. While computationally efficient, we analyze how this affects the theoretical convergence rate.
  • Polyak-Ruppert Averaging: Our primary contribution to the algorithm's efficiency is the application of iterate averaging. Instead of relying solely on the most recent estimate, the algorithm maintains a running average of all previous estimates, which stabilizes the path toward the QSD.

Identifying the "CLT Trap"

A significant finding of our theoretical analysis is the identification of a "trap" in the standard algorithm's convergence. We established a Central Limit Theorem (CLT) for the algorithm, which reveals that if the spectral gap between the principal and non-principal eigenvalues is too small, the convergence rate can degrade from the ideal $\sqrt{n}$ to a much slower $n^{1-\epsilon}$. This explains why previous heuristic methods often struggled with systems characterized by slow internal dynamics relative to their absorption rate.

Experimental Results

We evaluated the standard and improved algorithms across three synthetic benchmarks:

  1. Loopy Markov Chain: A toy model designed to violate standard CLT conditions, highlighting the failure points of the original physics method.
  2. M/M/1/100 Queue: A classic queueing model with a finite capacity of 100 states.
  3. Contact Process on a Complete Graph: A high-dimensional model of infection spreading among 100 nodes, representing the complex IPS that motivated this research.

In all cases, the improved version utilizing Polyak-Ruppert averaging consistently achieved the optimal $\sqrt{n}$ convergence rate. In high-dimensional tests like the Contact Process, the improved method outperformed the original heuristic by several orders of magnitude in terms of Mean Squared Error (MSE).

Conclusion and Future Directions

This work transforms a physics heuristic into a mathematically rigorous tool for probability and optimization. By proving convergence and establishing the CLT, we provide a "speed limit" for QSD estimation. Our proposed use of Polyak-Ruppert averaging ensures that this limit is reached even in difficult, near-singular systems.

Future research will focus on extending these proofs to infinite (countable) state spaces, such as the M/M/1/$\infty$ queue, and adapting the framework for continuous state spaces (diffusion processes). Additionally, further work is needed to optimize the "Doeblinization" constant to balance simulation speed with the volatility of the distribution estimate.

Summary updated

Abstract

This paper studies a method, which has been proposed in the Physics literature by [8, 7, 10], for estimating the quasi-stationary distribution. In contrast to existing methods in eigenvector estimation, the method eliminates the need for explicit transition matrix manipulation to extract the principal eigenvector. Our paper analyzes the algorithm by casting it as a stochastic approximation algorithm (Robbins-Monro) [23, 16]. In doing so, we prove its convergence and obtain its rate of convergence. Based on this insight, we also give an example where the rate of convergence is very slow. This problem can be alleviated by using an improved version of the algorithm that is given in this paper. Numerical experiments are described that demonstrate the effectiveness of this improved method.
BibTeX
@inproceedings{blanchet2012theoretical,
  author = {José Blanchet and Peter W. Glynn and Shuheng Zheng},
  title = {{Theoretical analysis of a Stochastic Approximation approach for computing Quasi-Stationary distributions}},
  booktitle = {EVOLVE},
  year = {2012},
  doi = {10.1007/978-3-642-31519-0\_2},
}
Figure