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