31.3. Random Numbers¶
31.3.1. Random Numbers¶
The success of randomized algorithms depends on having access to a good random number generator. While modern compilers are likely to include a random number generator that is good enough for most purposes, it is helpful to understand how they work, and to even be able to construct your own in case you don't trust the one provided. This is easy to do.
First, let us consider what a random sequence. From the following list, which appears to be a sequence of "random" numbers?
- 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
- 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
- 2, 7, 1, 8, 2, 8, 1, 8, 2, ...
In fact, all three happen to be the beginning of a some sequence in which one could continue the pattern to generate more values (in case you do not recognize it, the third one is the initial digits of the irrational constant \(e\)). Viewed as a series of digits, ideally every possible sequence has equal probability of being generated (even the three sequences above). In fact, definitions of randomness generally have features such as:
- One cannot predict the next item. The series is unpredictable.
- The series cannot be described more briefly than simply listing it out. This is the equidistribution property.
There is no such thing as a random number sequence, only "random enough" sequences. A sequence is pseudorandom if no future term can be predicted in polynomial time, given all past terms.
Most computer systems use a deterministic algorithm to select pseudorandom numbers. [1] The most commonly used approach historically is known as the Linear Congruential Method (LCM). The LCM method is quite simple. We begin by picking a seed that we will call \(r(1)\). Then, we can compute successive terms as follows.
where \(b\) and \(t\) are constants.
By definition of the \(\bmod\) function, all generated numbers must be in the range 0 to \(t-1\). Now, consider what happens when \(r(i) = r(j)\) for values \(i\) and \(j\). Of course then \(r(i+1) = r(j+1)\) which means that we have a repeating cycle.
Since the values coming out of the random number generator are between 0 and \(t-1\), the longest cycle that we can hope for has length \(t\). In fact, since \(r(0) = 0\), it cannot even be quite this long. It turns out that to get a good result, it is crucial to pick good values for both \(b\) and \(t\). To see why, consider the following example.
Example 31.3.1
Given a \(t\) value of 13, we can get very different results depending on the \(b\) value that we pick, in ways that are hard to predict.
In the case of \(b=5\), the generator goes through only a short sequence before repeating, with the series depending on the seed value chosen. Clearly, a \(b\) value of 5 is far inferior to \(b\) values of 6 or 7 in this example.
If you would like to write a simple LCM random number generator of your own, an effective one can be made with the following formula.
| [1] | Another approach is based on using a computer chip that generates random numbers resulting from "thermal noise" in the system. Time will tell if this approach replaces deterministic approaches. |
