1

2 つの乱数関数 f1()、f2() があります。

f1() は確率 p1 で 1 を返し、確率 1-p1 で 0 を返します。

f2() は確率 p2 で 1 を返し、確率 1-p2 で 0 を返します。

確率 p3(与えられた確率) で 1 を返し、確率 1-p3 で 0 を返す新しい関数 f3() を実装したいと思います。関数 f3() の実装では、関数 f1() と f2() を使用できますが、他のランダム関数は使用できません。

p3=0.5 の場合の実装例:

int f3()
{
    do
    {
        int a = f1();
        int b = f1();
        if (a==b) continue;
        // when reachs here 
        // a==1 with probability p1(1-p1)
        // b==1 with probability (1-p1)p1
        if (a==1) return 1;//now returns 1 with probability 0.5
        if (b==1) return 0;
    }while(1)
}

この f3() の実装は、確率 0.5 で 1 を返し、確率 0.5 で 0 を返すランダム関数を提供します。しかし、p3=0.4 で f3() を実装する方法は? 何も思いつきません。

その仕事は可能ですか？そして、f3() を実装する方法は?

前もって感謝します。

4

6 に答える 6

3 
p1 = 0.77  -- arbitrary value between 0 and 1

function f1()
   if math.random() < p1 then
      return 1
   else
      return 0
   end
end

-- f1() is enough.  We don't need f2()

p3 = 0.4 -- arbitrary value between 0 and 1

--------------------------

function f3()
   left = 0
   rigth = 1
   repeat
      middle = left + (right - left) * p1
      if f1() == 1 then 
         right = middle
      else
         left = middle
      end
      if right < p3 then     -- completely below 
         return 1
      elseif left >= p3 then -- completely above 
         return 0
      end
   until false  -- loop forever
end
于 2013-05-10T14:18:30.913 に答える
3

これは、p3 が有理数であれば解けます。

これには条件付き確率を使用する必要があります。

例えばこれをp3=0.4にしたい場合の方法は以下の通りです。

p3 の分数形式を計算します。私たちの場合、p3=0.4=2/5 です。

ここで、分母と同じ分布 (たとえば、f1 から、とにかく f2 は使用しません) から同じ数の確率変数を生成し、それらを X1、X2、X3、X4、X5 と呼びます。それらの合計が p3 の分数形式の分子と等しくなるまで、これらすべてのランダム X 変数を再生成する必要があります。

これが達成されると、X1 (または、n が X 変数の値とは無関係に選択された他の Xn) を返すだけです。5 つの X 変数の中に 2 つの 1 があるため (それらの合計が分子に等しいため)、X1 が 1 である確率は正確に p3 です。

無理数 p3 の場合、f1 だけでは問題を解決できません。今はよくわかりませんが、p1*q+p2*(1-q) の形式の p3 について解くことができると思います。ここで、q は同様の方法で有理数であり、分布 f1 で適切な量の X を生成します。分布 f2 の Ys を、特定の事前定義された合計になるまで計算し、そのうちの 1 つを返します。これはまだ詳しく説明する必要があります。

于 2013-05-09T11:41:31.137 に答える
1

anatolyg と Egor のアイデアを実装します。

inline double random(void)
{
    return static_cast<double>(rand()) / static_cast<double>(RAND_MAX);
}

const double p1 = 0.8;
int rand_P1(void)
{
    return random() < p1;
}

int rand_P2(void)//return 0 with 0.5
{
    int x, y; while (1)
    {
        mystep++;
        x = rand_P1(); y = rand_P1();
        if (x ^ y) return x;
    }
}

double p3 = random();
int rand_P3(void)//anatolyg's idea
{
    double tp = p3; int bit, x;
    while (1)
    {
        if (tp * 2 >= 1) {bit = 1; tp = tp * 2 - 1;}
        else {bit = 0; tp = tp * 2;}
        x = rand_P2();
        if (bit ^ x) return bit;
    }
}

int rand2_P3(void)//Egor's idea
{
    double left = 0, right = 1, mid;
    while (1)
    {
        dashenstep++;
        mid = left + (right - left) * p1;
        int x = rand_P1();
        if (x) right = mid; else left = mid;
        if (right < p3) return 1;
        if (left > p3) return 0;
    }
}

大規模な数学計算では、P3 が [0,1) に一様に分布していると仮定すると、Egor の期待値は (1-p1^2-(1-p1)^2)^(-1) になります。アナトリグは 2(1-p1^2-(1-p1)^2)^(-1) です。

于 2013-05-12T17:21:38.437 に答える