next up previous

4 N-tuple Generation With LCGs

Suppose we wanted to choose random locations in the unit square for Monte Carlo trials in an application program. A very easy way to choose these points is to select two random values, and , in [0,1) and choosing the point as the current point of interest in the square. More generally, we would generate a point by plotting vs. , where and are of course obtained by scaling successive outputs, and , of the generator by . If we repeat this procedure for a large number of trials, we would like to expect that we will achieve a reasonably good ``covering'' of the unit square and in a ``randomly'' ordered fashion. We would be suspicious of a generator that produced points in the square that were, say, clustered in the bottom half, or perhaps covered the square in some clear order from left to right. Many other forms of obvious nonrandom behavior would be equally unacceptable for most Monte Carlo applications. A characteristic of LCGs is that points selected in this way and plotted in the unit square begin to form regular-looking rows or dotted lines that are easily discernible when enough points have been plotted and when viewed at the proper scale. Over the entire period of an LCG, if all consecutive pairs are plotted, then these rows fill in to become evenly spaced between points.