cnrs   Université de Toulouse

Table of contents for this issue | Previous article | Next article
Nicolas Bousquet
Accelerated Monte Carlo estimation of exceedance probabilities under monotonicity constraints
Annales de la faculté des sciences de Toulouse Sér. 6, 21 no. 3 (2012), p. 557-591, doi: 10.5802/afst.1345
Article PDF | Reviews MR 3076412 | Zbl 1275.62058

Résumé - Abstract

The problem of estimating the probability ${p}=P(g({\bf X})\le 0)$ is considered when ${\bf X}$ represents a multivariate stochastic input of a monotonic function $g$. First, a heuristic method to bound ${p}$, originally proposed by de Rocquigny (2009), is formally described, involving a specialized design of numerical experiments. Then a statistical estimation of ${p}$ is considered based on a sequential stochastic exploration of the input space. A maximum likelihood estimator of ${p}$ build from successive dependent Bernoulli data is defined and its theoretical convergence properties are studied. Under intuitive or mild conditions, the estimation is faster and more robust than the traditional Monte Carlo approach, therefore adapted to time-consuming computer codes $g$. The main result of the paper is related to the variance of the estimator. It appears as a new baseline measure of efficiency under monotonicity constraints, which could play a similar role to the usual Monte Carlo estimator variance in unconstrained frameworks. Furthermore the bias of the estimator is shown to be corrigible via bootstrap heuristics. The behavior of the method is illustrated by numerical tests conducted on a class of toy examples and a more realistic hydraulic case-study.


[1] Anonymous.— Open TURNS version 0.14.0 – Reference guide. Tech. rep., EDF-EADS-PhiMeca (2011).
[2] Bercu (B.).— Inégalités exponentielles pour les martingales [in french]. Journées ALEA 2008 CIRM p. 10-14 March (2008).
[3] Bester (C.), Hansen (C.).— Bias reduction for Bayesian and frequentist estimators. Working Paper. University of Chicago (2005).
[4] Cannamela (C.), Garnier (J.), Iooss (B.).— Controlled stratification for quantile estimation. Annals of Applied Statistics 2, p. 1554-1580 (2008).  MR 2655671 |  Zbl 1156.62023
[5] Chan (T.).— A (slightly) faster algorithm for Klee’s measure problem. p. 94-100, College Park, MD, USA (2008).  MR 2504275 |  Zbl 1221.65059
[6] Chen (G.).— Monotonicity of dependence concepts: from independent random vector into dependent random vector. World Academy of Science, Engineering and Technology 57, p. 399-408 (2009).
[7] Chlebus (B.).— On the Klee’s measure problem in small dimensions. Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (1998).  Zbl 0936.68055
[8] Cox (D.), Snell (E.).— A general definition of residuals. Journal of the Royal Statistical Society 30, p. 248-275 (1968).  MR 237052 |  Zbl 0164.48903
[9] Crowder (M.).— Maximum likelihood estimation for dependent observations. Journal of the Royal Statistical Society 38, p. 43-53 (1975).  MR 403035 |  Zbl 0324.62023
[10] Crowder (M.).— On constrained maximum likelihood estimation with non-iid. observations. Annals of the Institute of Statistical Mathematics 36, p. 239-249 (1983).  MR 758500 |  Zbl 0553.62027
[11] Daniels (H.), Velikova (M.).— Monotone and partially monotone neural networks. IEEE Transactions in Neural Networks 21, p. 906-917 (2010).
[12] de Berg (M.), van Kreveld (M.), Overmars (M.), Schwarzkopf (O.).— Computational Geometry Algorithms and Applications. Springer-Verlag (1997).  MR 1470713 |  Zbl 0939.68134
[13] de Rocquigny (E.).— Structural reliability under monotony: A review of properties of FORM and associated simulation methods and a new class of monotonous reliability methods (MRM). Structural Safety 31, p. 363-374 (2009).
[14] Durot (C.).— Monotone nonparametric regression with random design. Mathematical Methods in Statistics 17, p. 327-341 (2008).  MR 2483461 |  Zbl 1231.62066
[15] Efron (B.), Tibshirani (R.J.).— An Introduction to the Bootstrap. New York: Chapman & Hall (1993).  MR 1270903 |  Zbl 0835.62038
[16] Erickson (J.).— Klee’s measure problem. Tech. rep., University of Illinois at Urbana-Champaign, URL: (1998).
[17] Ferrari (S.), Cribari-Neto (F.).— On bootstrap and analytical bias correction. Economics Letters 58, p. 7-15 (1998).  MR 1608586 |  Zbl 0899.90043
[18] Figueira (J.), Greco (S.), Erhgott (M.).— Multiple criteria decision analysis – State of the art – Survey. Springer’s International Series (2005).  Zbl 1060.90002
[19] Fleischer (M.).— The measure of Pareto optima. Applications to multi-objective metaheuristics. vol. 262, p. 519-523, Faro, Portugal (2003).  Zbl 1036.90530
[20] Glynn (P.), Rubino (G.), Tuffin (B.).— Robustness properties and confidence interval reliability. In: Rare Event Simulation. Wiley (2009).  MR 2730762
[21] Hurtado (J.).— An examination of methods for approximating implicit limit state functions from the viewpoint of statistical learning theory. Structural Safety 26, p. 271-293 (2004).
[22] Kleijnen (J.).— Simulation optimization via bootstrapped kriging: Survey. Tech. rep., Rport from Tilburg University, Center for Economic Research (2011).
[23] Kleijnen (J.), van Beers (W.).— Monotonicity-preserving bootstrapped kriging metamodels for expensive simulations. Tech. rep., Discussion Paper 2009-75, Tilburg University, Center for Economic Research (2009).
[24] Kroese (D.), Rubinstein (R.).— Simulation and the Monte Carlo Method (2nd edition). Wiley (2007).  MR 2365210 |  Zbl 1147.68831
[25] Lemaire (M.), Pendola (M.).— PHIMECA-SOFT. Structural Safety 28, p. 130-149 (2006).
[26] Limbourg (P.), de Rocquigny (E.), Andrianov (G.).— Accelerated uncertainty propagation in two-level probabilistic studies under monotony. Reliability Engineering and System Safety 95, p. 998-1010 (2010).
[27] Lin (D.).— A new class of supersaturated design. Technometrics 35, p. 28-31 (1993).
[28] MacKay (M.), Beckman (R.), Conover (W.).— A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21, p. 239-249 (1979).  MR 533252 |  Zbl 0415.62011
[29] Madsen (H.), Ditlevsen (O.).— Structural reliability methods. Wiley (1996).
[30] Meyer (P.A.).— Martingales and stochastic integrals. Lecture Notes in Mathematics Vol. 284. Springer-Verlag (1972).  MR 426145 |  Zbl 0239.60001
[31] Morio (J.).— Influence of input pdf parameters of a model on a failure probability estimation. Simulation Modelling Practice and Theory 19, p. 2244-2255 (2011).
[32] Munoz-Muniga (M.), Garnier (J.), Remy (E.), de Rocquigny (E.).— Adaptive directional stratification for controlled estimation of the probability of a rare event. Reliability Engineering and System Safety (in press) (2011).
[33] Overmars (M.H.), Yap (C.K.).— New upper bounds in Klee’s measure problem. SIAM Journal of Computing 20, p. 1034-1045 (1991).  MR 1135747 |  Zbl 0737.68045
[34] Rajabalinejad (M.), Meester (L.), van Gelder (P.), Vrijling (J.).— Dynamic bounds coupled with Monte Carlo simulations. Reliability Engineering and System Safety 96, p. 278-285 (2011).
[35] Ranjan (P.), Bingham (D.), Michailidis (G.).— Sequential experiment design for contour estimation from complex computer codes. Technometrics 50, p. 527-541 (2008).  MR 2655651
[36] Rüschendorf (L.).— On the distributional transform, Sklar’s theorem, and the empirical copula process. Journal of Statistical Planning and Inference 139, p. 3921-3927. (2009)  MR 2553778 |  Zbl 1171.60313
[37] Shamos (M.I.), Hoey (D.).— Geometric intersection problems. Proceedings of the 17th IEEE Symposium about the Foundations of Computer Science (FOCS’76) p. 208-215 (1976).  MR 455532
[38] Tsompanakis (Y.), Lagaros (N.), Papadrakakis (M.), Frangopol (D.e.).— Structural design optimization considering uncertainties. Taylor & Francis (2007).
[39] van Leeuwen (J.), Wood (D.).— The measure problem for rectangular ranges in $d$-space. Journal of Algorithms 2, p. 282-300 (1981).  MR 632450 |  Zbl 0487.68032
Search for an article
Search within the site