LowdiscrepancySequenzen

Low discrepancy sequences, also known as quasi-random sequences, are sequences of numbers designed to fill a multidimensional space more uniformly than purely random sequences. While pseudorandom number generators aim to produce numbers that appear random and lack discernible patterns, low discrepancy sequences aim for a systematic distribution that minimizes gaps and clumps. This makes them particularly useful in numerical integration, where they can achieve faster convergence rates compared to traditional Monte Carlo methods.

The key idea behind low discrepancy sequences is to reduce the "discrepancy," which is a measure of how unevenly a set of points is distributed within a given space. Various constructions exist, such as Sobol' sequences, Halton sequences, and Faure sequences, each employing different strategies to achieve this uniformity. For instance, Halton sequences use prime bases to generate coordinates for different dimensions, ensuring that the digits in their base expansions are distributed evenly.

In applications like Monte Carlo integration, where the error typically decreases with the square root of the number of samples, low discrepancy sequences can reduce the error to be inversely proportional to the number of samples. This significant improvement in convergence makes them a preferred choice for high-dimensional integration problems and in fields such as computer graphics for rendering and in scientific simulations. The predictability of their distribution, in contrast to the inherent randomness of pseudorandom numbers, is their defining characteristic and primary advantage.