17

確率 p で 1 を生成し、確率 (1-p) で 0 を生成するバイアス付き乱数ジェネレーターがあります。p の値がわかりません。これを使用して、確率 0.5 で 1 と確率 0.5 で 0 を生成する偏りのない乱数ジェネレーターを作成します。

注: この問題は、Cormen、Leiserson、Rivest、Stein による Introduction to Algorithms の演習問題です。(clrs)

4

7 に答える 7

28

イベント (p)(1-p) と (1-p)(p) は等確率です。それらをそれぞれ 0 と 1 として取り、他の 2 つの結果のペアを破棄すると、偏りのないランダム ジェネレーターが得られます。

コードでは、これは次のように簡単に実行できます。

int UnbiasedRandom()
{
    int x, y;

    do
    {
        x = BiasedRandom();
        y = BiasedRandom();
    } while (x == y);

    return x;
}
于 2009-12-31T19:51:42.850 に答える
9

偏ったコインから偏りのないコインを生成する手順は、最初にフォン ノイマン(数学および多くの関連分野で多大な業績を上げた人物) によるものでした。手順は非常に簡単です。

  • コインを2回投げます。
  • 結果が一致する場合は、最初からやり直して、両方の結果を忘れます。
  • 結果が異なる場合は、最初の結果を使用し、2 番目の結果は無視します。

このアルゴリズムが機能する理由はp(1-p)、HT を取得する確率が であるためです。これは、TH を取得するのと同じ(1-p)pです。したがって、2 つのイベントの可能性は等しくなります。

私もこの本を読んでいて、予想される実行時間を尋ねています。2 回のトスが等しくない確率はz = 2*p*(1-p)であるため、予想実行時間は1/zです。

前の例は有望に見えます (結局のところ、バイアスが のバイアス付きコインがある場合p=0.99、コインを約 50 回投げる必要がありますが、これはそれほど多くはありません)。したがって、これが最適なアルゴリズムであると考えるかもしれません。残念ながらそうではありません。

シャノンの理論的限界との比較は次のとおりです（画像はこの回答から取得されます）。これは、アルゴリズムが優れていることを示していますが、最適とはほど遠いものです。

ここに画像の説明を入力

このアルゴリズムで HHTT が破棄されることを考えれば改善策が思いつきますが、実際には TTHH と同じ確率です。したがって、ここで停止して H を返すこともできます。HHHHTTTT などについても同様です。これらのケースを使用すると、予想される実行時間が改善されますが、理論的には最適化されません。

そして最後に-pythonコード：

import random

def biased(p):
    # create a biased coin
    return 1 if random.random() < p else 0

def unbiased_from_biased(p):
    n1, n2 = biased(p), biased(p)
    while n1 == n2:
        n1, n2 = biased(p), biased(p)

    return n1

p = random.random()
print p

tosses = [unbiased_from_biased(p) for i in xrange(1000)]
n_1 = sum(tosses)
n_2 = len(tosses) - n_1
print n_1, n_2

それはかなり自明であり、ここに結果の例があります：

0.0973181652114
505 495

ご覧のとおり、 のバイアスがあったにも関わらず、0.097ほぼ同じ数の1とが得られました。0

于 2016-04-24T21:51:58.970 に答える
4

一度に 2 ビットを取得し、01 を 0 に、10 を 1 に対応させ、00 または 11 を繰り返すという von Neumann に起因するトリックはすでに出てきています。この方法を使用して単一のビットを取得するために抽出する必要があるビットの期待値は であり1/p(1-p)、 が特に小さいか大きい場合pは非常に大きくなる可能性があるため、特に次のことが明らかであるため、方法を改善できるかどうかを尋ねる価値があります。多くの情報を破棄します (すべて 00 と 11 のケース)。

「フォン・ノイマン・トリック・バイアス」のグーグル検索により、問題のより良い解決策を開発するこの論文が作成されました。アイデアは、一度に 2 ビットを取得するというものですが、最初の 2 つの試行で 00 と 11 しか生成されない場合は、0 のペアを単一の 0 として、1 のペアを単一の 1 として扱い、フォン ノイマンのトリックを適用します。これらのペアに。それでもうまくいかない場合は、このレベルのペアで同様に組み合わせてください。

さらに、この論文はこれを、バイアスされたソースから複数のバイアスのないビットを生成するように発展させ、本質的にビットペアからビットを生成する2つの異なる方法を使用し、正確な数のビットを生成するという意味でこれが最適であるというスケッチを与えます元のシーケンスにエントロピーが含まれていること。

于 2009-12-31T20:37:27.440 に答える
2

一連の異なる値 (0 の後に 1、または 1 の後に 0) が得られるまで、RNG から値のペアを引き出す必要があります。次に、そのシーケンスの最初の値 (または最後の値は関係ありません) を取得します。(つまり、描画されたペアが 2 つのゼロまたは 2 つの 1 である限り、繰り返します)

この背後にある計算は単純です。0 から 1 のシーケンスは、1 から 0 のシーケンスとまったく同じ確率です。このシーケンスの最初 (または最後) の要素を新しい RNG の出力として常に取得することで、ゼロまたは 1 を取得する機会を均等に得ることができます。

于 2009-12-31T19:52:50.213 に答える
1

これが 1 つの方法ですが、おそらく最も効率的ではありません。[0..., 1, 0..., 1] (0... は 1 つ以上の 0) の形式のシーケンスが得られるまで、一連の乱数を調べます。0 の数を数えます。最初のシーケンスが長い場合は 0 を生成し、2 番目のシーケンスが長い場合は 1 を生成します (同じ場合は再試行します)。

これは、放射性粒子の崩壊から乱数を生成するために HotBits が行うことと似ています。

任意の減衰の時間はランダムであるため、2 つの連続する減衰間の間隔もランダムです。次に、これらの間隔のペアを測定し、2 つの間隔の相対的な長さに基づいて 0 または 1 ビットを出力します。2 つの減衰で同じ間隔を測定した場合、測定を破棄して再試行します。

HotBits: 仕組み

于 2009-12-31T19:53:09.777 に答える