確率的アルゴリズム

Question

確率的ランダムソースがあります。これにより、確率$ 1/2 $のビット$ 0 $（または$ 1 $）が得られます。セットS = $ {0、1、...、n-1 } $に均一な分布を生成したい。

どのアルゴリズムが確率で$ 1/n $を与え、値$ i in s $を与えます。必要なビット数。

Answer 1

$ n $が2のパワーである場合、バイナリ表現のビットあたりビットを決定することにより、値$ i $を単純に決定できます。したがって、$ n = 8 $の場合、ソースを3回尋ねます。結果として$ 1,1,0 $を得るとしたら、このイベントを選択したイベントにマッピングされます。明らかに、$ log n $ビットが必要です。

$ n $が2つのパワーでない場合、上記の方法に従うと、$ n $が2つのパワーである場合、a aは間違いなく均一な分布を得ることができます。 $ k $ビットのサンプルをサンプリングすると、$ k $ -digitバイナリ番号$ b $が表示されます。$$ i leftarrow frac {b} {2^k} n。$$を選択できます。

サンプリングするビットが多いほど、均一な分布に近づきます。ケースのためのより複雑な方法があると確信していますwehere $ n neq 2^k $