乱数ジェネレータを使用するとモジュロバイアスが発生すると言われるのはなぜですか? 質問する

はrand()、0から までの自然数を選択する擬似乱数生成器ですRAND_MAX。これは で定義される定数ですcstdlib（こちらを参照）。記事の概要については を参照してくださいrand()。

では、0 から 2 の間の乱数を生成したい場合はどうなるでしょうか。説明のために、 がRAND_MAX10 で、 を呼び出して 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 までの数値の範囲を等確率で返すのはいつでしょうか? がいつでしょうか。この場合、 は0 から n-1 までの数値を等確率で返すというRAND_MAX%n == n - 1以前の仮定に加えて、n の法クラスも均等に分布することになります。rand()RAND_MAX

では、この問題をどうやって解決するのでしょうか? 大雑把な方法としては、希望する範囲の数字が得られるまで乱数を生成し続けることです。

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

int x;

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

x %= n;