Abstract
This paper discusses a novel strategy for simulating rare events and an associated Monte Carlo estimation of tail probabilities. Our method uses a system of interacting particles and exploits a Feynman-Kac representation of that system to analyze their fluctuations. Our precise analysis of the variance of a standard multilevel splitting algorithm reveals an opportunity for improvement. This leads to a novel method that relies on adaptive levels and produces, in the limit of an idealized version of the algorithm, estimates with optimal variance. The motivation for this theoretical work comes from problems occurring in watermarking and fingerprinting of digital contents, which represents a new field of applications of rare event simulation techniques. Some numerical results show performance close to the idealized version of our technique for these practical applications.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arnold, B.C., Balakrishnan, N., Nagaraja, H.N.: A First Course in Order Statistics. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Wiley, New York (1992)
Au, S.K., Beck, J.L.: Estimation of small failure probabilities in high dimensions by subset simulation. Probab. Eng. Mech. 16(4), 263–277 (2001)
Au, S.K., Beck, J.L.: Subset simulation and its application to seismic risk based on dynamic analysis. J. Eng. Mech. 129(8) (2003)
Barg, A., Blakley, G.R., Kabatiansky, G.A.: Digital fingerprinting codes: problem statements, constructions, identification of traitors. IEEE Trans. Signal Process. 51(4), 960–980 (2003)
Botev, Z.I., Kroese, D.P.: An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting. Methodol. Comput. Appl. Probab. 10(4), 471–505 (2008)
Botev, Z.I., Kroese, D.P.: Efficient Monte Carlo simulation via the generalized splitting method. Stat. Comput. (2011). doi:10.1007/s11222-010-9201-4
Bucklew, J.A.: Introduction to Rare Event Simulation. Springer Series in Statistics. Springer, New York (2004)
Cérou, F., Del Moral, P., Guyader, A.: A non asymptotic variance theorem for unnormalized Feynman-Kac particle models. Ann. Inst. Henri Poincaré, Probab. Stat. 47(3) (2011, in press)
Cérou, F., Del Moral, P., Le Gland, F., Lezaud, P.: Genetic genealogical models in rare event analysis. ALEA Lat. Am. J. Probab. Math. Stat. 1, 181–203 (2006)
Cérou, F., Guyader, A.: Adaptive multilevel splitting for rare event analysis. Stoch. Anal. Appl. 25(2), 417–443 (2007)
Copy Protection Technical Working Group. www.cptwg.org
Del Moral, P.: Feynman-Kac Formulae, Genealogical and Interacting Particle Systems with Applications. Probability and its Applications. Springer, New York (2004)
Del Moral, P., Doucet, A., Jasra, A.: Sequential Monte Carlo samplers. J. R. Stat. Soc., Ser. B, Stat. Methodol. 68(3), 411–436 (2006)
Del Moral, P., Lezaud, P.: Branching and interacting particle interpretation of rare event probabilities. In: Blom, H., Lygeros, J. (eds.) Stochastic Hybrid Systems: Theory and Safety Critical Applications. Lecture Notes in Control and Information Sciences, vol. 337, pp. 277–323. Springer, Berlin (2006)
Doucet, A., de Freitas, N., Gordon, N. (eds.): Sequential Monte Carlo Methods in Practice. Statistics for Engineering and Information Science. Springer, New York (2001)
Garvels, M.J.J.: The splitting method in rare event simulation. Thesis, University of Twente, Twente, May 2000
Glasserman, P., Heidelberger, P., Shahabuddin, P., Zajic, T.: Multilevel splitting for estimating rare event probabilities. Oper. Res. 47(4), 585–600 (1999)
Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1), 97–109 (1970)
Johansen, A.M., Del Moral, P., Doucet, A.: Sequential Monte Carlo samplers for rare events. In: Proceedings of the 6th International Workshop on Rare Event Simulation, Bamberg, pp. 256–267 (2006)
Kahn, H., Harris, T.E.: Estimation of particle transmission by random sampling. Natl. Bur. Stand., Appl. Math. Ser. 12, 27–30 (1951)
Lagnoux, A.: Rare event simulation. Probab. Eng. Inf. Sci. 20(1), 45–66 (2006)
Le Gland, F., Oudjane, N.: A sequential algorithm that keeps the particle system alive. In: Blom, H., Lygeros, J. (eds.) Stochastic Hybrid Systems: Theory and Safety Critical Applications. Lecture Notes in Control and Information Sciences, vol. 337, pp. 351–389. Springer, Berlin (2006)
Merhav, N., Sabbag, E.: Optimal watermarking embedding and detection strategies under limited detection resources. IEEE Trans. Inf. Theory 54(1), 255–274 (2008)
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087–1092 (1953)
Rosenbluth, M.N., Rosenbluth, A.W.: Monte Carlo calculation of the average extension of molecular chains. J. Chem. Phys. 23, 356 (1955)
Rubinstein, R.: The Gibbs cloner for combinatorial optimization, counting and sampling. Methodol. Comput. Appl. Probab. 4, 491–549 (2008)
Tardos, G.: Optimal probabilistic fingerprint codes. In: Proc. of the 35th Annual ACM Symposium on Theory of Computing, pp. 116–125. ACM, San Diego (2003)
Tierney, L.: Markov chains for exploring posterior distributions. Ann. Stat. 22(4), 1701–1762 (1994). With discussion and a rejoinder by the author
van der Vaart, A.W.: Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partially supported by the French Agence Nationale de la Recherche (ANR), project Nebbiano, number ANR-06-SETI-009.
Rights and permissions
About this article
Cite this article
Cérou, F., Del Moral, P., Furon, T. et al. Sequential Monte Carlo for rare event estimation. Stat Comput 22, 795–808 (2012). https://doi.org/10.1007/s11222-011-9231-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11222-011-9231-6