C拼图: Make a fair coin from a biased coin

Question

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

Let the function_A return 0 with probability 40% and 1 with probability 60%. Generate a function_B with probabilities 50-50 using only function_A only.

我想到了以下几点:

 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 x 0.4 x 0.6) = 1/0.48 ~= 2.083 次迭代。每次迭代抛两个硬币，因此我们需要抛掷大约 4.16 次硬币才能获得公平的抛掷。

希望这对您有所帮助!