TOPICS
Search

Quasirandom 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.


See also

Hammersley Point Set, Pseudorandom Number, Quasirandom Number, Random Number, Uniform Distribution Theory, van der Corput Sequence

Portions of this entry contributed by Aurel Trandafir

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Quasirandom Sequence

Cite this as:

Trandafir, Aurel and Weisstein, Eric W. "Quasirandom Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/QuasirandomSequence.html

Subject classifications