Simple Stratified Sampling for Simulating Multi-dimensional Markov Chains

Monte Carlo (MC) is widely used for the simulation of discrete time Markov chains. We consider the case of a d-dimensional continuous state space and we restrict ourselves to chains where the d components are advanced independently from each other, with d random numbers used at each step. We simulate N copies of the chain in parallel, and we replace pseudorandom numbers on \(I^d := (0,1)^d\) with stratified random points over \(I^{2d}\) : for each point, the first d components are used to select a state and the last d components are used to advance the chain by one step. We use a simple stratification technique: let p be an integer, then for \(N=p^{2d}\) samples, the unit hypercube is dissected into N hypercubes of measure 1/N and there is one sample in each of them. The strategy outperforms classical MC if a well-chosen multivariate sort of the states is employed to order the chains at each step. We prove that the variance of the stratified sampling estimator is bounded by \(\mathcal {O}(N^{-(1+1/(2d))})\) , while it is \(\mathcal {O}(N^{-1})\) for MC. In numerical experiments, we observe empirical rates that satisfy the bounds. We also compare with the Array-RQMC method.