Direct simulation of an event with probability 1/1024 spends almost every draw learning nothing. Importance sampling draws from a different distribution q under which the event is common and weights each draw by the likelihood ratio p/q, which keeps the estimator unbiased. The whole question is what the reweighting does to the variance: a good q divides it by about 123, a bad one multiplies it by about 9546, and a q with a hole where the event lives gives no estimator at all.
Core ideas
Three ideas. The first is the identity, the second is the condition that decides whether there is an estimator at all, and the third is where all the risk in the method is concentrated.
E_p[h] = Σ h(x)p(x) = Σ h(x)(p(x)/q(x))q(x) = E_q[h·p/q], which is multiplying and dividing by the same thing. So the reweighted estimator is unbiased for the same number as the direct one, exactly, for every valid q. The estimate is not where the difference between a good q and a bad one lives.
q must put positive mass everywhere p·h does. If it does not, the likelihood ratio is undefined exactly where the event lives, and an implementation that quietly skips that outcome returns a number that is biased low with nothing on the page to reveal it. There is no partial credit: either the identity holds or there is no estimator.
A draw that misses the event contributes nothing whatever its weight; a draw that hits contributes its whole weight. So the variance is decided by how large the weight is on the outcomes that matter, and a q that makes the event rarer makes that weight enormous. The method can therefore be catastrophically worse than doing nothing, with no symptom except the variance figure.
The material
The identity that makes the reweighting legitimate, the condition it needs, and the three orders of magnitude between a good choice and a bad one.
Direct simulation of a rare event is an arithmetic problem before it is anything else. To see an event of probability 1/1024 even ten times takes about ten thousand draws, and to estimate it to within ten per cent takes on the order of a hundred thousand. Nine hundred and ninety-nine draws in a thousand return a zero and teach nothing, and the arithmetic gets worse in exact proportion as the event gets more interesting.
To estimate E_p[h(X)], draw X₁, …, Xₙ from a different distribution q and report the average of h(Xᵢ)·p(Xᵢ)/q(Xᵢ). The factor p/q is the likelihood ratio or importance weight. q is the proposal.
If q(x) > 0 whenever p(x)h(x) ≠ 0, then E_q[h(X)p(X)/q(X)] = E_p[h(X)]. The estimator is therefore unbiased for the same quantity as direct simulation, for every proposal satisfying that condition and for no other.
E_q[h·p/q] = Σ_x q(x)·h(x)p(x)/q(x), summed over the x with q(x) > 0.
The q(x) cancels, leaving Σ h(x)p(x) over those same x. By the support condition every x with h(x)p(x) ≠ 0 is among them, so the sum is Σ_x h(x)p(x) = E_p[h].
The cancellation is also the proof that the condition cannot be relaxed: an x with p(x)h(x) ≠ 0 and q(x) = 0 is a term present in the target sum and absent from the reweighted one, so the estimator is short by exactly that term.
□
The event on this page is ten fair coins all landing heads. Its probability under p is exactly 1/1024, which is what makes the comparison a measurement rather than a demonstration: both estimators are aiming at a number already known, so any difference between them must be variance. Direct sampling has per-draw variance p(1 − p) = 1023/1048576.
Take q to be ten coins with P(head) = 4/5. Under q the event has probability 1048576/9765625, about 0.1074 — roughly one draw in nine rather than one in a thousand — and the weight on it is 9765625/1073741824, about 0.0091. The per-draw variance becomes 8717049/1099511627776, about 0.0000079, which is the original variance divided by 32505856/264153 ≈ 123.0569.
Take P(head) = 1/5 instead. The event now has probability 1/9765625 under q — about a hundred times rarer than it already was — and the weight on it is 9765625/1024, about 9537. One draw in ten million contributes nine thousand five hundred, and the per-draw variance is 1220703/131072, about 9.31: the original variance multiplied by 295928/31 ≈ 9546.0645.
Two thousand draws under the good proposal hit the event two hundred and fifteen times and estimate 0.00097771 against the exact 0.00097656. Two thousand draws under the fair coin hit it once and estimate 1/2000 = 0.0005. Two thousand draws under the bad proposal hit it not at all and estimate exactly 0 — not near the answer, at zero, with a perfectly ordinary-looking trace and nothing on the page to suggest anything went wrong except the variance figure.
That is the failure this lesson leads with. A bad proposal looks fine on a short run because all of the damage is in the spread and none of it is in the picture: the estimate is stable at zero, the running average is a flat line, and the estimator is still unbiased. What is wrong is that one draw in ten million would have carried the entire estimate, and this run did not get it.
Take the good proposal and remove its mass on ten heads, redistributing it over the other outcomes. The result is a genuine probability distribution — its entries are positive where they are present and they sum to 1 — and the panel refuses it. p puts 1/1024 on the event and q puts nothing there, so the likelihood ratio is undefined exactly where the estimator needs it.
The refusal is the interesting behaviour. An implementation that skipped the undefined outcome would return a number, and the number would be biased low by precisely the term it dropped — which here is the whole of the answer, so it would return zero, every time, with a variance of zero to go with it. A confident, reproducible, perfectly stable wrong answer is the worst thing a simulation can produce, and the only defence is a support check that refuses rather than degrades.
Note what the condition is not about. It is not about q being close to p, and it is not about making the event common; those decide the variance, which is a question of how good the estimator is. The support condition decides whether there is an estimator, which is a prior question with a yes-or-no answer.
Interactive
Sample where the event is, weight each draw by p/q, and watch what happens to the variance
Method
Five steps, and the third is the one that separates a hard problem from an impossible report.
To see an event of probability θ about m times takes roughly m/θ draws. At θ = 1/1024 and m = 10 that is ten thousand; at θ = 10⁻⁶ it is ten million, and the arithmetic decides the question before any cleverness is needed.
Tilting a parameter — a coin's bias, an arrival rate, a service time — is the usual move. The proposal has to be something you can both sample from and evaluate, because the weight needs q(x) for every drawn x.
q(x) > 0 wherever p(x)h(x) ≠ 0. This is a yes-or-no question about the two distributions and it is answered before a single draw is taken. A proposal that fails it is not a worse estimator; it is not an estimator.
A draw that misses the event contributes 0 × weight = 0, and it still counts in the denominator. Averaging only the hits estimates a conditional expectation, which is a different and much larger number.
Both estimators are unbiased, so the estimates will be near each other when both are working and the comparison tells you nothing. The per-draw variance under p against the per-draw variance under q is the entire result, and a proposal whose ratio is below one has made the problem worse.
The event is ten fair coins all landing heads. Its probability is exactly 1/1024, so nothing below is an approximation of an unknown: every figure is a fraction, and the two estimators are being compared on a quantity they both already agree about.
The fair-coin row is worth keeping because it shows the method contains direct simulation as a special case: set q = p, every weight is exactly 1, and the ratio of variances is exactly 1. Importance sampling is not a different estimator, it is the same estimator with a parameter, and the parameter is the proposal.
The bad row is the one to be frightened of. Its estimate is 0 and its trace is a flat line at zero, which is the most stable-looking output on the page, and the estimator is still unbiased: in expectation, over enough runs, those one-in-ten-million draws carrying a weight of nine thousand five hundred would bring the average back to 1/1024. The expectation is right and no run will ever show it.
For a faded rehearsal, drag the draw count from 2000 to 4000 under the bad proposal. The supplied first move is that the per-draw variance does not change at all — it is a property of p, q and the event, not of the run — so the variance of the average falls by exactly half. Say how many draws it would take for that average to have a standard error smaller than 1/1024 itself, and then say what that number means about the proposal.
You should be able to derive the reweighting identity and see in the derivation why the support condition cannot be relaxed, choose a tilted proposal for a rare event and compute its likelihood ratios, state the per-draw variance under both the target and the proposal as exact fractions and divide them, recognise a zero-hit run as a variance symptom rather than as convergence, and refuse a proposal with a hole in its support rather than patching it.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.