1

より小さな確率セットからより大きな確率セットを生成するにはどうすればよいですか?
これはアルゴリズム設計マニュアルからのものです -Steven Skiena
Q:

等しい確率で {0,1,2,3,4} から数を生成する乱数ジェネレータ (rng04) を使用して、0 から 7 までの数 (rng07) を等しい確率で生成する乱数ジェネレータを記述しますか?

rng04主に2つの出力を合計することに基づいて、約3時間試しました。問題は、その場合、各値の確率が異なることです。4 は 5/24 の確率で発生し、0 の発生は 1/24 です。マスクする方法をいくつか試しましたが、できません。

誰かがこれを解決できますか？

4

3 に答える 3

4

2 組の乱数 (最初の乱数と 2 番目の乱数{0,1,2,3,4})を組み合わせて、n*n明確な可能性を生み出す方法を見つける必要があります。基本的に問題は、追加するとこのようなものが得られることです

        X
      0 1 2 3 4

  0   0 1 2 3 4
Y 1   1 2 3 4 5
  2   2 3 4 5 6
  3   3 4 5 6 7
  4   4 5 6 7 8

重複がありますが、これはあなたが望むものではありません。2 つのセットを組み合わせる 1 つの可能な方法は、Z = X + Y*5whereXとYare の 2 つの乱数です。それはあなたにこのような結果のセットを与えるでしょう

        X
       0  1  2  3  4

  0    0  1  2  3  4
Y 1    5  6  7  8  9
  2   10 11 12 13 14
  3   15 16 17 18 19
  4   20 21 22 23 24

乱数のセットが大きくなったので、逆の手順を実行して小さくする必要があります。このセットには25個別の値があります (5 で開始し、2 つの乱数を使用したため、5*5=25)。必要なセットには、8 つの個別の値があります。これを行う単純な方法は次のようになります

x = rnd(5)  // {0,1,2,3,4}
y = rnd(5)  // {0,1,2,3,4}
z = x+y*5   // {0-24}
random07 = x mod 8

これは確かに の範囲になり{0,7}ます。しかし、値{1,7}は 3/25 回表示され、値0は 4/25 回表示されます。これは0 mod 8 = 0、、、および.8 mod 8 = 016 mod 8 = 024 mod 8 = 0

これを修正するには、上記のコードをこれに変更します。

do {
  x = rnd(5)  // {0,1,2,3,4}
  y = rnd(5)  // {0,1,2,3,4}
  z = x+y*5   // {0-24}
while (z != 24)

random07 = z mod 8

これは、確率を下げている 1 つの値 ( 24) を取り、それを破棄します。このような「悪い」値を取得した場合に新しい乱数を生成すると、アルゴリズムの実行時間がわずかに長くなります (この場合、1/25 の時間で実行に 2 倍の時間がかかり、1/625 の場合は 3 倍の時間がかかります)。ロングなど）。しかし、それはあなたに正しい確率を与えます。

于 2009-08-12T19:12:14.017 に答える
3

もちろん、実際の問題は、合計の真ん中にある数字 (この場合は 4) が多くの組み合わせ (0+4、1+3 など) で発生するのに対し、0 と 8 には 1 つの方法しかないという事実です。生産される。

この問題を解決する方法はわかりませんが、少し軽減してみます。考慮すべき点:

  • 0 から 7 の範囲には 8 つの可能な値があるため、最終的に目指すべき状況の総数は 8 の倍数でなければなりません。そうすることで、そのコドメイン内の値ごとに整数の分布を持つことができます。
  • 2 つの密度関数の合計を取ると、可能な状況の数 (入力の順列が異なるという点で、合計を評価するときに必ずしも異なるとは限りません) は、各入力セットのサイズの積に等しくなります。
  • したがって、2 つの {0,1,2,3,4} セットを合計すると、5*5=25 の可能性があります。
  • 5 の累乗から 8 の倍数 (最初のポイントを参照) を得ることができないため (2 番目のポイントを参照。ただし、1 を超える任意の数のセットに外挿してください)、そのため、考えられる状況の余剰が必要になります。それらが発生した場合、それらのいくつかを無視します。
  • これを行う最も簡単な方法は、この時点でわかる限り、2 つの {0,1,2,3,4} セット (25 の可能性) の合計を使用し、1 を無視することです (24 を残すため、倍数8の）。
  • したがって、課題は次のようになりました。残りの 24 の可能性を 8 つの出力値に分配する方法を見つけてください。このために、おそらく合計を使用するのではなく、入力値のみを使用する必要があります。

これを行う 1 つの方法は、入力から構成された基数 5 の数値を想像することです。44 (これは 25 番目の余分な値です。取得した場合は、新しい入力セットを合成します) を無視して、残りのモジュロ 8 を取得すると、24 の異なる入力の組み合わせ (それぞれ 3 つ) で 0-7 が得られます。均等配分です。

于 2009-08-12T19:09:41.120 に答える
2

私の論理は次のようになります。

rn07 = 0;
do {
  num = rng04;
}
while(num == 4);

rn07 = num * 2;
do {
  num = rng04;
}
while(num == 4);

rn07 += num % 2
于 2009-08-12T19:05:51.393 に答える