  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.

Probability