Accelerated Accuracy in the Simulation of Markov Chains.
NORTH CAROLINA UNIV AT CHAPEL HILL
Pagination or Media Count:
This paper describes a method of obtaining results from the simulation of a finite 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. For a finite state nearest neighbor chain the paper 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 0 sq. rt. of k as k approaches infinity. When rotation sampling is used this bound is 0k squared1n k cubed. This lower bound also holds for the more general finite state chains. A simulation of the MM1 queueing model with finite capacity n is used to illustrate the effectiveness of the technique for selected values of k, n and activity level rho. Author
- Statistics and Probability
- Computer Programming and Software