Accelerated Convergence in the Simulation of Countably Infinite State Markov Chains

摘要

This paper describes a method of obtaining results from the simulation of a countably infinite state positive recurrent aperiodic Markov chain at a cost considerably below the cost required to achieve the same accuracy with pure random sampling. By reorganizing k independent epochs or tours simulated serially into k replications simulated in parallel, one can induce selected joint distributions across replications that produce the cost-saving benefits. The joint distributions follow from the use of rotation sampling, a special case of the antithetic variate method. The chains considered are of the band type so that for the state space S = (0,1,2,...) there exists an integer, delta, such that transition from a state i can move no further than to states i - delta and i + delta. The paper shows that an estimator of interest has variance bounded above by O(delta squared (ln k) to the 4th power/k squared) when using rotation sampling, as compared to a variance O(l/k) for independent sampling. Moreover, the mean cost of simulation based on rotation sampling has an upper bound O((delta ln k) squared) as compared to at least O(k) for independent sampling. The paper also describes how one can exploit special structure in a model together with rotation sampling to improve the bound on variance for essentially the same mean cost.