Rare-event-conditional estimation

As seen in tail risk estimation.

At the moment I mostly care about splitting simulation, but the set-up for that problem is here.

I consider the problem of simulating some quantity of interest conditional on a tail-event defined on a \(d\)-dimensional continuous random variable \(X\) and importance function \(S: \mathbb{R}^d\rightarrow \mathbb{R}\). We write the conditional density \(f^*\) in terms of the density of \(X\) as

\[ f^*(L) = \frac{1}{\ell_\gamma}\mathbb{I}\{L\geq \gamma\} \]


\[ \ell(\gamma):=\mathbb{I}\{L\geq \gamma\} \]

is a normalising constant; specifically, \(\ell(\gamma)\) is the cumulative distribution of the random variable \(L.\)

So, using naïve Monte Carlo, you can estimate this by taking the empirical cdf of \(N\) independent simulations of variable \(L_i\) as an estimate of the true cdf:

\[ \hat{\ell}(\gamma) = \frac{1}{N}\sum_{i=1}^N \mathbb{I}\{L_i\geq \gamma\} \]

Note that if the quantity of interest is precisely this cdf for values of \(\gamma\) close to the expectation we may already be done, depending what we regard as a “good” estimate.

But if we care about rare tail events specifically, we probably need to work harder. Suppose hold \(\gamma\) fixed and \(\ell (\gamma) \ll 10^{-2}\), we have a bad convergence rate for this estimator. 🏗 convergence rates, number of samples.

Importance sampling

🏗 explain explicitly the variance of this estimator.

I simulate using a different variable \(L'=S(L)\). I am interested in the probability of a random portfolio loss \(L\) exceeding a threshold, \(\mathbb{P}(L\geq\gamma)\).

\[ \ell(\gamma) := \mathbb{P}\left(S\right) \]


Dynamic splitting



Asmussen, Søren, Klemens Binswanger, and Bjarne Højgaard. 2000. “Rare Events Simulation for Heavy-Tailed Distributions.” Bernoulli 6 (2, 2): 303–22. https://doi.org/10.2307/3318578.
Asmussen, Søren, and Peter W. Glynn. 2007. Stochastic Simulation: Algorithms and Analysis. 2007 edition. New York: Springer.
Asmussen, Søren, and Dirk P. Kroese. 2006. “Improved Algorithms for Rare Event Simulation with Heavy Tails.” Advances in Applied Probability 38 (2, 2): 545–58. http://www.jstor.org/stable/20443455.
Ben Rached, Nadhir, Zdravko Botev, Abla Kammoun, Mohamed-Slim Alouini, and Raul Tempone. 2018. “On the Sum of Order Statistics and Applications to Wireless Communication Systems Performances.” IEEE Transactions on Wireless Communications 17 (11, 11): 7801–13. https://doi.org/10.1109/TWC.2018.2871201.
Botev, Z. I. 2017. “The Normal Law Under Linear Restrictions: Simulation and Estimation via Minimax Tilting.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 79 (1): 125–48. https://doi.org/10.1111/rssb.12162.
Botev, Zdravko I., and Dirk P. Kroese. 2008. “An Efficient Algorithm for Rare-Event Probability Estimation, Combinatorial Optimization, and Counting.” Methodology and Computing in Applied Probability 10 (4, 4): 471–505. https://doi.org/10.1007/s11009-008-9073-7.
———. 2012. “Efficient Monte Carlo Simulation via the Generalized Splitting Method.” Statistics and Computing 22 (1, 1): 1–16. https://doi.org/10.1007/s11222-010-9201-4.
Botev, Zdravko I., and Pierre L’Ecuyer. 2020. “Sampling Conditionally on a Rare Event via Generalized Splitting.” INFORMS Journal on Computing, April. https://doi.org/10.1287/ijoc.2019.0936.
Botev, Zdravko I., Pierre L’Ecuyer, Gerardo Rubino, Richard Simard, and Bruno Tuffin. 2012. “Static Network Reliability Estimation via Generalized Splitting.” INFORMS Journal on Computing 25 (1, 1): 56–71. https://doi.org/10.1287/ijoc.1110.0493.
Botev, Zdravko I., Pierre L’Ecuyer, and Bruno Tuffin. 2013. “Markov Chain Importance Sampling with Applications to Rare Event Probability Estimation.” Statistics and Computing 23 (2, 2): 271–85. https://doi.org/10.1007/s11222-011-9308-2.
Botev, Zdravko I., Robert Salomone, and Daniel Mackinlay. 2019. “Fast and Accurate Computation of the Distribution of Sums of Dependent Log-Normals.” Annals of Operations Research, February. https://doi.org/10.1007/s10479-019-03161-x.
Botev, Zdravko, and Pierre L’Ecuyer. 2017. “Simulation from the Normal Distribution Truncated to an Interval in the Tail.” In Proceedings of the 10th EAI International Conference on Performance Evaluation Methodologies and Tools, 23–29. VALUETOOLS’16. ICST, Brussels, Belgium, Belgium: ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering). https://doi.org/10.4108/eai.25-10-2016.2266879.
Bréhier, Charles-Edouard, Ludovic Goudenège, and Loïc Tudela. 2016. “Central Limit Theorem for Adaptive Multilevel Splitting Estimators in an Idealized Setting.” In Monte Carlo and Quasi-Monte Carlo Methods, edited by Ronald Cools and Dirk Nuyens, 163:245–60. Springer Proceedings in Mathematics & Statistics. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-33507-0_10.
Cérou, F., P. Del Moral, T. Furon, and A. Guyader. 2011. “Sequential Monte Carlo for Rare Event Estimation.” Statistics and Computing 22 (3): 795–808. https://doi.org/10.1007/s11222-011-9231-6.
Cérou, Frédéric, Pierre Del Moral, François Le Gland, and Pascal Lezaud. 2006. “Genetic Genealogical Models in Rare Event Analysis.” ALEA, Latin American Journal of Probability and Mathematical Statistics. https://hal.inria.fr/inria-00071391.
Cérou, Frédéric, and Arnaud Guyader. 2007. “Adaptive Multilevel Splitting for Rare Event Analysis.” Stochastic Analysis and Applications 25 (2, 2): 417–43. https://doi.org/10.1080/07362990601139628.
Cérou, Frédéric, F. Le Gland François, P. Del Moral, and P. Lezaud. 2005. “Limit Theorems for the Multilevel Splitting Algorithm in the Simulation of Rare Events.” In Proceedings of the Winter Simulation Conference, 2005. https://doi.org/10.1109/WSC.2005.1574309.
Charles-Edouard, Bréhier, Gazeau Maxime, Goudenège Ludovic, Lelièvre Tony, and Rousset Mathias. 2015. “Unbiasedness of Some Generalized Adaptive Multilevel Splitting Algorithms.” May 11, 2015. http://arxiv.org/abs/1505.02674.
Dai, Chenguang, Jeremy Heng, Pierre E. Jacob, and Nick Whiteley. 2020. “An Invitation to Sequential Monte Carlo Samplers.” July 23, 2020. http://arxiv.org/abs/2007.11936.
Dean, Thomas, and Paul Dupuis. 2009. “Splitting for Rare Event Simulation: A Large Deviation Approach to Design and Analysis.” Stochastic Processes and Their Applications 119 (2, 2): 562–87. https://doi.org/10.1016/j.spa.2008.02.017.
Del Moral, Pierre, and Pascal Lezaud. 2006. “Branching and Interacting Particle Interpretations of Rare Event Probabilities.” In Stochastic Hybrid Systems, pp 277–323. Lecture Notes in Control and Information Science, Volume 337. Berlin, Heidelberg: Springer. https://doi.org/10.1007/11587392_9.
Garvels, M. J. J., and D. P. Kroese. 1998. “A Comparison of RESTART Implementations.” In Proceedings of the 1998 Winter Simulation Conference, 1:601–608 vol.1. Washington, DC, USA: IEEE. https://doi.org/10.1109/WSC.1998.745040.
Glasserman, P., P. Heidelberger, P. Shahabuddin, and T. Zajic. 1998. “A Large Deviations Perspective on the Efficiency of Multilevel Splitting.” IEEE Transactions on Automatic Control 43 (12, 12): 1666–79. https://doi.org/10.1109/9.736061.
Glasserman, Paul, Philip Heidelberger, Perwez Shahabuddin, and Tim Zajic. 1998. “A Look At Multilevel Splitting.” In Monte Carlo and Quasi-Monte Carlo Methods 1996, edited by Harald Niederreiter, Peter Hellekalek, Gerhard Larcher, and Peter Zinterhof, 98–108. Lecture Notes in Statistics. New York, NY: Springer. https://doi.org/10.1007/978-1-4612-1690-2_5.
Johansen, Adam M., Pierre Del Moral, and Arnaud Doucet. 2006. “Sequential Monte Carlo Samplers for Rare Events.” In Proceedings of the 6th International Workshop on Rare Event Simulation, 256–67. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=
L’Ecuyer, Pierre, Jose H. Blanchet, Bruno Tuffin, and Peter W. Glynn. 2010. “Asymptotic Robustness of Estimators in Rare-Event Simulation.” ACM Transactions on Modeling and Computer Simulation 20 (1, 1): 6:1–41. https://doi.org/10.1145/1667072.1667078.
L’Ecuyer, Pierre, Valérie Demers, and Bruno Tuffin. 2006. “Splitting for Rare-Event Simulation.” In 38th Conference on Winter Simulation, 137–48. WSC ’06. Monterey, California: Winter Simulation Conference. https://doi.org/10.1109/WSC.2006.323046.
———. 2007. “Rare Events, Splitting, and Quasi-Monte Carlo.” ACM Transactions on Modeling and Computer Simulation (TOMACS), April. http://www-labs.iro.umontreal.ca/ lecuyer/myftp/papers/split.pdf.
L’Ecuyer, Pierre, François Le Gland, Pascal Lezaud, and Bruno Tuffin. 2009. “Splitting Techniques.” In Rare Event Simulation Using Monte Carlo Methods, Chapter 3. John Wiley & Sons, Ltd. https://doi.org/10.1002/9780470745403.ch3.
Rubino, Gerardo, and Bruno Tuffin, eds. 2009. Rare Event Simulation Using Monte Carlo Methods. 1st ed. Chichester, U.K: John Wiley & Sons, Ltd. https://doi.org/10.1002/9780470745403.
Rubinstein, Reuven Y., and Dirk P. Kroese. 2016. Simulation and the Monte Carlo Method. 3 edition. Wiley Series in Probability and Statistics. Hoboken, New Jersey: Wiley.
Shahabuddin, Perwez. 1994. “Importance Sampling for the Simulation of Highly Reliable Markovian Systems.” Management Science 40 (3, 3): 333–52. https://doi.org/10.1287/mnsc.40.3.333.
Villén-Altamirano, Manuel, and José Villén-Altamirano. 2011. “The Rare Event Simulation Method RESTART: Efficiency Analysis and Guidelines for Its Application.” In Network Performance Engineering: A Handbook on Convergent Multi-Service Networks and Next Generation Internet, edited by Demetres D. Kouvatsos, 509–47. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-02742-0_22.