I agree generally to what Clay sets out below. However, the test cannot be run apart from the other integral parts involved. Incidentally, try running triplet, or even greater, autocorrelation of the 200 megabytes set out at our web site. there is absolutely no problem. As indicated in our statistics, we have already done that. On Wed, 4 Dec 1996, Clay Olbon II wrote:
At 09:24 PM 12/3/96 -0800, Eric Murray wrote:
I did some more experiments with the IPG stream-cipher algorithim and random number tests. Since IPG claim that their algorithim passes chi-square tests of randomness, I found a chi-square test program. It's written by Peter Boucher and was posted to sci.crypt in '93 (<2bum8sINN98j@roche.csl.sri.com>).
Eric,
The chi-square test is fairly easy to implement. Understanding the alogrithm and interpreting what the test results mean is as important as a proper implementation. An excellent text that covers testing PRNGs (including, chi-square, KS, runs (up, down, above & below the mean), and autocorrelation) is Simulation Modeling & Analysis, by Law & Kelton.
Does the 'runs up' (or 'runs down') test with run-length equal to two get me anything over the standard chi-square test? I left it in.
Yes. It tests yet another aspect of "is the data truly random?"
First I ran the output from my version of the IPG algorithim that I posted a couple days ago :
% ./boucher < ipg.out Occurances: n = 12000000, V=-8375833.71 Character occurances non-random Successions: n = 46875, V=62287.82 Character successions non-random
Unless the V is a typo, there is an error in the code. The chi-square statistic can never be negative.
Then I ran output from a test RNG that's basically a loop around random():
% ./boucher < myrandom/out Occurances: n = 3414720, V=213050.62 Character occurances non-random Successions: n = 13338, V=1143.41 Character successions non-random
I did considerable testing on random() a while back. It is actually quite good at producing a uniform distribution. There were other problems however (notably autocorrelation in triplets).
Eric Murray ericm@lne.com ericm@motorcycle.com http://www.lne.com/ericm PGP keyid:E03F65E5 fingerprint:50 B0 A2 4C 7D 86 FC 03 92 E8 AC E6 7E 27 29 AF
I suggest you take a look at the chi-square program and check it for errors. Based on the above observations, I am a little suspicious of your results.
As a side note, I tend to test PRNGs using stream lengths that are similar to what I will need in a real use of the generator. I also test multiple seeds, because statistically, some seeds will fail. Of course, testing multiple seeds has its own problems (see the bonferroni inequality) of which most non-statisticians are unaware.
I have been curious for a while about developing a statistical test that would examine the expected number of failures of a repeated statistical test. Haven't had the time to look into it yet though - not enough hours in the day. ******************************************************* Clay Olbon olbon@ix.netcom.com engineer, programmer, statistitian, etc. **********************************************tanstaafl
With Kindest regards, Don Wood