2 Random numbers

2.7 Generating random digits

For the congruential methods we could let the new number to be generated depend not just on the previous number generated but on some of the previously generated numbers

            Xi = a1Xi-1+...+akXi-k (mod m)

This will make the period to be of the order of m^k. One special case is to let m=2 so that the generator generates binary digits. Then of course a_i are 0 or 1 with a_k=1. By choosing the parameters carefully the maximal period 2^k-1 is obtained.

Illustration: Let k=2, i.e.

          bi=a1bi-1+bi-2 (mod 2)

We have two possibilities 1) a₁=0, 2) a₁=1.

1) b_i = b_i-2 (mod m). Starting with b₀=0 and b₁=1 (any combination except 0, 0 can be used) we obtain the sequence 011... i.e., a period of 1.

2)b_i=b_i-1+b_i-2 (mod 2). Starting with b₀=0 and b₁=1 we obtain the sequence 011 011 ... i.e., the maximal period 3 (=2²-1).

The problem of finding optimal weights a_i is equivalent to finding primitive polynomials of degree k (mod 2). We may use k adjacent digits in the sequence to obtain random numbers with k digits. In case 2), k=2 we obtain the sequence 01, 11, 10, or written in decimal 1, 3, 2, i.e., all numbers representable with two binary digits except 0.

2.8 Combining generators

MacLaren and Marsaglia (see Knuth) have suggested the following highly recommended algorithm to combine two random sequences X_i and Y_i into a "considerably more random" sequence by using an auxilary vector V[0],...,V[k-1] originally filled with the first k values of the X-sequence:

    1.Set X, Y equal to the next numbers of the sequences
      Xi, Yi respectively.
    2.Set j <- floor(kY/m), where m is the modulus 
      used in  Yi; i.e. j is a random number in [0,k-1].
    3. Output V[j] and then set V[j] <- Xi.