Variance reduction's greatest hits

Monte Carlo simulation is an incredibly versatile tool for studying complex stochastic systems. By replicating the simulation several times independently, one can in principle estimate performances measures of the system to arbitrary accuracy. Decisions and operating rules call also be optimized via Simulation. A major drawback, however. is that the method converges very slowly and often requires an excessive amount of computing time. Efficiency improvement methods provide ways of either reducing the required computing time for a given target accuracy, or of obtaining an estimator with better accuracy for a given Computational budget. Variance reduction is the primary way of improving efficiency. Key ideas for variance reduction were already introduced in the early days of the Monte Carlo method, in the late forties, at Los Alamos. Since then, enormous progress has been made in our understanding of these methods. This paper is a guided tour of live different methods that can make a huge difference in the accuracy of simulation estimators. They can reduce the variance (or improve the efficiency) by in arbitrary large factor. In some situations, this type of efficiency improvement is essential for the simulation approach to be viable. We discuss common random numbers and their synchronization I-or comparing similar systems. (or derivative estimation, and for optimization, importance sampling for rare-event Simulation, exploiting auxiliary information via control variates. smoothing estimators via conditional Monte Carlo. and reducing(,, the noise via generalized antithetic variates or quasi-Monte Carlo. We give examples where a clever use of these methods can make a huge difference in the required computing time for a given target accuracy.