Unbiased estimation with biased samplers
- This thesis discusses how to construct unbiased estimators from biased estimators. Many situations that call for Monte Carlo methods lack known algorithms for exactly generating the random object for which an expectation is to be computed. Frequently, however, one can generate arbitrarily close approximations to the random object. We introduce a simple randomization idea for creating unbiased estimators in such a setting based on a sequence of approximations. We then describe the implications for two important cases: solutions to stochastic differential equations (SDEs), and equilibrium random variables associated with ergodic Markov chains. The first chapter briefly provides the context and motivation for the theory developed in this thesis and present an overview of the results. The second chapter introduces a general approach to the construction of unbiased estimators from a sequence of biased estimators. We provide the conditions under which the new estimators achieve "square root" convergence, and prove central limit theorems with respect to computational budget. The performance of the resulting unbiased estimators depends on the choice of randomization distributions. We identify the optimal choice of the randomization distributions. Applying the general approach, we show that one can build finite-variance unbiased estimators with a square root convergence rate whenever one has available a scheme that produces strong error of an order greater than 1/2 for the path functional under consideration. The new estimators are the first of their kind to both be unbiased and achieve square root convergence for multi-dimensional SDEs. Numerical experiments with various path functionals of continuous-time processes that arise in finance illustrate the effectiveness of our estimators. Our algorithm is competitive with, and often beats, the state-of-the-art multi-level Monte Carlo method. The third chapter applies our general approach to the computation of equilibrium expectations of ergodic Markov chains. Our approach provides an alternative to the class of algorithms known as "perfect sampling" or "exact sampling." Instead of sampling from the exact equilibrium distribution, our approach constructs unbiased estimators for equilibrium expectation. By aiming for a slightly less ambitious goal than exact sampling, our method can address a broader class of processes with much less care and effort. In particular, we provide a recipe for the construction of unbiased estimators (with square root convergence in great generality) for general positive Harris recurrent chains. Moreover, we show how one can construct unbiased estimators for non-Harris chains such as contraction chains.
|Type of resource
|electronic; electronic resource; remote
|1 online resource.
|Stanford University, Institute for Computational and Mathematical Engineering.
|Glynn, Peter W
|Glynn, Peter W
|Statement of responsibility
|Submitted to the Institute for Computational and Mathematical Engineering.
|Thesis (Ph.D.)--Stanford University, 2013.
- © 2013 by Chang-Han Rhee
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...