Recursive Monte Carlo filters: algorithms and theoretical analysis. (English) Zbl 1086.62106

Summary: Recursive Monte Carlo filters, also called particle filters, are a powerful tool to perform computations in general state space models. We discuss and compare the accept-reject version with the more common sampling importance resampling version of the algorithm. In particular we show how auxiliary variable methods and stratification can be used in the accept-reject version, and we compare different resampling techniques. In a second part, we show laws of large numbers and a central limit theorem for these Monte Carlo filters by simple induction arguments that need only weak conditions. We also show that, under stronger conditions, the required sample size is independent of the length of the observed series.


62M20 Inference from stochastic processes and prediction
65C60 Computational problems in statistics (MSC2010)
62M09 Non-Markovian processes: estimation
60F05 Central limit and other weak theorems
60G35 Signal detection and filtering (aspects of stochastic processes)
60J22 Computational methods in Markov chains
65C05 Monte Carlo methods
Full Text: DOI arXiv


[1] Atar, R. and Zeitouni, O. (1997). Exponential stability for nonlinear filtering. Ann. Inst. H. Poincaré Probab. Statist. 33 697-725. · Zbl 0888.93057
[2] Carpenter, J., Clifford, P. and Fearnhead, P. (1999). Improved particle filter for nonlinear problems. IEE Proceedings F , Radar , Sonar and Navigation 146 2-7.
[3] Chopin, N. (2004). Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference. Ann. Statist. 32 2385-2411. · Zbl 1079.65006
[4] Crisan, D. (2001). Particle filters–A theoretical perspective. In Sequential Monte Carlo Methods in Practice (A. Doucet, N. de Freitas and N. Gordon, eds.) 17-41. Springer, Berlin. · Zbl 1056.93573
[5] Crisan, D., Del Moral, P. and Lyons, T. (1999). Discrete filtering using branching and interacting particle systems. Markov Process. Related Fields 5 293-318. · Zbl 0967.93088
[6] Crisan, D. and Lyons, T. (2002). Minimal entropy approximations and optimal algorithms. Monte Carlo Methods Appl. 8 343-355. · Zbl 1018.65014
[7] Del Moral, P. and Guionnet, A. (2001). On the stability of interacting processes with applications to filtering and genetic algorithms. Ann. Inst. H. Poincaré Probab. Statist. 37 155-194. · Zbl 0990.60005
[8] Del Moral, P. and Miclo, L. (2000). Branching and interacting particle systems. Approximations of Feynman-Kac formulae with applications to non-linear filtering. Séminaire de Probabilités XXXIV . Lecture Notes in Math. 1729 1-145. Springer, Berlin. · Zbl 0963.60040
[9] Devroye, L. (1987). A Course in Density Estimation. Birkhäuser, Basel. · Zbl 0617.62043
[10] Dobrushin, R. L. (1956). Central limit theorem for non-stationary Markov chains. I, II. Theory Probab. Appl. 1 65-80, 329-383. · Zbl 0093.15001
[11] Douc, R., Moulines, E. and Rydén, T. (2004). Asymptotic properties of the maximum likelihood estimator in autoregressive models with Markov regime. Ann. Statist. 32 2254-2304. · Zbl 1056.62028
[12] Doucet, A., de Freitas, N. and Gordon, N., eds. (2001). Sequential Monte Carlo Methods in Practice . Springer, New York. · Zbl 0967.00022
[13] Frühwirth-Schnatter, S. (1994). Data augmentation and dynamic linear models. J. Time Ser. Anal. 15 183-202. · Zbl 0815.62065
[14] Godsill, S. J., Doucet, A. and West, M. (2004). Monte Carlo smoothing for nonlinear time series. J. Amer. Statist. Assoc. 99 156-168. · Zbl 1089.62517
[15] Gordon, N. J., Salmond, D. J. and Smith, A. F. M. (1993). Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings F , Radar and Signal Processing 140 107-113.
[16] Hannan, E. J. and Deistler, M. (1988). The Statistical Theory of Linear Systems . Wiley, New York. · Zbl 0641.93002
[17] Harvey, A. C. (1989). Forecasting , Structural Time Series Models and the Kalman Filter. Cambridge Univ. Press.
[18] Hürzeler, M. and Künsch, H. R. (1998). Monte Carlo approximations for general state-space models. J. Comput. Graph. Statist. 7 175-193.
[19] Hürzeler, M. and Künsch, H. R. (2001). Approximating and maximizing the likelihood for a general state space model. In Sequential Monte Carlo Methods in Practice (A. Doucet, N. de Freitas and N. Gordon, eds.) 159-175. Springer, New York. · Zbl 1056.93580
[20] Künsch, H. R. (2001). State space and hidden Markov models. In Complex Stochastic Systems (O. E. Barndorff-Nielsen, D. R. Cox and C. Klüppelberg, eds.) 109-173. Chapman and Hall/CRC, Boca Raton, FL. · Zbl 1002.62072
[21] Le Gland, F. and Oudjane, N. (2004). Stability and uniform approximation of nonlinear filters using the Hilbert metric and application to particle filters. Ann. Appl. Probab. 14 144-187. · Zbl 1060.93094
[22] Liu, J. S. and Chen, R. (1998). Sequential Monte Carlo methods for dynamic systems. J. Amer. Statist. Assoc. 93 1032-1044. · Zbl 1064.65500
[23] Pitt, M. K. and Shephard, N. (1999). Filtering via simulation: Auxiliary particle filters. J. Amer. Statist. Assoc. 94 590-599. · Zbl 1072.62639
[24] Pitt, M. K. and Shephard, N. (2001). Auxiliary variable based particle filters. In Sequential Monte Carlo Methods in Practice (A. Doucet, N. de Freitas and N. Gordon, eds.) 273-293. Springer, New York. · Zbl 1056.93590
[25] Robert, C. P. and Casella, G. (1999). Monte Carlo Statistical Methods . Springer, New York. · Zbl 0935.62005
[26] Rubin, D. (1988). Using the SIR algorithm to simulate posterior distributions. In Bayesian Statistics 3 (J. M. Bernardo, M. H. DeGroot, D. V. Lindley and A. F. M. Smith, eds.) 395-402. Oxford Univ. Press. · Zbl 0713.62035
[27] Shephard, N. (1996). Statistical aspects of ARCH and stochastic volatility. In Time Series Models: In Econometrics , Finance and Other Fields (D. R. Cox, D. V. Hinkley and O. E. Barndorff-Nielsen, eds.) 1-67. Chapman and Hall, London.
[28] Whitley, D. (1994). A genetic algorithm tutorial. Stat. Comput. 4 65-85.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.