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 (δ 2 (ln k ) 4 / k 2 ) 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 2 )) 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.