Importance sampling

Idea: A plain run that starves

Default chance $0.002$: $10000$ plain paths see about $10000\times 0.002=20$ defaults.

• The other $9980$ paths tell you nothing
• Importance sampling moves paths to the action, then corrects

Formula: Reweighting

$E_p[f(X)]=E_q[f(X)w(X)],w=\frac{p}{q}$

Draw from q and weight each draw by p/q. Unbiased if q > 0 wherever p·f is not 0.

Example: A weighted run

True default $0.002$, sampled at $q=0.1$, cost $8000$. Of $1000$ draws, $104$ default. What is the estimate?

1. Weight: $\frac{0.002}{0.1}=\frac{1}{50}$
2. Estimate: $104\times 8000\times \frac{\frac{1}{50}}{1000}=16.64$

Formula: Variance for a rare event

$\mathrm{Var}\text{per}\text{draw}=\frac{p^2}{q}-p^2$

Falls as the sampling chance q rises towards 1. The ideal q follows |f| times p.

Quick check: Variance saved

A default with $p=0.002$ is sampled with $q=0.1$. What is the variance of one weighted draw?

Common mistake: It can make things worse

A $0.5$ event sampled at $q=0.1$: $\frac{0.5^2}{0.1}-0.5^2=2.25$, against $0.25$ plain.

Instead Never give q thinner tails than p: one huge weight can move everything.

Formula: Effective sample size

$\text{ESS}={\left(\sum w_i\right)}^2/\sum w_i^2$

How many equal draws the weighted sample is worth. A small share of n means do not trust it.

Quick check: Check the weights

$5$ draws have weights $2$, $2$, $2$, $2$, $10$. What is the effective sample size?

Idea: Say it out loud

Report the effective sample size beside the estimate, not only the error bar.

• A region q never visits is one the estimate never sees
• Shift or tilt p towards the scenarios that matter