C谜题：用有偏差的硬币制造公平的硬币

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

Let the function_A返回 0 与 概率 40% 和 1 有概率 60%。生成一个function_B和 概率 50-50 仅使用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？

这是一个经典的概率难题，据我所知，您无法仅通过两次调用该函数来完成此任务。但是，您可以用低电压来做到这一点expected调用该函数的次数。

观察结果是，如果你有一枚有偏差的硬币，正面朝上的概率为 p，并且如果你抛硬币两次，那么：

• The probability that it comes up heads twice is p²
• 正面先出现、反面次之的概率为 p(1-p)
• 反面先出现、正面次之的概率为 (1-p)p
• The probability that it comes up tails twice is (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 次硬币翻转才能获得公平的翻转。

希望这可以帮助！