Quasirandom Sequence

A sequence of -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  will produce outputs so that each trial has the same probability of generating a point on equal subintervals, for example  and . Therefore, it is possible for  trials to coincidentally all lie in the first half of the interval, while the 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.

REFERENCES:

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Quasi- (that is, Sub-) Random Sequences." §7.7 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 299-306, 1992.