A number of different methods have been proposed and developed for the efficient Monte Carlo estimation of probabilities and expected values related to rare events. Examples include various forms of important sampling and schemes based on branching processes, such as RESTART (REpetitive Simulation Trials After Reaching Thresholds) and DPR (Direct Probability Redistribution). However, performance analysis and especially the design problem for these methods can be quite subtle. In this talk we will give an overview of an approach to both design and analysis that is based on subsolutions to an associated partial differential equation. The approach provides necessary and sufficient conditions for asymptotically optimal performance as a large deviation parameter tends to its limit, and also quantifies the speed-up for schemes that are suboptimal.
After reviewing the standard Monte Carlo methods, we give an overview of how subsolutions are used for design and present results on performance analysis. The theory has been developed for both importance sampling and branching types schemes and, though similar, there are interesting differences that will be discussed. The last part of the talk will focus on examples and open problems.