.NET Framework: random number generator creates a repeating pattern

Question

EDIT: This is not a duplicate, and it is not the result of a naive misunderstanding of using a random number generator. Thank.

I seem to have found a duplicate pattern in the numbers generated by the System.Random class. I use the "master" random instance to generate seed for the second "main" random instance. The values ​​obtained in this basic random instance have a repeating pattern. In particular, the generated 3rd number is very predictable.

The program below shows the problem. Note that every other value is used every time through the loop.

using System; class Program { static void Main(string[] args) { // repeat experiment with different master RNGs for (int iMaster = 0; iMaster < 30; ++iMaster) { // create master RNG var rngMaster = new Random(iMaster + OFFSET); // obtain seed from master RNG var seed = rngMaster.Next(); // create main RNG from seed var rngMain = new Random(seed); // print 3rd number generated by main RNG var ignore0 = rngMain.Next(LIMIT); var ignore1 = rngMain.Next(LIMIT); var randomNumber = rngMain.Next(LIMIT); Console.WriteLine(randomNumber); } } const int OFFSET = 0; const int LIMIT = 200; } 

I think this should produce arbitrary output, but the actual output on my box is:

 84 84 84 84 84 84 84 84 84 84 84 ... 

Can someone explain what is going on here? Changing the OFFSET and LIMIT constants changes the output value, but it always repeats.

Answer 1

Welcome to the world of non-cryptographically strong RNGs. Apparently, the built-in RNG.NET tends to make the 3rd number, which it issues 84 if you limit it to 0 to 200 for your exits. Take a look at the next version of the program, it shows more of what happens on output.

 class Program { static void Main(string[] args) { Console.WindowWidth = 44; Console.WindowHeight = 33; Console.BufferWidth = Console.WindowWidth; Console.BufferHeight = Console.WindowHeight; string template = "|{0,-5}|{1,-11}|{2,-5}|{3,-5}|{4,-5}|{5,-5}|"; Console.WriteLine(template, "s1", "s2", "out1", "out2", "out3", "out4"); Console.WriteLine(template, new String('-', 5), new String('-', 11), new String('-', 5), new String('-', 5), new String('-', 5), new String('-', 5)); // repeat experiment with different master RNGs for (int iMaster = 0; iMaster < 30; ++iMaster) { int s1 = iMaster + OFFSET; // create master RNG var rngMaster = new Random(s1); // obtain seed from master RNG var s2 = rngMaster.Next(); // create main RNG from seed var rngMain = new Random(s2); var out1 = rngMain.Next(LIMIT); var out2 = rngMain.Next(LIMIT); var out3 = rngMain.Next(LIMIT); var out4 = rngMain.Next(LIMIT); Console.WriteLine(template, s1, s2, out1, out2, out3, out4); } Console.ReadLine(); } const int OFFSET = 0; const int LIMIT = 200; } 

Here is the conclusion

 | s1 | s2 | out1 | out2 | out3 | out4 |
 | ----- | ----------- | ----- | ----- | ----- | ----- |
 | 0 | 1559595546 | 170 | 184 | 84 | 84 |
 | 1 | 534011718 | 56 | 177 | 84 | 123 |
 | 2 | 1655911537 | 142 | 171 | 84 | 161 |
 | 3 | 630327709 | 28 | 164 | 84 | 199 |
 | 4 | 1752227528 | 114 | 157 | 84 | 37 |
 | 5 | 726643700 | 0 | 150 | 84 | 75 |
 | 6 | 1848543519 | 86 | 143 | 84 | 113 |
 | 7 | 822959691 | 172 | 136 | 84 | 151 |
 | 8 | 1944859510 | 58 | 129 | 84 | 189 |
 | 9 | 919275682 | 144 | 122 | 84 | 28 |
 | 10 | 2041175501 | 30 | 115 | 84 | 66 |
 | 11 | 1015591673 | 116 | 108 | 84 | 104 |
 | 12 | 2137491492 | 2 | 102 | 84 | 142 |
 | 13 | 1111907664 | 88 | 95 | 84 | 180 |
 | 14 | 86323836 | 174 | 88 | 84 | 18 |
 | 15 | 1208223655 | 60 | 81 | 84 | 56 |
 | 16 | 182639827 | 146 | 74 | 84 | 94 |
 | 17 | 1304539646 | 31 | 67 | 84 | 133 |
 | 18 | 278955818 | 117 | 60 | 84 | 171 |
 | 19 | 1400855637 | 3 | 53 | 84 | 9 |
 | 20 | 375271809 | 89 | 46 | 84 | 47 |
 | 21 | 1497171628 | 175 | 40 | 84 | 85 |
 | 22 | 471587800 | 61 | 33 | 84 | 123 |
 | 23 | 1593487619 | 147 | 26 | 84 | 161 |
 | 24 | 567903791 | 33 | 19 | 84 | 199 |
 | 25 | 1689803610 | 119 | 12 | 84 | 38 |
 | 26 | 664219782 | 5 | 5 | 84 | 76 |
 | 27 | 1786119601 | 91 | 198 | 84 | 114 |
 | 28 | 760535773 | 177 | 191 | 84 | 152 |
 | 29 | 1882435592 | 63 | 184 | 84 | 190 |

Thus, there are some strong correlations between the first output of the main RND and the first few outputs of the second RNG, which was shackled first. Random RNG is not designed to be “safe,” it is designed to be “fast,” so things like what you see here are trade-offs between fast and safe. If you don’t need such things, you need to use a cryptographically secure random number generator.

However, simply switching to a cryptographic random number generator (CRNG) is not enough, you still need to be careful how you use CRNG. A very similar issue occurred with WEP wireless security. Depending on what was indicated in the header, it was possible to predict which value for the initial value (WEP key) for the random number generator was used to protect the connection. Although they used CRNG (they used RC4), they did not use it correctly (you need to spit out a few 1000 iterations before the output becomes unpredictable).

Answer 2

After running the code, it looks like a return value for the third element - regardless of the fact that the seed is a pretty bad flaw. I modified your code as follows to make it a little more flexible:

 public static void TestRNG() { const int OFFSET = 0; const int LIMIT = 200; const int RndCount = 50; const int FieldsPerLine = 10; int Rnd; for (int iMaster = 0; iMaster < RndCount; ++iMaster) { // create master RNG var rngMaster = new Random(iMaster + OFFSET); // obtain seed from master RNG var seed = rngMaster.Next(); // create main RNG from seed var rngMain = new Random(seed); // print 3rd number generated by main RNG Console.WriteLine(); for (int Loop = 0; Loop < FieldsPerLine; Loop++) { Rnd = rngMain.Next(LIMIT); Console.Write(Rnd.ToString().PadLeft(3) + " "); } } } 

The result is as follows:

 170 184 84 84 5 104 164 113 181 147 56 177 84 123 150 132 149 56 142 88 142 171 84 161 94 160 134 199 102 28 28 164 84 199 39 189 119 141 62 168 114 157 84 37 184 17 105 84 23 108 0 150 84 75 129 45 90 27 183 48 86 143 84 113 74 74 75 169 144 188 172 136 84 151 18 102 60 112 104 129 58 129 84 189 163 130 46 55 64 69 144 122 84 28 108 159 31 197 25 9 30 115 84 66 53 187 16 140 185 149 116 108 84 104 198 15 1 82 145 89 2 102 84 142 142 44 186 25 106 29 88 95 84 180 87 72 172 168 66 170 174 88 84 18 32 100 157 110 26 110 60 81 84 56 177 129 142 53 187 50 146 74 84 94 121 157 127 196 147 190 31 67 84 133 66 185 113 138 108 130 117 60 84 171 11 14 98 81 68 70 3 53 84 9 156 42 83 24 28 11 89 46 84 47 101 70 68 166 189 151 175 40 84 85 45 99 54 109 149 91 61 33 84 123 190 127 39 51 109 31 147 26 84 161 135 155 24 194 70 171 33 19 84 199 80 184 9 137 30 112 119 12 84 38 25 12 195 79 190 52 5 5 84 76 169 40 180 22 151 192 91 198 84 114 114 69 165 165 111 132 177 191 84 152 59 97 150 107 71 72 63 184 84 190 4 125 136 50 32 12 149 177 84 28 148 154 121 193 192 153 35 171 84 66 93 182 106 135 153 93 121 164 84 104 38 10 91 78 113 33 7 157 84 143 183 39 77 20 73 173 93 150 84 181 128 67 62 163 34 113 179 143 84 19 72 95 47 106 194 53 65 136 84 57 17 124 32 48 154 194 151 129 84 95 162 152 18 191 115 134 37 122 84 133 107 180 3 134 75 74 123 115 84 171 52 9 188 76 35 14 9 108 84 10 196 37 173 19 196 154 95 102 84 48 141 65 158 162 156 95 181 95 84 86 86 94 144 104 117 35 66 88 84 124 31 122 129 47 77 175 152 81 84 162 176 150 114 189 37 115 38 74 84 0 120 179 99 132 198 55 124 67 84 38 65 7 85 75 158 195 10 60 84 76 10 35 70 17 118 136 96 53 84 115 155 64 55 160 79 76 182 46 84 153 99 92 40 103 39 16 

In the past, I saw code examples that do not use the first 3 or 4 values ​​returned by the Random.Next method. Now I know why. Thus, a simple job is to throw away the first 4 values ​​returned by the Random.Next method.

If you are interested in a very fast random number generator that also produces high-quality random numbers, then check out the TinyMT project - which I have ported from C.

Answer 3

This is just a comment, but he needs space. I manually added padding and comments to the DotLisp code only in the SO text box. The code is identical, except if it uses (.Next (Random. i)) as a seed, or simply uses i as a seed itself and whether it checks the third or fourth random .Next case.

I did not check again right now, but I believe that every .Next x always extracts one new pattern and converts the result to something between 0 and x-1 .

The use of x = (* 15 183) = 2745 happened because, looking at smaller ranges and more similar to 10000 seeds, I found that the third .Next x was "uniform" random, but with two "uniformity" speeds; a smaller range of smaller selected values ​​ranged from 177 to 190 adjacent numbers. (You can see this by calling (print-histo h) on the last line, but decrease the number of seeds tested :-)) When I increased the number of seeds, I increased this range.

The code simply accumulates a counter for each .Next x result and displays the counter of these counters. For a true uniform random .Next x this should lead to a good bell curve, as seen from the latter case (fourth .Next , consecutive seeds).

 (let (h (Hashtable.)) (dotimes i 6553600 (lets (s (.Next (Random. i)) r (Random. s)) ; using random seed (dotimes j 2 r.Next) ; skipping 2 results (let (x (r.Next (* 15 183))) (xh (+ 1 (or (xh) 0)))))) (print-histo (histo h.Values))) 

  1 2368 3 2369 11 2370 20 2371 11 2372 12 2373 17 2374 15 2375 8 2376 13 2377 20 2378 11 2379 3 2380 8 2382 94 2383 253 2384 296 2385 240 2386 248 2387 238 2388 233 2389 252 2390 236 2391 321 2392 163 2393 18 2394 

A beveled bell curve and another small flat bell curve or just a very uneven tail.

 (let (h (Hashtable.)) (dotimes i 6553600 (lets (s (.Next (Random. i)) r (Random. s)) ; using random seed (dotimes j 3 r.Next) ; skipping 3 results (let (x (r.Next (* 15 183))) (xh (+ 1 (or (xh) 0)))))) (print-histo (histo h.Values))) 

  11 2377 43 2378 90 2379 114 2380 138 2381 133 2382 132 2383 143 2384 127 2385 147 2386 130 2387 136 2388 145 2389 223 2390 430 2391 354 2392 177 2393 72 2394 

Two curved bells with one wide and one narrow.

 (let (h (Hashtable.)) (dotimes i 6553600 (let (r (Random. i)) ; using sequential seed (dotimes j 2 r.Next) ; skipping 2 results (let (x (r.Next (* 15 183))) (xh (+ 1 (or (xh) 0)))))) (print-histo (histo h.Values))) 

  12 2380 104 2381 143 2382 123 2383 106 2384 55 2385 115 2386 387 2387 511 2388 537 2389 454 2390 194 2391 4 2392 

Effectively two curved bells.

 (let (h (Hashtable.)) (dotimes i 6553600 (let (r (Random. i)) ; using sequential seed (dotimes j 3 r.Next) ; skipping 3 results (let (x (r.Next (* 15 183))) (xh (+ 1 (or (xh) 0)))))) (print-histo (histo h.Values))) 

  18 2384 154 2385 432 2386 758 2387 798 2388 477 2389 105 2390 3 2391 

Finally, a simple bell curve.

In general, it seems that there are two separate questions: the third sample is not very uniform at all, and the seeds created in the first sample either emphasize the problem or show a separate problem.