Blanchet, J., Glynn, P., Zheng, S. (2013). Empirical Analysis of a Stochastic Approximation Approach for Computing Quasi-stationary Distributions. In: Schütze, O., et al. EVOLVE – A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation II. Advances in Intelligent Systems and Computing, vol 175. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31519-0_2

View Publication

Abstract

This paper studies a method for estimating the quasi-stationary distribution of various interacting particle processes has been proposed by [6, 5, 8]. This method improved upon existing methods in eigenvector estimation by eliminating the need for explicit transition matrix representation and multiplication. However, this method has no firm theoretical foundation. Our paper analyzes the algorithm by casting it as a stochastic approximation algorithm (Robbins-Monro) [12]. In doing so, we prove its convergence and 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 this algorithm that is given in this paper. Numerical experiments are described that demonstrate the effectiveness of this improved method.

Authors
Jose Blanchet, Peter Glynn, Shuheng Zheng
Publication date
2013
Conference
EVOLVE-A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation II
Pages
19-37
Publisher
Springer Berlin Heidelberg