半分ビットの確率を求めるRubyスクリプト

今日のエントリでは，高校の数学などで出てくる「n C m」というのを，"n choose m"と書くことにします．(tex記法できれいに出てこないので．)
レポートの解説は昨日の昼過ぎに完成し，公開ました．
その中で，「Nビット(ただしNは偶数)の値をランダムに生成したとき，その中に1のビット数がちょうど半分になる確率」を，N=8とN=32のときに求めています．
数式としては，

Nビットの中のちょうどN/2ビットが1になるのは，"N choose N/2"通り
Nビットのすべてのパターンは， $2^N$ 通り
なので確率は，"N choose N/2" / $2^N$

と表せますが，Nが大きくなるにつれて，この確率がどんなふうになるのか，ちょっと想像しにくいです．階乗というのが曲者a hard nut to crackです．
プログラムをする前の小話ですが，具体的なNが分かっていて，"N choose N/2"を計算するには，Google検索が使えます．詳細も便利です．
ですがこの方法で，いくらでも大きな値を求められる保証はありません．google:2^1024は無理のようです．
Googleの話はここまでにしまして，結局，プログラムを自作しました．Nを指定したら，これらの値を求めるプログラムです．
値が小さければC言語で書けますが，Nに128とか1024とか入れてみたいので，いくらでも大きな整数を表現でき，かつプログラムをシンプルに書くことのできる，Rubyを採用しました．
早速ですがコードです．

#!/usr/bin/env ruby

# 指定した偶数のビット長に対して，
# 重み(1のビット数)がビット長のちょうど半分になるビット列の個数と，
# ランダムなビット列の重みがビット長のちょうど半分になる確率を求める．

class Halfbits
  def initialize(bit_ = 32)
    @bit = bit_.to_i
  end

  def start
    if @bit % 2 == 1
      puts "odd bits"
      return
    end

    calc
    print to_s
  end

  def calc
    @numerator = choose_half
    @denominator = 2 ** @bit

#    # 確率を求める簡便な方法．ただし@bit=1024では正しく計算できない．
#    @probability = @numerator.to_f / @denominator.to_f

    require 'bigdecimal'
    num_big = BigDecimal(@numerator.to_s)
    den_big = BigDecimal(@denominator.to_s)
    @probability = (num_big / den_big).to_f
  end

  def to_s
    <<EOS
bit: #{@bit}
half bits: #{@numerator}
all bits: #{@denominator}
probability: #{@probability}
EOS
  end

  def choose_half
    # "@bit choose @bit/2" を，
    # (@bit * (@bit - 1) * … * (@bit / 2 + 1)) / (1 * 2 * … * (@bit))
    # により計算する．

    result = 1
    1.upto(@bit / 2) do |i|
      result *= (@bit - i + 1)
      result = result / i
    end
    result
  end
end

if __FILE__ == $0
  Halfbits.new(ARGV.shift || 32).start
end

少し解説をしておきますと，

小さなRuby スクリプトでも，クラスを定義して，「クラス名.new.start」により本体を実行する習慣をつけています．本体実行の直前のif文については，google:if __FILE__ == $0をご覧ください．
メソッドchoose_halfで，"N choose N/2"を求めます．コメントにあるように式変形をして，分子は大きい値から掛けていき*1，分母は小さい値から割っています．これで，途中で小数になることなく，正しい値が求められます．
確率は，分子と分母を求めて割り算，では終わりません．整数割る整数は，整数になってしまうので，不動小数点型に変換してから割り算を…これでも，Nが1024くらいになると，ダメでした．結局，bigdecimalライブラリを使いました．

そして実行結果．

$ ruby halfbits.rb
bit: 32
half bits: 601080390
all bits: 4294967296
probability: 0.139949934091419
$ ruby halfbits.rb 8
bit: 8
half bits: 70
all bits: 256
probability: 0.2734375
$ ruby halfbits.rb 1024
bit: 1024
half bits: 44(略)70
all bits: 17(略)16
probability: 0.0249278058929795

1024ビットの乱数で，1のビットがちょうど512個になる確率は，40分の1程度．思っていたより高いなあというのが，率直なところです．

*1:と思ったのだけど分子も小さい値から掛けていっていいのかも…．

わさっきhb

大学（教育研究）とか，親馬鹿とか，和歌山とか，とか，とか．

半分ビットの確率を求めるRubyスクリプト