A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains

Pierre L'Ecuyer (), Christian Lécot () and Bruno Tuffin ()
Additional contact information
Pierre L'Ecuyer: GERAD and Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, C.P. 6128, Succ. Centre-Ville, Montréal, Québec, Canada H3C 3J7
Christian Lécot: Laboratoire de Mathématiques, Université de Savoie, 73376 Le Bourget-du-Lac Cedex, France
Bruno Tuffin: IRISA-INRIA, Campus Universitaire de Beaulieu, 35042 Rennes Cedex, France

Operations Research, 2008, vol. 56, issue 4, 958-975

Abstract: We introduce and study a randomized quasi-Monte Carlo method for the simulation of Markov chains up to a random (and possibly unbounded) stopping time. The method simulates n copies of the chain in parallel, using a ( d+1 )-dimensional, highly uniform point set of cardinality n , randomized independently at each step, where d is the number of uniform random numbers required at each transition of the Markov chain. The general idea is to obtain a better approximation of the state distribution, at each step of the chain, than with standard Monte Carlo. The technique can be used in particular to obtain a low-variance unbiased estimator of the expected total cost when state-dependent costs are paid at each step. It is generally more effective when the state space has a natural order related to the cost function.We provide numerical illustrations where the variance reduction with respect to standard Monte Carlo is substantial. The variance can be reduced by factors of several thousands in some cases. We prove bounds on the convergence rate of the worst-case error and of the variance for special situations where the state space of the chain is a subset of the real numbers. In line with what is typically observed in randomized quasi-Monte Carlo contexts, our empirical results indicate much better convergence than what these bounds guarantee.

Keywords: simulation; efficiency; probability; Markov processes (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0556 (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:56:y:2008:i:4:p:958-975

Access Statistics for this article

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