半年ほど前、ショックな出来事があった。それまでずっと正しいと信じていたアルゴリズムが間違いであることが判明したのだ。
コトの発端は、このブログにもたま〜にコメントを書き込んでくれる
木公さんのブログで、
ある確率を求めるために始めたモンテカルロ・シミュレーション。そこで行われていた「ランダマイズ」処理。
「ランダマイズ」ってのは、要するに、トランプの「シャッフル」みたいなもので…(後から考えてみれば、この程度の理解しかしていなかったことが間違いの原因だったのだが)。例えば、0から9の数字の書いてある10枚のカードがあるとして、これが1列に並んでいる。これをデタラメに並べ替えるような処理。
僕がいつもやっていたのは、次のようなやり方。
まず、SeatNo[]という「席順」を管理する配列にあらかじめ0〜9の数字を入れておいて(初期状態では、0〜9の順に並んでいるということ)、
for (i = 0; i < SeatNo.Length; i++)
SeatNo[i] = i;
次に、ある位置に置いてあるカードとその位置とは異なる位置に置いてあるカードとの入れ替えを、全ての位置について1回ずつ行う(方式1)。
for (i = 0; i < SeatNo.Length; i++) {
do {
r = rnd(0, SeatNo.Length);
} while (i == r)
swap(SeatNo[i], SeatNo[r]);
}
ここで「rnd(x, y)」というのは、x以上y未満の整数の乱数を返す関数。
「何かdo-while文が嫌だなぁ〜」という気分のときは、「『自分自身と入れ替える』(結局入れ替わらないが)ってのもアリにしよう!」と、
for (i = 0; i < SeatNo.Length; i++) {
r = rnd(0, SeatNo.Length);
swap(SeatNo[i], SeatNo[r]);
}
こうしていた(方式2)。
アイデアのモトにはまさに「トランプのシャッフル」がある。目の前にトランプを1列に並べて、これとこれ、これとこれ、とデタラメに選んでは入れ替えていく。ところが、木公クンの調査によると、このやり方では「ランダマイズされていない」という。
上のやり方で、もしちゃんとランダマイズされているのだとしたら、ランダマイズ後の各SeatNo[]には0〜9が等しい確率で入っているはずである。初期化してはランダマイズ、初期化してはランダマイズ、という処理を嫌になるほど繰り返せば、各SeatNo[]には平均して「4.5(0〜9の平均値)」に近い値が入っているはずである。そうなってないなら、何かが間違っている、ということである。
(ところで、関係ないけど、プログラミングの本を読んでいると、上の「嫌になるほど繰り返す」みたいな表現を「文学的表現」と呼ぶ人がときどきいる。一種のお世辞のつもりなのか、「文学」に対する揶揄なのか、あるいは単にバカなだけなのかよくわからないが、いずれにせよ、その著者自身の文章表現力の乏しさみたいなものが表われてしまっているように思う。)
そこで、実際に上の(偽)ランダマイズ処理を1000万回行って平均値を求めてみると…、
確かにランダムになっていない(笑)。それどころか、綺麗にバイアスがかかってる(涙)。この「中央より後半で膨らむ」形は、並び替えるカードの枚数に依存せずに現れる。
考えてみれば、「ランダマイズ」というのは、単に「シャッフルする」ことではなく、文字通り「ランダム」にしないといけない。つまり、現在の状況(並び替え前のカードの並び方)に依存せずに、生じうる全ての事象(「並び方」)が等しい確率で生じるような方法で並び替えなければ「ランダマイズ」とは言えない。ところが、僕は「デタラメに入れ替える処理を何回も繰り返せば、『ランダム』になるだろう」という程度にしか考えていなかった。逆に言うと、僕の「トランプのシャッフル」では、トランプの並び方は
ランダマイズされていないんですね。ランダマイズされているという前提で賭ければ、当然負ける。
よ〜く考えてみれば、上のやり方で「ランダマイズされていない」のは当たり前で、方式1だと9
10=3486784401通りの「並び替え」パターンが生じうるし、方式2だと10
10=10000000000通りの「並び替え」パターンが生じうる。ところが、そもそも10枚のカードの「並び方」のパターンというのは、10!=3628800通りしかない。そして、9
10も10
10も10!で割り切れない、ということは(ということは!)、これらの方式の「並び替え」では、各事象の生起確率に偏りがある、ということである(割り切れたとしても「各事象の生起確率が等しい」ことの保証にはならないが、割り切れていなければ絶対にダメである)。
例えば、ABCという3枚のカードがあるとして、この3枚のカードの「並び方」のパターンは、ABC、ACB、BAC、BCA、CAB、CBAの6通り(=6!)しかない(まさに「順列」)。今、ABCの順で並んでいるとして、これを方式1で並び替えると生じる結果は、何とACB、BAC、CBAの3通りしかないのだ! 生起頻度は、ACBとBACが3回ずつ、CBAが2回で、全部足すと当然8回(=2
3)。方式2で並び替えると、8通りの「並び方」全てが生じるが、生起頻度は、ACB、BAC、BCAが5回ずつ、ABC、CAB、CBAが4回ずつ、と偏っている(全部足すと27回(=3
3))。
では、どうすればちゃんとしたランダマイズになるかと言えば、これがまた信じられないくらい単純な話。「順列」の考え方そのもので、あるカードとの入れ替え相手を決めるときに、既に確定したカードを選ばないようにするだけでいいのだ(方式3)。
for (i = 0; i < SeatNo.Length; i++) {
r = rnd(i, SeatNo.Length);
swap(SeatNo[i], SeatNo[r]);
}
どこが変わったかわかるだろうか? 「rnd(0, SeatNo.Length)」じゃなくて「rnd(i, SeatNo.Length)」。「0」を「i」にする。この1字の違いが大違い。上述の1000万回ランダマイズして平均値を求めてみる実験だと、どの位置の平均値も4.499〜4.501の間に納まっている(グラフを参照のこと)。このやり方だと、「並び替え」パターン数と「並び方」パターン数は一致するし、よ〜く考えれば、全ての「並び方」が1回ずつしか生起しないこともわかる。
この間違いが何故それほどショックだったかという言うと、有史以来僕が書いたあらゆるプログラム(その中には研究の一環として書いた実験制御プログラムやコンピュータ・シミュレーションのプログラムも当然含まれる)で、方式1か方式2を使っていたから。しかも、自分で書いたプログラムだけでなく、他人にまで「ランダマイズはこうやる」と何の疑いももたずに広めていたのだ。それが間違いだったのである。
半年経ってようやくショックは消えた。また、「ランダマイズ」という処理が単なる「シャッフル」とどう概念的に異なっているのか、よ〜く考えてみる機会を得て、「ランダマイズ」に対する洞察を多少なりとも深めることができたので、今となっては、まぁ良しとしている。やっぱり数学というもの、あるいは数学的素養というものは必要なものである。

0