Accelerated Accuracy in the Simulation of Markov Chains

George S. Fishman
Additional contact information
George S. Fishman: University of North Carolina, Chapel Hill, North Carolina

Operations Research, 1983, vol. 31, issue 3, 466-487

Abstract: 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.

Keywords: 567 simulation of Markov chains; 767 variance reduction for Markov chains (search for similar items in EconPapers)
Date: 1983
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.31.3.466 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:31:y:1983:i:3:p:466-487

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().