2004-11-05 9:54 AM
We learned about a neat trick when doing some Monte Carlo simulations last week. It’s not new by any means, but it’s cool, very useful, and I hadn’t heard of it before.Consider the application of Monte Carlo to the task of determining the probability that an event occurs. Let be the state space and be the region where the event occurs. Assume you have a (“generative”) model that allows you to calculate the probability of any state, , and that you also have a delta function Monte Carlo says: where is chosen uniformly randomly. So to estimate the size of we have: where are chosen uniformly randomly from . However, computationally speaking, this is not ideal, as typically is extremely small, necessitating software solutions like rational number packages to deal with the underflow. Importance sampling to the rescue. If we have a function “similar” to , importance sampling says we can rewrite the Monte Carlo equation as where is drawn according to rather than uniformly. In our case, if we choose , we have where we choose according to . And now we’re accumulating integers rather than very small floating-point numbers. In our case this lead to a speedup of many orders of magnitude.