Seeding Multiple Random Number Generators

Question

I have recently been discussing the initialisation of multiple random number generators of the same type in the comments of another post and in that discussion we asked the following questions:

1) Is it a good idea to create multiple instances of the same random number generator with different seeds and use these random number generators in different parts of the program?

2) In particular, can the technique of creating random number generators using the .Net Random class, seeded as below, and using each RNG in different program contexts cause problems:

int size = 64;  // The number of RNGs to use
int seed;       // Get seed using some normal technique
Random[] r = new Random[size];

for (int i = 0; i < size; i++)
{
    r[i] = new Random(seed + i);
}

3) What would you recommend instead if multiple streams of random numbers are required?

4) How would you recommend generating random numbers when thread safety is required?

Answer 1

1) Is it a good idea to create multiple instances of the same random number generator with different seeds and use these random number generators in different parts of the program?

No. The above scheme is in general not recommended.

In his book, The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, third edition, 1997, Dr. Knuth states that

It is not easy to invent a foolproof source of random numbers.

In this case, I point out that taking subsequences from a random sequence may be less random than the original sequence of random numbers:

• Random Numbers
• PCG

Notice that Micosoft's Random implementation is based on a subractive lagged-fibonacci generator:

• Reference Source - System.Random

This kind of random number generator is known for an inbuilt three-point correlation, after all, we're generating the next random number:

These kinds of Random Number Generators also depend heavily on the initialisation of their initial 55 number state. Poor initialisation may lead to poor random numbers. In the above case, similar states, may result in correlated random numbers from each of the different random number generators. Microsoft even recommends against this in their MSDN post about System.Random: MSDN The System.Random class and thread safety:

Instead of instantiating individual Random objects, we recommend that you create a single Random instance to generate all the random numbers needed by your app.

We shall look at an example where a particular initialisation creates strong correlation between the different random number generators and look for alternatives.

2) I have implemented a program that attempts to initialise 64 instances of Random as described above so that we observe any visible flaws. I chose a particular initialisation as a proof of concept:

int size = 64;    // The number of random numbers generators
int length = 20;  // The number of random numbers from each generator
int steps = 18;   // Move 18 steps forward in the beginning to show a particular phenomenon

Random[] r = new Random[size];

for (int i = 0; i < size; i++)
{
     r[i] = new Random(i + 1);

     // move RNG forward 18 steps
     for (int j = 0; j < steps; j++)
     {
          r[i].Next(3);
     }
}


for (int i = 0; i < size; i++)
{
     for (int j = 0; j < length; j++)
     {
          Console.Write(r[i].Next(3) + ", ");  // Generate a random number, 0 represents a small number, 1 a medium number and 2 a large number
     }

     Console.WriteLine();
}

This program generates the output shown here, each row represents the output from another RNG:

Notice that the highlighted columns: at particular places the RNGs seem to synchronise and produce output that does not look independent from each other.

I also wish to add another note, that creating a single list of random numbers and taking one random number from the list of each row also produces poor looking random numbers (the RNG being used here is known to have fail some statistical after all!).

3) The type of RNG used depends on your context. Some may be happy with the above output. In other cases, the RNG used may be unusable (Monte Carlo Simulation and Cryptography are two scenarios where System.Random should never be used, even for one stream of random numbers).

If you need to extract multiple subsequences of Random Numbers, find an RNG that has been designed for that purpose:

• PCG

4) Finally, what if I want to use System.Random in multiple threads? Microsoft MSDN has the answer in the same link I referred to above:

• MSDN The System.Random class and thread safety