### G-2023-68

# Simple stratified sampling for simulating multi-dimensional Markov chains

## , , and BibTeX reference

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.

Published **December 2023**
,
13 pages

### Research Axis

### Research applications

- Economy and finance
- Smart infrastructure (telecommunications, public transport, smart cities)
- Engineering (engineering design, digital design)
- Smart logistics (schedule design, supply chains, logistics, manufacturing systems)
- Marketing (business intelligence, revenue management, recommendation systems)

### Document

**G2368.pdf**
(500 KB)