low-discrepancy sequence

A sequence of n-tuples that fills n-space more uniformly than uncorrelated random points, sometimes also called a low-discrepancy sequence. Although the ordinary uniform random numbers and quasirandom sequences both produce uniformly distributed sequences, there is a big difference between the two. A uniform random generator on [0, 1) will produce outputs so that each trial has the same probability of generating a point on equal subintervals, for example [0, 1/2) and [1/2, 1). Therefore, it is possible for n trials to coincidentally all lie in the first half of the interval, while the (n + 1)st point still falls within the other of the two halves with probability 1/2. This is not the case with the quasirandom sequences, in which the outputs are constrained by a low-discrepancy requirement that has a net effect of points being generated in a highly correlated manner (i.e., the next point "knows" where the previous points are). Such a sequence is extremely useful in computational problems where numbers are computed on a grid, but it is not known in advance how fine the grid must be to obtain accurate results. Using a quasirandom sequence allows stopping at any point where convergence is observed, whereas the usual approach of halving the interval between subsequent computations requires a huge number of computations between stopping points.

Hammersley point set | pseudorandom number | quasirandom number | random number | uniform distribution theory | van der Corput sequence