literature on “stratified simulation”

I've thought of an approach to variance reduction that surely can't be new, but I haven't been able to find it published anywhere; I'd appreciate some leads.

Consider some sort of random variable $X$ that can be simulated using a sequence of IID random variables $U_i$ ($i \geq 1$) that are uniform in $[0,1]$. The ordinary Monte Carlo approach to learning things about the random variable $X$ is to run the process $n$ times, for some large $n$, using IID random variables $U_i^{(j)}$ ($i \geq 1$, $1 \leq j \leq n$) to obtain $n$ IID variables $X_j$ that are independent of one another and all distributed like $X$. But suppose that we let only the $U_i^{(1)}$'s be random, and we let $U_i^{(j)} = U_i^{(1)} + (j-1)\alpha_i$ (mod 1) for $2 \leq j \leq n$, for suitable choices of $\alpha_1,\alpha_2,\dots$. Then we get $n$ random variables that are each distributed like $X$ but are no longer independent; if we're lucky (and I think that we often will be), the copies of $X$ will be negatively correlated, so that $(X_1+X_2+...+X_n)/n$ will be more tightly distributed about the expected value of $X$ than it would be if we used ordinary Monte Carlo. In any case, since each $X_j$ is distributed like $X$, there's no bias in our estimate.

(In the original version of this posting I took $\alpha_i = 1/n$ for all $i$, but that's not a good idea; it will introduce positive correlations.)

More generally one could look at measure-preserving maps of $[0,1]$ rather than just addition of $\alpha_i$ (mod 1); one has a lot of freedom in setting things up. (Note that the method of antithetic variates uses the measure-preserving map $t \mapsto 1-t$.) But the scheme described above seems quite natural.

I feel that this particular wheel must have already been invented, so I'm reluctant to spend much time looking into it on my own without finding our more about what's already been done. (Sheldon Ross said my method reminded him of stratified sampling, so "stratified simulation" seems like a natural description.)

Jim Propp

• Hi what you describes I think is close to Randomized QMC methods, am i wrong ? – The Bridge Apr 14 '10 at 7:17
• You are right, but I haven't seen this idea applied in contexts like Markov chains. (Maybe it hasn't been.) – James Propp May 9 '10 at 5:45
• If you aren't familiar with it, check out the antithetic variate technique, which is an extremely simplified version of what you've done here. The idea in AV is to run the simulation first using U(0,1) independent random numbers U(1), U(2), ..., and then repeat the simulation using 1-U(1), 1-U(2), ... In many practical situations you generate U(0,1) random numbers and then transform them in some way to get random numbers according to a more complicated distribution. Unfortunately, this can often break the antithetic variate technique by ruining the negative correlation. – Brian Borchers Jan 17 '11 at 3:23