Accelerated Convergence in the Simulation of Countably Infinite State 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 6, 1074-1089

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

Keywords: 567 simulation; 761 Markov chains; 769 Monte Carlo method (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.6.1074 (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:6:p:1074-1089

Access Statistics for this article

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