9 ms·
I think you’re better of reading the relevant chapter in TAOCP. It has more detail, and this doesn’t add anything from past 1970 or so. For example, it doesn’t
by Someone 9y ago
I think you’re better of reading the relevant chapter in TAOCP. It has more detail, and this doesn’t add anything from past 1970 or so. For example, it doesn’t even _mention_ the diehard and dieharder tests, let alone discuss their merits. (CORRECTION: it does. Thanks to marvy for pointing that out)
Also, I think the final line in this text (”Correct generators usually pass tests, and buggy generators usually fail.”) is at least dangerously misleading.
Firstly, I would use good/bad, not correct/buggy, but that is minor. My major issue is the idea that bad generators usually fail. Only really bad generators usually fail. Somewhat bad generators fail tests less often, and only slightly bad generators can pass many, many tests, only to show their weakness in some particular setting.
For example, if I take the output r1,r2,r3… of a good generator and swap r1 and r2 if r1>r2, r3 and r4 if r3>r4, etc. the result isn’t truly random, but will pass many tests.
If you suspect your generator to have this problem, it is extremely easy to test for it, but if you don’t, that may be hard.
A good array of tests will test subsequences, and find this easily (the average of the odd samples will typically be less than expected, and the average of the even samples will typically be larger)
- marvy 9y ago> For example, it doesn’t even _mention_ the diehard and dieharder tests, let alone discuss their merits It mentions the DIEHARD test near the beginning. Try ctrl-F.
- brians 9y agoYou think a length two repeat in the most significant bits will hide from statistical tests? That doesn’t sound plausible to me. Can you show a good RNG for which this mutation passes tests?
- Someone 9y agoI don’t claim that, but it will pass the tests described in the text being discussed.
- gamegoblin 9y agoYour example will fail the "Overlapping permutations" test and "Runs test" from the diehard tests. I don't think it's really meaningful to point out that a bad RNG will pass many of the constituent tests of a particular test battery (e.g. diehard), because each constituent test is generally looking for one particular property.