Groupe d’études et de recherche en analyse des décisions

G-2007-20

Quasi-Monte Carlo Simulation of Discrete-Time Markov Chains on Multidimensional State Spaces

, et

We propose and analyze a quasi-Monte Carlo (QMC) method for simulating a discrete-time Markov chain on a discrete state space of dimension . Several paths of the chain are simulated in parallel and reordered at each step. We provide a convergence result when the number N of simulated paths increases toward infinity. Finally, we present the results of some numerical experiments showing that our QMC algorithm converges faster as a function of N, at least in some situations, than the corresponding Monte Carlo (MC) method.

, 20 pages