Few Loop Theorem

[G Anthony Kent]

Tom Erber of the Illinois Institute of Technology has published a paper on his "Few Loop Theorem" wherein he proposes that all digital random number generators eventually fall into one or another of a few possible endless loops.

 

Has anyone ever heard of this? What are the consequences? How can one program a computer to recognize if a random number generator has fallen into a loop?

[CraigD]

Tom Erber of the Illinois Institute of Technology has published a paper on his "Few Loop Theorem" wherein he proposes that all digital random number generators eventually fall into one or another of a few possible endless loops.

 

Has anyone ever heard of this?

I think you’re referring to The simulation of random processes on digital computers: unavoidable order, (1983) T Erber, T.M Rynne, J. Computational Physics, 49, 394-419.

 

I’ve not read the paper, but believe I understand the key idea underlying it – one at least as old as ca. 1975, when I encountered it – is that arithmetic random number generators aren’t actually random, but pseudorandom sequence generators. They’re always in a repeating loop. The size of that loop, however, depends on the size of the number used generate it – more precisely, assuming a good algorithm, the number of numbers before a repeat – the period – is about the square root of the largest number the calculator can fully represent.

 

I think it’s helpful to see a simple example of a pseudorandom number generating algorithm. Here’s one:

 

[math]r_{n+1} = (r_n +a ) \mod b[/math]

 

Here’s an example of its output using it with a=173, b=271, and [imath]r_0=0[/imath]:

0 173 75 248 150 52 225 127 29 202 104 6 179 81 254 156 58 231 133 35 208 110 12 185 87 260 162 64 237 139 41 214 116 18 191 93 266 168 70 243 145 47 220 122 24 197 99 1 174 76 249 151 53 226 128 30 203 105 7 180 82 255 157 59 232 134 36 209 111 13 186 88 261 163 65 238 140 42 215 117 19 192 94 267 169 71 244 146 48 221 123 25 198 100 2 175 77 250 152 54 227 129 31 204 106 8 181 83 256 158 60 233 135 37 210 112 14 187 89 262 164 66 239 141 43 216 118 20 193 95 268 170 72 245 147 49 222 124 26 199 101 3 176 78 251 153 55 228 130 32 205 107 9 182 84 257 159 61 234 136 38 211 113 15 188 90 263 165 67 240 142 44 217 119 21 194 96 269 171 73 246 148 50 223 125 27 200 102 4 177 79 252 154 56 229 131 33 206 108 10 183 85 258 160 62 235 137 39 212 114 16 189 91 264 166 68 241 143 45 218 120 22 195 97 270 172 74 247 149 51 224 126 28 201 103 5 178 80 253 155 57 230 132 34 207 109 11 184 86 259 161 63 236 138 40 213 115 17 190 92 265 167 69 242 144 46 219 121 23 196 98 0

 

The actual [imath]r_n[/imath] terms aren’t very goodly random, so it’s good to improve them by making them smaller with something like the following

 

[math]s_n = r_n \mod d[/math]

 

Using d=100, this transform the previous output to:

0 73 46 19 92 65 38 11 84 57 30 3 76 49 22 95 68 41 14 87 60 33 6 79 52 25 98 71 44 17 90 63 36 9 82 55 28 1 74 47 20 93 66 39 12 85 58 31 4 77 50 23 96 69 42 15 88 61 34 7 80 53 26 99 72 45 18 91 64 37 10 83 56 29 2 75 48 21 94 67 40 13 86 59 32 5 78 51 24 97 70 43 16 89 62 35 8 81 54 27 0

 

What are the consequences?

Since modern computer can fully represent very large numbers, the practical consequences are not too bad.

 

Practically, it’s less important that a pseudorandom number generator have a large period than it is that it exhibit good, random-like behavior.

 

In many cases, it’s useful that computer-generated pseudorandom numbers are predictable when their algorithm and seed number ([imath]r_0[/imath] in the above example), are know, because it allows a program to using them to be run with identical results as many times as needed for debugging or other analysis.

 

In other cases, such as cryptography, it’s not useful to know the seen number. Most present-day hardware and software is able to obtain seed numbers that are hard or impossible to know, by getting them from non-digital sources, such as the temperature of an electronic component, which is useful in these cases.

 

How can one program a computer to recognize if a random number generator has fallen into a loop?

As I noted above, one doesn’t need to, because one knows that any PRNG is always “in a loop”.