You must average a quantity over a distribution p you cannot easily draw from. So draw from an easy distribution q instead — and pay for the lie with a weight w(x)=p(x)/q(x). The corrected average is still exactly Ep[f]: the reweighting is unbiased by an algebraic identity, not by luck. Pick q well and the variance collapses to zero; pick it with a thin tail where p·f is heavy and it explodes. The blue team builds and proves the estimator; the red team drops the weight and watches it drift.
source H. Kahn & T. E. Harris, Estimation of Particle Transmission by Random Sampling, Nat. Bur. Standards Appl. Math. Ser. 12 (1951), pp. 27–30 — no stable open link, cited by author/title/year AMBER. Rendered, not quoted.
The whole trick is one line of algebra. Sample x ~ q, but score each sample by w(x)=p(x)/q(x):
Eq[ f(x)·p(x)/q(x) ] = Σx q(x)·f(x)·p(x)/q(x) = Σx p(x)·f(x) = Ep[f]. The q cancels — exactly, for any valid q. That makes the estimator unbiased.
Live for the chosen proposal: state, target p, proposal q, weight w=p/q, payoff f.
| x | p(x) | q(x) | w=p/q | f(x) |
|---|
Sample from the wrong distribution, then correct with a ratio. That single move is the engine under the policy gradient's off-policy correction — data gathered by a behaviour policy q, reweighted by π(a)/q(a) to estimate the return under the target policy p.
Same identity, different names: reward-weighted regression, self-normalized off-policy value, every clipped ratio in PPO. Each sphere is the next one's premise.
The blue team's live check: recompute the population estimator Σ q·f·(p/q) and confirm it equals the known truth Ep[f] = 3.2. If red drops the weight, this badge is where it shows.
Three discrete ingredients over states x ∈ {0,1,2,3,4}:
| meaning | values | |
|---|---|---|
| p | the target — hard to draw from | .1 .2 .3 .2 .2 |
| q | the proposal — easy to draw from | chosen below |
| f | the payoff f(x) | 1 2 3 4 5 |
The goal is Ep[f] = Σ p(x)f(x) = 3.2 — computed here as ground truth, then re-estimated below using samples from q with the weight correction.
Raw IS: (1/N) Σ f(xᵢ)·p(xᵢ)/q(xᵢ). Unbiased for Ep[f].
Every number is computed live from p, q, f on the spot — the population estimate exactly, the sample estimate from a fixed-seed PRNG. Nothing is looked up.
What the machine proves: the reweighted average is unbiased for Ep[f] = 3.2 under any valid q; the optimal proposal q ∝ f·p drives the variance to 0 (every corrected sample equals 3.2 exactly); the self-normalized form recovers the same answer knowing p only up to a constant; and a thin-tailed q blows the variance up (2.86 → 22.12).
The blue witness (left) confirms the identity live; the red team (right) drops the weight and makes it drift.
The effective sample size Nₑ = (Σwᵢ)²/Σwᵢ² collapses toward 1 as the weights become lopsided: you paid for N draws and got the information of one. In high dimension a hand-picked q almost always mismatches p somewhere — which is why adaptive / annealed proposals exist.
"More samples always fix it." Cut. With a mismatched q the variance can be infinite; more draws shrink nothing. Fix the proposal, not the count.
"You need p normalized to use IS." Cut. The self-normalized estimator divides by Σw, so any constant in p cancels — this engine proves p̃=7·p gives the identical answer.
"The optimal proposal is q ∝ p." Corrected. It is q ∝ |f|·p. For f ≥ 0 that gives zero variance — every corrected sample equals Ep[f] exactly.
The red team's move: drop the weight — just average f under the samples from q with no p/q correction. Now the estimator targets Eq[f], not Ep[f]. The blue witness (window 7) is watching.
Drop p/q and the unbiasedness identity fails: the population estimate slides from 3.2 to Eq[f] = 3.0, the witness recomputes, disagrees with the known truth, and turns red. Nothing is faked; the attack is real and it is caught.