確率を設定して別の確率を生成する

Question

小さな確率集合から大きな確率集合を生成するにはどうすればよいですか？
このアルゴリズム設計マニュアル-Steven Skiena
Qからのものである：

書き込みに等しい確率で、{0,1,2,3,4}から番号を生成する乱数発生器（rng04）を使用し0から7までの数字を生成する乱数ジェネレータ（rng07）？

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

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

Answer 1

2組の乱数（1番目と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つの方法は、です。ここで、XとYは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 = 0,16 mod 8 = 0、24 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 

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

Answer 2

私のロジックはこのようになります：

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

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

rn07 += num % 2 

Answer 3

本当の問題は、もちろん、和の真ん中に数字（この場合は4）は、多くの組み合わせで発生しているという事実である（0 + 4 、1 + 3など）、0と8は正確に1つの方法で作成されます。

この問題の解決方法はわかりませんが、私はそれを少し減らそうとしています。考慮すべきいくつかのポイント：

• 0-7の範囲は、8つの可能な値を持っているので、最終的にはあなたが目指すべき可能な状況の合計数は、整数を持つことができる方法8の倍数である必要がありますそのcodomainの値ごとの分布の。
• 2つの密度関数の合計をとると、可能な状況の数（入力の異なる順列の点で合計を評価したときに必ずしも明確ではない）は、各入力のサイズの積セット。
• したがって、2つの{0,1,2,3,4}セットを合計すると、5 * 5 = 25の可能性があります。あなたは可能なの黒字を持っている必要がありますので、
• 5のべき乗（第2のポイントを参照してくださいが、セットの任意の数にそれを外挿する> 1）から（最初のポイントを参照してください）8の倍数を取得することはできませんあなたの機能に状況があり、発生した場合はそれらの一部を無視します。
• これを行うための最も簡単な方法は、この時点で分かるように、2つの{0,1,2,3,4}セットの合計（25通りの可能性）を使用し、1を無視することです（24 、8の倍数）。
• これで、以下の課題が軽減されました。残りの24の可能性を8つの出力値に分配する方法を見つける。このため、おそらく合計を使用するのではなく、入力値だけを使用することになります。

これを行う1つの方法は、入力から作成されたベース5の数字を想像してください。 44を無視する（それはあなたの25番目の余計な値です;もしそれが得られれば、新しい入力セットを合成します）、8を法とする他のものを取ると、24通りの入力の組み合わせ（それぞれ3つ）均等な分布である。