1

有两个随机函数 f1(),f2()。

f1() 以概率 p1 返回 1，以概率 1-p1 返回 0。

f2() 以概率 p2 返回 1，以概率 1-p2 返回 0。

我想实现一个新函数 f3()，它以概率 p3（给定概率）返回 1，并以概率 1-p3 返回 0。在函数 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。我们应该重新生成所有这些随机 X 变量，直到它们的总和等于 p3 小数形式的分子。

一旦实现这一点，我们就返回 X1（或任何其他 Xn，其中 n 的选择与 X 变量的值无关）。由于 5 个 X 变量中有 2 个 1（因为它们的和等于分子），所以 X1 为 1 的概率正好是 p3。

对于非理性p3，仅使用f1无法解决问题。我现在不确定，但我认为，它可以求解 p1*q+p2*(1-q) 形式的 p3，其中 q 用类似的方法是有理的，生成适当数量的分布为 f1 的 Xs和 Ys，分布为 f2，直到它们具有特定的预定义总和，并返回其中之一。这个还是需要细说的。

于 2013-05-09T11:41:31.137 回答
2

首先要说，这是一个很好的问题来调整一个人的大脑。我设法解决了p3 = 0.4你刚刚要求的问题！而且我认为，对此类问题的概括并不是那么微不足道。:D

以下是如何解决它p3 = 0.4：

直觉来自你的例子。如果我们f1()在一次迭代中从五次生成一个数字（见下面的代码），我们可以得到32种类型的结果，如下所示：

 1: 00000
 2: 00001
 3: 00010
 4: 00011
    .....
    .....
32: 11111

其中，有10 个这样的结果正好是两个1！确定这一点后，问题就变得简单了。只需返回14 种组合中的任何一种，并返回06 种其他组合！（因为概率 0.4 意味着得到1, 10 次中有 4 次）。你可以这样做：

  int f3()
 {
     do{
          int a[5];
          int numberOfOneInA = 0;
          for(int i = 0; i < 5; i++){
               a[i] = f1();
               if(a[i] == 1){
                 numberOfOneInA++;  
               }
          }

          if (numberOfOneInA != 2) continue;           
          else return a[0]; //out of 10 times, 4 times a[0] is 1!

     }while(1)
}

等待看到一个通用的解决方案。干杯!

于 2013-05-09T11:57:28.627 回答
1

这是一个适用p3于形式a/2^n（分母是 2 的幂的有理数）的想法。

生成n概率分布为 的随机数0.5：

x1, x2, ..., xn

将其解释为范围内的二进制数0...2^n-1；此范围内的每个数字具有相等的概率。如果这个数小于a，则返回 1，否则返回 0。

现在，由于这个问题是在计算机科学的背景下，假设它p3是一种形式a/2^n（这是计算机中数字的常见表示）似乎是合理的。

于 2013-05-09T12:18:58.423 回答
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)。并且 anatolyg 是 2(1-p1^2-(1-p1)^2)^(-1)。

于 2013-05-12T17:21:38.437 回答
0

从算法上讲，是的，有可能完成这项任务。

即使以编程方式，也有可能，但问题很复杂。

让我们举个例子。

令 F1(1) = .5 这意味着 F1(0) =.5 F2(2) = .8 这意味着 F1(0) =.2

假设您需要一个 F3，这样 F3(1)= .128

让我们尝试分解它。

 .128
= (2^7)*(10^-3) // decompose this into know values 
= (8/10)*(8/10)*(2/10) 
= F2(1)&F2(1)*(20/100) // as no Fi(1)==2/10 
= F2(1)&F2(1)*(5/10)*(4/10)
= F2(1)&F2(1)&F1(1)*(40/100)
= F2(1)&F2(1)&F1(1)*(8/10)*(5/10)
= F2(1)&F2(1)&F1(1)&F2(1)&F1(1)

所以 F3(1)=.128 如果我们定义 F3()=F2()&F2()&F2()&F1()&F1()

同样，如果您想要 F4(1)=.9 ，

你给它 F4(0)=F1(0) | F2(0) =F1(0) F2(0)=.5 .2 =.1 即F4(1)=1-0.1=0.9

这意味着 F4 只有在两者都为零时才为零。

所以使用这个（ & ， | 和 ， not(!) ， xor(^) 如果你想要）操作与 f1,f2 的组合使用肯定会给你 F3 ，它完全由 f1,f2 制成，

找到给你准确概率的组合可能是 NP 难题。

所以，最后回答你的问题，是否可能？是的，这是一种方法，可能可以对它进行许多黑客攻击以优化它，从而为您提供任何最佳方式。

于 2013-05-09T12:20:24.687 回答