A variance analysis of the Metropolis Light Transport algorithm
The Metropolis Light Transport algorithm is a variant of the classic Metropolis method used in statistical physics. A variance analysis of the Metropolis Light Transport algorithm is presented that bounds its variance in terms of the number of paths used and the intrinsic correlation between samples. It is shown that the variance of a pixel is ?(1/N), where N is the number of samples for the entire image. The analysis uses basic probability, Bayes law, and the principle of stationary distributions. This result implies that the presence of correlation in the algorithm does not make its asymptotic time complexity worse than uncorrelated Monte Carlo methods such as path tracing.
monte carlo three-dimensional graphics and realism raytracing simulation and modeling analysis of algorithms and problem complexity numerical algorithms and problems probability and statistics