[解決済み】乱数生成器を使うとモジュロバイアスがかかると言われるのはなぜ？

疑問点

この質問はよく見かけますが、本当の意味での具体的な回答は見たことがありません。そこで、以下のような乱数生成器を使用したときに、なぜ "モジュロ・バイアス" が発生するのかを理解する助けになればと思い、ここに投稿しようと思います。 rand() をC++で作成しました。

どのように解決するのですか？

そこで rand() は擬似乱数生成器で、0から RAND_MAX で定義される定数です。 cstdlib (この 記事 に関する一般的な概要については rand() ).

では、例えば0と2の間の乱数を生成したい場合はどうなるでしょうか。説明の便宜上、次のようにしましょう。 RAND_MAX が 10 で、0 から 2 までの乱数を生成するために rand()%3 . しかし rand()%3 は、0と2の間の数字を同じ確率で生成するわけではありません!

いつ rand() は0、3、6、9を返します。 rand()%3 == 0 . したがって、P(0) = 4/11

いつ rand() は1、4、7、10を返す。 rand()%3 == 1 . したがって、P(1) = 4/11

いつ rand() は2,5,8を返す。 rand()%3 == 2 . したがって、P(2) = 3/11

これでは、0と2の間の数字が同じ確率で生成されません。もちろん、小さな範囲ではこれは大きな問題ではないかもしれませんが、大きな範囲では分布が歪み、小さな数字に偏りが生じる可能性があります。

では、どのような場合に rand()%n は、0からn-1までの数値の範囲を同じ確率で返すのでしょうか？それは RAND_MAX%n == n - 1 . この場合、先ほどの仮定と合わせて rand() は0から RAND_MAX のモジュロクラスも等しい確率で分布しているはずです。

では、この問題を解決するにはどうしたらよいのでしょうか。乱数を発生させ続け、目的の範囲に入る数を得るというのが粗い方法です。

int x; 
do {
    x = rand();
} while (x >= n);

の値が小さいと効率が悪くなります。 n を持っているだけなので n/RAND_MAX を実行する必要があります。 RAND_MAX/n を呼び出します。 rand() を平均すると

で割り切れる長さの大きな範囲を指定するのが、より効率的な計算式のアプローチとなります。 n というように RAND_MAX - RAND_MAX % n で、その範囲に入る乱数が出るまで乱数を発生させ続けて、そのモジュラスを取る。

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

の値が小さい場合 n を1回以上呼び出す必要はほとんどありません。 rand() .

引用文献と参考文献。

• CPlusPlusリファレンス

• エターナルコンフュージョン