ランダム順列

id:namasute0:20060129#1138517314による指摘。
さて、実はこのような指摘が出るかもしれないことは実は予期していて、考えてあったりする。この指摘のキモは、random関数が返す値が実際にはrandomと言うわけではないことに由来している。
例えば、[0,1)の範囲の値を本当にランダムに返す関数があったとして、この関数が0.5を返す確率はいくつだろうか、という問題を考える。で、この答えとしては、0.5 * (計算機イプシロン) * 2というのがおそらく答えになる・・・のだけれども、この計算機イプシロンって何よ？という話。つまり、これって単純に数を浮動小数点でしか表せないという仕様があるからこういう現象が発生しているのであって、実数をきちんと表現することが可能ならば問題はないはずなのだ。
つまり、こういうことだ。[0,1)の範囲の値を本当にランダムに返す関数があれば、その関数がちょうど0.5を返す確率というのは0になるはずだ。つまり、これを前提にすれば、複数回のrandによって同じ値が返ってくることはありえない。
で、実は残りの二つのアルゴリズムもこの影響と言うのは受けたりする。例えばint(rand(3))は本当に0が1/3で、1が1/3で・・・となるのだろうか？あるとても大きな数kがあったとして、1/kと1/(k+1)の間に一つも浮動小数点がないということはありえるんじゃないか？
なんか逃げているような気もするけれども、本質的にrandamでないものを使ってrandomを作ろうとしているわけで、当然こうなる。僕はその精度の中で十分にランダムなものを生成していると思うのだけれどもどうか。