From: Ilmari Heikkinen <kig@...>
Date: 2004-12-17T11:26:41+09:00
Subject: Re: [ANN] rand.rb 0.9: Random access methods for Enumerables

> How could you know, there is as much randomness as you want?

Here's a method for testing bias in array shuffle. I'd be interested in 
hearing about other approaches to probabilistic testing.. anyone?

module RandTests
   # RandTests.check_bias{|arr| arr.shuffle!}
   # => [true, {[2, 3, 1]=>8407, [2, 1, 3]=>8323, [3, 2, 1]=>8382,
   #      [1, 2, 3]=>8442, [3, 1, 2]=>8255, [1, 3, 2]=>8191}]
   #
   # Caveat!
   # Only works for (very) small arrays.
   # E.g. array of size 10 has 10! permutations = 3628800,
   # which means that you'd have to do around 10^9 to 10^10 tests
   # for the bias check to work properly and even then the permissible 
bias
   # would have to be large.
   #
   def self.check_bias(
     array_size=3,
     test_count=50000,
     permissible_bias=0.02,
     &block
   )
     total_permutation_count = (1..array_size).inject{|s, i| s*i} # 
factorial
     array = (1..array_size).to_a
     avg_permutation_count = test_count.to_f / total_permutation_count

     permutation_counts = {}
     (1..test_count).each{
       perm = block.call(array.dup)
       permutation_counts[perm] ||= 0
       permutation_counts[perm] += 1
     }
     test_result = permutation_counts.all?{|perm, count|
       count.between?(
         avg_permutation_count - permissible_bias*avg_permutation_count,
         avg_permutation_count + permissible_bias*avg_permutation_count)
     }
     [test_result, permutation_counts]
   end
end


-Ilmari