1

I've had a chance to see some interesting piece of code that was either used as an April Fools joke (update became public on April 1st) or was just a bug, because someone did not understand how to use RNGs.

Question is related to Random class being part of .NET/C#, but maybe other RNGs work the same way.

Simplified version of the code I found, after taking out all the unnecessary details, would look like this:

for ( int i = startI; i < stopI; ++i ) {
    int newValue = new Random( i ).Next( 0, 3 ); // new RNG with seed i generates a single value from 3 options: 0, 1 and 2
    // rest of code
}

I did run simple test of that code in LINQPad to see if what I was observing in program was just my "luck" or whether maybe that's actually how RNG used this way will work. Here's the code:

int lastChoice = -1;
int streakLength = -1;

for ( int i = 0; i < 100000000; ++i ) {
    int newChoice = new Random( i ).Next( 0, 3 );
    if ( newChoice == lastChoice ) {
        streakLength++;
        ( i + ";" + lastChoice + ";" + streakLength ).Dump();
    } else {
        lastChoice = newChoice;
        streakLength = 1;
    }
}

"The End".Dump();

(The Dump() method simply prints the value to the screen)

The result of running this "script" was just "The End", nothing more. It means, that for 100M cycles of generating a random value, not a single time was it able to generate same consecutive values, when having only 3 of them as an option.

So back to my question from the title - does increasing the seed of RNG (specifically the .NET/C#'s Random class, but general answer is also welcome) by one after every (integer) random number generation would ensure that no repeated consecutive values would occur? Or is that just pure luck?

Soul Reaver
  • 2,012
  • 3
  • 37
  • 52
  • The better solution and how the Random class is intended to be used is not create a new instance every time you need a random number, but just to instantiate it once and reuse it. Every time you call Next, it's internal seed will change anyway in order that a subsequent call to Next will return another number. – ckuri Apr 02 '20 at 06:56
  • @ckuri It is not the question of how I should use it, since that is not my code, I am not maintaining it. I am only interested about `Random` (or other RNGs) internals, whether such usage of it would offer me no consecutive repeats of values since that is what I was surprisingly observing. Actual "target" of that code (unless that is a joke as I mentioned), is to at some point give you 4 consecutively repeated values, while I was not able to see even two same digits side by side. – Soul Reaver Apr 02 '20 at 07:02
  • 2
    The internals of the Random class are that if you don't provide a seed it will use the current time as seed. Thus in a tight loop it will get so fast that the clock doesn't change and you will get the same seed and thus sequences, as seen in example 1. If you provide a seed that isn't the case. IIRC the class uses the Mersenne Twister algorithm which is constructed in a way to minimize the chance of equal sequences for different seeds. I think that there are seeds which yield the same sequences, however I don't know if there are consecutive seeds for which this is also applies. – ckuri Apr 02 '20 at 07:11
  • I'm not understanding the point of this question. I get the basic premise. But, there are only ~4 billion possible seed values. Why not just run the program longer (i.e. 40x longer than you have at least once already), and then you'll know for sure what that one specific implementation of a PRNG will do? As a programming exercise, parallelize the test; with just 4 cores, it'd only take 10x the time you've run it for already (the partitions are almost completely independent...you only need to keep track of the first and last result for each and compare those to the adjacent partitions). – Peter Duniho Apr 02 '20 at 10:32
  • If for some reason you really really don't want a simple empirical answer, you can see the code for yourself here: https://referencesource.microsoft.com/#mscorlib/system/random.cs,92e3cf6e56571d5a,references (and no, there is no general answer...each PRNG will have its own characteristics) – Peter Duniho Apr 02 '20 at 10:32
  • Also, note that looking at the code, you can see right away that if you start at `int.MinValue`, the first two iterations will yield the same result. Granted, this is a degenerate case, since both `int.MinValue` and `int.MinValue + 1` are immediately converted to `int.MaxValue`. But it is at least a literally true example of what you're asking about. – Peter Duniho Apr 02 '20 at 10:44

1 Answers1

3

The behavior you show depends on the PRNG.

For many PRNGs, including linear PRNGs such as the one implemented in the .NET Framework's System.Random, if you initialize two instances of a PRNG with consecutive seeds, the number sequences they produce may be correlated with each other, even though each of those sequences produces random-behaving numbers on its own. The behavior you describe in your question is just one possible result of this.

For System.Random in particular, this phenomenon is described in further detail in "A Primer on Repeatable Random Numbers".

Other PRNGs, however, give each seed its own independent pseudorandom number sequence (an example is SFC64 and counter-based PRNGs; see, e.g., "Parallel Random Numbers: As Easy as 1, 2, 3"), and some PRNGs can be "jumped ahead" a huge number of steps to produce pseudorandom number sequences that are independent with respect to each other.

See also:

Peter O.
  • 32,158
  • 14
  • 82
  • 96