29

これはC＃よりも数学に関連している可能性がありますが、C＃ソリューションが必要なので、ここに配置します。

私の質問は、乱数ジェネレーターの確率についてです。より具体的には、可能な各値が等しい確率で返されるかどうかです。

最初の整数と最後の整数の間の数値を返すRandom.Next（int、int）メソッドがあることを知っています（最後は排他的です）。

Random.Next()[オーバーロードなし]は、0からInt32.MaxValue（2147483647）-1の間の値、つまり2147483646を返します。

1〜10の値が必要な場合は、これを呼び出すことができますが、Random.Next(1, 11)1〜10のすべての値が発生する確率は同じですか？

たとえば、範囲は10であるため、2147483646は10で完全に割り切れないため、値1〜6の確率はわずかに高くなります（理由2147483646 % 10 = 6）。もちろん、これは、Random.Next()[オーバーロードなし]内のすべての値が0から2147483646までの値を等しい確率で返すことを前提としています。

範囲内のすべての数値が同じ確率で発生することをどのように保証しますか？一部の人が他の人よりも高い能力を持っていることが不公平である宝くじタイプのシステムについて考えてみましょう。これにRNGに組み込まれたC＃を使用するのではなく、単なる例として使用しました。

4

4 に答える 4

17

私はあなたの投稿で実際に肉の質問に答えた人は誰もいないことに注意してください：

たとえば、範囲は10であるため、2147483646は10で完全に割り切れないため、値1〜6の確率はわずかに高くなります（2147483646％10 = 6であるため）。もちろん、これは、[オーバーロードなしの] Random.Next（）内のすべての値が、等しい確率で0から2147483646までの値を返すことを前提としています。

範囲内のすべての数値が同じ確率で発生することをどのように保証しますか？

そうです、不均衡の原因となる値を捨てるだけです。たとえば、に均一な分布を生成できるRNGが{ 0, 1, 2, 3, 4 }あり、それを使用してに均一な分布を生成したいとします{ 0, 1 }。素朴な実装は次のとおりです。から描画してから{0, 1, 2, 3, 4}値を返します% 2。ただし、これにより明らかに偏ったサンプルが生成されます。これは、ご存知のように、5（アイテムの数）が2で均等に割り切れないために発生します。したがって、代わりに、値を生成するドローをスローします4。したがって、アルゴリズムは次のようになります。

 draw from { 0, 1, 2, 3, 4 }
 if the value is 4, throw it out
 otherwise, return the value % 2

この基本的な考え方を使用して、一般的な問題を解決できます。

ただし、1から10までのすべての値は、発生する確率が同じですか？

はい、そうです。MSDNから：

疑似乱数は、有限の数のセットから等しい確率で選択されます。

編集：どうやら、ドキュメントは.NETの現在の実装と一致していません。ドキュメントには描画が均一であると記載されていますが、コードはそうではないことを示唆しています。しかし、それはこれが解決可能な問題であるという事実を否定するものではなく、私のアプローチはそれを解決する1つの方法です。

于 2012-04-16T17:47:28.673 に答える
11

RNGに組み込まれているC＃は、ご想像のとおり、均一に分散されたものです。に指定した範囲を指定すると、すべての数値が同じように発生する可能性がありますNext(min, max)。

たとえば、1Mのサンプルを取得し、各数値が実際に表示される回数を保存することで、これを自分でテストできます（私は持っています）。グラフ化すると、ほぼ平坦な曲線になります。

また、尤度が等しい各数値は、各数値が同じ回数発生することを意味するわけではないことにも注意してください。100回の反復で1から10までの乱数を調べている場合、各数値の10倍の発生が均等に分布することはありません。いくつかの数は8回発生する可能性があり、他の数は12または13回発生する可能性があります。ただし、反復回数が増えると、これはある程度均等になる傾向があります。

また、コメントで言及されているので、追加します。より強力なものが必要な場合は、暗号化PRNGを調べてください。Mersenne Twisterは、私が見たもの（高速、計算コストが安い、膨大な期間）から特に優れており、C＃でのオープンソースの実装があります。

于 2012-04-16T17:37:05.930 に答える
9

テストプログラム：

var a = new int[10];
var r = new Random();
for (int i = 0; i < 1000000; i++) a[r.Next(1, 11) - 1]++;
for (int i = 0; i < a.Length; i++) Console.WriteLine("{0,2}{1,10}", i + 1, a[i]);

出力：

1 99924
 2 100199
 3 100568
 4 100406
 5 100114
 6 99418
 7 99759
 8 99573
 9 100121
10 99918

結論：

各値は同じ確率で返されます。

于 2012-04-16T17:37:22.623 に答える
3

灰とdtbが正しくない：いくつかの数字が他の数字よりも発生する可能性が高いと疑うのは正しいことです。

を呼び出すと.Next(x, y)、y--xの可能な戻り値があります。.NET 4.0Randomクラスは、の戻り値に基づいて戻り値を計算しますNextDouble()（これは少し簡略化された説明です）。

明らかに、可能なdouble値のセットは有限であり、ご存知のように、の可能な戻り値のセットのサイズの倍数ではない場合があります.Next(x, y)。したがって、入力値のセットが均一に分布していると仮定すると、一部の出力値はわずかに発生する可能性が高くなります。

数値のdouble値がいくつあるか（つまり、無限大とNaN値を除く）はわかりませんが、確かに2^32より大きくなります。あなたの場合、議論のために2 ^ 32の値を想定すると、4294967296の入力を10の出力にマッピングする必要があります。一部の値では、発生する確率が429496730/429496729高くなるか、0.00000023283064397913028110629パーセント高くなります。実際、入力状態の数は2 ^ 32より大きいため、確率の差はさらに小さくなります。

于 2012-04-16T17:56:33.613 に答える