HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains

P. l'Ecuyer 1 Christian Lécot 2 Bruno Tuffin 3
3 ARMOR - Architectures and network models
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes, Ecole Nationale Supérieure des Télécommunications de Bretagne
Abstract : We introduce and study a randomized quasi-Monte Carlo method for estimating the state distribution at each step of a Markov chain, under the assumption that the chain has a totally ordered (discrete or continuous) state space. The number of steps in the chain can be random and unbounded. The method simulates $n$ copies of the chain in parallel, using a $(d+1)$-dimensional low-discrepancy 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. This technique is effective in particular to obtain a low-variance unbiased estimator of the expected total cost up to some random stopping time, when state-dependent costs are paid at each step. We provide numerical illustrations where the variance reduction with respect to standard Monte Carlo is substantial. The variance is reduced by factors of several thousands in some cases. We prove bounds on the convergence rate of the worst-case error and variance for special situations. In line with what is typically observed in RQMC contexts, our empirical results indicate much better convergence than what these bounds guarantee.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:34:39 PM
Last modification on : Friday, February 4, 2022 - 3:21:52 AM
Long-term archiving on: : Sunday, April 4, 2010 - 7:57:38 PM


  • HAL Id : inria-00070462, version 1


P. l'Ecuyer, Christian Lécot, Bruno Tuffin. A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains. [Research Report] RR-5545, INRIA. 2005, pp.32. ⟨inria-00070462⟩



Record views


Files downloads