How do correlated samples influence the behavior of a Monte Carlo renderer?

Question

Most descriptions of Monte Carlo rendering methods, such as path tracing or bidirectional path tracing, assume that samples are generated independently; that is, a standard random number generator is used that generates a stream of independent, uniformly distributed numbers.

We know that samples that are not chosen independently can be beneficial in terms of noise. For example, stratified sampling and low-discrepancy sequences are two examples of correlated sampling schemes that almost always improve render times.

However, there are many cases where the impact of sample correlation is not as clear-cut. For example, Markov Chain Monte Carlo methods such as Metropolis Light Transport generate a stream of correlated samples using a Markov chain; many-light methods reuse a small set of light paths for many camera paths, creating many correlated shadow connections; even photon mapping gains its efficiency from reusing light paths across many pixels, also increasing sample correlation (although in a biased way).

All of these rendering methods can prove beneficial in certain scenes, but seem to make things worse in others. It's not clear how to quantify the quality of error introduced by these techniques, other than rendering a scene with different rendering algorithms and eyeballing whether one looks better than the other.

So the question is: How does sample correlation influence the variance and the convergence of a Monte Carlo estimator? Can we somehow mathematically quantify which kind of sample correlation is better than others? Are there any other considerations that could influence whether sample correlation is beneficial or detrimental (e.g. perceptual error, animation flicker)?

Answer 1

There is one important distinction to make.

Markov Chain Monte Carlo (such as Metropolis Light Transport) methods fully acknowledge the fact that they produce lots of highly correlated, it is actually the backbone of the algorithm.

On other hand there are algorithms as Bidirectional Path Tracing, Many Light Method, Photon Mapping where the crucial role plays Multiple Importance Sampling and its balance heuristics. Optimality of balance heuristic is proven only for samples that are independent. Many modern algorithms have correlated samples and for some of them this causes troubles and for some it doesn't.

The problem with correlated samples was acknowledged in the paper Probabilistic Connections for Bidirectional Path Tracing. Where they have altered balance heuristics to take into account the correlation. Have a look at figure 17 in the paper to see the result.

---

I would like to point out that correlation is "always" bad. If you can afford to make brand new sample than do it. But most of the time you can't afford it so you hope that the error due to the correlation is small.

Edit to explain the "always": I mean this in the context of MC integration

Where you measure the error with variance of the estimator

If the samples are independent that the covariance term is zero. Correlated samples make always this term nonzero thus increasing variance of the final estimator.

This is at first sight somewhat contradictory what we encounter with stratified sampling because stratification lowers the error. But you can't prove that stratified sampling converges to the desired result just from the probabilistic point of view, because in the core of stratified sampling there is no probability involved.

---

And the deal with stratified sampling is that it is basically not a Monte Carlo method. Stratified sampling comes from standard quadrature rules for numerical integration which works great for integrating smooth function in low dimensions. This is why it is used for handling direct illumination which is low dimensional problem, but its smoothness is disputable.

So stratified sampling is yet different kind of correlation than for example correlation in Many Light methods.

Answer 2

The hemispherical intensity function, i.e. the hemispherical function of incident light multiplied by the BRDF, correlates to the number of samples required per solid angle. Take the sample distribution of any method and compare it to that hemispherical function. The more similar they are, the better the method is in that particular case.

Note that since this intensity function is typically unknown, all of those methods use heuristics. If the assumptions of the heuristics are met, the distribution is better (= closer to the desired function) than a random distribution. If not, it's worse.

For example, importance sampling uses the BRDF to distribute samples, which is simple but only uses a part of the intensity function. A very strong light source illuminating a diffuse surface at shallow angle will get few samples, although its influence might still be huge. Metropolis Light Transport generates new samples from previous one's with high intensity, which is good for few strong light sources, but doesn't help if light arrives evenly from all directions.