Monte Carlo estimation of small probabilities and expected values determined by rare events can be tricky. The two most commonly applied methods are those based on change-of-measure arguments and known as importance sampling, and those which use branching processes and are referred to as multi-level splitting. There are a number of heuristic guides to the design of schemes, and certainly successful applications have been reported. However, it is also known that these guides can suggest schemes that perform badly.

In this talk we first review both approaches and the sources of poor performance. When the probability of interest can be approximated via large deviations, there is a naturally related nonlinear partial differential equation (known as a Hamilton- Jacobi-Bellman equation). Schemes for both types of approximation can be associated with what are called importance functions. We will show that these schemes are stable in an appropriate sense if and only if the importance function is a subsolution to this equation, and also characterize the performance of the scheme in terms of the value of the function at a certain point.