Concept

Importance sampling

A Monte Carlo method that draws samples more often where they matter and weights each by the inverse of how much more often it was drawn. The weighting keeps the estimate unbiased, and a good choice of where to sample can shrink its error enormously.

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

Two unbiased estimates of one integral, and their spread. The sharply peaked integrand with the proposal density that follows it, above a strip plot of 200 estimates from each of two methods; the weighted estimates cluster 4.2 times more tightly about the same value.

Sampling where the answer lives

Monte Carlo error cannot be made to fall faster than the square root, so the only thing left to attack is the constant in front of it. Drawing points where the integrand is large, and dividing by how often they were drawn, leaves the answer alone and can shrink the noise many times over.

probability · Monte Carlo

One random path estimates the whole tree. probe columns 4,2,5,3,6,0; choices 8,5,3,1,2,1; estimate 769; exact 2057.

One random path down a search tree

Before running a search that may take a week, it is worth knowing whether it will take a week or a century. Donald Knuth's answer, from 1975, is to walk down the search tree once at random, multiply the numbers of choices met on the way, and add up the products: the result is, on average, exactly the size of the tree. On the eight-queens tree one path guesses 769 against a true 2,057 and twenty thousand paths average to within a tenth of a per cent. On a tree built to hide its bulk, the same unbiased estimate is almost always wrong by a factor of thousands.

probability · Monte Carlo

Named alongside it

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

Monte Carlo Variance Backtracking Convergence rate Estimator bias Exhaustive search Expectation Independence Integral Probability density Sampling Unbiased estimator

All concepts