Rare-event-conditional estimation

May 29, 2017 — November 10, 2017

Suspiciously similar content

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 : R^{d} \to R$ . We write the conditional density $f^{*}$ in terms of the density of $X$ as

$f^{*} (L) = \frac{1}{ℓ_{γ}} I {L \geq γ}$

where

$ℓ (γ) := I {L \geq γ}$

is a normalising constant; specifically, $ℓ (γ)$ 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{ℓ} (γ) = \frac{1}{N} \sum_{i = 1}^{N} I {L_{i} \geq γ}$

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

But if we care about rare tail events specifically, we probably need to work harder. Suppose we hold $γ$ fixed and $ℓ (γ) ≪ 10^{- 2}$ , we have a bad convergence rate for this estimator. 🚧TODO🚧 clarify convergence rates, number of samples.

1 Importance sampling

🚧TODO🚧 clarify 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, $P (L \geq γ)$ .

$ℓ (γ) := P (S)$

TBC.

2 Dynamic splitting

TBC.

3 Large deviations

Touchette (2011)

The theory of large deviations deals with the probabilities of rare events (or fluctuations) that are exponentially small as a function of some parameter, e.g., the number of random components of a system, the time over which a stochastic system is observed, the amplitude of the noise perturbing a dynamical system or the temperature of a chemical reaction. The theory has applications in many different scientific fields, ranging from queuing theory to statistics and from finance to engineering. It is also increasingly used in statistical physics for studying both equilibrium and nonequilibrium systems. In this context, deep analogies can be made between familiar concepts of statistical physics, such as the entropy and the free energy, and concepts of large deviation theory having more technical names, such as the rate function and the scaled cumulant generating function.

4 References

Asmussen, Binswanger, and Højgaard. 2000. “Rare Events Simulation for Heavy-Tailed Distributions.” Bernoulli.

Asmussen, and Glynn. 2007. Stochastic Simulation: Algorithms and Analysis.

Asmussen, and Kroese. 2006. “Improved Algorithms for Rare Event Simulation with Heavy Tails.” Advances in Applied Probability.

Ben Rached, Botev, Kammoun, et al. 2018. “On the Sum of Order Statistics and Applications to Wireless Communication Systems Performances.” IEEE Transactions on Wireless Communications.

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

Botev, Zdravko I., and Kroese. 2008. “An Efficient Algorithm for Rare-Event Probability Estimation, Combinatorial Optimization, and Counting.” Methodology and Computing in Applied Probability.

———. 2012. “Efficient Monte Carlo Simulation via the Generalized Splitting Method.” Statistics and Computing.

Botev, Zdravko, and 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. VALUETOOLS’16.

Botev, Zdravko I., and L’Ecuyer. 2020. “Sampling Conditionally on a Rare Event via Generalized Splitting.” INFORMS Journal on Computing.

Botev, Zdravko I., L’Ecuyer, Rubino, et al. 2012. “Static Network Reliability Estimation via Generalized Splitting.” INFORMS Journal on Computing.

Botev, Zdravko I., L’Ecuyer, and Tuffin. 2013. “Markov Chain Importance Sampling with Applications to Rare Event Probability Estimation.” Statistics and Computing.

Botev, Zdravko I., Salomone, and MacKinlay. 2019. “Fast and Accurate Computation of the Distribution of Sums of Dependent Log-Normals.” Annals of Operations Research.

Bréhier, Goudenège, and Tudela. 2016. “Central Limit Theorem for Adaptive Multilevel Splitting Estimators in an Idealized Setting.” In Monte Carlo and Quasi-Monte Carlo Methods. Springer Proceedings in Mathematics & Statistics.

Cérou, Frédéric, Del Moral, Le Gland, et al. 2006. “Genetic Genealogical Models in Rare Event Analysis.” ALEA, Latin American Journal of Probability and Mathematical Statistics.

Cérou, Frédéric, and Guyader. 2007. “Adaptive Multilevel Splitting for Rare Event Analysis.” Stochastic Analysis and Applications.

Cérou, Frédéric, Le Gland, François, Del Moral, et al. 2005. “Limit Theorems for the Multilevel Splitting Algorithm in the Simulation of Rare Events.” In Proceedings of the Winter Simulation Conference, 2005.

Cérou, F., Moral, Furon, et al. 2011. “Sequential Monte Carlo for Rare Event Estimation.” Statistics and Computing.

Charles-Edouard, Maxime, Ludovic, et al. 2015. “Unbiasedness of Some Generalized Adaptive Multilevel Splitting Algorithms.” arXiv:1505.02674 [Math, Stat].

Dai, Heng, Jacob, et al. 2020. “An Invitation to Sequential Monte Carlo Samplers.” arXiv:2007.11936 [Stat].

Dean, and Dupuis. 2009. “Splitting for Rare Event Simulation: A Large Deviation Approach to Design and Analysis.” Stochastic Processes and Their Applications.

Del Moral, and Lezaud. 2006. “Branching and Interacting Particle Interpretations of Rare Event Probabilities.” In Stochastic Hybrid Systems. Lecture Notes in Control and Information Science, Volume 337.

Garvels, and Kroese. 1998. “A Comparison of RESTART Implementations.” In Proceedings of the 1998 Winter Simulation Conference.

Glasserman, P., Heidelberger, Shahabuddin, et al. 1998. “A Large Deviations Perspective on the Efficiency of Multilevel Splitting.” IEEE Transactions on Automatic Control.

Glasserman, Paul, Heidelberger, Shahabuddin, et al. 1998. “A Look At Multilevel Splitting.” In Monte Carlo and Quasi-Monte Carlo Methods 1996. Lecture Notes in Statistics.

Johansen, Del Moral, and Doucet. 2006. “Sequential Monte Carlo Samplers for Rare Events.” In Proceedings of the 6th International Workshop on Rare Event Simulation.

L’Ecuyer, Blanchet, Tuffin, et al. 2010. “Asymptotic Robustness of Estimators in Rare-Event Simulation.” ACM Transactions on Modeling and Computer Simulation.

L’Ecuyer, Demers, and Tuffin. 2006. “Splitting for Rare-Event Simulation.” In 38th Conference on Winter Simulation. WSC ’06.

———. 2007. “Rare Events, Splitting, and Quasi-Monte Carlo.” ACM Transactions on Modeling and Computer Simulation (TOMACS).

L’Ecuyer, Le Gland, Lezaud, et al. 2009. “Splitting Techniques.” In Rare Event Simulation Using Monte Carlo Methods.

Li, Duan, and Liu. 2021. “Machine Learning Framework for Computing the Most Probable Paths of Stochastic Dynamical Systems.” Physical Review E.

Rubino, and Tuffin, eds. 2009. Rare Event Simulation Using Monte Carlo Methods.

Rubinstein, and Kroese. 2016. Simulation and the Monte Carlo Method. Wiley series in probability and statistics.

Shahabuddin. 1994. “Importance Sampling for the Simulation of Highly Reliable Markovian Systems.” Management Science.

Touchette. 2011. “A Basic Introduction to Large Deviations: Theory, Applications, Simulations.”

Villén-Altamirano, and 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. Lecture Notes in Computer Science.