Probabilistic Algorithms

2 Random numbers

Index - - Contents - - Previous chapter - Next chapter - - Previous page - Next page

2.2 Pseudo random number generation
Most generators internally produce uniformly distributed integers X_i in (0,X_max) which then are transformed to (0, 1) by u_i := X_i/X_max. To get uniform random numbers x_i in the interval (a, b) we make the transformation
                x_i := a + (b-a)u_i
Often the generation has the functional form
                     X_i := f(C,X_i-1)
where C denotes some free parameters. In this case at most all the numbers [0 ... X_max] can be generated in some order before the numbers will repeat. We then say that the period is X_max+1, i.e., the maximal possible. For a given generator the order is then fixed, the only variable is the choice of starting number, the so called seed. If the period is not the maximal then the generator consists of a set of ordered sequences. Which sequence is chosen depends then on the seed. In order to be able to either repeat with the same or different random numbers it is therefore important that the user can provide the seed.
An example of a generator is the multiplicative congruential generator
               X_i := c₁X_i-1 (mod c₂)
where c₂ is a suitable base (often 10 or 2) raised to some power. X_max=c₂-1 and the seed is X₀. The number Y (mod c) is in [0,c-1] and is obtained by writing Y = nc + Y (mod c). (25 (mod 7) = 4 = 25 - 3x7).
Of course the quality of such pseudo random numbers depends on that only a small part of the sequence is used and that the numbers produced by using some specific seed have good random characteristics.
In some cases it might be possible to find the function f^k(C,X_i) that in a single step gives the i+k:th number where k>1
                f^k(C,X_i) = f(f(...(f(C,X_i))...)
Using the functional form f^k(C,X_i), k=1,2,... for successive pseudo random numbers might help in finding such parameters C and seed which gives maximal length.
The choice of parameters C might also influence on the quality of the pseudo random numbers. The mathematics needed for such analysis is far from trivial and we will not dwell on this here but rather rely on quality generators developed by others.