Simple stratified sampling for simulating multi-dimensional Markov chains

, et

référence BibTeX

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.

, 13 pages

Axe de recherche

Applications de recherche


G2368.pdf (450 Ko)