DouKaku? 2264 shiro: 巧みだなあと思ったんですが、ごくわずかの...(重複無し乱数)

Comment detail

重複無し乱数 (Nested Flatten)

This comment is reply for 2256 rubikitch: 久々の1行問題(重複無し乱数). Go to thread root.

巧みだなあと思ったんですが、ごくわずかの確率でrandが同じ値を返すケースがあるはずで、その場合の要素の並び順はsortの実装によって固定されてしまうから、微妙に偏りが出てくるんじゃないかな、という気もします。

(例えば簡略化のために要素数を2つ、randは0か1しか返さないとして、sortがstableだとすると、可能な4通りの組み合わせのうち(0 1)が3回、(1 0)が1回となる)

現実にはdoubleが重なる確率なんて極めて低いでしょうけど。

ライブラリを使ってシャッフルしているケースでももしかするとそういう偏りがある可能性はありますね。

気になったのでPythonのrandomライブラリを見てみたところ#2254と同じアルゴリズムでした。

for i in reversed(xrange(1, len(x))):
    # pick an element in x[:i+1] with which to exchange x[i]
    j = int(random() * (i+1))
    x[i], x[j] = x[j], x[i]

ご指摘ごもっともと思ったのでMATLABでこのアルゴリズムで生成する数列の偏りをチェックしてみました(#2615)。このチェック方法がいいのかどうかは実はよく分からないのですが、これでおおざっぱに見る限り普通の精度の乱数を使えば偏りはものすごく小さそうです。ちなみにMATLABの標準のrandpermという同じ目的の関数も#2256と同様のアルゴリズムになっています。

もちろん、IEEE doubleを使った場合2^53通りの値がrandで出現するので (Rubyはメルセンヌツイスタでしたよね? )、「値が衝突する可能性」自体がものすごく少ないです (サンプル数10^5くらいじゃその計算をdoubleでやったら計算誤差よりはるかに小さいくらいの影響)。

ただ、暗号とかストカスティックシミュレーションみたいな、膨大なデータから統計的に意味を見つけ出すような分野で、素材となる元のランダム列に偏りが入っていると結果に影響が出てくるわけで、「そういう用途には使えない」ということだけわかっていれば良いのでは。標準Cの rand() が「用途によっては使えない」のと同じような意味で。

今回のお題はbingoですから、その範囲では十分に題意に沿った回答であると思います。

先の投稿の意図は(rand自体の品質の話ではなく)このアルゴリズム自体に起因する偏りがrandの精度に対してどれくらい小さいかを直感的に見たというだけのもので、最初の投稿について題意云々を批判したつもりはまったくないのですが、そのように読めたのでしたらもうしわけなかったです。失礼しました。

ああ、私もshgさんの投稿を批判と取ったわけではありません。2番目と3番目のパラグラフはshgさんの投稿に対してではなく、このやりとりを読んだ第3者の人が必要以上に問題を大げさにとらえたらまずいなという予防線みたいなつもりでした。まぎらわしくってすみません。

で、実際の偏りの評価なんですが、「randの精度に対して急速に小さくなる」というのはまあ予想できることで、「ものすごーく小さいはずなんだけれど実際のところ53bit精度では具体的にどのくらいの偏りなのかな」という点に触れられていなかったのでああいう書き方になってしまった、ようです。今読み返すとちゃんとしたコメントになっていませんね。失礼しました。

実は#2264時点で衝突する確率の計算も試みてみたのですが、doubleで計算したらすぐに誤差に埋もれてしまうし、無限多倍長数で計算したら計算時間が爆発したので諦めていたのでした。ちゃんと近似式を導いて評価するのが良いのでしょうが…

乱数が衝突する確率を直接計算すると、pを乱数の精度(最小単位の意味で)として、

1-(1-p)(1-2p)(1-3p)...(1-(n-1)p)

みたいな感じでしょうか。p=2^(-53)でn=25だとおよそ2.1e-14。p=2^(-31)でn=100だとおよそ2.3e-6。n個の中で衝突する確率なのでこの値は当然nに大きく依存しますが、実際は衝突は全体にまんべんなく確率的に起きるわけでnが大きいと偏りの問題が大きくなるというわけではないですよね。

bingoの評価としては、1〜nのそれぞれが1番目、2番目、.. n番目に来る確率みたいなのをチェックする方がより直接的かな? (してません)

古い話へのフォローですが、ちゃんと衝突確率を計算してるページを見つけました。(タイトルだけ見るとsort_by{rand}のせいでBigDecimalに問題が生じたのかと勘違いしそうですが、単に衝突確率計算で多倍長整数演算を使いまくったというだけの話のようです。)

see: sort_by{rand}'s bias makes BigDecimal cry

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq