What is importance sampling, and how does it work?

In this article

1. Before you start
2. Why interviewers ask this
3. Importance sampling from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the statistics and probability learning path.

Why interviewers ask this

A candidate who says "just sample more" for a rare event has missed that the cost can be astronomical, and importance sampling is the standard answer to that cost. It comes up in probability and machine learning rounds that touch rare events, off-policy reinforcement learning or approximate inference, and it is a compact test of whether you understand unbiased estimation and variance.

A weak answer says "you sample from a different distribution and reweight." A strong answer writes the weight, says why the estimate stays unbiased, says what the best proposal looks like, and names the failure: a proposal with lighter tails than the target can give infinite variance. A Staff-level answer adds the diagnostic, the effective sample size, and connects it to the ratio inside the Proximal Policy Optimization (PPO) objective. Our probability interview questions page lists neighbouring questions.

Importance sampling from first principles

Importance sampling

Importance sampling is a Monte Carlo technique that estimates the expected value of a function under a target distribution p by drawing samples from a different distribution q and multiplying each sample's value by the weight p divided by q, which corrects for having sampled from the wrong distribution.

Importance weight

An importance weight is the ratio w(x) = p(x) / q(x) attached to a sample x drawn from q. It is large where q undersamples the target and small where q oversamples it, so the weighted average has the same expected value as an average over p.

Effective sample size

The effective sample size is the number of equally weighted samples that would be worth the same as a weighted set. It equals the squared sum of the weights divided by the sum of the squared weights, and it drops when a few samples carry most of the weight.

In plain words

You want to know how often a huge storm floods a town. Such storms are rare in your records. So you use a simulation that makes huge storms common. Then you shrink each simulated flood. If the simulation makes a storm 50 times more often than reality does, each simulated flood from that storm counts as one fiftieth of a real flood (illustrative). The analogy breaks here: the shrink factor must be exact. The simulation must also be able to produce every storm that matters.

In one precise sentence, importance sampling replaces an average over p with an average over q by multiplying each term by p over q. Owen puts the recipe as getting more samples in "the important region" and then correcting for that distortion (Owen, lecture slides, 2018, slide 3).

Step 1: Pick a proposal and draw samples from it

The target is the expected value of a function f under a density p, written as the integral of f times p. The proposal q is any density you can sample from. Owen's rule is to choose q with q(x) greater than zero whenever f(x) times p(x) is not zero (Owen, 2018, slide 6).

Input: the target p, the function f and a candidate q. Output: samples x₁ to xₙ drawn from q, not from p. In the tail example below, f is the indicator that a standard normal value is at least 4, which is almost never true under p, so q is a normal centered at 4, where the indicator is true about half the time. You now know where the samples come from; the next step repairs what that choice distorted.

Step 2: Weight each sample by p over q and average

Each sample x gets the importance weight w(x) = p(x) / q(x), and the estimate is the average of f(x) times w(x) over the samples:

This estimator is unbiased: its expected value under q is the integral of f times p, which is the quantity you wanted, as long as the support condition of step 1 holds (Owen, 2018, slide 6). Without the weights the estimate is biased, because you would be averaging over q.

The weights cancel q inside the integral, which is why the estimate is unbiased:

The random error depends on the second moment of the weighted values:

If q is much smaller than p where f is nonzero, p²/q blows up, which is the light-tail failure of step 3. Elvira et al. (2018) describe the weight as the correction for the mismatch between the proposal and the target.

Input: samples and two density formulas. Output: one number. The estimate is now correct on average; step 3 asks whether it is correct on this run.

Step 3: Check the effective sample size and the tails

The effective sample size, n_e, is the squared sum of the weights divided by the sum of the squared weights, and it always lies between 1 and n (Owen, 2018, slide 10):

If all weights are equal, n_e equals n; if only one weight is positive, n_e is 1. Both cases follow directly from the formula. With 5 weights equal to 1 and 95 equal to 0 (illustrative), n_e is 5.¹ Owen's project-scheduling example shows the damage: with 10,000 samples a naive proposal gave n_e of about 4.9, and one observation held 43% of the weight (Owen, 2018, slides 19-21).

The cause is usually the tails. The proposal needs heavier tails than the target: a normal target with a Student t proposal is fine, the reverse is problematic (Owen, 2018, slide 11). Check n_e, not n.

Step 4: Choose a proposal that leaves few surprises

The best proposal is proportional to the absolute value of f times p; for a nonnegative f that proposal gives zero variance (Owen, 2018, slide 7). You cannot use it directly, because normalizing it requires the very integral you are estimating. The practical aim is a q roughly proportional to f times p. Give it tails at least as heavy as p's.

A defensive mixture is a proposal that mixes the target p itself into q with a fixed fraction, which bounds every weight by one over that fraction (Owen, 2018, slide 31). It sacrifices some efficiency for protection against surprises.

Why a slightly wrong proposal fails in high dimensions

In high dimensions the sample size needed grows roughly like the exponential of the Kullback–Leibler (KL) divergence between p and q for a generic f, so a proposal that is a little off in many dimensions can be catastrophic (Owen, 2018, slide 8). You now have the whole method: choose q, draw, weight, then check.

1 · Pick a proposal2 · Draw samples3 · Weight and average4 · Check the sizeReplay

Step-by-step description

1. Choose q with tails at least as heavy as p.
2. Draw x from q so the rare region is hit.
3. Multiply each value by p over q.
4. Effective sample size shows if few weights dominate.

• Samples are drawn from the proposal q, not from the target p.
• Each sample is multiplied by the weight p divided by q.
• The effective sample size says how many equal-weight samples the weighted set is worth.

The diagram repeats the order of the steps. Samples are drawn from the proposal q, not from the target p. Each sample is multiplied by the weight p divided by q. The effective sample size says how many equal-weight samples the weighted set is worth.

Worked example

The task is to estimate the probability that a standard normal value Z is at least 4. The exact value is about 3.17 × 10⁻⁵.¹ With plain Monte Carlo and 10,000 samples you expect 0.317 hits, so most runs see none.¹

Owen's rare-event analysis explains the cost. For an event of probability ε, the coefficient of variation of plain Monte Carlo is about the square root of one over n times ε, so a coefficient of variation of 0.1 needs n of about 100 over ε; at ε of 10⁻⁹ that is about 10¹¹ samples (Owen, 2018, slide 4). For this tail that rule gives about 3.16 million samples.¹

Now use the proposal q, a normal centered at 4 with spread 1. The weight for a mean shift of θ is exp(−θx + θ²/2) (Owen, 2018, slide 11), which for θ = 4 is exp(−4x + 8). Half the draws land at or above 4, and each hit is multiplied by its weight.¹

All values above are computed.¹ A standard error is the typical size of the random error of an estimate, here the spread of the estimate across repeated runs. At 10,000 samples the standard error is 56.3 per million for plain sampling and 0.67 per million for importance sampling, against an answer of 31.7 per million.¹

Text description of the diagram

• Standard error is 56.3 per million for plain sampling and 0.67 per million for importance sampling.
• The exact probability is about 31.7 per million.

Now the bad proposal: a normal centered at 0 with spread 0.5. Its draws reach 4 with probability about 6.2 × 10⁻¹⁶, so the estimate is almost surely exactly zero, and in the variance formula of step 2 the term p²/q is proportional to exp(x²) in the tail for q = N(0, 0.5²), so the variance is infinite.¹ This is the light-tail failure of step 3.

Owen's scheduling example shows the same lesson on a real model. Plain sampling saw the event 2 times in 10,000 runs; tilting only the 4 critical-path tasks (200,000 runs) reduced variance by about 1,200, with n_e of about 7,470 (Owen, 2018, slides 19-21).

Trade-offs and edge cases

Importance sampling can be far better or far worse than plain sampling. Owen says it can turn an intractable problem into an easy one, and also give infinite variance (Owen, 2018, slide 2); his book calls the method much harder to use than other variance reduction methods (Owen, book chapter 1).

Self-normalized importance sampling is the estimator that divides the weighted sum of f values by the sum of the weights, so it works when p or q is known only up to a constant. It has a small bias that vanishes as the sample grows (Owen, 2018, slide 12). It needs q greater than zero wherever p is greater than zero, even where f is zero (Owen, 2018, slide 12). It cannot approach zero variance; its optimal proposal puts about half its probability inside a rare event, whereas the ordinary estimator's optimum puts all of it there (Owen, book chapter 9).

Text description of the diagram

• Ordinary importance sampling is unbiased; the self-normalized version has a small bias that vanishes as samples grow.
• The optimal self-normalized proposal puts half its probability in the rare event, and the ordinary one puts all of it.

Ordinary importance sampling is unbiased; the self-normalized version has a small bias that vanishes as samples grow. The optimal self-normalized proposal puts half its probability in the rare event, and the ordinary one puts all of it.

Rejection sampling is a different tool: it needs a known bound on p over q and wastes rejected draws, while importance sampling keeps every draw and tracks weights (Owen, 2018, slide 15); see rejection sampling.

The same weight appears in reinforcement learning. A policy is the rule that picks an action given a state. PPO collects data with an old policy and reuses it for several update steps, so it multiplies the advantage by the ratio of new to old action probability (Schulman et al., 2017, §3). That ratio is commonly described as an importance weight (Garg et al., 2021). Without a constraint, maximizing it "would lead to an excessively large policy update" (Schulman et al., 2017, §3). Clipping is cutting a quantity to a fixed range, and PPO clips the ratio to between 1 minus ε and 1 plus ε, with ε of 0.2 as the paper's example.

Values follow from the formula of the paper by arithmetic.¹ Clipping buys lower variance at the price of bias, because it cuts off large weights. Lambert's book on reinforcement learning from human feedback has sections on clipped importance sampling policy optimization (§6.2.10) and truncated importance sampling (§6.3.4) (Lambert, 2026). In asynchronous training systems the policy that generated a sample can lag the policy being trained, which is another place an importance weight appears.

How to answer it in an interview

The spoken structure: say the estimator, say why it is unbiased, give the rare-event use, then name the tail failure and the diagnostic.

Common mistakes

• "Importance sampling always reduces variance." (wrong) A poor proposal can give infinite variance. (right) "It reduces variance only when q is close to proportional to f times p and has heavy enough tails."
• "You just sample from the important region." (wrong) Without the p over q weights the estimate is biased. (right) "I sample from q and reweight, so the expectation matches p."
• "The estimate is biased because you sample from the wrong distribution." (wrong) The ordinary estimator is exactly unbiased under the support condition. (right) "Only the self-normalized version has a small bias, and it vanishes with more samples."
• "More samples fix a bad proposal." (wrong) The sample size needed can grow roughly with the exponential of the KL divergence, and the effective sample size can stay tiny. (right) "I look at n_e and improve q."
• "The best q is p." (wrong) The best q is proportional to the absolute value of f times p. (right) "I put mass where the integrand is large."

Follow-up questions

Where does importance sampling appear in RLHF?

In reinforcement learning from human feedback (RLHF), the reinforcement learning stage samples text from the language model and scores it with a reward model (Lambert, 2026). Policy-gradient updates such as PPO reuse those samples with the ratio of new to old policy probability, which is an importance weight, and clipping limits its effect.

Is the importance sampling ratio the policy ratio or the likelihood ratio?

Both names describe the same quantity in this setting: the new policy's probability of an action divided by the old policy's. The page on the importance sampling ratio covers the wording.

How is importance sampling different from rejection sampling?

Accepted rejection samples are exact draws from p, so they need no weights, whereas importance samples stay draws from q and always carry weights. The price of rejection sampling is a known bound on p over q and the discarded draws.

What happens if the proposal has lighter tails than the target?

The weights are unbounded in the tail, the variance can be infinite, and the effective sample size collapses; a heavier-tailed or defensive-mixture proposal avoids it.

When do you use self-normalized importance sampling?

Use it when p or q is known only up to a constant, accepting a small bias that vanishes as samples grow. Self-normalization also arises in Bayesian computation, where a posterior is known only up to a constant; see Bayes theorem interview questions.

Sources

1. Monte Carlo: Importance sampling (lecture slides, Art B. Owen) — Stanford University, LMS/CRiSM Summer School, University of Warwick, 1 Jan 2018
2. Monte Carlo theory, methods and examples, Chapter 1: Introduction — Art B. Owen, Stanford University (book draft), 1 Jan 2013
3. Monte Carlo theory, methods and examples, Chapter 9: Importance sampling — Art B. Owen, Stanford University (book draft), 1 Jan 2013
4. Proximal Policy Optimization Algorithms (arXiv 1707.06347) — arXiv (Schulman et al., OpenAI), 28 Aug 2017
5. Reinforcement Learning from Human Feedback (arXiv 2504.12501) — arXiv (Nathan Lambert), 11 Sep 2026
6. On Proximal Policy Optimization's Heavy-tailed Gradients — ICML 2021 (Garg et al.), 1 Jan 2021
7. Rethinking the Effective Sample Size (arXiv 1809.04129) — arXiv (Elvira, Martino, Robert), 1 Jan 2018