Skip to main content
SpringerLink
Log in

Simulation and Estimation of Extreme Quantiles and Extreme Probabilities

  • Published:
Applied Mathematics & Optimization Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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)

    MATH  Google Scholar 

  2. 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)

    Article  Google Scholar 

  3. 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)

    Article  Google Scholar 

  4. 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)

    Article  MathSciNet  Google Scholar 

  5. Botev, Z.I., Kroese, D.P.: Efficient Monte Carlo simulation via the generalized splitting method. Stat. Comput. (2011)

  6. Bucklew, J.: Introduction to Rare Event Simulation. Springer Series in Statistics. Springer, New York (2004)

    MATH  Google Scholar 

  7. Cérou, F., Guyader, A.: Adaptive multilevel splitting for rare event analysis. Stoch. Anal. Appl. 25(2), 417–443 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. 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)

    MathSciNet  MATH  Google Scholar 

  9. Cérou, F., Guyader, A., Rubinstein, R., Vaisman, R.: Smoothed splitting method for counting (2011, submitted)

  10. Cérou, F., Del Moral, P., Furon, T., Guyader, A.: Sequential Monte Carlo for rare event estimation. Stat. Comput. (2011)

  11. Cérou, F., Del Moral, P., Guyader, A.: A non asymptotic theorem for unnormalized Feynman-Kac particle models. Ann. IHP (Probab. Stat.) (2011)

  12. Chopin, N., Robert, C.P.: Properties of nested sampling. Biometrika 97(3), 741–755 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Del Moral, P., Doucet, A., Jasra, A.: Sequential Monte Carlo samplers. J. R. Stat. Soc., Ser. B, Stat. Methodol. 68(3), 411–436 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  14. Glasserman, P., Heidelberger, P., Shahabuddin, P., Zajic, T.: Multilevel splitting for estimating rare event probabilities. Oper. Res. 47(4), 585–600 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  15. Glynn, P.W., Whitt, W.: The asymptotic efficiency of simulation estimators. Oper. Res. 40(3), 505–520 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  16. Hammersley, J., Handscomb, D.: Monte Carlo Methods. Methuen, London (1965)

    Google Scholar 

  17. IBM (2001). www.trl.ibm.com/projects/RightsManagement/datahiding/dhvgx_e.htm

  18. Kahn, H., Harris, T.: Estimation of particle transmission by random sampling. Natl. Bur. Stand., Appl. Math. Ser. 12, 27–30 (1951)

    Google Scholar 

  19. 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)

    Google Scholar 

  20. Merhav, N., Sabbag, E.: Optimal watermarking embedding and detection strategies under limited detection resources. IEEE Trans. Inf. Theory 54(1), 255–274 (2008)

    Article  MathSciNet  Google Scholar 

  21. Meyn, S., Tweedie, R.: Markov Chains and Stochastic Stability. Communications and Control Engineering Series. Springer, London (1993)

    MATH  Google Scholar 

  22. Robert, C., Casella, G.: Monte Carlo Statistical Methods, 2nd edn. Springer Texts in Statistics. Springer, New York (2004)

    MATH  Google Scholar 

  23. 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)

    Article  MathSciNet  MATH  Google Scholar 

  24. Rosenbluth, M., Rosenbluth, A.: Monte Carlo calculation of the average extension of molecular chains. J. Chem. Phys. 23(2), 356–359 (1955)

    Article  Google Scholar 

  25. Rubinstein, R.: The Gibbs cloner for combinatorial optimization, counting and sampling. Methodol. Comput. Appl. Probab. 11(4), 491–549 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  26. Schervish, M.J.: Theory of Statistics. Springer Series in Statistics. Springer, New York (1995)

    MATH  Google Scholar 

  27. Skilling, J.: Nested sampling for general Bayesian computation. Bayesian Anal. 1(4), 833–859 (2006) (electronic)

    MathSciNet  Google Scholar 

  28. Skilling, J.: Nested sampling for Bayesian computations. In: Bayesian Statistics (Oxford Sci. Publ.), vol. 8, pp. 491–524. Oxford Univ. Press, Oxford (2007)

    Google Scholar 

  29. Tierney, L.: Markov chains for exploring posterior distributions. Ann. Stat. 22(4), 1701–1762 (1994) With discussion and a rejoinder by the author

    Article  MathSciNet  MATH  Google Scholar 

  30. van der Vaart, A.: Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (1998)

    MATH  Google Scholar 

  31. Van Zwet, W.R.: Convex Transformations of Random Variables. Mathematical Centre Tracts, vol. 7. Mathematisch Centrum, Amsterdam (1964)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université Rennes 2, 35043, Rennes Cedex, France

    Arnaud Guyader & Eric Matzner-Løber

  2. INRIA Rennes, 35043, Rennes Cedex, France

    Arnaud Guyader

  3. Information Sciences Group, Los Alamos National Laboratory, Los Alamos, NM, 86545, USA

    Nicolas Hengartner

Authors
  1. Arnaud Guyader
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nicolas Hengartner
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eric Matzner-Løber
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Arnaud Guyader.

Additional information

This work was partially supported by the Nebbiano project, ANR-06-SETI-009, and by LANL LDRD 20080391ER.

Rights and permissions

Reprints 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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00245-011-9135-z

Keywords

Search

Navigation