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
