Interactive Educational Modules in
Scientific Computing

Quasi-Random Sequences

This module compares random and quasi-random sequences by plotting in two dimensions sequences of pairs of numbers of each type. For Monte Carlo integration and a variety of other applications, random numbers are used to sample within some geometric domain. In some cases it may be more important to achieve approximately uniform coverage of the domain than for the sampling to be truly random. Quasi-random sequences, also known as low-discrepancy sequences, are carefully constructed to spread approximately uniformly over a given domain while still maintaining some appearance of randomness. Hence, quasi-random sequences may sometimes be more appropriate than truly random sequences.

This module plots a sequence of random points on the left and a sequence of quasi-random points on the right. The user adds points to the plots by clicking Add Points. The user can select how many points are added to the graph with each click of the button, controlling how quickly the graphs fill in with points. Clicking Reset clears the graphs and resets the quasi-random sequences. The pseudorandom sequence used to generate the points on the left is the linear congruential generator used in Java's Math.random( ) function. Menus allow the user to select how the quasi-random points are generated:

  • Halton sequences, one of the earliest methods for generating quasi-random sequences, depend on choosing a prime number b as the base or radix to generate the sequence. The jth number in the sequence, xj, is computed by writing j in base b and flipping the base-b digits across the radix point. For example, in base 2, the 6th number in the sequence is 0.0112 = 3 ⁄ 8 = 0.37510. For Halton sequences, the user can select the radix b defining a specific sequence.
  • Sobol sequences, one of the most commonly used quasi-random sequences today, are more complicated. Each primitive polynomial over the finite field GF(2) generates a Sobol sequence depending on a set of initial “direction numbers”. This module allows the user to select a primitive polynomial, completing the definition of the Sobol sequence with a table of predetermined initial direction numbers. For a more complete description of Sobol sequences, see reference [2].

For either Halton sequences or Sobol sequences, the user chooses a sequence for each of the coordinates in the plane. Each coordinate sequence assigns the jth number of the quasi-random sequence to its coordinate in the jth point in the sequence of points, regardless of whether the same sequence is chosen for both coordinates. Thus if the same sequence is chosen for both coordinates, every point will lie on the line x = y. If the sequences are different, the quasi-random points will eventually fill out the unit square, usually covering it quite well before the limit of resolution for the graphs is reached at about 8200 points, at which point the graphs must be cleared.

References:

  1. Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 13.4, especially Figure 13.1.
  2. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes, 2nd edition, Cambridge University Press, New York, 1992. See Section 7.7.

Developers: Evan VanderZee and Michael Heath