17

ジョシュが与えられた上限を持つ正の乱数を生成する欠陥のあるランダムメソッドの例ではn、私は彼が述べている2つの欠陥を理解していません。

本の方法は次のとおりです。

private static final Random rnd = new Random();

//Common but deeply flawed
static int random(int n) {
    return Math.abs(rnd.nextInt()) % n;
}
  • 彼は、n が 2 の小さなべき乗である場合、生成される一連の乱数は短時間で繰り返されると述べています。これはなぜですか？のドキュメントにRandom.nextInt()はReturns the next pseudorandom, uniformly distributed int value from this random number generator's sequence.、 n が小さい整数の場合、シーケンスが繰り返されることはありませんが、なぜこれは 2 のべき乗にのみ適用されるのでしょうか?
  • 次に、n が 2 のべき乗でない場合、ある数値は他の数値よりも平均して頻繁に返されると彼は言います。Random.nextInt()均一に分散されたランダムな整数を生成する場合、なぜこれが発生するのですか? （彼はこれを明確に示すコードスニペットを提供していますが、なぜこれが当てはまるのか、これがnが2の累乗であることとどのように関連しているのかわかりません）。
4

2 に答える 2

38

質問 1: n が小さい 2 の累乗の場合、生成される一連の乱数は短時間で繰り返されます。

これは、ジョシュが言っていることの結果ではありません。むしろ、それは単に線形合同ジェネレーターの既知のプロパティです。ウィキペディアには次のように書かれています。

LCG のもう 1 つの問題は、m が 2 の累乗に設定されている場合、生成されたシーケンスの下位ビットの周期がシーケンス全体よりもはるかに短いことです。出力シーケンスの b 表現。ここで、ある整数 k に対して b k = m は、最大で b nの周期で繰り返されます。

これはJavadocにも記載されています。

このクラスで実装されているような線形合同擬似乱数ジェネレータは、下位ビットの値のシーケンスに短い周期があることが知られています。

関数の他のバージョンである は、Random.nextInt(int)この場合は異なるビットを使用することでこれを回避します (強調は私のものです)。

このアルゴリズムは、n が 2 のべき乗である場合を特別に扱います。つまり、基礎となる疑似乱数ジェネレーターから正しい数の上位ビットを返します。

これは、独自の範囲変換Random.nextInt(int)を使用して実行するよりも優先する正当な理由です。Random.nextInt()

質問 2: 次に彼は、n が 2 の累乗でない場合、ある数値が他の数値よりも平均して多く返されると述べています。

によって返すことができる2 32nextInt()の異なる数値があります。を使用してそれらを n 個のバケットに入れようとした場合% n、n が 2 の累乗でない場合、一部のバケットは他のバケットよりも多くの数を持ちます。これは、元の分布が均一であったとしても、一部の結果が他の結果よりも頻繁に発生することを意味します。

これを小さな数字で見てみましょう。nextInt()4 つの等確率の結果、0、1、2、および 3 が返され% 3たとします。それらに適用するとどうなるか見てみましょう。

0 maps to 0
1 maps to 1
2 maps to 2
3 maps to 0

ご覧のとおり、アルゴリズムは 1 と 2 をそれぞれ返す場合よりも 2 倍の頻度で 0 を返します。

これは、n が 2 の累乗の場合には発生しません。これは、2 の累乗が他方で割り切れるためです。考慮してくださいn=2：

0 maps to 0
1 maps to 1
2 maps to 0
3 maps to 1

ここで、0 と 1 は同じ頻度で発生します。

その他のリソース

以下に、LCG に関連する追加のリソースをいくつか示します。

于 2015-01-05T12:18:54.590 に答える
5

1)nが 2 の累乗の場合rnd % n、元の数ビットの下位ビットを選択するのと同じです。Java で使用されるタイプのジェネレーターによって生成される数値の下位ビットは、上位ビットよりも「ランダム性が低い」ことが知られています。これは、数値を生成するために使用される数式のプロパティにすぎません。

2) によって返される可能な最大値random()は 10 であり、n = 7. ここn % 7で、番号 7、8、9、および 10 をそれぞれ 0、1、2、3 にマップします。したがって、元の数が均一に分布している場合、4、5、6 の 2 倍の頻度で出現するため、結果は小さい方の数に大きく偏ります。この場合、これはnが 2 のべき乗であるかどうかに関係なく発生します。しかし、10 の代わりに、たとえば 15 (2^4-1) を選択した場合、n2 の累乗である任意の は、「過剰な」数がないため、均一な分布になります。可能な値の総数が可能な残りの数で正確に割り切れるため、範囲の最後に残してバイアスを引き起こします。

于 2015-01-05T12:19:35.553 に答える