Pierre L'Ecuyer: Randomized Quasi-Monte Carlo simulation to estimate the distribution of the state of a transient Markov chain at each step

This is a joint work with Christian Lécot and Bruno Tuffin.

We study a randomized quasi-Monte Carlo method for estimating the state distribution at each step of a Markov chain with totally ordered (discrete or continuous) state space. The number of steps in the chain can be random and even unbounded. The method can be used in particular to estimate the expected total cost up to some random stopping time, when state-dependent costs are paid at each step. 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. It provides an unbiased estimator of the expected cost. Under certain conditions on the structure of the chain, we can prove that the variance converges to zero at a faster rate, as a function of $n$, than for standard Monte Carlo. We provide various numerical examples where the variance reduction with respect to standard Monte Carlo is substantial.

Back to the Index