| 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 |
| 599 |
|
| 600 |
================================================================== |
| 601 |
08/16/06 |
| 602 |
|
| 603 |
OK, lots has happened. First of all, I've discovered what I believe to |
| 604 |
be at least one, maybe two diehard data errors -- rngs consistently fail |
| 605 |
operm5 and bitstream that I (and everybody else) believe to be "good" |
| 606 |
ones insofar as such a thing exists. Not surprising -- the data being |
| 607 |
used to compute the test statistics was simulated between 10 and 20 |
| 608 |
years ago and this test routinely uses more random numbers from better |
| 609 |
generators in any given test than were likely used to simulate them in |
| 610 |
the first place. |
| 611 |
|
| 612 |
Second, dieharder is already in the process of developing quite a user |
| 613 |
base. People have ported it to Windows, for example, and Dirk |
| 614 |
Eddelbuettel is interested in adding a native R interface to the tests |
| 615 |
(to be able to take advantage of several of the other facilities that R |
| 616 |
provides, a la octave/matlab/maple/mathematica as a programming UI). |
| 617 |
|
| 618 |
To facilitate both this latter project and the eventual creation of a |
| 619 |
true GTK-based GUI for dieharder, I've begun the fairly monumental task |
| 620 |
of splitting off all the tests, the add-on rng's that are intended to be |
| 621 |
part of the basic package, and all the intrinsic support functions into |
| 622 |
a standalone link library and associated set of include files. I know |
| 623 |
from experience writing libwulf to support wulfware apps that this is a |
| 624 |
bit tricky, and I expect there to be deep bugs and places where the API |
| 625 |
and separation are not clean for quite some time now. However, when I'm |
| 626 |
DONE it should be REALLY EASY to replace the front end UI. In fact, if |
| 627 |
I clean up the UI itself while I'm at it to make it even more modular |
| 628 |
than it is, I should be able to add a GTK basic interface in a very |
| 629 |
short period of time. |
| 630 |
|
| 631 |
I'm also stripping down the actual source part of dieharder (the tty |
| 632 |
interface version) and putting most of the documentation and so on in |
| 633 |
with the LIBRARY, since that is where it will be needed. Eventually I |
| 634 |
should need something like man pages and/or a manual for the |
| 635 |
libdieharder library, in addition to a much smaller set of toplevel |
| 636 |
dieharder documentation. The application (in any UI version) should |
| 637 |
REALLY be fairly self-documenting as a design goal. |
| 638 |
|
| 639 |
To mark the advent of a version that appears to build on top of |
| 640 |
completely separated libdieharder.a, largely decrufted on both sides, |
| 641 |
I'm bumping the major number of dieharder even though this wasn't an |
| 642 |
original design goal. It clearly merits a major version bump anyway. |
| 643 |
The minor.minor numbers will retain their original meaning (bugfix |
| 644 |
advances and number of tests supported) except that now I should |
| 645 |
probably reset bugfix to 0 in both libdieharder and dieharder. I don't |
| 646 |
know what I'll do about synchronicity between the two -- really I should |
| 647 |
extract numbers from libdieharder to set dieharder version numbers, but |
| 648 |
parsing out all the screen-scraping macros gives me a headache so I'll |
| 649 |
await inspiration or need before messing with it. |
| 650 |
|
| 651 |
Note finally that doing this has put adding more e.g. marsaglia_tsang |
| 652 |
tests on hold. I do have an extensive agenda here -- fixing up a |
| 653 |
"super" version of sts_serial, adding sts_serial itself (which should be |
| 654 |
more or less equivalent to rgb_bitdist, only the latter doesn't compute |
| 655 |
the correct statistic for a chisq, alas), figuring out what the RIGHT |
| 656 |
data is for diehard_operm5 and diehard_bitstream, completing the |
| 657 |
installation of 10^11 to 10^12 sample-based target data of my OWN for |
| 658 |
marsaglia_tsang_gcd, and so on. However, clearly this needs to wait |
| 659 |
until the development environment is stable again, which could be days |
| 660 |
yet, or even longer depending on what else I have to do for Duke etc. |
| 661 |
|
| 662 |
I also haven't even looked at the WinXX patches -- I'll have to figure |
| 663 |
them out all over again after splitting off the library, I expect. |
| 664 |
|
| 665 |
Still, progress is being made. I think that the application is |
| 666 |
definitely out there to where a) it could be announced more publically |
| 667 |
on e.g. the stats lists -- maybe when the libdieharder split has been in |
| 668 |
"alpha" for at least a while...;-) and b) it is time to look for grant |
| 669 |
support for this project to accomplish certain specific goals -- |
| 670 |
supporting testing on a cluster (by the time we're done the |
| 671 |
sts_series/rgb_bitdist/rgb_lmn tests are going to be BIG CPU |
| 672 |
consumers:-), finishing off all the desired/required tests, |
| 673 |
re-simulating key target data for the brave new world of unlimited rands |
| 674 |
to test, and "getting the word out" via publication, travelling to |
| 675 |
learned meetings and presenting, and so on. I'd guess that this will |
| 676 |
require a fairly serious grant for at least 3-5 years to do all that |
| 677 |
needs to be done that I know of already, and may need even more if (as I |
| 678 |
suspect) things are discovered that require significant new work to be |
| 679 |
done on testing algorithms themselves, e.g. "moment expansion" type |
| 680 |
tests, a connection between high-dimensional test failure and bit |
| 681 |
distribution tests. |
| 682 |
|
| 683 |
I have high hopes for the lmn test, although it may prove only the first |
| 684 |
step in lmnop, lmnopqr, lmnopqrst, etc... -- sampling lagged correlation |
| 685 |
between l-bit number, m-bit gap, n-bit number, o-bit gap, p-bit |
| 686 |
number...etc. MANY tests seem to be fancy ways of doing just this and |
| 687 |
nothing more, interestingly enough -- in some cases ways of examining |
| 688 |
only a projective subspace of the failures one might occur from a truly |
| 689 |
systematic test of this sort. For example, a Knuth test that reveals |
| 690 |
hyperplanar clustering of rand triplets viewed as spatial coordinates is |
| 691 |
effectively observing non-uniformity of the random integers represented |
| 692 |
by the conjunction of the three bitstrings... but without attempting to |
| 693 |
validate true randomness on 96-bit integers! |
| 694 |
================================================================== |
| 695 |
|
| 696 |
10/10/06 |
| 697 |
|
| 698 |
Well, many many more bugs were discovered (mostly by Charles Karney) and |
| 699 |
fixed and the tests are much improved as a result. At this point "good" |
| 700 |
generators pass all but the operm5 and bitstream tests. operm5 I |
| 701 |
STRONGLY suspect of containing a significant error. bitstream the jury |
| 702 |
is still out on -- the whole series of n-bit monkey tests bothers me |
| 703 |
as they seem inevitably related to rgb_bitdist but less specific and |
| 704 |
sensitive. They are, however, more asymptotic and I've got to really |
| 705 |
think about it before passing final judgement (hopefully buttressed by |
| 706 |
very specific examples of correlated failure according to specific |
| 707 |
patterns). |
| 708 |
|
| 709 |
I added a whole selection of bit manipulation tools. I can now grab |
| 710 |
GUARANTEED sequential bits from the bitstream produced by any of the |
| 711 |
supported rngs (independent of rmax_bits). I can easily generate a |
| 712 |
string of (precisely) uints with 32 supposedly random bits from this |
| 713 |
sequential stream. I can rotate this uint in place and mask/select any |
| 714 |
of its bits. I can grab arbitrary bit windows within a block of memory, |
| 715 |
and can grab arbitrary ntuples within a block of memory with periodic |
| 716 |
boundary conditions. These routines (only) should be used to access the |
| 717 |
rngs in nearly all tests as they eliminate spurious effects from a rng |
| 718 |
returning only 31 bits on a test that de facto presumes 32, or 22 bits, |
| 719 |
or 16 bits. They also permit true overlapping samples to be generated |
| 720 |
absolutely trivially on a given fixed buffer for overlapping sample |
| 721 |
tests in dieharder (where it is by no means obvious that overlapping |
| 722 |
matters in any significant way). |
| 723 |
|
| 724 |
It is time to create two new tests. One of them generalizes rgb_bitdist |
| 725 |
so that the ntuples it samples can be created by more or less arbitrary |
| 726 |
sample patterns, e.g. |
| 727 |
|
| 728 |
stream: 0101010001111101010110101110100010101110101001011001110110110... |
| 729 |
-------|(repeat) |
| 730 |
|
| 731 |
Get sequential 8-tuples e.g. 01010100 -- existing rgb_bitdist test for |
| 732 |
nbits = 8. |
| 733 |
|
| 734 |
|
| 735 |
stream: 0101010001111101010110101110100010101110101001011001110110110... |
| 736 |
----....---|(repeat) |
| 737 |
|
| 738 |
Get 4 bits, skip 4 bits, get 4 bits to make the 8-tuple 01010111, test |
| 739 |
stream of 8-tuples created with this repeating pattern with rgb_bitdist. |
| 740 |
This should reveal fourier-like correlations of certain kinds within 12 |
| 741 |
bits, but is LESS sensitive than properly testing 12 bits directly. |
| 742 |
|
| 743 |
|
| 744 |
stream: 0101010001111101010110101110100010101110101001011001110110110... |
| 745 |
--........--........--........-|(repeat) |
| 746 |
|
| 747 |
Get 2 bits, skip 8 bits, get 2 bits, skip 8, get 2, skip 8, get 2 to |
| 748 |
make the 8-tuple 01111000, test stream of 8-tuples created with this |
| 749 |
repeating pattern with rgb_bitdist. Note that this test looks for |
| 750 |
relatively LONG range ntuplet correlations -- a fourier-like correlation |
| 751 |
over 32 bit cycles and embedded 8 bit cycles at the same time. |
| 752 |
|
| 753 |
stream: 0101010001111101010110101110100010101110101001011001110110110... |
| 754 |
.....................................---|(repeat) |
| 755 |
|
| 756 |
Skip 37 bits, get 4, run rgb_bitdist on the stream of 4-tuplets produced |
| 757 |
e.g. 1101 etc. Note well that 37 bits is odd and prime, as is 41! This |
| 758 |
approach can look for trouble in difficult places that might well be |
| 759 |
missed by a binary-happy sampling of sequential uints. |
| 760 |
|
| 761 |
This method of sampling can also be run on a single large buffer with |
| 762 |
overlap. In principle, one can construct a lagged test series that |
| 763 |
should reveal e.g. hyperplanar distributions very precisely. However, |
| 764 |
it is still likely limited by the number of bits one can practically run |
| 765 |
rgb_bitdist on, which appears to be somewhere in the ballpark of 12 to |
| 766 |
16. Nevertheless, it also allows one to sample and discover at least a |
| 767 |
large class of problems across a much larger number of bits. |
| 768 |
|
| 769 |
Note well that in principle ALL the tests in dieharder could run on |
| 770 |
random numbers (uints or whatever) that are generated by using a |
| 771 |
patterned, lagged selection of bits such as this. We can therefore |
| 772 |
accomplish a huge amount of flexibility if we build still more routines |
| 773 |
into bits.c, e.g. |
| 774 |
|
| 775 |
uint get_rand_pattern((void)*result,int rsize,int *pattern,gsl_rng *gsl_rng){} |
| 776 |
|
| 777 |
where pattern is a variable length vector such as: |
| 778 |
|
| 779 |
pattern[0] = 2; |
| 780 |
pattern[1] = -8; |
| 781 |
pattern[2] = 2; |
| 782 |
pattern[3] = -8; |
| 783 |
pattern[4] = 2; |
| 784 |
pattern[5] = -8; |
| 785 |
pattern[6] = 2; |
| 786 |
pattern[7] = 0; |
| 787 |
|
| 788 |
which can be parsed to build an arbitrary sized return very easily. |
| 789 |
Another routine might use pattern and a varying offset to generate the |
| 790 |
ten distinct samplings of the bitstream that use one or more of the |
| 791 |
skipped bits, or even the full 32 corresponding to all overlapping |
| 792 |
samples with an offset that runs from 0 to 31, pulled either from |
| 793 |
primary bitstream or from a large cyclic buffer. |
| 794 |
|
| 795 |
I'm moderately tempted to write the Master Bit Selector in this way, but |
| 796 |
the damnable bit selection routines are actually a real pain in the ass |
| 797 |
to write and especially debug, so I think I'll start with |
| 798 |
get_rand_pattern (an obvious generalization of get_rand_bits()) and go |
| 799 |
from there. |
| 800 |
|
| 801 |
Then the entire decision on what to run and test is on the calling |
| 802 |
program. If I make int *pattern a global variable that can be |
| 803 |
allocated, set, used, and freed by the caller before calling any test |
| 804 |
and use only get_rand_pattern() to get ints for testing, ALL tests can |
| 805 |
be run on selected patterns. Dieharder can then sweep over patterns and |
| 806 |
really test the hell out of rngs... |
| 807 |
|
| 808 |
There is a second kind of test that we must implement -- one that I'm |
| 809 |
very well qualified to write on the basis of published research. The |
| 810 |
CLT is a very powerful thing. It predicts BOTH the mean AND the |
| 811 |
variance of any normal sampling process (and probably higher order |
| 812 |
moments as well -- there should be a series of cumulants, really, that |
| 813 |
describe the distribution of means). |
| 814 |
|
| 815 |
This gives us the ability to write a very subtle and sensitive test for |
| 816 |
global autocorrelation over arbitrary internal scales. This is a |
| 817 |
research question (for me, anyway) but it seems that if a system has |
| 818 |
internal correlations that prevent samples from being truly iid, this |
| 819 |
will show up as a variance that does not scale correctly with the number |
| 820 |
of samples. By comparing the VARIANCES, not the means, one should be |
| 821 |
able to directly observe that a statistic has e.g. fewer samples in it |
| 822 |
than you think that it does because of correlations between samples, |
| 823 |
even correlations over a very long time scale. |
| 824 |
|
| 825 |
A classic example is a sample stream with true periodicity -- you think |
| 826 |
that you've accumulated M samples with a variance that scales like |
| 827 |
1/sqrt{M} but really you've gotten the same P samples (each with |
| 828 |
variance that scales like 1/sqrt{P}). The observed variance is |
| 829 |
therefore going to be much smaller than the expected variance for M |
| 830 |
samples, off by a factor of sqrt{M/P}. Similar considerations hold for |
| 831 |
e.g. overlapping bit pattern selection where there is an |
| 832 |
"autocorrelation time" associated with the overlap. |
| 833 |
|
| 834 |
Here we might have a string like: |
| 835 |
|
| 836 |
11010111010101000101010... |
| 837 |
|
| 838 |
generating: |
| 839 |
|
| 840 |
11 01 01 11 01 01 01 00 01 01 01 0... |
| 841 |
|
| 842 |
and |
| 843 |
|
| 844 |
.1 10 10 11 10 10 10 10 00 10 10 10... |
| 845 |
|
| 846 |
EACH of these strings can be tested with e.g. rgb_bitdist to see if the |
| 847 |
patterns are correctly distributed to yield a p-value. If the generator |
| 848 |
passes two bit tests independent of the offset, the distribution of p |
| 849 |
will of course be correct for either sequence. What of the "mixed" |
| 850 |
(interleaved) sequence: |
| 851 |
|
| 852 |
11 01 01 11 01 01 01 ... |
| 853 |
|
| 854 |
+ 10 10 11 10 10 10 10 ... |
| 855 |
|
| 856 |
= 11 10 01 10 01 11 11 10 01 10 01 10 01 10 ... ? |
| 857 |
|
| 858 |
Well, it is pretty much guaranteed to have the right number of 00's, |
| 859 |
01's, 10's and 11's overall. However, we can make an even stronger |
| 860 |
statement. Suppose that we know that the original bit sequence passes |
| 861 |
the >>3<<-tuple rgb_bitdist test. Then in fact we know that it has the |
| 862 |
right mean distribution of 000 001 010 011 100 101 110 111's. In that |
| 863 |
case as we parse these combinations into the two overlapping duplets, we |
| 864 |
get: |
| 865 |
|
| 866 |
P(000) = 1/8 => 00 00 |
| 867 |
P(001) = 1/8 => 00 01 |
| 868 |
P(010) = 1/8 => 01 10 |
| 869 |
P(011) = 1/8 => 01 11 |
| 870 |
P(100) = 1/8 => 10 00 |
| 871 |
P(101) = 1/8 => 10 01 |
| 872 |
P(110) = 1/8 => 11 10 |
| 873 |
P(111) = 1/8 => 11 11 |
| 874 |
|
| 875 |
If we see 00, then (as we will with probability 1/4, inherited from the |
| 876 |
triplet probability table and validated by the passing of rgb_bitdist |
| 877 |
for the two independent bit sequences separately), we know that it must |
| 878 |
be followed by 00 or 01. |
| 879 |
|
| 880 |
Suppose there were a surplus of 00s relative to 01s. Then there would |
| 881 |
be more than 1/8 000s and less than 1/8 001s and we could not have |
| 882 |
passed the rgb_bitdist test for triplets. This idea is obviously |
| 883 |
extensible for arbitrary ntuplets -- if one passes rgb_bitdist without |
| 884 |
overlap for n bits, one is guaranteed to pass with overlap at n-1 bits. |
| 885 |
|
| 886 |
Consequently there is really >>no point<< in running rgb_bitdist on a |
| 887 |
series of ntuplets. If one observes the correct (binomial) probability |
| 888 |
distribution for the duplets 00, 01, 10, 11 over many samples, then one |
| 889 |
cannot help but have the correct probability distribution for the monets |
| 890 |
0 and 1 separately. If one has the the correct binomial distribution of |
| 891 |
triplets, one cannot help but have the right distribution of duplets and |
| 892 |
monets, and so on, whether or not overlapping samples are used. |
| 893 |
|
| 894 |
This last example is an excellent case of conditional probability at |
| 895 |
work. If we shift our sample window by one bit from a window that |
| 896 |
yields a valid distribution, {\em all that matters} is whether or not |
| 897 |
that additional bit is a 0 or 1 with the correct frequency. There are |
| 898 |
always only {\em two} possibilities: |
| 899 |
|
| 900 |
bbbb0 -> bbbb and bbb0 |
| 901 |
bbbb1 -> bbbb and bbb1 |
| 902 |
|
| 903 |
If that bit is random with probability 0.5, then we should be able to |
| 904 |
use Bayes theorem to generate very simple proofs that everything stated |
| 905 |
above is correct. |
| 906 |
|
| 907 |
================================================================== |
| 908 |
01/29/07 |
| 909 |
|
| 910 |
OK, just finished repackaging dieharder to use subpackages and a single |
| 911 |
source tree to build both libraries and the dieharder ui. This will |
| 912 |
TREMENDOUSLY simplify both the semiseparate maintenance of the R UI as |
| 913 |
an RPM and the soon-come GUI built with Gtk/glade or the like. In fact, |
| 914 |
any number of UI's can be added to this source tree, including ones |
| 915 |
under separate subversion trees. I rather expect that even if I |
| 916 |
maintain a separate svn tree and a standalone RPM build/specfile for |
| 917 |
gdieharder, I'll probably keep the gdieharder development node here for |
| 918 |
convenience if nothing else. It's either that or develop only on |
| 919 |
platforms where libdieharder is stable and installed. |
| 920 |
|
| 921 |
I've added a directory point for R, there is already a separate |
| 922 |
directory point for the manual (which will eventually get its own RPM). |
| 923 |
|
| 924 |
I'm wondering if I need to create a mailman list for dieharder. |
| 925 |
Probably really close. Anyway, on to future plans, which is one thing |
| 926 |
the NOTES are for. I still have several new RNGs to add, several tests |
| 927 |
to debug or re-engineer (they consistently fail "good" generators, |
| 928 |
suggesting "bad" tests). I need to create a "standard dataset" and run |
| 929 |
the old fortran diehard against it to create a test reference, then see |
| 930 |
if I can reproduce the reference test values (within spitting distance) |
| 931 |
using the dieharder replacements. That would help me resolve this |
| 932 |
question -- if I get the same numbers on a reference dataset then the |
| 933 |
new code is "good", so if that same code fails "good" rngs, the old code |
| 934 |
is probably bad. Or something like that. |
| 935 |
|
| 936 |
I also need to add a still further improved reporting facility, |
| 937 |
especially for e.g the bitlevel tests. One doesn't ONLY want to know if |
| 938 |
the rgb_bitdist 1's test fails, one wants to know if the sample had an |
| 939 |
excess of 0's or 1's, and by how many sigma, per run, in a table. |
| 940 |
Ditto the per run distribution of 00 01 10 11 in the 2's test, 000 001 |
| 941 |
010... for the 3's test, at least out to maybe 8 bits (a table with 256 |
| 942 |
entries is BARELY displayable, at least on a pixelized panel of lights |
| 943 |
display in a GUI). Improved visualization is also important, for |
| 944 |
example to see hyperplane development for certain generators. |
| 945 |
|
| 946 |
I still need to work on the bits.c routines and at the very least get to |
| 947 |
where I can pack uints with arbitrary blocks of bits and holes. This |
| 948 |
will permit me to work on fourier and lagged sample tests, ones that |
| 949 |
look for bitlevel correlations in samples pulled with (say) 23-bit holes |
| 950 |
between the end of one uint bitset and the next in an imagined |
| 951 |
continuous stream of random bits. |
| 952 |
|
| 953 |
I need to upload the new 2.x release to the website, and probably clean |
| 954 |
up the website. Sigh. LOTS to do, and so little time and |
| 955 |
competition... |
| 956 |
|
| 957 |
================================================================== |
| 958 |
02/27/07 |
| 959 |
|
| 960 |
dieharder now builds with the usual ./configure;make sequence. Gnu |
| 961 |
Build Tools Suck. However, they are standard and expected, if |
| 962 |
infinitely painful. Hopefully this will facilitate the debian build, |
| 963 |
though, and make rpm still works. |
| 964 |
|
| 965 |
May have fixed a minor bug in operm5, where it has been claimed that the |
| 966 |
correct number of degrees of freedom is 5!-4! = 96, not 99. This makes |
| 967 |
at least some sense, so I implemented the change, but operm5 has MORE |
| 968 |
errors in either code or data, and I don't have time or knowledge to fix |
| 969 |
them... |
| 970 |
|
| 971 |
On to the next step -- putting the code on a truly public svn repo --- |
| 972 |
code.google.com. This will take one little bit of work, as the svnsync |
| 973 |
didn't work the first times I tried it... |
| 974 |
|
| 975 |
========================================================================== |
| 976 |
03/09/08 |
| 977 |
|
| 978 |
OK, so GBT don't suck, they are merely difficult. I'm about to release |
| 979 |
a fairly major set of fixes and a new test or three, and one of the main |
| 980 |
focuses of this round of changes has been to make libtool and the GBT |
| 981 |
truly happy and dieharder perhaps more portable as a consequence. This |
| 982 |
is still a process not without pain -- documentation is mediocre, |
| 983 |
undocumented features abound, rpath evil must be hand-repaired in order |
| 984 |
to facilitate rpm builds -- but it does look as if the GBT CAN be used |
| 985 |
to run major projects and automate a lot of the same stuff my original |
| 986 |
build automated, once you figure out how. |
| 987 |
|
| 988 |
As far as tests go, I've implemented a number of fixes and "new" tests |
| 989 |
since the last time around, and am about to get truly serious about a |
| 990 |
certain class of tests. |
| 991 |
|
| 992 |
The most important new test is sts_serial. IMO this may prove to be the |
| 993 |
most useful of all rng tests save -- perhaps -- rgb_bitdist, which tests |
| 994 |
very much the same thing a very slightly different way. |
| 995 |
|
| 996 |
The most important planned addition is a "shuffler" that can be used to |
| 997 |
access the rng stream with lag, with or without loss. In particular, |
| 998 |
I'd like to be able to generate a stream to sample with an adjustable |
| 999 |
lag in between samples, at the bit level, to be able to detect weakly |
| 1000 |
correlated cycles in the bitstream. |
| 1001 |
|
| 1002 |
Most of the tests in dieharder are really only strongly sensitive to |
| 1003 |
what I might call "first order" departure from randomness, first order |
| 1004 |
decorrelation. They measure statistics generated from sampling the rng |
| 1005 |
stream in order, with each sample presumed to be independent. They do |
| 1006 |
not, for the most part (with certain exceptions, that is) detect whether |
| 1007 |
any given rand is correlated with the rand that immediate follows it, or |
| 1008 |
the one two rands downstream, or the one fifty rands downstream -- those |
| 1009 |
are "second order" correlations. |
| 1010 |
|
| 1011 |
Amazingly, there seems to be no test that simply and directly evaluates |
| 1012 |
|
| 1013 |
A(d) = <(1.0-2.0*x_i) *(1.0-2.0*x_{i+d})>, |
| 1014 |
|
| 1015 |
the average autocorrelation of the floating point random number stream |
| 1016 |
shifted so that the expected autocorrelation is zero for all |
| 1017 |
displacements d. However, this test really needs to be run in a variety |
| 1018 |
of ways, as one can imagine bitlevel correlations that will show up |
| 1019 |
strongly on bitlevel tests but weakly on floating point tests. |
| 1020 |
|
| 1021 |
Naturally, one can imagine looking at higher order moments as well. |
| 1022 |
|
| 1023 |
To facilitate tests of all of these sorts, I want to wrap the gsl |
| 1024 |
generator in such a way that one can request: |
| 1025 |
|
| 1026 |
n bits, skip m bits (throwing them away), to facilitate "direct" |
| 1027 |
searches for |
| 1028 |
|
| 1029 |
and returning the n bits, or |
| 1030 |
|
| 1031 |
a uint composed of the upper n bits, skip m uints, lower 32-n bits or |
| 1032 |
vice versa. Nothing is thrown away. |
| 1033 |
|
| 1034 |
Or |
| 1035 |
|
| 1036 |
a bit stream returnable as n-bit window or uints made up of any |
| 1037 |
reasonable shuffling or displacements of components, with or without |
| 1038 |
interleaving (lossless) or loss. |
| 1039 |
|
| 1040 |
With such an interface, one could use ALL of the dieharder tests to |
| 1041 |
check for the (mostly) first order randomness of streams generated from |
| 1042 |
various interleaved displacements of any generator. They would then all |
| 1043 |
"magically" become second order (or higher order) tests! |
| 1044 |
|
| 1045 |
rgb |
| 1046 |
|
| 1047 |
========================================================================== |
| 1048 |
09/04/08 |
| 1049 |
|
| 1050 |
I've made many changes and bugfixes -- one of which is to fix the |
| 1051 |
run_test() routines so that they create, run, and destroy the tests, one |
| 1052 |
at a time (which suggests that it may well be time to alter the way |
| 1053 |
results are passed back or futher encapsulate tests to simplify |
| 1054 |
dieharder's logic, even at the expense of having tests that "function |
| 1055 |
like diehard's" did. As in some diehard tests generate two statistics |
| 1056 |
in one run; it may be time to separate them into two tests and run them |
| 1057 |
independently with their own names and their own pvalue returns, even at |
| 1058 |
the expense of efficiency. |
| 1059 |
|
| 1060 |
However, I'm writing to post this as my current design goal for -T(able) |
| 1061 |
output with an optional flat to control just what is included in the |
| 1062 |
table and header. Here's the proposed "standard" table output: |
| 1063 |
|
| 1064 |
#======================================================================== |
| 1065 |
# Generator Tested: mt19937 |
| 1066 |
# Test Name | n-bits | p-samples | t-samples | p-value(s) |
| 1067 |
#======================================================================== |
| 1068 |
RGB Bit Distribution Test| 1 | 100 | 100000 | 0.55579848 |
| 1069 |
RGB Bit Distribution Test| 2 | 100 | 100000 | 0.69322169 |
| 1070 |
... |
| 1071 |
|
| 1072 |
Each field's presence or absence will be able to be turned on or off by |
| 1073 |
means of a flag bit. The presence of the header, and whether or not it |
| 1074 |
contains e.g. the rng descriptors (name and/or filename) will be flag |
| 1075 |
bit controlled as well, with -q basically setting the bits to suppress |
| 1076 |
headers altogether. |
| 1077 |
|
| 1078 |
In this way, with suitable flag settings, one can "just" output pvalues, |
| 1079 |
can output names and pvalues, can output just names and assessments, |
| 1080 |
etc. |
| 1081 |
|
| 1082 |
I'm guessing that the following are all fields we want to be able to |
| 1083 |
control with their own flag bits: |
| 1084 |
|
| 1085 |
THEADER |
| 1086 |
TGEN |
| 1087 |
TNAME |
| 1088 |
TSNAME |
| 1089 |
TNBITS |
| 1090 |
TPSAMPLES |
| 1091 |
TTSAMPLES |
| 1092 |
TPVALUE |
| 1093 |
TASSESSMENT |
| 1094 |
|
| 1095 |
Anyway, let's do it... |
| 1096 |
|
| 1097 |
9/19/08 |
| 1098 |
|
| 1099 |
That worked really well. However, I now have to handle some way of |
| 1100 |
managing the tests that take ntuple as an argument for e.g. lag or |
| 1101 |
ntuple size. I >>think<< that the only correct way to manage this will |
| 1102 |
be to move the loops to the run_all_tests() function, since that is ONLY |
| 1103 |
a CLI feature, and call the execute_test within it as per usual. That |
| 1104 |
way run_test WITH a setting of ntuple will be entirely API driven and |
| 1105 |
consistent. |
| 1106 |
|
| 1107 |
The other thing(s) I have to implement include: Some sort of CLI flags |
| 1108 |
or control variables to tell dieharder when and how to set a random |
| 1109 |
number seed. We have several possible seed strategies, you see: |
| 1110 |
|
| 1111 |
a) Dieharder reseeds from /dev/random or clock one time at the time |
| 1112 |
the rng is initialized, and then left alone (CLI) until the rng is freed |
| 1113 |
(UI) or the program is ended (CLI). The Rdh UI could in principle |
| 1114 |
permit the seed to be interactively reset by the user at any time; |
| 1115 |
that's up to Dirk. |
| 1116 |
|
| 1117 |
When dieharder outputs results, one of the output flags will indicate |
| 1118 |
whether or not the rng seed should appear. In general it probably |
| 1119 |
should, but only the one seed randomly picked at the beginning. |
| 1120 |
|
| 1121 |
b) Dieharder uses a seed entered by the user one time at the |
| 1122 |
beginning. This should clearly be able to perfectly reproduce any |
| 1123 |
identical sequence of tests (including dieharder -a results) that began |
| 1124 |
with just that seed, so this specific thing should be a possibility. |
| 1125 |
|
| 1126 |
c) Dieharder uses a seed entered by the user at the beginning to set |
| 1127 |
the seed at the beginning of each test. This usage is primarily for |
| 1128 |
validation purposes, since doing this makes results from "series" tests |
| 1129 |
that run closely related tests on various ntuples or lags not |
| 1130 |
independent. For example, rgb_bitstream for an ntuple of 4 is obviously |
| 1131 |
going to be strongly correlated with the results for an ntuple of 8 |
| 1132 |
STARTED FROM THE SAME SEED; the two half-bytes that make up each 8 were |
| 1133 |
previously tested and the results of that test will clearly affect the |
| 1134 |
results for 8. The same problem exists for the closely related |
| 1135 |
sts_serial, but it keeps track and attempts to correct for it. |
| 1136 |
|
| 1137 |
Still, entering a seed and having it used to reseed EACH test run means |
| 1138 |
that dieharder -a -S 1 can EASILY generate an entire set of |
| 1139 |
reference/validation results that can then be generated and compared one |
| 1140 |
at a time in Rdh (which doesn't "do" a -a test). If we seeded only at |
| 1141 |
the beginning, any tiny variation in e.g. the number of rands called or |
| 1142 |
test order would produce different downstream numbers and a failure to |
| 1143 |
validate. |
| 1144 |
|
| 1145 |
Obviously this mode should not be used for testing, as one expects |
| 1146 |
"failures" to cluster in linked tests because of the aforementioned |
| 1147 |
non-independent of the results. If 4 bit numbers lead to a "weak" |
| 1148 |
pvalue, testing 8 bit numbers should also lead to a weak pvalue and/or |
| 1149 |
vice versa. |
| 1150 |
|
| 1151 |
Our current difficulty is that we have THREE possibilities but only TWO |
| 1152 |
CLI control states -- with -S whatever or without. Without is fine -- |
| 1153 |
that can and should select random seeding. With, however, requires a |
| 1154 |
second CLI switch option to select between the two seeding strategies. |
| 1155 |
|
| 1156 |
There really isn't anything wrong with providing the fourth combination |
| 1157 |
of two separate toggles as follows: |
| 1158 |
|
| 1159 |
|
| 1160 |
Strategy \ Seed| 0 | 1 |
| 1161 |
------------------------------------------------------------------ |
| 1162 |
beginning| random at beginning | from Seed at beginning |
| 1163 |
per test | random per test | from Seed per test |
| 1164 |
|
| 1165 |
SO, it looks like we need to introduce TWO variables. -s sets the |
| 1166 |
strategy. -S sets the seed to the selected value, or left alone at 0, |
| 1167 |
sets seed to a "random" choice. |
| 1168 |
|
| 1169 |
This works because -s is liberated now that we don't need to select sts |
| 1170 |
tests that way. So is -r and -d. We should probably keep -d and use it |
| 1171 |
for -d(ieharder test name/test number) the same way -g allows or will |
| 1172 |
allow one to pick either one. -r, well, we'll have to think about what |
| 1173 |
to do with it, eventually. |
| 1174 |
|
| 1175 |
This is enough for now. |