.NET Framework: Random number generator produces repeating pattern

Question

EDIT: This is not a duplicate, and it's not a result of a naive misunderstanding of how to use a random number generator. Thanks.

I seem to have discovered a repeating pattern in the numbers generated by the System.Random class. I am using a "master" Random instance to generate a seed for a second "main" Random instance. The values produced by this main Random instance exhibit a repeating pattern. In particular, the 3rd number produced is very predictable.

The program below demonstrates the problem. Note that a different seed value is used each 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 random output, but the actual output on my box is:

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

Can anyone explain what's going on here? Changing the OFFSET and LIMIT constants changes the output value, but it's always repeating.

Answer 1

Welcome to the world of non cryptographically strong RNGs. Apparently the built in .NET RNG has a tendency to make the 3rd number it outputs 84 if you limit it to 0 to 200 for its outputs. Take a look at the following version of the program, it shows more of what is going on in the 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 output

|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  |

So there are some strong correlations between the first output of the master RND and the first few outputs of a second RNG that was chained off of the first. The Random RNG is not designed to be "secure" it is designed to be "fast", so things like what you are seeing here are the tradeoffs between being fast and secure. If you don't want things like this to happen you need to use a cryptographicly secure random number generator.

However just switching to a Cryptographic Random Number Generator (CRNG) is not enough you still need to be careful how you use the CRNG. A very similar problem happened with WEP wireless security. Depending on what IV was given in the header it was possible to predict what the seed value (the WEP key) for the random number generator was used to protect the connection. Although they used a CRNG (they used RC4) they did not use it correctly (you have to spit out a few 1000 iterations before the output becomes non predictable).

Answer 2

After running the code myself, it looks like the value returned for the 3rd element - regardless of 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 output looks like this:

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

I have seen code examples in the past that don't use the first 3 or 4 values returned from the Random.Next method. Now I know why. So, a simple work around would be to throw away the first 4 values returned from 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 ported from the original C code.

Answer 3

This is barely more than a comment, but it needs the space. I have manually added indentation and comments to the DotLisp code in the SO textbox only. The code is identical except for whether it is using the (.Next (Random. i)) as seed, or if it just uses the i as the seed itself, and whether it checks the third or fourth .Next random.

I didn't check again right now, but I believe each .Next x always retrieves one new sample and converts that result to something between 0 and x-1.

Using x = (* 15 183) = 2745 came about because looking at smaller ranges and more like 10000 seeds, I found the third .Next x was 'uniform' random, but with two rates of 'uniform'; the smaller range of lesser chosen values was about 177 to 190 contiguous numbers. (You can see this by calling (print-histo h) in the last line, but reduce the number of seeds tested :-) ) When I increased the number of seeds I increased this range.

The code just accumulates a count for each .Next x result and displays the count of those counts. For a true uniform random .Next x this should produce a nice bell curve, as seen by the last case (fourth .Next, sequential 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)))
    (x h (+ 1 (or (x h) 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 skewed bell curve and another small flat bell curve or just a very non uniform 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)))
    (x h (+ 1 (or (x h) 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 bell curves with the 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)))
    (x h (+ 1 (or (x h) 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 bell curves.

(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)))
   (x h (+ 1 (or (x h) 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 summary, it looks like there's two separate issues going on: the third sample is not very uniform in general and the seeds produced by the first sample either emphasise the problem or show a separate issue.