“Resetting” pseudo-random number generator seed mu

问题:

Today, my friend had a thought that setting the seed of a pseudo-random number generator multiple times using the pseudo-random number generated to "make things more randomized".

An example in C#:

// Initiate one with a time-based seed
Random rand = new Random(milliseconds_since_unix_epoch());
// Then loop for a_number_of_times...
for (int i = 0; i < a_number_of_times; i++)
{
    // ... to initiate with the next random number generated
    rand = new Random(rand.Next());
}
// So is `rand` now really random?
assert(rand.Next() is really_random);

But I was thinking that this could probably increase the chance of getting a repeated seed being used for the pseudo-random number generator.

Will this

1. make things more randomized,
2. making it loop through a certain number of seeds used, or
3. does nothing to the randomness (i.e. neither increase nor decrease)?

Could any expert in pseudo-random number generators give some detailed explanations so that I can convince my friend? I would be happy to see answers explaining further detail in some pseudo-random number generator algorithm.

回答1:

There are three basic levels of use for pseudorandom numbers. Each level subsumes the one below it.

1. Unexpected numbers with no particular correlation guarantees. Generators at this level typically have some hidden correlations that might matter to you, or might not.
2. Statistically-independent number with known non-correlation. These are generally required for numerical simulations.
3. Cryptographically secure numbers that cannot be guessed. These are always required when security is at issue.

Each of these is deterministic. A random number generator is an algorithm that has some internal state. Applying the algorithm once yields a new internal state and an output number. Seeding the generator means setting up an internal state; it's not always the case that the seed interface allows setting up every possible internal state. As a good rule of thumb, always assume that the default library random() routine operates at only the weakest level, level 1.

To answer your specific question, the algorithm in the question (1) cannot increase the randomness and (2) might decrease it. The expectation of randomness, thus, is strictly lower than seeding it once at the beginning. The reason comes from the possible existence of short iterative cycles. An iterative cycle for a function F is a pair of integers n and k where F^(n) (k) = k, where the exponent is the number of times F is applied. For example, F^(3) (x) = F(F(F(x))). If there's a short iterative cycle, the random numbers will repeat more often than they would otherwise. In the code presented, the iteration function is to seed the generator and then take the first output.

To answer a question you didn't quite ask, but which is relevant to getting an understanding of this, seeding with a millisecond counter makes your generator fail the test of level 3, unguessability. That's because the number of possible milliseconds is cryptographically small, which is a number known to be subject to exhaustive search. As of this writing, 2^50 should be considered cryptographically small. (For what counts as cryptographically large in any year, please find a reputable expert.) Now the number of milliseconds in a century is approximately 2^(41.5), so don't rely on that form of seeding for security purposes.

回答2:

Your example won't increase the randomness because there is no increase in entropy. It is simply derived from the execution time of the program.

Instead of using something based of the current time, computers maintain an entropy pool, and build it up with data that is statistically random (or at least, unguessable). For example, the timing delay between network packets, or key-strokes, or hard-drive read times.

You should tap into that entropy pool if you want good random numbers. These are known as Cryptographically secure pseudorandom number generators.

In C#, see the Cryptography.RandomNumberGenerator Class for the right way to get a secure random number.

回答3:

This will not make things more "random".

Our seed determines the random looking but completely determined sequence of numbers that rand.next() gives us.

Instead of making things more random, your code defines a mapping from your initial seed to some final seed, and, given the same initial seed, you will always end up with the same final seed.

Try playing with this code and you will see what I mean (also, here is a link to a version you can run in your browser):

int my_seed = 100; // change my seed to whatever you want
Random rand = new Random(my_seed);
for (int i = 0; i < a_number_of_times; i++)
{
    rand = new Random(rand.Next());
}
// does this print the same number every run if we don't change the starting seed?
Console.WriteLine(rand.Next()); // yes, it does

The Random object with this final seed is just like any other Random object. It just took you more time then necessary to create it.