2

最近のインタビューで、私は次の質問をされました。random2()等しい確率（0.5）で0または1を返す関数があります。の実装random4()と をrandom3()使用して記述しrandom2()ます。random4()こんな感じで簡単に実装できました

if(random2())
  return random2();
return random2() + 2;

しかし、私は苦労しましrandom3()た。私が表現できる唯一の認識：

uint32_t sum = 0;
for (uint32_t i = 0; i != N; ++i)
  sum += random2();
return sum % 3;

のこの実装はrandom4()、私の直感のみに基づいています。数学的に正しいことを証明できないので、実際に正しいかどうかはわかりません。誰かこの質問を手伝ってくれませんか。

4

2 に答える 2

4

ランダム3:

これが最も効率的な方法かどうかはわかりませんが、私の見解は次のとおりです。

x = ランダム 2 + 2*ランダム 2

起こりうること:

0 + 0 = 0
0 + 2 = 2
1 + 0 = 1
1 + 2 = 3

上記は起こり得るすべての可能性であり、したがって、それぞれの確率は等しいので...

(p(x=c)は x = c である確率です)

p(x=0) = 0.25
p(x=1) = 0.25
p(x=2) = 0.25
p(x=3) = 0.25

x = 3 の間、別の数を生成し続け、0,1,2 に等しい確率を与えます。より技術的には、x=3 からの確率をそれらすべてに繰り返し分配し、p(x=3) が 0 になる傾向があるため、他の確率はそれぞれ 0.33 になる傾向があります。

コード：

do
  val = random2() + 2*random2();
while (val != 3);
return val;

ランダム4:

コードを実行してみましょう。

if(random2())
  return random2();
return random2() + 2;

最初の呼び出しは 50% の確率で 1 (true) => 50% * 50% の確率で 0 または 1 を返すため、それぞれ 25%

最初の呼び出しは 50% の確率で 0 (false) => 50% * 50% の確率で 2 または 3 を返すため、それぞれ 25%

したがって、コードは等しい確率で 0,1,2,3 を生成します。

e4e5f4 の回答に触発された更新:

上で提供したものよりも決定論的な答えについては...

何度も呼び出しrandom2て大きな数を生成し、結果を目的の数で変更します。

これはそれぞれの正確な確率ではありませんが、近いでしょう。

したがって、32 回の呼び出しによる 32 ビット整数の場合random2、target = 3:

Total numbers: 4294967296
Number of x's such that x%3 = 1 or 2: 1431655765
Number of x's such that x%3 = 0: 1431655766
Probability of 1 or 2 (each): 0.33333333325572311878204345703125
Probability of 0: 0.3333333334885537624359130859375

したがって、正しい確率の 0.00000002% 以内というのは、かなり近いようです。

コード：

sum = 0;
for (int i = 0; i < 32; i++)
  sum = 2*sum + random2();
return sum % N;

ノート：

pjr が指摘したように、これは一般に、上記の拒否方法よりもはるかに効率的ではありません。拒否メソッドを使用して同じ数の呼び出しrandom2(つまり 32) になる確率 (これが最も遅い操作であると仮定) は です0.25^(32/2) = 0.0000000002 = 0.00000002%。これは、この方法が正確ではないという事実と相まって、拒否方法をより優先します。この数値を下げると、実行時間は短縮されますが、エラーが増加します。おそらく、棄却メソッドの平均実行時間に近づくには、かなり下げる必要があります (したがって、エラーが大きくなります)。

上記のアルゴリズムには最大実行時間があることに注意してください。拒否メソッドはそうではありません。乱数ジェネレーターが何らかの理由で完全に壊れている場合、拒否された数値を生成し続け、拒否メソッドでかなりの時間または永久に実行される可能性がありますが、上記の for ループは何が起こっても 32 回実行されます。

于 2013-04-24T08:30:33.660 に答える
3

modulo( %) を使用するとバイアスが生じるため、使用はお勧めしません。のべき乗である場合にのみ、マッピングがうまくいきます。それ以外の場合は、他の回答で示唆されているように、ある種の拒否が関係しています。n2

別の一般的なアプローチは、組み込みの PRNG をエミュレートすることです。

  • 32 を生成random2()し、それを 32 ビット整数にマップします
  • 範囲内の乱数(0,1)を最大整数値で割って取得します
  • nこの数値に(=3,4...73 など) を掛けるだけでfloor、目的の出力が得られます。
于 2013-04-24T08:52:46.607 に答える