in reply to Testing for randomness

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.

Replies are listed 'Best First'.
Re: Re: Testing for randomness
by sandfly (Beadle) on Oct 29, 2003 at 22:35 UTC
    >>
    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.

[reply]

In Section Seekers of Perl Wisdom