Large deviations for weighted empirical measures arising in importance sampling

H. Hult, P. Nyquist

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

Abstract

In this paper the efficiency of an importance sampling algorithm is studied by means of large deviations for the associated weighted empirical measure. The main result, stated as a Laplace principle for these weighted empirical measures, can be viewed as an extension of Sanov's theorem. The main theorem is used 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 and of the reduction in cost compared to standard Monte Carlo.

Original languageEnglish
Pages (from-to)138-170
Number of pages33
JournalStochastic Processes and their Applications
Volume126
Issue number1
DOIs
Publication statusPublished - 1 Jan 2016
Externally publishedYes

Fingerprint

Empirical Measures
Importance sampling
Importance Sampling
Large Deviations
Sanov's Theorem
Quantile
Set theory
Laplace
Estimate
Sample Size
Quantify
Target
Subset
Costs
Theorem
Standards

Keywords

  • 65C05
  • 68U20
  • MSC primary 60F10
  • secondary 60G57

Cite this

@article{88bd4ca33af04f288190e5694120f244,
title = "Large deviations for weighted empirical measures arising in importance sampling",
abstract = "In this paper the efficiency of an importance sampling algorithm is studied by means of large deviations for the associated weighted empirical measure. The main result, stated as a Laplace principle for these weighted empirical measures, can be viewed as an extension of Sanov's theorem. The main theorem is used 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 and of the reduction in cost compared to standard Monte Carlo.",
keywords = "65C05, 68U20, MSC primary 60F10, secondary 60G57",
author = "H. Hult and P. Nyquist",
year = "2016",
month = "1",
day = "1",
doi = "10.1016/j.spa.2015.08.002",
language = "English",
volume = "126",
pages = "138--170",
journal = "Stochastic Processes and their Applications",
issn = "0304-4149",
publisher = "Elsevier",
number = "1",

}

Large deviations for weighted empirical measures arising in importance sampling. / Hult, H.; Nyquist, P.

In: Stochastic Processes and their Applications, Vol. 126, No. 1, 01.01.2016, p. 138-170.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Large deviations for weighted empirical measures arising in importance sampling

AU - Hult, H.

AU - Nyquist, P.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - In this paper the efficiency of an importance sampling algorithm is studied by means of large deviations for the associated weighted empirical measure. The main result, stated as a Laplace principle for these weighted empirical measures, can be viewed as an extension of Sanov's theorem. The main theorem is used 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 and of the reduction in cost compared to standard Monte Carlo.

AB - In this paper the efficiency of an importance sampling algorithm is studied by means of large deviations for the associated weighted empirical measure. The main result, stated as a Laplace principle for these weighted empirical measures, can be viewed as an extension of Sanov's theorem. The main theorem is used 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 and of the reduction in cost compared to standard Monte Carlo.

KW - 65C05

KW - 68U20

KW - MSC primary 60F10

KW - secondary 60G57

UR - http://www.scopus.com/inward/record.url?scp=84948440031&partnerID=8YFLogxK

U2 - 10.1016/j.spa.2015.08.002

DO - 10.1016/j.spa.2015.08.002

M3 - Article

AN - SCOPUS:84948440031

VL - 126

SP - 138

EP - 170

JO - Stochastic Processes and their Applications

JF - Stochastic Processes and their Applications

SN - 0304-4149

IS - 1

ER -