A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains

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.