| 1 |
These are some simple design notes to document this program and to guide |
| 2 |
further work. |
| 3 |
|
| 4 |
This program is designed to do the following: |
| 5 |
|
| 6 |
a) Encapsulate every RNG known to humans for testing. We will use the |
| 7 |
GSL both for its rich supply of ready-to-test RNG's and for its |
| 8 |
relatively simple and consistent encapsulation of any new RNG's we add |
| 9 |
-- /dev/random is already encapsulated and can serve as a template for |
| 10 |
future work. [1/16/03 rgb] |
| 11 |
|
| 12 |
b) test speed of the available RNG's. Both: |
| 13 |
i) In "native/standard" subroutine calls (with the subroutine call |
| 14 |
overhead included). [This is done, 1/16/03, rgb] |
| 15 |
ii) In a custom "vector" form, where a whole block of dedicated |
| 16 |
memory is filled in one pass from a given algorithm, and |
| 17 |
subsequently accessed via a macro that only calls for a refill |
| 18 |
when the vector is exhausted. |
| 19 |
|
| 20 |
c) test quality of the available RNG's. There are at least three |
| 21 |
primary sources of tests that will be used in this tool. |
| 22 |
|
| 23 |
i) RGB tests. These are the tests I myself have implemented. To |
| 24 |
the best of my knowledge these are new, although of course |
| 25 |
my knowledge is far from complete. |
| 26 |
|
| 27 |
ii) DIEHARD, by Dr. George Marsaglia of FSU. This is a well-known |
| 28 |
and venerable "battery of tests" of RNG's. |
| 29 |
|
| 30 |
iii) NIST STS/FIPS (NIST special publication 800-22, revised |
| 31 |
5/15/2001). This is also a suite of RNG tests, with some |
| 32 |
overlap with DIEHARD. I will probably implement only selected |
| 33 |
tests from this suite at least at first, as some of them |
| 34 |
appear to be relatively weak compared to e.g. rgb_binomial |
| 35 |
and to test basically the same thing. |
| 36 |
|
| 37 |
iv) Additional tests that are to be found on the web and in the |
| 38 |
literature, where they appear to test things not |
| 39 |
well-represented in tests already implemented in one suite |
| 40 |
or another. |
| 41 |
|
| 42 |
d) test quality of any input set of "random" data according to i-iv in |
| 43 |
c). This will let us test arbitrary RNG's via their data, including and |
| 44 |
especially hardware generators. Note that hardware generators available |
| 45 |
as "devices" will be interfaced via a). This step will only be |
| 46 |
implemented when enough tests to make it worthwhile are already |
| 47 |
implemented. |
| 48 |
|
| 49 |
|
| 50 |
Addendum and explanation of copyright issues. |
| 51 |
|
| 52 |
The STS was written by a variety of authors: |
| 53 |
|
| 54 |
Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, |
| 55 |
Stefan Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert, |
| 56 |
James Dray, San Vo. |
| 57 |
|
| 58 |
None of the actual code in the STS suite has been used in this tool -- |
| 59 |
all testing routines have been written using only the STS published |
| 60 |
document as an excellent reference. GSL routines have been used |
| 61 |
throughout, where possible, for computing things such as erfc or Q. |
| 62 |
Since I am not using their code, I am omitting their copyright notice, |
| 63 |
but wish to acknowledge their documentation of the selected tests |
| 64 |
anyway. All the code in dieharder is GPL open source in any event, but |
| 65 |
academic credit matters. |
| 66 |
|
| 67 |
Similarly, DIEHARD is the work of George Marsaglia. Dr. Marsaglia |
| 68 |
doen't have any written copyright notice or license terms that I could |
| 69 |
find in the sources provided on the website where he openly distributes |
| 70 |
source for his own suite, but in keeping with a minor design goal of |
| 71 |
completely original GPL code, all the DIEHARD algorithms have also been |
| 72 |
completely rewritten without directly utilizing any of the actual |
| 73 |
diehard code. Fortunately, Dr. Marsaglia also provides clear |
| 74 |
documentation for his test suite, making it a fairly simple matter to |
| 75 |
implement the tests. Source code WAS examined (but not copied) to |
| 76 |
clarify places where the documentation of the tests was openly erroneous |
| 77 |
(as in the parking lot test) or unclear but dieharder code is completely |
| 78 |
original and its development thoroughly documented in CVS and (later) |
| 79 |
SVN tree form, checkin by checkin. |
| 80 |
|
| 81 |
The relatively few tests I have added are motivated by a desire to get a |
| 82 |
less ambiguous answer than many of these tests provide. In many cases |
| 83 |
it is not (or should not) be correct to say that one "accepts" a |
| 84 |
generator as being a good one just because a test run of the generator |
| 85 |
has a p-value significantly greater than 0. A few moment's |
| 86 |
experimentation, especially with relatively small data sets, should |
| 87 |
convince one that even "bad" RNG's can sometimes, or even frequently, |
| 88 |
return an "acceptable" p-value. Only when the size of the test is |
| 89 |
increased, or the test is repeatedly run with different seeds, does it |
| 90 |
become apparent that although it sometimes performs acceptably (the |
| 91 |
result of a run isn't inconsistent with the generator producing "real" |
| 92 |
random numbers) it sometimes performs so poorly that the result can |
| 93 |
>>never<< be explained or believed for a true random number generator. |
| 94 |
|
| 95 |
That is, while a really poor p-value allows us to reject the hypothesis |
| 96 |
that the tested generator is random, acceptable p-values, even a fair |
| 97 |
number of them in repeated tests, do not usually support accepting the |
| 98 |
hypothesis -- at best they don't support rejection. |
| 99 |
|
| 100 |
Running a test repeatedly to generate a full distribution of results and |
| 101 |
then directly comparing the entire distribution with theory appears to |
| 102 |
provide greater sensitivity and accuracy in the rejection process than |
| 103 |
"simple" tests that generate only a single quantity. This motivated the |
| 104 |
rgb_binomial test, which has proven very good at rejecting "bad" rng's. |
| 105 |
|
| 106 |
Similarily, it may prove useful to directly generate an empirical |
| 107 |
distribution of p-values themselves (repeating a test many times with |
| 108 |
different seeds and binning the p-values) and compare it to the expected |
| 109 |
distribution (which might work for erfc-based p-values, although not so |
| 110 |
well for Q-based p-values). This can replace running a test many times |
| 111 |
looking for an anomalous number of "poor" p-values mixed in with ones |
| 112 |
that are not so poor as to lead to immediate rejection. |
| 113 |
|
| 114 |
Contributions of rng's (consistently GSL-wrapped as e.g. dev_random.c |
| 115 |
demonstrates) and/or additional tests would be most welcome. |
| 116 |
|
| 117 |
rgb |
| 118 |
|
| 119 |
|
| 120 |
STS Critique, By Statistic |
| 121 |
|
| 122 |
The Monobit Statistic |
| 123 |
|
| 124 |
The monobit statistic checks to make sure that the raw number of 1's and |
| 125 |
0's approximately balance in a given bitstring. This is actually a |
| 126 |
decent thing to test, but there is a better way to test it. Given a |
| 127 |
relatively short bitstring (e.g. n<=160 bits), the probability that it |
| 128 |
will have k bits according to the null hypothesis is p(n,k,1/2) (the |
| 129 |
binomial distribution of outcomes over n independent trials, each with |
| 130 |
p=1/2). If one runs m runs of n independent trials each, and |
| 131 |
accumulates X[k] (the count histogram for each possible value of output |
| 132 |
k in [0,n]) then one has X[k], the expected value histogram Y(k) = |
| 133 |
m*p(n,k,1/2), and sigma(k) = sqrt(m)*p(n,k,1/2). From this it is simple |
| 134 |
to compute a p-value from an incomplete gamma function for the |
| 135 |
>>details<< of the distribution of 1's. One can even do it two ways -- |
| 136 |
with an independent random number seed for each of the m samples, or |
| 137 |
by simply running the rng with its original seed long enough to produce |
| 138 |
m*n bits. |
| 139 |
|
| 140 |
This binomial test is stronger than the monobit test. Any result |
| 141 |
histogram that passes it necessarily passes the monobit test for the |
| 142 |
aggregate distribution with m*n bits (as I hope is obvious -- passing it |
| 143 |
means that the distribution is binomial in detail, not just uniformly |
| 144 |
balanced. However, it is simple enough to compute the monobit result |
| 145 |
more or less in passing in the binomial test by simply summing the count |
| 146 |
histogram at the end or aggregating a total 1-bit count as one goes. In |
| 147 |
that case one can generate two p-values -- a p-value for the monobit |
| 148 |
test and one for the binomial -- in one pass for the same data. I would |
| 149 |
predict that the binomial p-value is strictly less than the monobit |
| 150 |
p-value, and that there exist rng's that pass the monobit that |
| 151 |
explicitly fail the binomial, but we can determine that empirically. |
| 152 |
|
| 153 |
This chisq-based binomial test methodology can be used to improve nearly |
| 154 |
any single test statistic in sts. Instead of looking at the expected |
| 155 |
value of the statistic itself, frame its generation as a Bernoulli trial |
| 156 |
with a known percentage, compute the expected binomial distribution and |
| 157 |
its error, generate the result histogram as the test statistic, and use |
| 158 |
chisq and the complementary incomplete gamma function Q(a,x) to generate |
| 159 |
a p-value over many smaller "independent" trials instead of one long |
| 160 |
one. |
| 161 |
|
| 162 |
This suggests ways of improving e.g. the runs and other tests as well, |
| 163 |
see below. |
| 164 |
|
| 165 |
The Runs Statistic |
| 166 |
|
| 167 |
For n bits, count the test statistic X as the number of (overlapping) 01 |
| 168 |
and 10 pairs and add one. Compute p_1 = (# ones)/n, p_0 = (1 - p_1) |
| 169 |
(and ensure that they are close enough to p_0 = p_1 = 0.5). Compute the |
| 170 |
expected number of 01 and 10 pairs as Y = 2*n*p_1*p_0. Compute the |
| 171 |
expected error in the number of 01 and 10 pairs as sigma = |
| 172 |
2*sqrt(2*n)*p_1*p_0. Finally, compute the p-value as erfc(|X - |
| 173 |
Y|/sigma). |
| 174 |
|
| 175 |
This methodology seems questionable, at least to me. |
| 176 |
|
| 177 |
First of all, it seems odd to use a p_0 and p_1 derived from the sample, |
| 178 |
given that the null hypothesis is p_0 = p_1 = 0.5 and independent. |
| 179 |
Ensuring that the sample passes monobit (in a slightly different |
| 180 |
formulation) to start means that one has conditionally >>accepted<< this |
| 181 |
null hypothesis for the rng before beginning the runs test, using |
| 182 |
different p's implies a different null hypothesis. |
| 183 |
|
| 184 |
In addition, given their prior assumption that p_1 = # ones/# bits, |
| 185 |
their computation of the probability of p_01 and p_10 (and hence Y) is |
| 186 |
erroneous. The probability of 01 in a finite string of n bits, subject |
| 187 |
to constrained numbers of 0's and 1's needs to be computed WITHOUT |
| 188 |
replacement, just as one does with a deck of cards. After shuffling a |
| 189 |
deck of cards known to contain four aces, the probability that the top |
| 190 |
two cards are aces is not (4/52)*(4/52), but rather (4/52)*(3/52) -- if |
| 191 |
the first card is an ace, it means there are fewer aces left in the deck |
| 192 |
for the second card. To be consistent, they should compute the expected |
| 193 |
number of 01 strings in a 10-bit sequence containing 6 1's as |
| 194 |
(4/10)(6/9) and not (4/10)(6/10). They need to choose between a null |
| 195 |
hypothesis of p_1 = p_0 = 0.5 (where they can presume successive bit |
| 196 |
probabilities to be independent) and a null hypothesis of p_1 = (# |
| 197 |
1's)/(# bits) and use "probability for a 1, given that the first draw is |
| 198 |
a 0". This matters for short strings. |
| 199 |
|
| 200 |
Next, they don't wrap the n-value bitstring into a torus. Consequently, |
| 201 |
there are only n-1 bitpairs examined, and thus the expected value should |
| 202 |
be Y = 2*(n-1)*p_1*p_0 and not 2*n*p_1*p_0. For large n, of course, it |
| 203 |
won't matter (neither will the previous two problems, at least not |
| 204 |
much), but it is surprisingly sloppy mathematically. |
| 205 |
|
| 206 |
In addition there is no reason I can see to add a 1 to the test |
| 207 |
statistic of (# of 01 and 10 pairs in an overlapping scan of the |
| 208 |
string). This is very difficult to understand, as it clearly breaks the |
| 209 |
symmetry of this test statistic with the complementary view where the |
| 210 |
test statistic X is (# of 00 or 11 pairs in an overlapping scan of the |
| 211 |
string) but Y and sigma are the same -- the sum of the Y's necessarily |
| 212 |
equals n (or n-1, if that is the number of examined pairs). This leads |
| 213 |
to an obvious problem for short strings, e.g. n = 2, where the formula |
| 214 |
they give for the expected number of 01 or 10's measured is |
| 215 |
2*2*(1/2)*(1/2) = 1, but the statistic can only take on the values 1 or |
| 216 |
2, each with probability 1/2. There is something odd here. |
| 217 |
|
| 218 |
Finally, it is more than a bit crazy to view this assessment as somehow |
| 219 |
a measure of excessive sequential correlation, as a measure of "runs". |
| 220 |
Let us reframe the test statistic (count of 01 and 10's) in terms of our |
| 221 |
null hypothesis. Presuming random, equal probability 0's and 1's, we |
| 222 |
expect 25% each of 00 01 10 11. Given an exemplary bit string of e.g. |
| 223 |
1001101011, it doesn't really matter if one examines disjoint bitpairs |
| 224 |
(10 01 10 10 11) (n/2 bitpairs for n even) or the overlapping bitpairs |
| 225 |
10 00 01 11 10 01 10 01 11 11 (wrapping the last pair around |
| 226 |
periodically to ensure symmetry and n pairs of bits, EACH pair is |
| 227 |
expected to occur with a frequency, in the limit of many bitpairs, of |
| 228 |
#bitpairs*(1/4). |
| 229 |
|
| 230 |
Furthermore, in an ensemble of measurements of bitpair frequencies, each |
| 231 |
distinct possibility is (for lots of identical bitsets) to be binomially |
| 232 |
distributed with respect to the rest (as in p_01 = 1/4, p_!01 = 3/4) |
| 233 |
regardless of whether or not sequential overlapping bitpairs are |
| 234 |
counted. We can understand this by noting that our null hypothesis (a |
| 235 |
random generator producing pairs of bits) can be applied to any pair of |
| 236 |
bits in any string. |
| 237 |
|
| 238 |
Note also that in a given bitstring with periodic wraparound, the number |
| 239 |
of 01 (overlapping) pairs must equal the number of 10 pairs. This can |
| 240 |
be proven with ease. Every bit flipped can either change >>both<< the |
| 241 |
01 and 10 count by one (flipping a bit with two neighbors that are both |
| 242 |
0 or both 1) or it can leave them both the same (flipping a bit with a |
| 243 |
neighboring 0 AND a neighboring 1). This wreaks a certain measure of |
| 244 |
havoc on the notion that each sequentially overlapping pair examined is |
| 245 |
an independent measurement -- measuring any pair of (01 or 10 count) and |
| 246 |
(00 or 11 count) suffices to determine the counts for all four possible |
| 247 |
bit pairs. |
| 248 |
|
| 249 |
The only question remaining is whether measuring the counts using |
| 250 |
overlapping bitpairs is more or less rigorous a test than measuring the |
| 251 |
counts using non-overlapping pairs. That is, can a generator create a |
| 252 |
bitstring that is correctly pairwise distributed in both non-overlapping |
| 253 |
pair sequences but that is NOT correctly pairwise distributed in |
| 254 |
overlapping pair sequences or vice versa. The answer is not terribly |
| 255 |
obvious, but if we make the very weak presumption that our test |
| 256 |
measurments do not depend, on average, on whether we begin them |
| 257 |
systematically at bit 0 or bit 1 (so that if we have a bad generator |
| 258 |
we'll eventually fail for either starting point with roughly equal |
| 259 |
frequency for different starting seeds and/or first-bit displacements), |
| 260 |
then measuring both possibilities for each string should (on average) |
| 261 |
produce results that are conservatively related to measuring one |
| 262 |
possibility on twice as many strings. |
| 263 |
|
| 264 |
To put it another way, if a generator creates strings that >>fail<< the |
| 265 |
overlapping test, they would necessarily fail at least one of the two |
| 266 |
non-overlapping tests possible for the same bitstring, since the counts |
| 267 |
for the two non-overlapping tests add to produce the count for the |
| 268 |
non-overlapping test. For this addition to push values out of |
| 269 |
acceptable ranges one would require two deviations from the expected |
| 270 |
value in the same direction. If we only make the extremely weak |
| 271 |
assumption that failure of the non-overlapping tests is equally likely |
| 272 |
for both possible cyclic starting points, the 1/sqrt(2) scaling implicit |
| 273 |
in using both strings is thus conservative. |
| 274 |
|
| 275 |
However, we can easily average over this as well by simply randomly |
| 276 |
starting each non-overlapping run on bit 0 or bit 1. This might |
| 277 |
actually simplify the code and provides an ADDITIONAL measure of |
| 278 |
randomness as the two results should themselves be binomially |
| 279 |
distributed, independently. |
| 280 |
|
| 281 |
The final problem with runs is that it is not easy to see how to extend |
| 282 |
it to a higher order. For example, does 101 occur too often? How about |
| 283 |
010? Again, each bit pattern should occur at a rigorously predicted |
| 284 |
rate for p_0 = p_1 = 0.5 and independent bits, e.g. p_000 = p_001 = |
| 285 |
p_010 = ... = 1/8 for any distinct three-bit combination, p_0000... = |
| 286 |
1/16 for four-bit combinations, and so on. EACH of these outcomes |
| 287 |
should occur with binomially distributed frequencies when measured as a |
| 288 |
bernoulli trial with p_xyz, (1 - p_xyz), making it easy to compute both |
| 289 |
Y and sigma. This suggests that the correct generalization of monobit |
| 290 |
and runs (and probably more of the sts tests) is a test that (in one |
| 291 |
pass): |
| 292 |
|
| 293 |
a) presumes a valid bitlevel rng so that p_0 = p_1 = 0.5 exactly, all |
| 294 |
bits independent (null hypothesis). |
| 295 |
|
| 296 |
b) counts 1's (and infers 0's) for M sets of N bits, incrementing a |
| 297 |
histogram vector of the number of 1's observed accordingly. This is |
| 298 |
rigorously compared for EACH possible value of the count to the expected |
| 299 |
binomial distribution of counts. |
| 300 |
|
| 301 |
c) counts e.g. 00,01,10,11 overlapping pairs. We showed above that |
| 302 |
the count of 01's exactly equals the count of 10's. The count of 11 |
| 303 |
pairs equals the total number of pairs less the count of 00's, 01's and |
| 304 |
10's (all known). Even though these are not all independent, there is |
| 305 |
no harm and a small ease of coding advantage in binning all four counts |
| 306 |
in four result histograms, each to be compared to its binomial |
| 307 |
expectation. |
| 308 |
|
| 309 |
d) counts e.g. 000, 001, 010... overlapping pairs. Here we IGNORE |
| 310 |
possible count relationships for sure (as we won't stop with three |
| 311 |
bits:-). Again, bin the outcome count frequencies and compare to their |
| 312 |
expected binomial distribution. |
| 313 |
|
| 314 |
This process can continue indefinitely, as long as we can accumulate |
| 315 |
enough counts in each pattern histogram to make aggregate statistics |
| 316 |
reliable. For example, at 8 bits, one is basically ensuring that the |
| 317 |
distribution of ascii characters is BOTH overall uniform (has the |
| 318 |
correct mean number of letters) AND that the actual distribution of |
| 319 |
those letters in samples is correct from the point of view of Bernoulli |
| 320 |
trials. |
| 321 |
|
| 322 |
I think that this process is strengthened significantly by conducting it |
| 323 |
simultaneously for all the sequences. The first measures "bit frequency |
| 324 |
and randomness". The second measures "pairwise sequential |
| 325 |
correlations". The third measure "three-bit sequential correlations" |
| 326 |
and so forth. A sequence might pass the first and fail the second, pass |
| 327 |
the first two and fail the third, pass the first seven and fail the |
| 328 |
eighth, pass the first eight and fail the 32nd (so that floats formed |
| 329 |
from the inverse are not uniformly distributed). |
| 330 |
|
| 331 |
=============== |
| 332 |
|
| 333 |
Addendum to previous note. The insight has struck me that all that this |
| 334 |
does is give one the actual DISTRIBUTION of outcomes for any given |
| 335 |
experiment. The distribution of sample means should be -- guess what -- |
| 336 |
normal -- provided that there are enough elements in the sample itself. |
| 337 |
For small numbers of elements in the sample, they should be binomial if |
| 338 |
the experiment is framed as a bernoulli trial. I'll bet that if I |
| 339 |
convert smoothly from binomial into normal as the number of outcome |
| 340 |
states exceeds the threshold where computing binomial probabilities is |
| 341 |
reasonably possible, I'll see no difference in an appropriately computed |
| 342 |
chisq! |
| 343 |
|
| 344 |
This is the solution to the problem of doing long strings. If I counted |
| 345 |
e.g. bitpair combinations across a string of length 8, (for many |
| 346 |
samples) binomial is appropriate. If I count bitpair combinations |
| 347 |
across a string of length 2^23 (8 million), I can't do binomial, but |
| 348 |
don't have to. Outcomes will be normally distributed about the expected |
| 349 |
means. |
| 350 |
|
| 351 |
SO, this is the answer to the bigger problem of why one should ever |
| 352 |
trust "p-value" for a single sample, or even a dozen samples, of a |
| 353 |
random process. Sure (to quote Marsaglia) "p happens", but it doesn't |
| 354 |
JUST happen, it happens according to a distribution. Instead of |
| 355 |
wondering if THIS occurrence of p = 0.02 from a single mean value is |
| 356 |
reasonable or not, compute the p of an entire distribution of mean |
| 357 |
values compared to the appropriate normal or binomial distribution, and |
| 358 |
get a p-value one can really trust! |
| 359 |
|
| 360 |
======================= |
| 361 |
|
| 362 |
OK, so I'm stupid and I'm wrong. sts_monobit is, in fact, more |
| 363 |
sensitive than rgb_binomial although rgb_binomial might yet pick up a |
| 364 |
generator that passes sts_monobit and fail it -- one that preserves the |
| 365 |
symmetry of its 0/1 distribution about the midpoint (so the mean number |
| 366 |
of 0's and 1's is correct) but has the >>wrong<< distribution, e.g. is |
| 367 |
not binomial. |
| 368 |
|
| 369 |
As it turns out, most distributions that fail rgb_binomial do not have |
| 370 |
symmetry about their midpoint and consequently fail sts_monobit "before" |
| 371 |
failing rgb_binomial. If you like, rgb_binomial only becomes reliable |
| 372 |
when there is enough data to fill the primary non-zero bins near the |
| 373 |
middle, which takes a goodly chunk of data. sts_monobit, in the |
| 374 |
meantime, just adds up the number of 0's and 1's while steadily chopping |
| 375 |
down sigma -- by the time one has sampled a few thousand bits a lot of |
| 376 |
rng's are already 0/1 asymmetric enough to fail monobit, but the bin |
| 377 |
sigma's are still large enough to forgive a lot of slop in any given |
| 378 |
bin. |
| 379 |
|
| 380 |
Interestingly, binomial can be applied to very small bitstrings -- in |
| 381 |
fact, to bitstrings of length 1 (I think). At that point it should |
| 382 |
become equivalent to monobit, but in a somewhat different way, |
| 383 |
especially since rgb_binomial now evaluates monobit directly on the |
| 384 |
accumulated bit values. |
| 385 |
|
| 386 |
Looks like I >>do<< have some work to do to fully understand everything, |
| 387 |
I do I do...;-) |
| 388 |
|
| 389 |
============== |
| 390 |
|
| 391 |
Whoo, dawgies! Out of a bit of insight, rgb_persist was born, and it |
| 392 |
explains why a LOT of rng's suck incredibly. Lots of rng's quite |
| 393 |
literally never change the contents of certain bits (usually lower |
| 394 |
order bits). One common symptom is for an rng to always return odd |
| 395 |
or even numbers. Another common symptom is for a rng to fail a |
| 396 |
distributional test when the repeated bits are measured (as repeated 1's |
| 397 |
cause an excess of 1's, repeated 0's an excess of 0's, even repeated |
| 398 |
01's can cause runs/bitpair tests to fail). Worse, rgb_persist clearly |
| 399 |
shows that MOST rng's that exhibit the problem at all exhibit it |
| 400 |
STRONGLY (LOTS of repeated lower order bits) for at least some seeds. |
| 401 |
Using them, one runs a significant (indeed, a near "sure thing") risk of |
| 402 |
encountering seeds such that as many as 18 bits out of 32 are repeated, |
| 403 |
leaving one with only a fraction of the variation you thought you |
| 404 |
had. |
| 405 |
|
| 406 |
At this point, I'd have to say that rgb_persist is one of the first |
| 407 |
tests to run on ANY rng, and any rng that fails it should probably |
| 408 |
just be rejected out of hand -- even if only the last (least |
| 409 |
significant) bit is repeated, it seems dangerous to use an rng that |
| 410 |
produces only even or only odd numbers from any given seed, even for |
| 411 |
games. |
| 412 |
|
| 413 |
Writing the dumpbits and rgb_persist routines also gave me insight into |
| 414 |
how rgb_binomial and even the sts routines might be failing relative to |
| 415 |
their design goals. I've been processing bits least to most |
| 416 |
significant, and I've been ignoring random_max when doing so. This is |
| 417 |
a capital mistake, as of course an rng will fail when it only returns |
| 418 |
e.g. 16 bits in a 32 bit slot (and the other bits are necessarily |
| 419 |
repeated). I've probably been "passing" only rng's that return a full |
| 420 |
32 "random bits" (and of course don't fail e.g. rgb_persist()). |
| 421 |
|
| 422 |
SO, I need to rewrite sts_monobit, sts_runs, and rgb_binomial (last |
| 423 |
first) so that they only check bits in the valid part of each returned |
| 424 |
word. This will be modestly annoying, but is of course absolutely |
| 425 |
necessary for the results to mean a damn thing. |
| 426 |
|
| 427 |
==================== |
| 428 |
|
| 429 |
Note the new test rgb_bitdist, which is the BEST generalization of |
| 430 |
sts_monobit and perhaps better than rgb_binomial as well. We need to |
| 431 |
merge sts_monobit, rgb_persist, and rgb_bitdist into a single test |
| 432 |
that measures the total/average bit number, the per-bit-slot |
| 433 |
total/average number, and derives the cumulative bitmask of repeated |
| 434 |
bits. |
| 435 |
|
| 436 |
Two additional directions to take this: |
| 437 |
|
| 438 |
First: |
| 439 |
|
| 440 |
generate a set of Ntest variables for e.g. |
| 441 |
1 bit |
| 442 |
2 bit |
| 443 |
3 bit |
| 444 |
4 bit |
| 445 |
... |
| 446 |
N bit |
| 447 |
|
| 448 |
combinations (one each). For number of bits and bitpattern, sweep the |
| 449 |
bitstring and accumulate the frequency histogram (for each possible |
| 450 |
bitpattern in each string location) |
| 451 |
|
| 452 |
ntest[no_of_bits].x[bit_pattern_slot] |
| 453 |
|
| 454 |
with periodic wraparound on the bitstring and so forth -- this is, in |
| 455 |
fact, sts_runs but for arbitrary numbers of bits and accumulating BOTH |
| 456 |
the totals AND the actual distribution, and check the chisq on the |
| 457 |
distribution and the pvalue of the total expected. |
| 458 |
|
| 459 |
Second: |
| 460 |
|
| 461 |
Here we look for subtle sequential bitlevel correlations. We do the |
| 462 |
same test as before, except that the frequency histogram is LATERAL -- |
| 463 |
doing each bit position in a sequential fashion. This test should see a |
| 464 |
clear failure for bits that don't change (strong sequential correlation, |
| 465 |
that) but should ALSO discover individual bits that do things like: |
| 466 |
01010101 or 0011110000111100 or any other "balanced" repetition. |
| 467 |
|
| 468 |
In fact, we may eventually do a fft on the forward sequential bit |
| 469 |
sequences to see if there are even very weak sequential bit-level |
| 470 |
correlations like 001010100001100010 (where every sequential triplet has |
| 471 |
two 0's and one 1), even if the triplets themselves are "random". A |
| 472 |
good frequency test on all 3-way bit patterns should catch this, of |
| 473 |
course, and the lovely thing about binary is that I can always use a |
| 474 |
suitably masked integer conversion of the bit pattern itself as the |
| 475 |
histogram index! So it needn't be TOO horrible to encode. |
| 476 |
|
| 477 |
===================================================== |
| 478 |
|
| 479 |
Note on diehard parking lot test. First of all, the documentation for |
| 480 |
the test is incorrect -- it tests for "crashes" (overlap) of SQUARE cars |
| 481 |
with sides of length 1, not ROUND cars of RADIUS one as Marsaglia's |
| 482 |
documentation and comments assert. If round cars ("helicopters", to |
| 483 |
borrow Marsaglia's term) are used a different distribution is obtained |
| 484 |
with mean over 4000. |
| 485 |
|
| 486 |
Actually to me, round cars seems very very similar to one of Knuth's |
| 487 |
tests for hyperplanar distribution of random coordinates, which has a |
| 488 |
much more solid theoretical foundation; I suspect the tests are more or |
| 489 |
less equivalent in sensitivity and will yield identical success/failure |
| 490 |
patterns in 99% of all cases (maybe even 100%). And the sensitivity of |
| 491 |
this test sucks -- it was very difficult for me to find a test that |
| 492 |
failed it out of the entire GSL collection (trying a half dozen |
| 493 |
known-weak generators or more in the process). The one that finally DID |
| 494 |
fail it really, really sucked and failed all sorts of other tests. |
| 495 |
|
| 496 |
I'd be interested to see if this test deserves to live, in the long run. |
| 497 |
I rather suspect that Knuth tests in variable dimensions will yield a |
| 498 |
much more systematic view of RNG failure, just as rgb_bitdist does |
| 499 |
compared to e.g. runs tests. |
| 500 |
|
| 501 |
================================================================== |
| 502 |
07/11/06 |
| 503 |
|
| 504 |
I've just finished testing Marsaglia's bitstream test, and it is (like |
| 505 |
rgb_bitdist) a test that nothing survives. In fact, it is a dead |
| 506 |
certainty that rgb_bitdist is a better version of the same basic test, |
| 507 |
and that generators that fail rgb_bitdist at (say) 6 bits are going to |
| 508 |
fail Marsaglia's less sensitive 20-bit test. What his test does that |
| 509 |
bitstream doesn't is use a single relatively coarse grained test |
| 510 |
statistic -- the expected number of missing 20 bit numbers out of 2 |
| 511 |
million trials -- instead of doing what rgb_bitdist does, which is |
| 512 |
do a chisq test on the fractional occupancy of the entire VECTOR of 20 |
| 513 |
bit numbers. |
| 514 |
|
| 515 |
Research question: Which is more sensitive AT 20 bits? It seems to me |
| 516 |
that the chisq vector test is clearly superior as it would catch many |
| 517 |
possible "bad" distributions that conserved the mean number of missing |
| 518 |
numbers at this sample size (however unlikely such special deviations |
| 519 |
might be in practice) but then there is the question of sensitivity |
| 520 |
given a fixed sample size. SO FAR, however, rgb_bitdist continues to |
| 521 |
be the premier test for revealing failure, with nothing getting out |
| 522 |
alive past 6 bits, ASSUMING that I'm computing the vector chisq and |
| 523 |
p-value per run correctly and not just revealing that I'm using the |
| 524 |
wrong form as the number of bits goes up. |
| 525 |
|
| 526 |
Oh, and nothing survives diehard_bitdist EITHER, at least when one |
| 527 |
cranks the test up past Marsaglia's wimply 20 iterations to (say) 200. |
| 528 |
At that point the non-uniformity of the p-distribution is absolutely |
| 529 |
apparent -- it even has structure. That is, some seeds lead to biased |
| 530 |
results that are TOO CLOSE to the mean value and not properly |
| 531 |
distributed... an interesting observation all by itself. |
| 532 |
|
| 533 |
rgb |
| 534 |
|
| 535 |
================================================================== |
| 536 |
07/11/06 later that day... |
| 537 |
|
| 538 |
diehard_count_1s_stream() now WORKS! What a PITA! And (I suspect) how |
| 539 |
unnecessary all the complexity! This test (as it turns out) computes |
| 540 |
chisq on what amounts to a strangely remapped rgb_bitdist test |
| 541 |
(precisely!) on four and five digit base 5 integers obtained by |
| 542 |
remapping bytes based on the number of 1's therein. |
| 543 |
|
| 544 |
That is, 256 possibilities are reduced to 5, each with a |
| 545 |
trivial-to-compute frequency/probability, the base 5 integer is left |
| 546 |
shifted (base 5!) and added to the next one to cumulate 4 or 5 digit |
| 547 |
numbers, those numbers are then counted, and the counts compared to the |
| 548 |
EXPECTED counts given the number of samples and turned into chisq (one |
| 549 |
each, for 4 and for 5 digit numbers). Sigh. |
| 550 |
|
| 551 |
OK then, we COULD just print the p-value of those chisq's -- an |
| 552 |
absolutely straightforward process. Alternatively, we could do what |
| 553 |
Marsaglia does -- compute the DIFFERENCE of the chisq's themselves, |
| 554 |
which of course are supposedly distributed around the number of degrees |
| 555 |
of freedom of each one separately, that is 3125 - 625 = 2500! This is |
| 556 |
the mean value of the difference, with stddev = sqrt(2*2500). This |
| 557 |
final result is turned into a p-value. |
| 558 |
|
| 559 |
This of course is wierd and wrong in so many ways. For one, it is |
| 560 |
entirely possible for chisq_4 and chisq_5 to differ systematically from |
| 561 |
their expected values, and it is perfectly possible and likely that |
| 562 |
those deviations would occur in the same direction -- e.g. down -- so |
| 563 |
that the 4 byte and 5 byte streams BOTH have fewer degrees of freedom |
| 564 |
than expected. Of course in this case part of the individual deviations |
| 565 |
CANCEL and is not visible in the final p-value! |
| 566 |
|
| 567 |
Honestly, I can think of pretty much "no" reasonable ways that this |
| 568 |
final pvalue can fail where any/all of the p-values for the 4 or 5 (or 2 |
| 569 |
or 3 or 1 or 17) digit distributions would not also fail, but I can (and |
| 570 |
just did) think of a way that the final p-value might MARGINALLY pass |
| 571 |
while the individual p-values fail. |
| 572 |
|
| 573 |
Although the general approach is a good one, what is clearly needed is a |
| 574 |
new test -- one that extends rgb_bitdist to multidigit strings of smaller |
| 575 |
base. For example, right now rgb_bitdist tests the FREQUENCY of the |
| 576 |
occurrence of all 5 digit strings but not all 5 digit strings taken two |
| 577 |
at a time (32 x 32 = 1K possbilities). Of course one REASON that I |
| 578 |
don't do that is that I >>already<< do e.g. 10 bit strings -- the DIRECT |
| 579 |
frequency distribution of those 1K possibilities, which obviously |
| 580 |
samples all the 5 bit combos taken two at a time!. And besides, every |
| 581 |
rng I have tested fails at the level of what amounts to two digit octal |
| 582 |
numbers -- six bit strings. So I'm cynical about this. |
| 583 |
|
| 584 |
I also don't think that this really counts 1's. How is this one iota |
| 585 |
different from simply evaluating the distribution of bytes (8 bit |
| 586 |
randoms)? If the complete distribution of 8 bit bytes (rgb_bitdist at 8 |
| 587 |
bits) is random, ALL DERIVED DISTRIBUTIONS are random, with the only |
| 588 |
catchy part being temporal/sequential correlations that might be |
| 589 |
revealed from taking the strings four or five bytes at a time (at the |
| 590 |
expense of compressing the information tremendously). |
| 591 |
|
| 592 |
Once again, this test seems reduceable to but not as sensitive as |
| 593 |
rgb_bitdist at a given level, unfortunately a level far beyond where all |
| 594 |
known rng's fail anyway. It is a MEASURE of the lack of sensitivity |
| 595 |
that this does does NOT fail for many of those rng's where rgb_bitdist |
| 596 |
does... |
| 597 |
|
| 598 |
rgb |