NDLI: On Lyapunov Inequalities and Subsolutions for Efficient Importance Sampling

Content Provider	ACM Digital Library
Author	Blanchet, Jose Glynn, Peter Leder, Kevin
Copyright Year	2012
Abstract	In this article we explain some connections between Lyapunov methods and subsolutions of an associated Isaacs equation for the design of efficient importance sampling schemes. As we shall see, subsolutions can be derived by taking an appropriate limit of an associated Lyapunov inequality. They have been recently proposed in several works of Dupuis, Wang, and others and applied to address several important problems in rare-event simulation. Lyapunov inequalities have been used for testing the efficiency of state-dependent importance sampling schemes in heavy-tailed or discrete settings in a variety of works by Blanchet, Glynn, and others. While subsolutions provide an analytic criterion for the construction of efficient samplers, Lyapunov inequalities are useful for finding more precise information, in the form of bounds, for the behavior of the coefficient of variation of the associated importance sampling estimator in the prelimit. In addition, Lyapunov inequalities provide insight into the various mollification procedures that are often required in constructing associated subsolutions. Our aim is to demonstrate that applying Lyapunov inequalities for verification of efficiency can help both guide the selection of various mollification parameters and sharpen the information on the efficiency gain induced by the sampler.
Starting Page	1
Ending Page	27
Page Count	27
File Format	PDF
ISSN	10493301
e-ISSN	15581195
DOI	10.1145/2331140.2331141
Volume Number	22
Issue Number	3
Journal	ACM Transactions on Modeling and Computer Simulation (TOMACS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-08-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Importance sampling Isaacs equation Lyapunov inequalities Rare events Variance reduction
Content Type	Text
Resource Type	Article
Subject	Computer Science Applications Modeling and Simulation

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient rare event simulation for heavy-tailed compound sums

Estimating small cell-loss ratios in ATM switches via importance sampling

Fast simulation of rare events in queueing and reliability models

Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks

On lyapunov inequalities and subsolutions for efficient importance sampling (2010)

Combining importance sampling and temporal difference control variates to simulate Markov Chains

Importance sampling for sums of random variables with regularly varying tails

Efficient simulation of buffer overflow probabilities in jackson networks with feedback

Rare events, splitting, and quasi-Monte Carlo

On Lyapunov Inequalities and Subsolutions for Efficient Importance Sampling

Similar Documents

Efficient rare event simulation for heavy-tailed compound sums

Estimating small cell-loss ratios in ATM switches via importance sampling

Fast simulation of rare events in queueing and reliability models

Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks

On lyapunov inequalities and subsolutions for efficient importance sampling (2010)

Combining importance sampling and temporal difference control variates to simulate Markov Chains

Importance sampling for sums of random variables with regularly varying tails

Efficient simulation of buffer overflow probabilities in jackson networks with feedback

Rare events, splitting, and quasi-Monte Carlo

On Lyapunov Inequalities and Subsolutions for Efficient Importance Sampling