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

一尘不染

algorithm

您有一个偏向随机数生成器，该生成器生成概率为p的1和概率为（1-p）的0。您不知道p的值。使用此方法可以生成一个无偏随机数生成器，该生成器以概率0.5生成1，以概率0.5生成0。

注意：此问题是Cormen，Leiserson，Rivest和Stein撰写的《算法导论》中的练习题。（clrs）

阅读 452

2020-07-28

共1个答案

一尘不染

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

在代码中，这很容易做到：

int UnbiasedRandom()
{
    int x, y;

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

    return x;
}

2020-07-28