Abstract
Let X be a random vector with distribution μ on ℝd and Φ be a mapping from ℝd to ℝ. That mapping acts as a black box, e.g., the result from some computer experiments for which no analytical expression is available. This paper presents an efficient algorithm to estimate a tail probability given a quantile or a quantile given a tail probability. The algorithm improves upon existing multilevel splitting methods and can be analyzed using Poisson process tools that lead to exact description of the distribution of the estimated probabilities and quantiles. The performance of the algorithm is demonstrated in a problem related to digital watermarking.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Arnold, B., Balakrishnan, N., Nagaraja, H.: 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), 901–917 (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)
Bucklew, J.: Introduction to Rare Event Simulation. Springer Series in Statistics. Springer, New York (2004)
Cérou, F., Guyader, A.: Adaptive multilevel splitting for rare event analysis. Stoch. Anal. Appl. 25(2), 417–443 (2007)
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., Rubinstein, R., Vaisman, R.: Smoothed splitting method for counting (2011, submitted)
Cérou, F., Del Moral, P., Furon, T., Guyader, A.: Sequential Monte Carlo for rare event estimation. Stat. Comput. (2011)
Cérou, F., Del Moral, P., Guyader, A.: A non asymptotic theorem for unnormalized Feynman-Kac particle models. Ann. IHP (Probab. Stat.) (2011)
Chopin, N., Robert, C.P.: Properties of nested sampling. Biometrika 97(3), 741–755 (2010)
Del Moral, P., Doucet, A., Jasra, A.: Sequential Monte Carlo samplers. J. R. Stat. Soc., Ser. B, Stat. Methodol. 68(3), 411–436 (2006)
Glasserman, P., Heidelberger, P., Shahabuddin, P., Zajic, T.: Multilevel splitting for estimating rare event probabilities. Oper. Res. 47(4), 585–600 (1999)
Glynn, P.W., Whitt, W.: The asymptotic efficiency of simulation estimators. Oper. Res. 40(3), 505–520 (1992)
Hammersley, J., Handscomb, D.: Monte Carlo Methods. Methuen, London (1965)
IBM (2001). www.trl.ibm.com/projects/RightsManagement/datahiding/dhvgx_e.htm
Kahn, H., Harris, T.: Estimation of particle transmission by random sampling. Natl. Bur. Stand., Appl. Math. Ser. 12, 27–30 (1951)
Knuth, D.: The Art of Computer Programming, Sorting and Searching. Addison-Wesley Series in Computer Science and Information Processing, vol. 3. Addison-Wesley, Reading (1973)
Merhav, N., Sabbag, E.: Optimal watermarking embedding and detection strategies under limited detection resources. IEEE Trans. Inf. Theory 54(1), 255–274 (2008)
Meyn, S., Tweedie, R.: Markov Chains and Stochastic Stability. Communications and Control Engineering Series. Springer, London (1993)
Robert, C., Casella, G.: Monte Carlo Statistical Methods, 2nd edn. Springer Texts in Statistics. Springer, New York (2004)
Roberts, G.O., Gelman, A., Gilks, W.R.: Weak convergence and optimal scaling of random walk Metropolis algorithms. Ann. Appl. Probab. 7(1), 110–120 (1997)
Rosenbluth, M., Rosenbluth, A.: Monte Carlo calculation of the average extension of molecular chains. J. Chem. Phys. 23(2), 356–359 (1955)
Rubinstein, R.: The Gibbs cloner for combinatorial optimization, counting and sampling. Methodol. Comput. Appl. Probab. 11(4), 491–549 (2009)
Schervish, M.J.: Theory of Statistics. Springer Series in Statistics. Springer, New York (1995)
Skilling, J.: Nested sampling for general Bayesian computation. Bayesian Anal. 1(4), 833–859 (2006) (electronic)
Skilling, J.: Nested sampling for Bayesian computations. In: Bayesian Statistics (Oxford Sci. Publ.), vol. 8, pp. 491–524. Oxford Univ. Press, Oxford (2007)
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.: Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (1998)
Van Zwet, W.R.: Convex Transformations of Random Variables. Mathematical Centre Tracts, vol. 7. Mathematisch Centrum, Amsterdam (1964)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partially supported by the Nebbiano project, ANR-06-SETI-009, and by LANL LDRD 20080391ER.
Rights and permissions
About this article
Cite this article
Guyader, A., Hengartner, N. & Matzner-Løber, E. Simulation and Estimation of Extreme Quantiles and Extreme Probabilities. Appl Math Optim 64, 171–196 (2011). https://doi.org/10.1007/s00245-011-9135-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00245-011-9135-z