Tarik Borogovac

May 2009
Constructive and Generic Control Variates For Monte Carlo Estimation
Committee Members: Advisor: Pirooz Vakili, SE/ME; Christos Cassandras, SE/ECE; Ioannis Paschalidis, SE/ECE; David Castañon, SE/ECE

Abstract: Estimation of quantities that can be represented as expectations of appropriately defined random variables is an important problem in diverse areas of science and engineering. Monte Carlo (MC) sampling/simulation is a very general approach for estimation, and is the method of choice in many application areas. To increase the computational efficiency of MC simulation a number of Variance Reduction Techniques (VRT), which aim to reduce the variance of the MC estimator, have been devised. The design of effective VRT’s has so far relied on the existence of specific problem features, and the acuity of the user to discover and properly exploit such features.

One of the most effective VRT’s is the method of Control Variates (CV). This method relies on a number of auxiliary random variables, called controls, that carry information about the estimation variable and “explain” part of its variance. If the means of the controls are known, or high quality estimates of them are available, the CV technique prescribes a generic procedure for transferring the relevant information to the estimation variable, leading to a controlled estimator with smaller variance. The main difficulty with the CV technique is in discovering controls that are informative about the estimation variable.

This thesis presents a generic approach to the selection controls that is applicable to a broad class of problems where the estimation variable depends on a model parameter. It is shown that under conditions information at a set of parameters can be used to define effective controls for estimation at neighboring parameters. A connection between sample-wise function approximation methods and the CV method is established. Motivated by this connection, controls for the estimation variable and for its sensitivity with respect to the parameter are proposed. Their effectiveness is demonstrated on simulations from the fields of finance, materials science and photon transport.

The requirement of tractability of controls is replaced by generic computational procedures through which the necessary information about the controls is procured. Two alternative algorithms that perform this function are given, and the CV estimators that result are analyzed.