Accelerated Accuracy in the Simulation of Markov Chains.
Abstract
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 0(k squared/(1n k) cubed). This lower bound also holds for the more general finite state chains. A simulation of the M/M/1 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1981
- Accession Number
- ADA099287
Entities
People
- George S. Fishman
Organizations
- University of North Carolina at Chapel Hill