In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N {\displaystyle N} , its subsequence x 1 , … , x N {\displaystyle x_{1},\ldots ,x_{N}} has a low discrepancy. Roughly speaking, the discrepancy of a sequence is low if the proportion of points in the sequence falling into an arbitrary set B is close to proportional to the measure of B, as would happen on average (but not for particular samples) in the case of an equidistributed sequence. Specific definitions of discrepancy differ regarding the choice of B (hyperspheres, hypercubes, etc.) and how the discrepancy for every B is computed (usually normalized) and combined (usually by taking the worst value). Low-discrepancy sequences are also called quasirandom sequences, due to their common use as a replacement of uniformly distributed random numbers. The "quasi" modifier is used to denote more clearly that the values of a low-discrepancy sequence are neither random nor pseudorandom, but such sequences share some properties of random variables and in certain applications such as the quasi-Monte Carlo method their lower discrepancy is an important advantage.
Applications
Quasirandom numbers have an advantage over pure random numbers in that they cover the domain of interest quickly and evenly. Two useful applications are in finding the characteristic function of a probability density function, and in finding the derivative function of a deterministic function with a small amount of noise. Quasirandom numbers allow higher-order moments to be calculated to high accuracy very quickly. Applications that don't involve sorting would be in finding the mean, standard deviation, skewness and kurtosis of a statistical distribution, and in finding the integral and global maxima and minima of difficult deterministic functions. Quasirandom numbers can also be used for providing starting points for deterministic algorithms that only work locally, such as Newton–Raphson iteration. Quasirandom numbers can also be combined with search algorithms. With a search algorithm, quasirandom numbers can be used to find the mode, median, confidence intervals and cumulative distribution of a statistical distribution, and all local minima and all solutions of deterministic functions.
Low-discrepancy sequences in numerical integration Various methods of numerical integration can be phrased as approximating the integral of a function f {\displaystyle f} in some interval, e.g. [0,1], as the average of the function evaluated at a set { x 1 , … , x N } {\displaystyle \{x_{1},\dots ,x_{N}}\} in that interval:
∫ 0 1 f ( u ) d u ≈ 1 N ∑ i = 1 N f ( x i ) . {\displaystyle \int _{0}^{1}f(u)\,du\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).}
If the points are chosen as x i = i / N {\displaystyle x_{i}=i/N} , this is the rectangle rule. If the points are chosen to be randomly (or pseudorandomly) distributed, this is the Monte Carlo method. If the points are chosen as elements of a low-discrepancy sequence, this is the quasi-Monte Carlo method. A remarkable result, the Koksma–Hlawka inequality (stated below), shows that the error of such a method can be bounded by the product of two terms, one of which depends only on f {\displaystyle f} , and the other one is the discrepancy of the set { x 1 , … , x N } {\displaystyle \{x_{1},\dots ,x_{N}}\} . It is convenient to construct the set { x 1 , … , x N } {\displaystyle \{x_{1},\dots ,x_{N}}\} in such a way that if a set with N + 1 {\displaystyle N+1} elements is constructed, the previous N {\displaystyle N} elements need not be recomputed. The rectangle rule uses point sets which have low discrepancy, but in general the elements must be recomputed if N {\displaystyle N} is increased. Elements need not be recomputed in the random Monte Carlo method if N {\displaystyle N} is increased, but the point sets do not have minimal discrepancy. By using low-discrepancy sequences we aim for low discrepancy and no need for recomputations, but actually low-discrepancy sequences can only be incrementally good on discrepancy if we allow no recomputation.
Definition of discrepancy The discrepancy of a set P = { x 1 , … , x N } {\displaystyle P=\{x_{1},\dots ,x_{N}}\} is defined, using Niederreiter's notation, as
… excerpt ends here. Continue reading the full article.
