Large deviations for weighted empirical measures arising in importance sampling

DOI10.1016/J.SPA.2015.08.002MaRDI QIDQ898403zbMATH OpenOpenAlexWikidataFDO

Authors Henrik Hult, Pierre Nyquist

Publication date 8 December 2015

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.2251

zbMATH Keywords

importance samplinglarge deviationsMonte Carlo methodempirical measures

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Large deviations (60F10) Random measures (60G57)

Abstract: Importance sampling is a popular method for efficient computation of various properties of a distribution such as probabilities, expectations, quantiles etc. The output of an importance sampling algorithm can be represented as a weighted empirical measure, where the weights are given by the likelihood ratio between the original distribution and the sampling distribution. In this paper the efficiency of an importance sampling algorithm is studied by means of large deviations for the weighted empirical measure. The main result, which is stated as a Laplace principle for the weighted empirical measure arising in importance sampling, can be viewed as a weighted version of Sanov's theorem. The main theorem is applied to quantify the performance of an importance sampling algorithm over a collection of subsets of a given target set as well as quantile estimates. The analysis yields an estimate of the sample size needed to reach a desired precision as well as of the reduction in cost for importance sampling compared to standard Monte Carlo.

Recommendations

• Efficient large deviation estimation based on importance sampling
• On large deviations theory and asymptotically efficient Monte Carlo estimation
• On Monte Carlo estimation of large deviations probabilities
• Counterexamples in importance sampling for large deviations probabilities
• Asymptotically efficient importance sampling for bootstrap

Cites work

• scientific article; zbMATH DE number 1153603 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• Analysis of an interacting particle method for rare event estimation
• Confidence intervals for quantiles when applying variance-reduction techniques
• Genealogical particle analysis of rare events
• Importance Sampling, Large Deviations, and Differential Games
• Large deviations for bootstrapped empirical measures
• Monte Carlo methods for value-at-risk and conditional value-at-risk: a review
• Rare Event Simulation using Monte Carlo Methods
• Splitting for rare event simulation: A large deviation approach to design and analysis
• Stochastic simulation: Algorithms and analysis
• Subsolutions of an Isaacs Equation and Efficient Schemes for Importance Sampling

Cited in

(8)

• Large deviations for bootstrapped empirical measures
• Importance Sampling and Necessary Sample Size: An Information Theory Approach
• Asymptotically efficient importance sampling for bootstrap
• Moderate deviation principles for importance sampling estimators of risk measures
• HEAVY TAILS, IMPORTANCE SAMPLING AND CROSS–ENTROPY
• Efficient large deviation estimation based on importance sampling
• Counterexamples in importance sampling for large deviations probabilities
• The sample size required in importance sampling

This page was built for publication: Large deviations for weighted empirical measures arising in importance sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898403)