Home | Course Outline | Lectures | Homework | Files

Lecture 2: January 19

Random sequences

A random sequence (or variable) is a sequence of values chosen from a fixed set of distinct elements with each element having a fixed probability of being chosen.

Successive tosses of coin generate a random sequence of "heads" and "tails". The set consists of two distinct elements, namely "heads" and "tails", with equal probabilities of 1/2 = 0.5 of being chosen.

Another example is provided by rolling a die with six faces labeled with 1, 2, 3, 4, 5, or 6 dots. The set here has six elements, and each of them has probability 1/6 of being chosen.

The set need not be finite. Consider dropping a pencil onto a table top point first. If the pencil lands exactly vertically, it is equally likely to come to rest with its tip pointing in any direction: this a contiuous infinity of such directions between 0 and 360 degrees. The probability of the tip pointing in any sector of angular width d equals 360/d.

NOTE: An essential property of random sequences is that a value in the sequence does not depend on the preceding value or on any of the other values in the sequence! It is impossible to predict the value prior to its being selected from the probability distribution!

Pseudo-random number generators

The following program random.java illustrates how a "random" sequence can be generated using a computer program:

// random.java

class random {
    public static void main (String[] args) {
        int n = 10;
        if (args.length > 0)
            n = Integer.parseInt(args[0]);
        boolean useMathRandom = args.length > 1;
        int m = 6075;
        int a = 106;
        int c = 1283;
        int seed = 0;
        for (int i= 0; i < n; i++) {
            if (useMathRandom)
                // use java.lang.Math.random
                seed = (int) (m * Math.random());
            else
                seed = (a * seed + c) % m;
            System.out.println(seed);
        }
    }
}

The program uses a "quick and dirty" linear congruential generator discussed in

§7.1 Uniform Deviates of the "Numerical Recipes" book. Running this program generates the following sequence of 10 random integers in the range [0, 6074]:

> java random
1283
3631
3444
1847
2665
4323
3896
1159
2637
1355

The number of values in the sequence can be set by including one command line argument:

> java random 5
1283
3631
3444
1847
2665

Supplying an arbitrary second command line argument causes the program to use the random number generator provided by the java.lang.Math class.

How good are they?

The values in a pseudo-random sequence are of course entirely predictable from preceding values! Such sequences are not really random. So if one uses a pseudo-random sequence in a calculation which assumes that the sequence is random, one would like to know whether the result of the calculation is reliable. The crucial question is: would one have obtained the same result (within statistical uncertainties) by using a "real" random sequence, such as that obtained by tossing a coin or dropping a pencil on its point?

There are several tests of quality of a pseudo-random number generator. Some of these are discussed in §12.6 Random Number Sequences of the textbook, and others in ""Numerical Recipes".

A very simple check on a generator is to plot the sequence and see if it "looks" random! Here is a plot of 20,000 values generated by

> java random 20000 > random.data
> gnuplot
gnuplot> plot "random.data" with dots

> java random 20000 1 > random.data
> gnuplot
gnuplot> plot "random.data" with dots

Which is the better of the two generators?

Questions or comments: phygons@acsu.buffalo.edu