Concept

Importance sampling — where it appears

A Monte Carlo method that draws from a convenient proposal distribution and reweights each draw by the ratio of the target density to the proposal's. It turns a rare-event probability into an average of weights, and its precision depends on how closely the proposal matches where the target puts its mass.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Estimating P(Z > 5) = 2.8665×10⁻⁷ with plain draws and with four proposals. One seed each. Plain simulation draws nothing past 5 in 100,000 and estimates zero throughout. At 100,000 draws the proposal N(5, 1) reads 1.009 of the truth, N(9, 1) 1.041, N(4.5, 0.25²) 1.039 and N(5, 0.3²) 1.008. Values above 2.2 are drawn at the top edge.

The draws aimed at the tail

The chance a standard normal exceeds 5 is 2.8665×10⁻⁷, and a plain simulation needs 349 million draws to estimate it to within ten per cent. Draws aimed at the tail and weighted back need 565. Aimed slightly too narrowly, the same method has an infinite variance, an interval that covers 86.0% and gets worse with more draws, and an effective sample size that reads healthier than a proposal that works.

method · Seeds

A cross-entropy fit of a normal proposal to P(Z > 5), stage by stage, fitting mean and spread or the mean alone. Each stage draws a thousand points from the current proposal, keeps the top tenth, and refits the normal to them, each weighted by the target density over the proposal's. Fitting the mean alone, the levels are 1.24, 2.99, 4.59, 5.00 and the fit reaches 5 at stage 4, ending at N(5.199, 1). Fitting mean and spread from the same seed, the spread goes 1.000, 0.456, 0.244, 0.096, 0.054, 0.043 over the first six stages, roughly halving each time, and after 30 stages the level has stalled at 3.728 with a spread of 1.0e-6, never reaching 5.

A proposal fitted to its own draws

The cross-entropy method fits an importance-sampling proposal from its own pilot draws, and asked to fit a normal's mean and spread to P(Z > 5) it fails before the question of variance arises: the spread halves at every stage, the level stalls near 3.7, and 95% of runs never reach the threshold, so the interval covers 1.1% of the time. Its ideal end point, the normal closest to Z conditioned past 5, is N(5.187, 0.181²), which has an infinite variance inside its own draws' reach and covers 93.7% at a thousand draws and 90.8% at ten thousand. Fitting the mean alone lands within a tenth of the best shift and covers 94.5%.

method · Seeds

Named alongside it

The objects these essays reach for when they reach for this one.

Closed form Coverage Effective sample size Monte Carlo Normal distribution Tail probability Adaptive procedure Confidence interval Cross entropy method Heavy tail Infinite variance Kullback leibler divergence

All concepts