Improving Monte Carlo Efficiency by Increasing Variance

This paper compares the performances of two well-known Monte Carlo procedures for estimating an unknown quantity as the size of the problem grows. One method based on the standard Monte Carlo approach generates K i.i.d. data points. The other derives its data from a single K-step sample path generated by a Markov chain. The paper gives necessary and sufficient conditions for the Markov chain approach to perform more efficiently than the standard Monte Carlo approach does. Moreover, it identifies circumstances under which this better efficiency grows with increasing problem size. This improved efficiency comes from reduced sample generating and function evaluating costs in the Markov chain approach that more than compensate for the increased variance of the estimator that the Markov chain sampling approach induces when compared to the standard Monte Carlo approach. Several examples illustrate how the benefits arise; one also demonstrates a case in which the standard Monte Carlo approach becomes increasingly preferred as the problem size grows.