Simulation of Markov Chains with Continuous State Space by Using Simple Stratified and Sudoku Latin Square Sampling

Monte Carlo (MC) is widely used for simulating discrete time Markov chains. Here, N copies of the chain are simulated in parallel, using pseudorandom numbers. We restrict ourselves to a one-dimensional continuous state space. We analyze the effect of replacing pseudorandom numbers on $$I := [0,1)$$ I : = [ 0 , 1 ) with stratified random points over $$I^2$$ I 2 : for each point, the first component is used to select a state and the second component is used to advance the chain by one step. Two stratified sampling techniques are compared: simple stratified sampling (SSS) and Sudoku Latin square sampling (SLSS). For both methods and for $$N=p^2$$ N = p 2 samples, the unit square is dissected into $$p^2$$ p 2 subsquares and there is one sample in each subsquare. For SLSS, each side of the unit square is divided into N subintervals and the projections of the samples on the side are distributed with one projection in each subinterval. Stratified strategies outperform classical MC if the N copies are reordered by increasing states at each step. We prove that the variance of SSS and SLSS estimators is bounded by $$\mathcal {O}(N^{-3/2})$$ O ( N - 3 / 2 ) , while it is bounded by $$\mathcal {O}(N^{-1})$$ O ( N - 1 ) for MC. The results of numerical experiments indicate that these upper bounds match the observed rates. They also show that SLSS gives a smaller variance than SSS.