Accelerated Accuracy in the Simulation of Markov Chains

This paper describes a method of obtaining results from the simulation of an n + 1 finite state positive recurrent aperiodic Markov chain at a cost considerably less than that required by pure random sampling to achieve the same accuracy. The method reorganizes k independent epochs (or tours) simulated serially into k replications simulated in parallel, and therefore produces cost savings by inducing selected joint distributions across replications. The joint distributions are derived by the use of rotation sampling, a special case of the antithetic variate method. The paper first describes the method as it applies to a finite state nearest neighbor chain. In particular, it shows that even for independent parallel replications, the cost of achieving a specified accuracy with serial simulation, relative to the cost for parallel simulation, has a lower bound O ( k 1/2 / n ) as k → ∞. When rotation sampling is used, this bound is O ( k 2 / n (ln k ) 3 ). A simulation of the M / M /1 queueing model with finite capacity n illustrates the effectiveness of the technique for selected values of k , n and activity level ρ. The paper then describes how this variance reducing technique applies to the simulation of a more general finite state chain. In particular, the lower bound on relative cost is O ( k 2 /ϕ(ln k ) 3 ), where ϕ is the total number of transitions that can occur from all n + 1 states. A computer program that implements the method for the general finite state case is briefly described.