0

前文

この質問は、(P)RNG および の動作に関するものではありませんrand()。これは、モジュロに対して均一に分散された 2 のべき乗値を使用することです。

序章

%関数から 0 から 5 の間の値を取得する場合など、値を範囲から別の範囲に変換するためにモジュロを使用すべきではないことはわかっていrand()ました。偏りが生じます。ここで説明されています https://bitbucket.org/haypo/hasard/src/ebf5870a1a54/doc/common_errors.rst?at=defaultおよびこの回答では、乱数ジェネレーターを使用するときにモジュロバイアスがあると人々が言うのはなぜですか?

しかし、今日、間違っているように見えるいくつかのコードを調査した後、モジュロの動作を示すツールを作成しました: https://gitorious.org/modulo-test/modulo-test/trees/masterで、十分に明確ではないことがわかりました。

サイコロはたったの3ビット

範囲0..5の6つの値でチェックしました。これらの値をコード化するために必要なビットは 3 ビットだけです。

$ ./modulo-test 10000 6 3
interations = 10000, range = 6, bits = 3 (0x00000007)
  [0..7] => [0..5]

theorical occurences    1666.67 probability 0.16666667

   [   0] occurences    2446    probability 0.24460000 ( +46.76%)
   [   1] occurences    2535    probability 0.25350000 ( +52.10%)
   [   2] occurences    1275    probability 0.12750000 ( -23.50%)
   [   3] occurences    1297    probability 0.12970000 ( -22.18%)
   [   4] occurences    1216    probability 0.12160000 ( -27.04%)
   [   5] occurences    1231    probability 0.12310000 ( -26.14%)

  minimum occurences    1216.00 probability 0.12160000 ( -27.04%)
  maximum occurences    2535.00 probability 0.25350000 ( +52.10%)
     mean occurences    1666.67 probability 0.16666667 (  +0.00%)
   stddev occurences     639.43 probability 0.06394256 (  38.37%)

3 ビットの入力では、結果は確かにひどいものですが、期待どおりに動作します。回答を参照してください https://stackoverflow.com/a/14614899/611560

入力ビット数を増やす

私を困惑させたのは、入力ビット数を増やすと結果が異なることでした。サンプル数などの反復回数を増やすことを忘れないでください。そうしないと、結果が間違っている可能性があります (「間違った統計」を参照)。

4ビットで試してみましょう：

$ ./modulo-test 20000 6 4
interations = 20000, range = 6, bits = 4 (0x0000000f)
  [0..15] => [0..5]

theorical occurences    3333.33 probability 0.16666667

   [   0] occurences    3728    probability 0.18640000 ( +11.84%)
   [   1] occurences    3763    probability 0.18815000 ( +12.89%)
   [   2] occurences    3675    probability 0.18375000 ( +10.25%)
   [   3] occurences    3721    probability 0.18605000 ( +11.63%)
   [   4] occurences    2573    probability 0.12865000 ( -22.81%)
   [   5] occurences    2540    probability 0.12700000 ( -23.80%)

  minimum occurences    2540.00 probability 0.12700000 ( -23.80%)
  maximum occurences    3763.00 probability 0.18815000 ( +12.89%)
     mean occurences    3333.33 probability 0.16666667 (  +0.00%)
   stddev occurences     602.48 probability 0.03012376 (  18.07%)

5ビットで試してみましょう：

$ ./modulo-test 40000 6 5
interations = 40000, range = 6, bits = 5 (0x0000001f)
  [0..31] => [0..5]

theorical occurences    6666.67 probability 0.16666667

   [   0] occurences    7462    probability 0.18655000 ( +11.93%)
   [   1] occurences    7444    probability 0.18610000 ( +11.66%)
   [   2] occurences    6318    probability 0.15795000 (  -5.23%)
   [   3] occurences    6265    probability 0.15662500 (  -6.03%)
   [   4] occurences    6334    probability 0.15835000 (  -4.99%)
   [   5] occurences    6177    probability 0.15442500 (  -7.34%)

  minimum occurences    6177.00 probability 0.15442500 (  -7.34%)
  maximum occurences    7462.00 probability 0.18655000 ( +11.93%)
     mean occurences    6666.67 probability 0.16666667 (  +0.00%)
   stddev occurences     611.58 probability 0.01528949 (   9.17%)

6ビットで試してみましょう：

$ ./modulo-test 80000 6 6
interations = 80000, range = 6, bits = 6 (0x0000003f)
  [0..63] => [0..5]

theorical occurences   13333.33 probability 0.16666667

   [   0] occurences   13741    probability 0.17176250 (  +3.06%)
   [   1] occurences   13610    probability 0.17012500 (  +2.08%)
   [   2] occurences   13890    probability 0.17362500 (  +4.18%)
   [   3] occurences   13702    probability 0.17127500 (  +2.77%)
   [   4] occurences   12492    probability 0.15615000 (  -6.31%)
   [   5] occurences   12565    probability 0.15706250 (  -5.76%)

  minimum occurences   12492.00 probability 0.15615000 (  -6.31%)
  maximum occurences   13890.00 probability 0.17362500 (  +4.18%)
     mean occurences   13333.33 probability 0.16666667 (  +0.00%)
   stddev occurences     630.35 probability 0.00787938 (   4.73%)

質問

入力ビットを変更すると（それに応じてサンプル数を増やすと）結果が異なる理由を教えてください。これらの背後にある数学的推論は何ですか?

間違った統計

以前のバージョンの質問では、32 ビットの入力と 1000000 回の反復のみ (例: 10^6 サンプル) のテストを示し、正しい結果が得られたことに驚いたと述べました。恥ずかしいことに、それは非常に間違っていました。ジェネレーターのすべての 2^32 値を取得するには、N 倍のサンプルが必要です。ここで、10^6 は 2^32 に比べてかなり小さいです。 これを数学/統計言語で説明できる人へのボーナス。.

ここで間違った結果：

$ ./modulo-test 1000000 6 32
interations = 1000000, range = 6, bits = 32 (0xffffffff)
  [0..4294967295] => [0..5]

theorical occurences  166666.67 probability 0.16666667

   [   0] occurences  166881    probability 0.16688100 (  +0.13%)
   [   1] occurences  166881    probability 0.16688100 (  +0.13%)
   [   2] occurences  166487    probability 0.16648700 (  -0.11%)
   [   3] occurences  166484    probability 0.16648400 (  -0.11%)
   [   4] occurences  166750    probability 0.16675000 (  +0.05%)
   [   5] occurences  166517    probability 0.16651700 (  -0.09%)

  minimum occurences  166484.00 probability 0.16648400 (  -0.11%)
  maximum occurences  166881.00 probability 0.16688100 (  +0.13%)
     mean occurences  166666.67 probability 0.16666667 (  +0.00%)
   stddev occurences     193.32 probability 0.00019332 (   0.12%)

Zed Shaw の優れた記事「Programmers Need To Learn Statistics Or I Will Kill They All」を何度も読み直さなければなりません。

4

2 に答える 2

9

本質的に、あなたは次のことをしています。

(rand() & 7) % 6

rand()に均一に分布し[0; RAND_MAX]、RAND_MAX+12の累乗であると仮定します。、、 ...、に評価rand() & 7できること、および結果が同等である可能性があることは明らかです。017

次に、モジュロの結果を取得するとどうなるかを見てみましょう6。

  • 0と6は0にマップされます。
  • 1と7は1にマップされます。
  • 2は2にマップされます。
  • 3は3にマップされます。
  • 4は4にマップされます。
  • 5は5にマップされます。

これは、他の数値の2倍の数の0と1を取得する理由を説明しています。

2番目のケースでも同じことが起こっています。ただし、「余分な」数値の値ははるかに小さいため、それらの寄与はノイズと区別できません。

要約すると、整数が[ 0;に均一に分布している場合 M-1]、そしてそれをモジュロでとると、がで割り切れNない限り、結果はゼロに向かってバイアスされます。MN

于 2013-01-30T22:16:54.327 に答える
2

rand()（または他のPRNG）は、間隔内の値を生成します[0 .. RAND_MAX]。[0 .. N-1]剰余演算子を使用して、これらを区間にマップします。

書く

(RAND_MAX+1) = q*N + r

と0 <= r < N。

次に、間隔内の各値に対して[0 .. N-1]、

  • q+1値rand()がより小さい場合、その値はその値にマップされますr
  • q値が。rand()の場合、その値はそれにマップされます>= r。

さて、qが小さい場合、との相対的な差は大きくなりますが、大きい場合q、たとえば、差は簡単に測定できません。q+1q2^32 / 6

于 2013-01-30T22:17:13.430 に答える