12

数値 0 (30% の確率) または 1 (70% の確率) を生成する rand1() という名前の関数がある場合、数値 0 または 1 の同等確率を生成する関数 rand2() をどのように記述して rand1() を使用しますか?

更新：</p>

最後に、これは書籍 Introduction to Algorithms (2nd) (この書籍の中国語版を購入しました) Excercise 5.1-3 の問題であることがわかりました。元の問題は次のとおりです。

5.1-3 1/2 の確率で 0 を、1/2 の確率で 1 を出力したいとします。自由に使えるのは、0 または 1 のいずれかを出力するプロシージャ BIASED-RANDOM です。ある確率 p で 1 を出力し、確率 1−p で 0 を出力します。ここで、0 < p < 1 ですが、p が何であるかはわかりません。サブルーチンとして BIASED-RANDOM を使用するアルゴリズムを与え、偏りのない答えを返し、確率 1/2 で 0 を返し、確率 1/2 で 1 を返します。p の関数としてのアルゴリズムの予想実行時間は?

解決策は次のとおりです。

偏りのないランダム ビットを取得するには、BIASED-RANDOM の呼び出しのみを指定して、BIASED-RANDOM を 2 回呼び出します。2 つの呼び出しが異なる値を返すまでこれを繰り返します。異なる値が返された場合は、2 つのビットの最初のビットを返します。

UNBIASED-RANDOM
while TRUE
do
x ← BIASED-RANDOM
y ← BIASED-RANDOM
if x != y
then return x

UNBIASED-RANDOM が 0 と 1 をそれぞれ確率 1/2 で返すことを確認するには、特定の反復で 0 が返される確率が次のようになることを確認します。

Pr {x = 0 and y = 1} = (1 − p)p ,

与えられた反復が 1 を返す確率は

Pr {x = 1 and y = 0} = p(1 − p) .

(BIASED-RANDOM によって返されるビットが独立していることに依存しています。) したがって、特定の反復で 0 が返される確率は、1 が返される確率と等しくなります。UNBIASED-RANDOM が値を返す方法は他にないため、返されます。確率 1/2 でそれぞれ 0 と 1。

4

4 に答える 4

13

2 つの数値を生成aし、b.

aが 0 で1 の場合b(21% の確率)、0 を生成します。が 1 で0 の
場合(21% の確率)、1 を生成します。 ab

他のすべてのケース (58% の確率) では、新しいaandbを生成して、もう一度試してください。

于 2012-08-25T13:02:11.027 に答える
4

2回呼び出すとrand1、とを取得する可能性が等しくなります。したがって、一致しない各ペアの最初のペアを返す（および一致するペアを破棄する）と、平均して、入力ビットあたりの出力ビットが取得されます（ここで、の確率は戻り値;あなたの例では0.7）、とは関係なく、各出力ビットは確率0.5で1になります。[1 0][0 1]0.5(1 - p2 - (1-p)2)prand11p

しかし、私たちはもっとうまくやることができます。

一致するペアを破棄するのではなく、反対の一致するペアが続くことを期待してそれらを覚えることができます-シーケンス[0 0 1 1]も[1 1 0 0]同様に可能性があり、そのようなシーケンスが表示されるたびに最初のビットを返すことができます（まだ出力があります）確率0.5。）[0 0 0 0 1 1 1 1]などのシーケンスを探して、それらを無期限に組み合わせ続けることができます。

さらに先に進むことができます-入力シーケンス[0 0 0 1]を検討し、現状と[0 1 0 0]同じ出力（[0]）を生成しますが、これら2つのシーケンスも同様に可能性が高いため、これから余分な出力を抽出し[0 0]て、最初のケース[0 1] と二番目。ただし、出力ビットのバッファリングを開始する必要があるため、ここでさらに複雑になります。

どちらの手法も再帰的に適用でき、限界までロスレスになります（つまりrand1、確率が0.5の場合、入力ビットごとに平均1つの出力ビットが得られます）。

完全な説明（数学を含む）はこちら：http ：//www.eecs.harvard.edu/~michaelm/coinflipext.pdf

于 2012-08-25T14:42:43.820 に答える
0

以下rand2の関数は、0または1の発生の50％の確率を提供します。

#define LIMIT_TO_CALCULATE_PROBABILITY 10 //set any even numbers

int rand2()
{
    static int one_occurred = 0;
    static int zero_occured = 0;
    int rand_value = 0;
    int limit = (LIMIT_TO_CALCULATE_PROBABILITY / 2);

    if (LIMIT_TO_CALCULATE_PROBABILITY == (one_occured + zero_occured))
    {
        one_occured = 0;
        zero_occured = 0;
    }

    rand_value = rand1();   

    if ((1 == rand_value) && (one_occured < limit))
    {
        one_occured++;
        return rand_value;
    }
    else if ((0 == rand_value) && (zero_occured < limit))
    {
        zero_occured++;
        return rand_value;
    }
    else if (1 == rand_value)
    {
        zero_occured++;
        return 0;
    }
    else if (0 == rand_value)
    {
        one_occured++;
        return 1;
    }   
}
于 2012-08-25T14:10:22.643 に答える
0

50％0 50％1にどれだけ近づきたいかを理解する必要があります。

rand1への繰り返し呼び出しの結果を追加する場合。結果が0または2の場合、返される値は0です。1の場合、1を返します。（コードでは、モジュロ2を使用できます）

int val = rand1();   // prob 30%      0, and 70%      1

val=(val+rand1())%2; // prob 58%      0, and 42%      1  (#1 see math bellow)
val=(val+rand1())%2; // prob 46.8%    0, and 53.2%    1  (#2 see math bellow)
val=(val+rand1())%2; // prob 51.28%   0, and 48.72%   1
val=(val+rand1())%2; // prob 49.488%  0, and 50.512%  1
val=(val+rand1())%2; // prob 50.2048% 0, and 49.7952% 1

あなたはその考えを理解します。したがって、確率がどれだけ近いかを判断するのはあなた次第です。その後のすべての呼び出しで50％50％に近づきますが、完全に等しくなることはありません。

確率の計算が必要な場合：

1

prob ((val+rand1()%2) = 0) = (prob(val = 0)*prob(rand1() = 0)) + (prob(val = 1)*prob(rand1() = 1)
                           = (0.3*0.3)+(0.7*0.7)
                           = 0.09 + 0.49
                           = 0.58
                           = 58%

prob ((val+rand1()%2) = 1) = (prob(val = 1)*prob(rand1() = 0)) + (prob(val = 0)*prob(rand1() = 1)
                           = (0.7*0.3)+(0.3*0.7)
                           = 0.21 + 0.21
                           = 0.42 
                           = 42%

2

 prob ((val+rand1()%2) = 0) = (prob(val = 0)*prob(rand1() = 0)) + (prob(val = 1)*prob(rand1() = 1)
                            = (0.58*0.3)+(0.42*0.7)
                            = 0.174 + 0.294
                            = 0.468
                            = 46.8%

 prob ((val+rand1()%2) = 1) = (prob(val = 1)*prob(rand1() = 0)) + (prob(val = 0)*prob(rand1() = 1)
                            = (0.42*0.3)+(0.58*0.7)
                            = 0.126 + 0.406
                            = 0.532
                            = 53.2%
于 2012-08-25T14:24:07.200 に答える