Analysis of a stochastic approximation algorithm for computing quasi-stationary distributions. (English) Zbl 1352.60106

Blanchet, J.; Glynn, P.; Zheng, S.

Adv. Appl. Probab. 48, No. 3, 792-811 (2016).

Summary: We study the convergence properties of a Monte Carlo estimator proposed in the physics literature to compute the quasi-stationary distribution on a transient set of a Markov chain (see [M. M. de Oliveira and R. Dickman, “How to simulate the quasistationary state”, Phys. Rev. E 71, 016129 (2005; doi:10.1103/PhysRevE.71.016129); “Quasi-stationary simulation: the subcritical contact process ”, Braz. J. Phys. 36, No. 3a, 685–689 (2006); R. Dickman and R. Vidigal, “Quasi-stationary distributions for stochastic processes with an absorbing state”, J. Phys. A 35, No. 5, 1147–1166 (2002)]). Using the theory of stochastic approximations we verify the consistency of the estimator and obtain an associated central limit theorem. We provide an example showing that convergence might occur very slowly if a certain eigenvalue condition is violated. We alleviate this problem using an easy-to-implement projection step combined with averaging.

MSC:

60J22	Computational methods in Markov chains
60J10	Markov chains (discrete-time Markov processes on discrete state spaces)
60F05	Central limit and other weak theorems
65C40	Numerical analysis or methods applied to Markov chains

Keywords:

quasi-stationary distribution; stochastic approximation; Markov chain; central limit theorem

References:

[1]	Aldous, D., Flannery, B. and Palacios, J. L. (1988). Two applications of urn processes to the fringe analysis of search trees and the simulation of quasi-stationary distributions of Markov chains. Prob. Eng. Inf. Sci. 2, 293-307. · Zbl 1134.68592 · doi:10.1017/S026996480000084X
[2]	Athreya, K. B. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Statist. 39, 1801-1817. · Zbl 0185.46103 · doi:10.1214/aoms/1177698013
[3]	Benaïm, M. and Cloez, B. (2015). A stochastic approximation approach to quasi-stationary distributions on finite spaces. Electron. Commun. Prob. 20, 14 pp. · Zbl 1321.65009 · doi:10.1214/ECP.v20-3956
[4]	Blanchet, J., Glynn, P. and Zheng, S. (2013). Empirical analysis of a stochastic approximation approach for computing quasi-stationary distributions. In EVOLVE , Springer, Berlin, 19-37.
[5]	Boyd, S. and Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. · Zbl 1058.90049
[6]	Burzdy, K., Hołyst, R. and March, P. (2000). A Fleming-Viot particle representation of the Dirichlet Laplacian. Commun. Math. Phys. 214, 679-703. · Zbl 0982.60078 · doi:10.1007/s002200000294
[7]	Darroch, J. N. and Seneta, E. (1965). On quasi-stationary distributions in absorbing discrete-time finite Markov chains. J. Appl. Prob. 2, 88-100. · Zbl 0134.34704 · doi:10.2307/3211876
[8]	Darroch, J. N. and Seneta, E. (1967). On quasi-stationary distributions in absorbing continuous-time finite Markov chains. J. Appl. Prob. 4, 192-196. · Zbl 0168.16303 · doi:10.2307/3212311
[9]	De Oliveira, M. M. and Dickman, R. (2005). How to simulate the quasistationary state. Phys. Rev. E 71, 016129.
[10]	De Oliveira, M. M. and Dickman, R. (2006). Quasi-stationary simulation: the subcritical contact process. Brazilian J. Phys. 36, 685-689.
[11]	Del Moral, P. and Miclo, L. (2006). Self-interacting Markov chains. Stoch. Anal. Appl. 24, 615-660. · Zbl 1093.60068 · doi:10.1080/07362990600632029
[12]	Dickman, R. and Vidigal, R. (2002). Quasi-stationary distributions for stochastic processes with an absorbing state. J. Phys. A 35, 1147-1166. · Zbl 0992.60098 · doi:10.1088/0305-4470/35/5/303
[13]	Dimov, I. T., Karaivanova, A. N. and Yordanova, P. I. (1998). Monte Carlo algorithms for calculating eigenvalues. In Monte Carlo and Quasi-Monte Carlo Methods 1996 (Salzburg; Lecture Notes Statist. 127 ), Springer, New York, pp. 205-220. · Zbl 0885.65041
[14]	Ferrari, P. A. and Marić, N. (2007). Quasistationary distributions and Fleming-Viot processes in countable spaces. Electron. J. Prob. 12, 684-702. · Zbl 1127.60088
[15]	Golub, G. H. and Van Loan, C. F. (1996). Matrix Computations , 3rd edn. Johns Hopkins University Press, Baltimore, MD. · Zbl 0865.65009
[16]	Groisman, P. and Jonckheere, M. (2013). Simulation of quasi-stationary distributions on countable spaces. Markov. Process. Relat. Fields. 19, 521-542. · Zbl 1321.60210
[17]	Karlin, S. and Taylor, H. M. (1975). A First Course in Stochastic Processes , 2nd edn. Academic Press, New York. · Zbl 0315.60016
[18]	Krasulina, T. P. (2013). The method of stochastic approximation for the determination of the least eigenvalue of a symmetrical matrix. USSR Comput. Math. Math. Phys. 9, 189-195. · Zbl 0241.65037 · doi:10.1016/0041-5553(69)90135-9
[19]	Krasulina, T. P. (1970). Method of stochastic approximation in the determination of the largest eigenvalue of the mathematical expectation of random matrices. Automat. Rem. Contr. 2, 215-221. · Zbl 0231.62099
[20]	Kushner, H. J. and Yin, G. (2003). Stochastic Approximation and Recursive Algorithms and Applications , 2nd edn. Springer, New York. · Zbl 1026.62084
[21]	Méléard, S. and Villemonais, D. (2012). Quasi-stationary distributions and population processes. Prob. Surveys 9, 340-410. · Zbl 1261.92056 · doi:10.1214/11-PS191
[22]	Oja, E. and Karhunen, J. (1985). On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix. J. Math. Anal. Appl. 106, 69-84. · Zbl 0583.62077 · doi:10.1016/0022-247X(85)90131-3
[23]	Permantle, R. (2007). A survey of random processes with reinforcement. Prob. Surveys 4, 1-79.
[24]	Polyak, B. T. and Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM J. Control Optimization 30, 838-855. · Zbl 0762.62022 · doi:10.1137/0330046
[25]	Robbins, H. and Monro, S. (1951). A stochastic approximation method. Ann. Math. Statist. 22, 400-407. · Zbl 0054.05901 · doi:10.1214/aoms/1177729586
[26]	Zheng, S. (2014). Stochastic approximation algorithms in the estimation of quasi-stationary distribution of finite and general state space Markov chains. Doctoral Thesis, Columbia University.