We propose two numerical schemes for approximating quasi-stationary distributions (QSD) of finite state Markov chains with absorbing states. Both schemes are described in terms of certain interacting chains in which the interaction is given in terms of the total time occupation measure of all particles in the system and has the impact of reinforcing transitions, in an appropriate fashion, to states where the collection of particles has spent more time. The schemes can be viewed as combining the key features of the two basic simulation-based methods for approximating QSD originating from the works of Fleming and Viot (1979) and Aldous, Flannery and Palacios (1998), respectively. The key difference between the two schemes studied here is that in the first method one starts with a(n) particles at time 0 and number of particles stays constant over time whereas in the second method we start with one particle and at most one particle is added at each time instant in such a manner that there are a(n) particles at time n. We prove almost sure convergence to the unique QSD and establish Central Limit Theorems for the two schemes under the key assumption that a(n) = o(n). When a(n) ~ n, the fluctuation behavior is expected to be non-standard. Some exploratory numerical results are presented to illustrate the performance of the two approximation schemes.
Keywords: Quasi-stationary distributions, stochastic approximation, interacting particles, central limit theorem, reinforced random walks, self-interaction, Fleming-Viot particle approximations
@article{PS_2022__26_1_69_0,
author = {Budhiraja, Amarjit and Fraiman, Nicolas and Waterbury, Adam},
title = {Approximating quasi-stationary distributions with interacting reinforced random walks},
journal = {ESAIM: Probability and Statistics},
pages = {69--125},
year = {2022},
publisher = {EDP-Sciences},
volume = {26},
doi = {10.1051/ps/2021019},
mrnumber = {4372631},
zbl = {1482.60097},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ps/2021019/}
}
TY - JOUR AU - Budhiraja, Amarjit AU - Fraiman, Nicolas AU - Waterbury, Adam TI - Approximating quasi-stationary distributions with interacting reinforced random walks JO - ESAIM: Probability and Statistics PY - 2022 SP - 69 EP - 125 VL - 26 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ps/2021019/ DO - 10.1051/ps/2021019 LA - en ID - PS_2022__26_1_69_0 ER -
%0 Journal Article %A Budhiraja, Amarjit %A Fraiman, Nicolas %A Waterbury, Adam %T Approximating quasi-stationary distributions with interacting reinforced random walks %J ESAIM: Probability and Statistics %D 2022 %P 69-125 %V 26 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ps/2021019/ %R 10.1051/ps/2021019 %G en %F PS_2022__26_1_69_0
Budhiraja, Amarjit; Fraiman, Nicolas; Waterbury, Adam. Approximating quasi-stationary distributions with interacting reinforced random walks. ESAIM: Probability and Statistics, Tome 26 (2022), pp. 69-125. doi: 10.1051/ps/2021019
[1] , and , Two applications of urn processes: the fringe analysis of search trees and the simulation of quasi-stationary distributions of Markov chains. Prob. Eng. Inform. Sci. 2 (1988) 293–307. | Zbl | DOI
[2] , Methuen’s monographs on applied probability and statistics. Methuen (1960).
[3] , Vertex-reinforced random walks and a conjecture of Pemantle. Ann. Probab. 25 (1997) 361–392. | MR | Zbl | DOI
[4] , Dynamics of stochastic approximation algorithms. Séminaire de probabilités, XXXIII 1709 (1999) 1–68. | MR | Zbl | Numdam | DOI
[5] , and , Stochastic approximation of quasi-stationary distributions for diffusion processesin a bounded domain. Ann. l’Inst. Henri Poincaré, Prob. Stat. 57 (2021) 726–739. | MR | Zbl
[6] and , A stochastic approximation approach to quasi-stationary distributions on finite spaces. Electron. Commun. Probab. 20 (2015) 1–13. | MR | Zbl | DOI
[7] , and , Stochastic approximation of quasi-stationary distributions on compact spaces and applications. Ann. Appl. Prob. 28 (2016). | MR | Zbl
[8] and , Asymptotic pseudotrajectories and chain recurrent flows, with applications. J. Dyn. Differ. Equ. 8 (1996) 141–176. | MR | Zbl | DOI
[9] , and , Vol. 22 of Adaptive Algorithms and Stochastic Approximations. Springer Science & Business Media (2012). | MR | Zbl
[10] , and , Analysis of a stochastic approximation algorithm for computing quasi-stationary distributions. Adv. Appl. Prob. 48 (2016) 792–811. | MR | Zbl | DOI
[11] , Vol. 48 of Stochastic Approximation: A Dynamical Systems Viewpoint. Springer (2009). | MR | Zbl
[12] , and , A Fleming–Viot particle representation of the Dirichlet Laplacian. Commun. Math. Phys. 214 (2000) 679–703. | MR | Zbl | DOI
[13] , , and , A central limit theorem for Fleming–Viot particle systems. Ann. l’Inst. Henri Poincaré, Prob. Stat. 56 (2020) 637–666. | MR | Zbl
[14] , and , Quasi-stationary distributions. Markov chains, diffusions and dynamical systems (2013). | MR | Zbl | DOI
[15] and , Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman-Kac semigroups. ESAIM: PS 7 (2003) 171–208. | MR | Zbl | Numdam | DOI
[16] and , A Moran particle system approximation of Feynman–Kac formulae. Stoch. Process. Appl. 86 (2000) 193–216. | MR | Zbl | DOI
[17] and , On convergence of chains with occupational self-interactions. Proc. Royal Soc. Lond. Ser. A: Math. Phys. Eng. Sci. 460 (2004) 325–346. | MR | Zbl | DOI
[18] and , Self-interacting Markov chains. Stoch. Anal. Appl. 24 (2006) 615–660. | MR | Zbl | DOI
[19] , Stochastic approximation with decreasing gain: convergence and asymptotic theory. Tech. report, IRISA (2000), Publication interne 952.
[20] and , Some measure-valued Markov processes in population genetics theory. Indiana Univ. Math. J. 28 (1979) 817–843. | MR | Zbl | DOI
[21] , Central limit theorems for stochastic approximation with controlled Markov chain dynamics. ESAIM: PS 19 (2013). | MR | Zbl | Numdam
[22] and , Simulation of quasi-stationary distributions on countable spaces. Markov Process. Related Fields 19 (2012). | MR | Zbl
[23] and , Martingale Limit Theory and its Applications. Academic Press (1980). | MR | Zbl
[24] and , Topics in Matrix Analysis. Cambridge University Press, New York, New York (1991). | MR | Zbl | DOI
[25] and , Stochastic estimation of the maximum of a regression function. Ann. Math. Stat. 23 (1952) 462–466. | MR | Zbl | DOI
[26] , On the solution of a problem in biology. Izv. NII Matem. Mekh. Tomskogo Univ. 2 (1938) 7–12.
[27] and , Vol. 35 of Stochastic Approximation and Recursive Algorithms and Applications. Springer Science & Business Media (2003). | MR | Zbl
[28] , and , Central limit theorem for stationary Fleming–Viot particle systems in finite spaces. ALEA 15 (2018) 1163–1182. | MR | Zbl | DOI
[29] and , Quasi-stationary distributions and population processes. Prob. Surv. 9 (2012) 340–410. | MR | Zbl | DOI
[30] , Quasi-stationary distributions: a bibliography. http://www.maths.uq.edu.au/pkp/papers/qsds/qsds.pdf (2008).
[31] and , A stochastic approximation method. Ann. Math. Stat. (1951) 400–407. | MR | Zbl | DOI
[32] , The theory of branching random processes. Uspekhi Mat. Nauk. 6 (1951) 47–99. | MR | Zbl
[33] , Stochastic Processes in Physics and Chemistry. Elsevier, North-Holland, Amsterdam (1992). | MR | Zbl
[34] , General approximation method for the distribution of Markov processes conditioned not to be killed. ESAIM: PS 18 (2014) 441–467. | MR | Zbl | DOI
[35] , and , An approximation scheme for quasi-stationary distributions of killed diffusions. Stoch. Process. Appl. 130 (2020) 3193–3219. | MR | Zbl | DOI
[36] , Certain limit theorems of the theory of branching processes. Dokl. Acad. Nauk. SSSR 56 (1947) 795–798. | MR | Zbl
Cité par Sources :
