Debian Codegraph @

libdieharder/NOTES

raw
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