From: Shin-ichiro HARA <sinara@...>
Date: 2005-07-05T16:59:34+09:00
Subject: [ruby-list:40915] Re: 配列をシャッフル

原です。

>小波です。
>
>Hiroyuki Adachi wrote:
>> array = [1, 2, 3, 4, 5]
>> array.each_index do |idx|
>>   jdx = rand(idx + 1)
>>   array[idx], array[jdx] = array[jdx], array[idx]
>> end
>> p array #=> [1, 4, 5, 2, 3]

>本当にランダムにシャッフルできるかどうかが気になったので

突然ですが、このアルゴリズムの正当性を数学的帰納法で証明します。

今、array = [0, 1, 2, ... , n-1] としておいて、

P(k) = 「array[0...k] までは 0,1,...,k-1 が一様にシャッフルさ
         れ、残り array[k..-1] は動いていない」

とおきます。まず全てが始まる前、P(0) は正しいのは明らか。今
P(idx) が正しいとする。このとき

   jdx = rand(idx + 1)
   array[idx], array[jdx] = array[jdx], array[idx]

がなされた後では、

(1) 数 idx は、array[0..idx] の各エントリと等確率にスワップ
されるので、idx が array[0..idx] のそれぞれのエントリに出現
する確率は p = 1/(idx+1) である。

(2) array[0..idx] のエントリを一つ固定する。スワップが平等な
ので、帰納法の仮定より数 0,1,...,idx-1 がそこに出現する確率は
等しい。(1)よりその値は各々 (1-p)/idx = 1/(idx+1) である。

以上よりP(idx+1)が正しい。よって、帰納的にP(n)すなわち、全て
一様にシャッフルされることが証明できた。（証終）


ところで、ちょっと気になったのが、

>せて，得られた統計データをΧ2乗検定してみました。大丈夫みたい。以下は
>検定に使ったソースです。検定はパスしました(^^)

ということなのですが、帰無仮説、対立仮説、有意水準などを設定
していないので、ここで小波さんがしていることは、いわゆる「検
定」ではないですよね。「アルゴリズムが正しいとすれば、この統
計量は（適合度検定でよく使われる）カイ２乗分布になるはずなの
で、そのカイ２乗分布の特徴の一つである50%点を理論値と比較し
てみた」というところでしょうか。

確かに今の場合、シャッフルが偏っていることを示すのではなくて
正しいことを示したいので、そう単純でなく、こんな風な話になっ
てしまうのは理解できるのですが、それにしても中央値のみを得て
他の情報を捨てているのがもったいない気がします。ヒストグラム
を眺めて納得するのが単純でいいかも。

一方、よく使われるアルゴリズムの正当性は、検定によらず確率
の計算よるべきではないでしょうか。計算可能な場合は。