piu lentoの日々 (piu lento days)

最初に断ると、正確には「(Linuxなどの)疑似乱数生成器(PRNG)の一様性の問題」だ。乱数自体の話は いろいろあるだろうけど、それではない。

前の稿に書いたように、乱数で画像の表示順序をランダムにしようとしたら、全然一様でなくて、偏りが大きくて  ばっさり棄てた。頻度の最多と最少の比が2以上もあるのでは、全く使えない。 (実験結果を最後に書く)

単に試行回数が少ないせいなのかと思ったが、階級(分類)数約30に対して1000回実施しても偏りは解消しなかった(約1.8)ので、永久に解消しないように思う。

ある掲示板で見たのだが、僕と類似の質問に対して、統計あるいは数学のプロらしき人が、「そんな試行回数じゃ全然足りない。文句を言う前に統計を勉強しろ」みたいな偉そうなことを書いていた。そういう連中は10万回とかが最低レベルで、基本は「無限の回数」なのだろうが、そんな前提では全く実用にならない!

そもそも、一様な乱数なら、なぜ試行開始から しばらく または ずっと 偏りが生ずるのだろうか? 階級数は少ない(= 狭い)ので偏る理由がない。確かに確率論的には ばらつくこともあり得るが、階級の数より充分大きい(例: 30倍)回数でも依然として偏ったままなのはおかしい。確率論での「充分大きい」は1000倍とか1万倍なのだろうか?

不思議なのは、それを使っているであろう多くのアプリケーションが問題ないことだ。僕の使い方が悪いのか、偶然問題が起こらないのか、そういうものなのか、実際には問題があるけど隠れているのかのどれかは分からない。

 

以下、細かい話である。

上に書いた、乱数のバラつき(階級数29の場合、最多と最少頻度の比が大きい)が気になったので、Linux、特にPHPで使える乱数機能を いろいろ試してみた。

なお、試行回数は階級数(29)の20倍の580回とした。また、頻度の集計には、Stack overflowの"How to generate a random number from a uniform distribution in php?"の回答1に書かれていたものを使った。

以下に、試した方法ごとの最多と最少頻度の比を示す。なお、実行するたびに比は変動するので、2回実施した。

1回目

• PHP: rand: 5.6※
• PHP: mt_rand:2.7※
• PHP: random_int: 2.4
• PHP: statsパッケージのstats_rand_gen_iuniform: 2.8
• /dev/urandom (4バイト読み出し): 4.7 (処理に誤りがあったので取り消し。やり直した値はPSを参照のこと。)
• opensslコマンド(openssl rand 4)＊: 3.0 (処理に誤りがあったので取り消し。やり直した値はPSを参照のこと。)
• shufコマンド(shuf -rn 1 -i 0-MAX): 2.5
• Python: numpy.random.uniform＊: 6.7
• rand+僕の改良案2＠: 2.3

2回目

• PHP: rand: 2.6
• PHP: mt_rand: 2.6
• PHP: random_int: 2.7
• PHP: statsパッケージのstats_rand_gen_iuniform: 2.8
• /dev/urandom: 3.1 (処理に誤りがあったので取り消し。やり直した値はPSを参照のこと。)
• opensslコマンド: rand: 2.8 (処理に誤りがあったので取り消し。やり直した値はPSを参照のこと。)
• shufコマンド: 2.6
• Python: numpy.random.uniform: 4
• rand+僕の改良案2: 4.1

メモ

• ※ ドキュメントではrandとmt_randは同じものなので、差が出るのはおかしい。mt_randをrandのあとに実行した関係があるのだろうか。実際、2回目はrandとmt_randの比は近かった。
• ＊ Pythonのnumpy.random.uniformは/dev/randomを使っているのか、随分時間が掛かった。opensslのrandも遅かった。
• ＠ randの出す値の密度や間隔と実際の値域のそれが異なることが悪いのかと思い、階級数より充分大きな範囲の乱数から縮小するようにしてみた。要するに、浮動小数点の乱数(0〜1)を任意の範囲の整数にする手順にしてみた。また、結果の整数の乱数を出すのに、以下の2とおりを試した。
  • 案1: mod(剰余)
  • 案2: 除算

 

結局、比較的少ない試行回数ではPHPのrandom_intとshufコマンドが一番一様そう(2.6付近)で、その次はstats_rand_gen_iuniform(2.8)となった。stats_rand_gen_iuniformは安定しているところが良さそうだ。

randやmt_randは悪くないが、変動が大きそうだ。opensslのrandは良くはないが、比較的安定している。なお、Pythonのnumpy.random.uniformや/dev/urandomは今一つだった(後者は使い方が悪いのかも知れない → opensslとともに整数化の処理に誤りがあったので値を取り消した。: 9/15 10:26)。

(9/15 9:03) numpy.random.uniformについては、参考にしたページにある分布のグラフは ほぼ平坦で、これなら許せる(と期待して試した)。その試行回数は10000回(個)なので、階級数(そこでは10)の1000倍くらい試行しないと一様にならないのかも知れない。この、どれだけ繰り返せば充分かというのは、どうすれば分かるのだろうか? また、本質的に そうできない用途では どうするのだろうか?

(9/15 9:12) と書いたあとにグラフを良く見たら、上の例で生成している乱数(グラフの横軸)は整数でなく浮動小数点数だった! 僕は整数に丸めて評価したので、その辺りに問題があるのかも知れない。丸めについては僕も気になっていて、上述の改善案で試行錯誤したけどうまく行かなかった。

グラフを目で見た時と同様に、積分して整数にすればうまく行くだろうか? 面倒なことだ・・・ ← 丸めるのは積分(個数を求める場合)でなく単なる整数化(例: 四捨五入)で良いから、問題なかったはず。

いずれにしても、僕にはまったく許容できない偏りである。

そういう問題または仕様あるいは注意事項があるなら、ドキュメントに書くべきだと思うが、まったく見たことがない。せいぜい"cryptographically secure"かどうかだけだ。

僕に言わせれば、こんなに偏るものがsecureとは思えない。まあ、見るところが違うのだろうけど。

 

(9/16 13:59) 元々の用途(このブログの「時替わりギャラリー」)に対する うまい対処方法(workaround)を思い付いた。: 画像を替えるのに乱数(PHPのrand)を使うが、それで次に表示する画像の番号を直接決めるのでなく、乱数と現在の画像の番号を加えたもの(と画像数の剰余(mod))を次の画像の番号にするのだ。現在の画像番号をn、全画像数をNとすると、次の画像番号n'は以下の式で得られる。

n'= (n + rand(1, N-2)) % N

rand: 整数の乱数: 引数: 最小値, 最大値
%: 剰余

これなら、仮に乱数に出やすい値xがあっても、今の画像からx枚目の画像が出やすくなるだけで、いつも同じ数種類の値(しかも、それらが画像数と「いい関係」にある)が出るのでない限り、特定の画像が出やすくなることは起こりにくいと考えられる。

が、実は そうでもないというオチはないか?: 少なくともrandは今の画像の番号は分からないので、特定の画像が出やすくなるような値は出せないはずだ。あるとすれば、周期的に同じような値が出ること(上の「いい関係」)だろうか? 考えると難しい(面倒だ)。

↓

(9/17 16:28) ところが、そうは問屋が卸さなかった。表示される画像をチェックしていたら、やっぱり良く出るものがあった。想像だが、上のように乱数に何かを加えたものも元の乱数と同じ性質であり、その元の乱数に良く出る値があるなら良く出るスキップ数となり、そのスキップ数と全画像数の関係(割り切れるか)にも よるだろうが、結局同じ画像が良く出るのではないだろうか。

結局、ギャラリー内の画像の順序のとおりに表示するように戻した。

↓

(9/18 12:22) その後、擬似的な乱数としてページのアクセス時刻(正確には この処理を開始する時の時刻, μs単位)を使ってみたが、不思議なことに やっぱり一様でなく、良く出る値(→ 良く出る画像)と全然出ない値が生じた。

例えば、(回数は多くないが、)71回(約4時間分)のアクセスでは、最高に出た値の頻度は最小(1回)の5倍だった。出ない値は2個で、全体の平均は2.6回だった。

アクセス時刻(の階級数での剰余)がある時刻に集中するとは考えられないので この原因も謎だが、出ない3個(各1回と想像)が出やすいところに回って、平均の2.6+2 → 5回になったのかも知れない。

画像数(= 階級数)が29個と、10の倍数でないなのが関係していることも疑った。: アクセスはランダムな時刻に来るが、その時刻を階級(各画像)に振り分ける時に偏りが生ずるのではないか? ただ、時刻は100μs単位(0-99)のように区切っては いないので、剰余が偏りを生むとは思えない。

が、頻度分布を見ると、後半の12から25までの頻度が比較的多いのが気になる。その幅は13で、100と29の剰余に合う。また、頻度の高い区間が始まる12は13-1だ。単なる偶然とは思うが不思議だ。

だから、これは たまたまアクセス時刻が偏ったためで、回数を多くすれ(長時間、数日?見れ)ば均等になるのだろう。が、僕には、起動後数時間経っても偏りが直らないのは許容できないので、この方法もボツにした。

 

PS. Pythonのページに関する追記から、試行回数を増やして一様性を比較してみたら、どうやら、階級数x500回以上試行すれば、僕が満足できる一様性(最多/最少が概ね1.2 → ばらつき20%以内)に できそうなことが分かった。 (9/15 10:37)

試行回数と各方式での最多と最少頻度の比を示す。

29階級x20回= 580回: 2.5辺り (Pythonは3辺り、opensslは5辺り)

• PHP: rand: 2.38
• PHP: random_int: 2.64
• /dev/urandom: 2.42
• shuf: 2.31
• openssl rand: 4.5
• Python numpy.random.uniform: 4.83 2.9

29階級x500回= 14500回: 1.3辺り (random_intとshufとPythonは1.2辺り)

• PHP: rand: 1.26
• PHP: random_int: 1.19
• /dev/urandom: 1.26
• shuf: 1.21
• openssl rand: 1.31
• Python numpy.random.uniform: 2.07 1.2

29階級x1000回= 29000回: 1.1辺り (random_intとshufは1.15辺り、Pythonは1.2辺り)

• PHP: rand: 1.11
• PHP: random_int: 1.15
• /dev/urandom: 1.11
• shuf: 1.24
• openssl rand: 1.11
• Python: numpy.random.uniform: 2.26 1.19

本文で懸念したように、/dev/urandomとopenssl randの使い方(整数化の方法)に誤りがあったので修正した。

また、Pythonの一様性が悪いのは、使い方が良くないせいかも知れない。 ← (9/15 13:42) Pythonのnumpy.random.uniformの出力に想定外の問題があった。: 生成する乱数の最小, 最大値での頻度が他のものの半分くらいになっていた(乱数を表示する時の丸めの問題かも知れない)。 → 仮対処として、生成する範囲を広く取って数を多目に生成して範囲内のものだけを使うようにしたら、一様性は改善された。 → 上を更新した。

それから、Pythonの1回の実行でその系統全部の乱数を生成するようにしたら、実行速度は速くなった。

結局、試行(繰り返し)回数を随分増やせば一様になることが確認できた。実際に使う時にはそうできないことがあるが、その場合は「シャフル」のように あらかじめ一様な分布を作っておくとか、分布が一様になるように調整(取捨選択)するのだろうか?

あと、この問題は「システムの起動後しばらくは(乱数が今一つなので)安全でない」ということには ならないのだろうか? (この辺りは全くの素人なので、単なる思いつきである。)

 

(9/15 10:37 若干修正, 10:37 PSを追加, 16:22 題を明確化; 9/16 13:59 対処方法を追記, 22:42 題を変更; 9/17 16:28, 9/18 12:22 乱数を諦めた件とその後の試行を追記)