C拼图:用有偏见的硬币做一个公平的硬币

Question

在下列情况下,如何确定函数返回0或1的概率:

让function_A返回0的概率为40%,1则概率为60%. 仅function_B使用仅生成具有50-50的概率function_A.

我想到了以下几点:

 function_B()
 {
     int result1=function_A();
     int result2=function_A();
     //two times 40% would result in 16% and 40%+60% would be 24%... two times 60%                        would be 36%
 }

什么组合可以给50-50？

Answer 1

这是一个经典的概率难题,据我所知,只用两次调用函数就不能做到这一点.但是,您可以使用较少的预期调用次数来执行此操作.

观察结果是,如果你有一个有偏差的硬币,它的概率为p,如果你将硬币翻转两次,那么:

• 它出现两次的概率是p ²
• 它首先出现的概率和第二个出现的尾部是p(1-p)
• 它首先出现的概率和第二个出现的概率是(1-p)p
• 它出现两次尾巴的概率是(1-p)²

现在,假设您反复翻转两个硬币,直到它们出现不同的值.如果发生这种情况,第一枚硬币出现的概率是多少？好吧,如果我们应用贝叶斯定律,我们就能做到

P(第一个硬币是两个硬币不同)= P(两个硬币不同,第一个硬币是头)P(第一个硬币是头)/ P(两个硬币不同)

第一枚硬币头部的概率是p,因为任何硬币投掷都以概率p出现.考虑到第一枚硬币是头部,两个硬币不同的概率是第二枚硬币出现尾部的概率,即(1-p).最后,两个硬币不同的概率是2p(1-p),因为如果你看一下上面的概率表,有两种方法可以发生,每种方法都有概率p(1-p).简化,我们得到了

P(第一枚硬币是两个硬币不同)= p(1-p)/(2p(1-p))= 1/2.

但是,如果硬币不同,那么第一枚硬币出现尾巴的可能性是多少？嗯,这与两个硬币不同时第一枚硬币没有出现的概率相同,即1 - 1/2 = 1/2.

换句话说,如果你持续翻转两个硬币直到它们出现不同的值,那么拿下你翻转的第一枚硬币的价值,你最终会用一枚有偏见的硬币制作一枚硬币!

在C中,这可能如下所示:

bool FairCoinFromBiasedCoin() {
    bool coin1, coin2;

    do {
        coin1 = function_A();
        coin2 = function_A();
    } while (coin1 == coin2);

    return coin1;
}

这可能看起来非常低效,但实际上并没有那么糟糕.它在每次迭代时终止的概率是2p(1-p).在期望中,这意味着在此循环终止之前我们需要1 /(2p(1-p))次迭代.对于p = 40%,这是1 /(2×0.4×0.6)= 1 /0.48~ = 2.083次迭代.每次迭代翻转两个硬币,因此我们需要大约4.16个硬币翻转以获得合理的翻转.

希望这可以帮助!

Answer 2

这是一种可行的方法,但需要反复试验.

1. function_A返回1 的机会:P(1)= p(例如p = 60%)
2. function_A返回0 的机会:P(0)= 1 - p
3. 在连续调用时返回值a,b,...的特定序列的机会function_A是P(a)P(b) ......

4. 观察某些组合将以相等的赔率出现,例如:

         P(a)*P(b) === P(b)*P(a)
    P(a)*P(b)*P(c) === P(b)*P(c)*P(a)
   
    etc.
   

5. 仅选择的(1,0)或(0,1)序列时,我们可以使用这一事实,我们后来才知道,机会任是

       P(1)*P(0)/(P(1)*P(0) + P(0)*P(1)) 
    => x / (x + x)
    => 1 / 2
   

然后,这将成为实现function_B的方法:

• function_A反复调用,直到我们收到(0,1)或(1,0)的序列
• 我们始终返回序列的第一个或最后一个元素(两者都具有0或1的相等几率)

function_B()
{
    do
    {
        int a = function_A();
        int b = function_A();
    } while( (a ^ b) == 0 ); // until a != b

    return a;
}