algorithm - 使用有偏随机数生成器的无偏随机数生成器

Question

您有一个有偏随机数生成器，它以概率 p 生成 1，以概率 (1-p) 生成 0。您不知道 p 的值。使用它可以生成一个无偏随机数生成器，它以 0.5 的概率生成 1，以 0.5 的概率生成 0。

注意:这道题是来自Cormen, Leiserson, Rivest, Stein的Introduction to Algorithms的练习题。(clrs)

Answer 1

事件 (p)(1-p) 和 (1-p)(p) 是等概率的。将它们分别取为 0 和 1，并丢弃其他两对结果，得到一个无偏随机生成器。

在代码中，这很容易完成:

int UnbiasedRandom()
{
    int x, y;

    do
    {
        x = BiasedRandom();
        y = BiasedRandom();
    } while (x == y);

    return x;
}