random_subset.rb

module Enumerable
  def sum
    inject(0) {|s, v| s + v}
  end

  def avg
    sum / length
  end
end

picks = Hash[(-5..rand(5)).map{ [rand(1000), []] }]
picks.each do |weight, counts|
  picks[weight] = [0] * picks.length
end

puts "Weights: #{picks.keys.sort.join ', '}"
puts

count = 0
while true
  picks.keys.sort_by do |weight|
    -1.0 * Math.log(rand()) / weight
  end.each_with_index do |weight, index|
    picks[weight][index] += 1
  end

  count += 1
  next unless count % 10000 == 0

  relative_position_errors = []

  picks.each do |weight, counts|
    picks.each do |weight2, counts2|
      next if weight == weight2
      expected = 1.0 * weight / (weight + weight2)

      actual = 0
      (1...picks.length).each do |position|
        # the probability that weight is picked before weight2 should be according to their relative weights
        greater = 1.0 * counts.first(position).sum / (counts.sum - counts[position])
        actual += 1.0 * counts2[position] / count * greater
      end

      relative_position_errors.push((expected - actual).abs / expected)
    end
  end

  first_position_errors = []
  picks.each do |weight, counts|
    expected = 1.0 * weight / picks.keys.sum
    actual = 1.0 * counts.first / counts.sum
    first_position_errors.push((expected - actual).abs / expected)
  end

  puts "After #{count} tries:"
  puts "Average Relative Position Error: #{relative_position_errors.avg}"
  puts "Maximum Relative Position Error: #{relative_position_errors.max}"
  puts "Average First Position Error: #{first_position_errors.avg}"
  puts "Maximum First Position Error: #{first_position_errors.max}"
end