Monte Carlo Crash Course: Quasi-Monte Carlo

Summary

Monte Carlo Crash CourseQuasi-Monte CarloWe’ve learned how to define and apply Monte Carlo integration—fundamentally, it’s the only tool we need. In the remaining chapters, we’ll explore ways to reduce variance and successfully sample difficult distributions.Variance & CorrelationIn chapter two, we determined that the variance of a Monte Carlo estimator is inversely proportional to its sample count. Empirically, we confirmed that our integrators’ expected error scaled with $$\frac{1}{\sqrt{N}}$$ in any dimension.Although dramatically faster than exponential, if we want a very accurate result, $$\frac{1}{\sqrt{N}}$$ may still be too slow. In practice, we can only scale sample count quadratically so many times.We also assumed that our samples are independent, so their variance is additive. However, our proof that Monte Carlo integration is unbiased didn’t rely on independence—so what if we relaxed that assumption?\[\begin{align*} \mathrm{Var}[X + Y] = \mathrm{Var}[X] + \mathrm{Var}[Y] + 2\mathrm{Cov}[X,Y] \end{align*}\]If $$X$$ and $$Y$$ are negatively correlated, $$\mathrm{Cov}[X,Y] < 0$$, decreasing the variance of $$X+Y$$. If we can assure that our samples are negatively correlated, our Monte Carlo estimator might converge faster than $$\frac{1}{\sqrt{N}}$$.Poisson Disk SamplingPerceptually, negatively correlated samples look “more random” than uncorrelated samples.That’s because uncorrelated samples often appear in clusters and may leave significant chunks of the domain entirely unsampled. Negative correlation causes the opposite behavior: the more samples an area contains, the less likely it is to be sampled, and vice versa.So, how can we generate negatively correlated samples? One approach is rejection sampling: simply discard samples that fall too close to any previous sample. This algorithm is known as Poisson disk sampling.Poisson disk sampling is useful for pre-generating samples with a minimum separation distance, but isn’t always applicable to Monte Carlo ...