We often think of choosing a random number as selecting one likely to occur as any other. Although each of us probably has a good intuitive sense of what we mean by "random number" the formal, mathematical notion can be a bit slippery. In fact, we usually think of sequences of random numbers. In this sense, any number in the sequence should have nothing to do with any other numbers of the sequence. So for example, the sequence of numbers 1,1,2,3,5,8,... is clearly not a random sequence in the above sense as each number is intimately tied to others in the sequence (each number is the sum of its two predecessors). On the other hand, the following sequence of integers appears to be random in this informal sense:
In some sense, there is no such thing as a computer generator of random numbers. All computers generate sequences of random numbers according to some prescribed algorithm. By design, such sequences are purely deterministic. Use the same algorithm, start with the same initial configuration, and you will get the exact same sequence.
All computer languages use random number generators to produce sequences in which each number is obtained from its successor by repeated application of a well-defined algorithm. These sequences start with a seed and apply the algorithm repeatedly to generate numbers. One of the well-known random number generators is known as the linear congruential method.
Starting with a seed , successive numbers in the sequence are determined by
where a is referred to as the multiplier, c is called the increment, and m is called the modulus. The resulting series is mapped onto region of interests. Although the linear congruential method can generate fairly good sequences of random numbers, it can fall into some short cycles. For example consider the following code:
OPTIONAL V.1a Evaluate for different , , . Choose and relatively prime (having no factors in common): What conclusion can you draw from this experiment?
The relation between ,, is quite complicated and follows from number theory (see Knuth "The Art of Computer Programming", Addison-Wesley, Vol II). What is easy to see is that a small modulus can lead to short cycles if you are not careful in how the increment and multiplier are chosen. (For a full treatment of the linear congruential method, see Weiss, G.H., "Random numbers and their Applications", American Scientist 71, 65-71, 1983). What is also quite easy to see is that this method is completely deterministic. Start with the same seed (i.e. the same x[0]), and the same sequence will be generated.
Although you can be much more careful in the choice of parameters (in particular, choosing a large modulus), and you can try variants such as a quadratic congruential method: the main point to keep in mind is that such methods are decidedly deterministic and have finite cycles.
OPTIONAL V.1b Change the code to the quadratic congruential method. Repeat experiment V.1b: What conclusion can you draw from this experiment?
|