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

Quasirandom sequences supply the deterministically chosen sample points used in quasi-Monte Carlo methods.

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, Quasi-Monte Carlo Method, 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 Resource. https://mathworld.wolfram.com/QuasirandomSequence.html

Subject classifications