Adaptive Stochastic Simulation for Structured Problems

Abstract

In this thesis, I examine several situations in which one can improve the efficiency of a stochastic simulation algorithm by adaptively exploiting special structure of the problem at hand.

The thesis is comprised of three independent papers. In the first paper, I propose a new variance reduction technique in the setting of comparing the performance of two stochastic systems. The technique is a natural generalization of common random number sampling, a well-known sampling strategy that may reduce variance in certain situations. Common random number sampling entails sampling the underlying uniform random variates according to a particular copula; my proposed method considers more general copulae. I identify properties such a copula must have in order to induce a valid sampling strategy, give examples of situations in which copulae exist that outperform common random numbers, and give an algorithm for computing an effective Gaussian copula.

In the second paper, I discuss an automated procedure for computing a control variate for the pricing of American options. The control variate is equal to the value of a particular martingale at the time the option is exercised. The martingale is constructed using an approximation of the value function in a backward dynamic program. We use adaptive linear regression splines to create the functional approximation. These splines have properties of which make them computationally convenient for constructing a martingale-based control variate of this type.

In the third paper, I describe and analyze a novel root-finding procedure for monotone, convex univariate functions in the presence of noise. The main result of the analysis is a probabilistic performance guarantee for the algorithm. Specifically, given an indifference parameter delta and a confidence level alpha, the algorithm returns a point whose absolute function value is less than delta with probability at least one minus alpha. The total amount of work required by the algorithm may be bounded in terms of the length of the compact interval on which the function is defined and the Lipschitz constant of the function.