×

Interacting Markov chain Monte Carlo methods for solving nonlinear measure-valued equations. (English) Zbl 1198.65024

Let \((S^{(l)},{\mathcal S}^{(l)})_{l\geq 0}\) be a sequence of measurable spaces, \({\mathcal P}(S^{(l)})\) the set of probability measures on \(S^{(l)}\), \(\pi^{(l)}\in{\mathcal P}(S^{(l)})\), \(l\geq 0\), where \(\pi^{(0)}\) is known. For \(l\geq 1\) consider the equations \(\pi^{(l)}= \Phi_l(\pi^{(l-1)})\) for some mappings \(\Phi_l:{\mathcal P}(S^{(l-1)})\to{\mathcal P}(S^{(l)})\). The authors develop a new class of interacting Markov chain Monte Carlo (i-MCMC) methods for a numerical approximation of the solution. At level \(l=0\) a Markov chain Monte Carlo (MCMC) algorithm is run to obtain a chain \(X^{(0)}= (X^{(0)}_n)_{n\geq 0}\) targeting \(\pi^{(0)}\). (The “time” index \(n\) corresponds to the number of iterations of the i-MCMC algorithm.) The occupation measure of the chain \(X^{(0)}\) at time \(n\) is used to design a second MCMC algorithm to generate \(X^{(1)}= (X^{(1)}_n)_{n\geq 0}\) at level \(1\) targeting \(\pi^{(1)}\): The elementary transition \(X^{(1)}_n\rightsquigarrow X^{(1)}_{n+1}\) of the chain \(X^{(1)}\) at “time” \(n\) depends on the occupation measure of \((X^{(0)}_0, X^{(0)}_1,\dots, X^{(0)}_n)\).
Similarly, the empirical measure of \(X^{(l-1)}\) at level \(l-1\) is used to “feed” an MCMC algorithm generating \(X^{(l)}\) targeting \(\pi^{(l)}\) at level \(l\). Denote \(\overline X^{(m)}_n:= (X^{(0)}_n,\dots, X^{(m)}_n)\), \(\overline\pi^{[m]}:= \pi^{(1)}\otimes\cdots\otimes \pi^{(m)}\), let \(\delta_{X,n,m}\), \(\delta_{\overline X,n,m}\) be the Dirac measures at \(X^{(m)}_n\), \(\overline X^{(m)}_n\), respectively, and set \(\eta^{[m]}_n:= (n+1)^{-1}\cdot \sum^n_{p=1} \delta_{X,p,m}\), \(\overline\eta^{[m]}_n:= (n+1)^{-1}\cdot \sum^n_{p=1} \delta_{\overline X,p,m}\).
The main results may then be written as follows: For every \(r\geq 1\), \(m\geq 1\), and any bounded measurable function \(f\) on \(S^{(0)}\times\cdots\times S^{(m)}\) we have \(\sup_{n\geq 1}\sqrt{n}{\mathbf E}(|\overline\eta^{[m]}_n(f)- \overline\pi^{[m]}(f)|^r)< \infty\) and, under additional regularity conditions, \[ \forall t\limsup_{n\to\infty}(1/n)\log{\mathbf P}(|\overline\eta^{[m]}_n(f)- \overline\pi^{[m]}(f)|> 1)< -t^2/2\overline\sigma^2_m \] with some positive constant \(\overline\sigma<\infty\).
Finally, for some \(\alpha\in(0,1]\) and any sequence of bounded measurable functions \(f_n|S^{(n)}\) with \(|f_n|\leq 1\), \(\sup_{k\geq 0}\,\sup_{n\geq 0} n^{\alpha/2}{\mathbf E}(|\eta^{(k)}_n(f_n)- \pi^{(k)}(f_n)|^r)< \infty\).

MSC:

65C05 Monte Carlo methods
47H20 Semigroups of nonlinear operators
60G35 Signal detection and filtering (aspects of stochastic processes)
60J85 Applications of branching processes
62G09 Nonparametric statistical resampling methods
47D08 Schrödinger and Feynman-Kac semigroups
47G10 Integral operators
62L20 Stochastic approximation
65C40 Numerical analysis or methods applied to Markov chains
60J22 Computational methods in Markov chains
60H25 Random operators and equations (aspects of stochastic analysis)
47J25 Iterative procedures involving nonlinear operators
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andrieu, C., Jasra, A., Doucet, A. and Del Moral, P. (2007). Non-linear Markov chain Monte Carlo via self-interacting approximations. Technical report, Dept. Mathematics, Bristol Univ. · Zbl 1359.60048
[2] Bercu, B., Del Moral, P. and Doucet, A. (2009). A functional central limit theorem for a class of interacting Markov chain Monte Carlo methods. Electron. J. Probab. 73 2130-2155. · Zbl 1191.60038
[3] Bercu, B., Del Moral, P. and Doucet, A. (2008). Fluctuations of interacting Markov chain Monte Carlo models. Technical Report INRIA 6438. · Zbl 1244.60043
[4] Brockwell, A., Del Moral, P. and Doucet, A. (2010). Sequentially interacting Markov chain Monte Carlo. Ann. Statist. · Zbl 1251.65002
[5] Del Moral, P. (2004). Feynman-Kac Formulae : Genealogical and Interacting Particle Systems With Applications . Springer, New York. · Zbl 1130.60003
[6] Del Moral, P. and Miclo, L. (2006). Self-interacting Markov chains. Stoch. Anal. Appl. 24 615-660. · Zbl 1093.60068 · doi:10.1080/07362990600632029
[7] Del Moral, P. and Miclo, L. (2003). On convergence of chains with time empirical self-interactions. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 460 325-346. · Zbl 1061.60069 · doi:10.1098/rspa.2003.1245
[8] Doucet, A., de Freitas, N. and Gordon, N., eds. (2001). Sequential Monte Carlo Methods in Practice . Springer, New York. · Zbl 0967.00022
[9] Kou, S. C., Zhou, Q. and Wong, W. H. (2006). Equi-energy sampler with applications in statistical inference and statistical mechanics. Ann. Statist. 34 1581-1652. · Zbl 1246.82054 · doi:10.1214/009053606000000515
[10] Lyman, E. and Zuckerman, D. M. (2006). Resolution exchange simulation with incremental coarsening. J. Chem. Theory Comp. 2 656-666.
[11] Mengersen, K. L. and Tweedie, R. L. (1996). Rates of convergence of the Hastings and Metropolis algorithms. Ann. Statist. 24 101-121. · Zbl 0854.60065 · doi:10.1214/aos/1033066201
[12] Robert, C. P. and Casella, G. (2004). Monte Carlo Statistical Methods , 2nd ed. Springer, New York. · Zbl 1096.62003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.