7

乱数ジェネレーターが実際の乱数を生成しているかどうかをどのようにテストしますか?

私のアプローチ:最初にサイズMのハッシュを作成します。ここで、Mは素数です。次に、乱数ジェネレーターによって生成された数値を取得し、Mを使用してmodを取得し、すべてのハッシュまたは一部のみが入力されることを確認します。それが私のアプローチです。視覚化でそれを証明できますか?

私はテストについての知識が非常に少ないので。この質問の徹底的なアプローチを提案してもらえますか?前もって感謝します

4

4 に答える 4

12

乱数ジェネレーターが正しく機能していることを保証できないことに注意してください。範囲[1,10]の完全な一様分布でさえ、10個の数値のランダムサンプリングで10x10を取得する可能性が10-10あることに注意してください。

可能性はありますか?もちろん違います。

だから-私たちは何ができますか?

乱数ジェネレーターが実際に均一に分散されている場合、組み合わせ(10,10、....、10)はありそうもないことを統計的に証明できます。この概念は、仮説検定と呼ばれます。このアプローチでは、「x%の確実性レベルで-データが一様分布から取得されているという仮説を棄却することができます」と言うことができます。

これを行う一般的な方法は、ピアソンのカイ2乗検定を使用することです。この考え方は、あなたの考え方と似ています。表に入力して、各セルで観測された(生成された)数値と、予想される数値を確認します。帰無仮説の下での各セルの数(あなたの場合、期待されるのはk/M-です。ここで、Mは範囲のサイズであり、kは取得された数の総数です)。
次に、データに対して何らかの操作を行い(この操作の正確な内容については、ウィキペディアの記事を参照してください)、数値(検定統計量)を取得します。次に、この数がカイ二乗分布から取得される可能性が高いかどうかを確認します。そうである場合-帰無仮説を棄却することはできません-そうでない場合-データが均一なランダムジェネレーターから取得されていないことをx%の確実性で確信できます。

編集:例:
あなたは立方体を持っていて、それが「公平」であるかどうかをチェックしたいと思います(で均一に分布してい[1,6]ます)。たとえば、200回投げて、次のテーブルを作成します。

number:                1       2         3         4          5          6
empirical occurances: 37       41        30        27         32         33
expected occurances: 33.3      33.3      33.3      33.3       33.3       33.3

さて、ピアソンのテストによると、統計は次のとおりです。

X = ((37-33.3)^2)/33.3 + ((41-33.3)^2)/33.3 + ... + ((33-33.3)^2)/33.3 
X = (18.49 + 59.29 + 10.89 + 39.69 + 1.69 + 0.09) / 33.3
X = 3.9

ランダムC~ChiSquare(5)の場合、それよりも高い確率3.9~0.45(ありそうもないことではありませんが)1です。

したがって、帰無仮説を棄却することはできず、データはおそらく均一に分布していると結論付けることができます。[1,6]


(1)値が0.05より小さい場合、通常は帰無仮説を棄却しますが、これはケースに大きく依存します。

于 2012-08-30T05:53:36.790 に答える
1

私の素朴な考え:
ジェネレーターはディストリビューションに従っています。(少なくともそうする必要があります。)妥当な量の実行を実行してから、値をグラフにプロットします。ポイントに回帰曲線を当てはめます。それが分布の形と相関している場合、あなたは良いです。(これは、投影とヒストグラムを使用した1Dでも可能です。また、MatLabなどの適切なツールを使用して完全に自動
化できます)前述のように、Diehardテストを使用することもできます。これは確かに優れていますが、少なくとも側。

于 2012-08-30T04:59:14.010 に答える
0

区間[0、1]で一様分布を生成したいとします。

次に、1つの可能なテストは

for i from 1 to sample-size
when a < random-being-tested() < b
counter +1
return counter/sample-size

そして、結果がba(bからaを引いたもの)に近いかどうかを確認します。

もちろん、0と1の間のa、bを入力として受け取る関数を定義し、カウンター/サンプルサイズとbaの差を返す必要があります。0.01の倍数、a <bの可能性のあるa、bをループします。差が事前設定されたイプシロンよりも大きい場合、たとえば0.001の場合は、a、bを印刷します。

これらは、外れ値が多すぎるa、bです。

サンプルサイズを5000にすると、ランダムにテストされるのは、合計で約5000 * 5050回呼び出されますが、それほど悪くないことを願っています。

于 2012-08-30T05:14:11.657 に答える
0

私も同じ問題を抱えていました。コードの記述が終了したとき(外部RNGエンジンを使用)

結果を調べたところ、多くの結果が必要な場合は常に、すべてがカイ2乗検定に失敗することがわかりました。

私のコードは乱数を生成し、各結果範囲の量のバケットを保持します。結果が多いのにカイ二乗検定が失敗する理由がわかりません。

私の調査中に、C#Random.next()が任意の範囲の乱数で失敗し、一部の数値のオッズが他の数値よりも優れていることがわかりました。さらに、RNGCryptoServiceProvider乱数プロバイダーが大きな数値をサポートしていないことがわかりました。

0〜1,000,000,000の範囲の数値を取得しようとすると、0〜300Mの範囲の数値の方が表示される確率が高くなります...

その結果、私はRNGCryptoServiceProviderを使用しており、範囲が1億を超える場合は、自分の数値(RandomHigh * 100M + RandomLow)を組み合わせ、両方のランダムの範囲が100Mよりも小さいので問題ありません。

幸運を!

于 2013-12-31T08:42:13.283 に答える