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

G-2009-03

On Array-RQMC for Markov Chains: Mapping Alternatives and Convergence Rates

, et

We study the convergence behavior of a randomized quasi-Monte Carlo (RQMC) method for the simulation of discrete-time Markov chains, known as array-RQMC. The goal is to estimate the expectation of a smooth function of the sample path of the chain. The method simulates n copies of the chain in parallel, using highly uniform point sets randomized independently at each step. The copies are sorted after each step, according to some multidimensional order, for the purpose of assigning the RQMC points to the chains. In this paper, we discuss and compare different ways of realizing this sort and assignment, and report empirical experiments on the convergence rate of the variance as a function of n. In these experiments, the variance reduction with respect to standard Monte Carlo is substantial and we observe (approximately) an O(n-2) convergence for the variance. On the other hand, for most standard discrepancies, the mean square discrepancy between the empirical and theoretical distributions of the states at any given step converges at a slower rate, approximately O(n-3/2) in some examples.

, 16 pages