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 that required to achieve the same accuracy with pure random sampling. Reorganizing k independent epochs or tours simulated serially into k replications simulated in parallel can induce selected joint distributions across replications that produce the cost savings. 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 some integer δ a transition from any state i = 0, 1, 2, … can move no further than to states i − δ and i + δ. The paper shows that an estimator of interest has variance bounded above by O(δ²(ln k)⁴/k²) when using rotation sampling, as compared to a variance O(1/k) for independent sampling. Moreover, the mean cost of simulation based on rotation sampling has an upper bound O((δ ln k²)) as compared to a cost of 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.