On asymptotically efficient simulation of large deviation probabilities

A. B. Dieker, Michel Mandjes

Type: Article

Publication Date: 2005-06-01

Citations: 35

DOI: https://doi.org/10.1239/aap/1118858638

Abstract

Let {ν ε , ε>0} be a family of probabilities for which the decay is governed by a large deviation principle, and consider the simulation of ν ε 0 ( A ) for some fixed measurable set A and some ε 0 >0. We investigate the circumstances under which an exponentially twisted importance sampling distribution yields an asymptotically efficient estimator. Varadhan's lemma yields necessary and sufficient conditions, and these are shown to improve on certain conditions of Sadowsky. This is illustrated by an example to which Sadowsky's conditions do not apply, yet for which an efficient twist exists.

Locations

Advances in Applied Probability - View - PDF
CWI's Institutional Repository (Centrum Wiskunde & Informatica) - View - PDF
Data Archiving and Networked Services (DANS) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	On asymptotically efficient simulation of large deviation probabilities	2005	A. B. Dieker Michel Mandjes
+ PDF Chat	Large deviations theory techniques in Monte Carlo simulation	1989	J.S. Sadowsky J.A. Bucklew
+	Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains	1990	J.A. Bucklew Peter Ney J.S. Sadowsky
+	Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains	1990	J.A. Bucklew Peter Ney J.S. Sadowsky
+	On Monte Carlo estimation of large deviations probabilities	1996	J.S. Sadowsky
+	Efficient Simulation for Large Deviation Probabilities of Sums of Heavy-Tailed Increments	2006	José Blanchet Jingchen Liu
+ PDF Chat	Efficient Large Deviation Estimation Based on Importance Sampling	2020	Arnaud Guyader Hugo Touchette
+	State-independent Importance Sampling for Estimating Large Deviation Probabilities in Heavy-tailed Random Walks	2012	A. M. Karthyek Rajhaa Sandeep Juneja
+	Importance Sampling for Simulation of Large and Moderate Deviation Probabilities of Tests and Estimators	2007	Mikhail Ermakov
+	Efficient simulation for large deviation probabilities of sums of heavy-tailed increments	2006	José Blanchet Jingchen Liu
+ PDF Chat	Efficient estimation of density and probability of large deviations of sum of IID random variables	2011	Santanu S. Dey Sandeep Juneja
+	Efficient estimation of density and probability of large deviations of sum of IID random variables	2011	Santanu S. Dey Sandeep Juneja
+	On Efficiency of Multilevel Splitting	2012	D.I. Miretskiy Werner Scheinhardt Michel Mandjes
+	Large Deviation Theory	2004	J.A. Bucklew
+ PDF Chat	Adaptive Sampling of Large Deviations	2018	Grégoire Ferré Hugo Touchette
+	On asymptotically efficient simulation of ruin probabilities in a Markovian environment	1992	Tapani Lehtonen Harri Nyrhinen
+	Efficient Rare-event Simulation for Perpetuities	2012	José Blanchet Henry Lam Bert Zwart
+	Efficient Rare-event Simulation for Perpetuities	2012	José Blanchet Henry Lam Bert Zwart
+	Efficient importance sampling for events of moderate deviations with applications	2004	Cheng–Der Fuh
+	On the optimality and stability of exponential twisting in Monte Carlo estimation	1993	J.S. Sadowsky

Works That Cite This (26)

Action	Title	Year	Authors
+ PDF Chat	Rare-event Simulation for Neural Network and Random Forest Predictors	2022	Yuanlu Bai Zhiyuan Huang Henry Lam Ding Zhao
+	State-independent Importance Sampling for Random Walks with Regularly Varying Increments	2014	Karthyek Murthy Sandeep Juneja José Blanchet
+ PDF Chat	Large deviation theory for a homogenized and “corrected” elliptic ODE	2011	Guillaume Bal Roger Ghanem Ian Langmore
+ PDF Chat	A survey of rare event simulation methods for static input–output models	2014	Jérôme Morio Mathieu Balesdent Damien Jacquemart Christelle Vergé
+ PDF Chat	Excessive backlog probabilities of two parallel queues	2019	Kamil Demirberk Ünlü Ali Devin Sezer
+ PDF Chat	Efficient Simulation of Large Deviation Events for Sums of Random Vectors Using Saddle-Point Representations	2013	Ankush Agarwal Santanu S. Dey Sandeep Juneja
+	Efficient Simulation of Random Walks Exceeding a Nonlinear Boundary	2006	A. B. Dieker Michel Mandjes
+	Efficient simulation for large deviation probabilities of sums of heavy-tailed increments	2006	José Blanchet Jingchen Liu
+	Efficient estimation of density and probability of large deviations of sum of IID random variables	2011	Santanu S. Dey Sandeep Juneja
+ PDF Chat	Adaptive Importance Sampling for Efficient Stochastic Root Finding and Quantile Estimation	2023	Shengyi He Guangxin Jiang Henry Lam Michael C. Fu

Works Cited by This (18)

Action	Title	Year	Authors
+	Large deviations for stochastic processes	2006	Jin Feng Thomas G. Kurtz
+ PDF Chat	Importance Sampling in the Monte Carlo Study of Sequential Tests	1976	David Siegmund
+	Large deviations for vector-valued Lévy processes	1994	A. de Acosta
+	Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains	1990	J.A. Bucklew Peter Ney J.S. Sadowsky
+	Importance Sampling, Large Deviations, and Differential Games	2004	Paul Dupuis Hui Wang
+ PDF Chat	Large Deviations for Exchangeable Random Vectors	1992	I. H. Dinwoodie Sandy L. Zabell
+	On Monte Carlo estimation of large deviations probabilities	1996	J.S. Sadowsky
+ PDF Chat	Importance Sampling Techniques for the Multidimensional Ruin Problem for General Markov Additive Sequences of Random Vectors	2002	Jeffrey F. Collamore
+	Large deviations and fast simulation in the presence of boundaries	2002	Søren Asmussen Pascal Fuckerieder Manfred Jobmann Hans-Peter Schwefel
+ PDF Chat	Counterexamples in importance sampling for large deviations probabilities	1997	Paul Glasserman Yashan Wang