Re: Testing for randomness

[Anonymous Monk]

I have several suggestions:

1. Do not try the compression-based attempt listed above, it isn't likely to work
2. You can't tell from a single test if a stretch of 500 heads followed by 500 tails is non-random: you'd have to permute or at the very least replicate
3. You can (should!) test higher-order statistics. Right now, you perform a chi-squared distributional test on 0-th order statistics (number of heads, number of tails). Instead, perform that test on the number of pairs (e.g. 1st order statistics): HH, HT, TH, TT. You can extend that to higher-orders if you are really interested, but first order should be enough to find bias, and easy to implement.

So in summary, I recommend you perform multiple (100s) tests on 0th, 1st, and 2nd order statistics.

[sandfly]

>>
You can't tell from a single test if a stretch of 500 heads followed by 500 tails is non-random: you'd have to permute or at the very least replicate
<<

The 500H,500T sequence would be extremely good evidence of a non-random generation. By my reckoning, in any one trial of 500 tosses, you have about 1 chance in 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 (== 10**50) of throwing all heads or all tails.

The odds of throwing the sequence are therefore about 1 in 10**100 - a googol. If that is not a good enough result, how would replicating the result help? You just change the odds to 1 in 10**200.