使用有偏的无偏随机数生成器 [英] Unbiased random number generator using a biased one

问题描述

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

You have a biased random number generator that produces a 1 with a probability p and 0 with a probability (1-p). You do not know the value of p. Using this make an unbiased random number generator which produces 1 with a probability 0.5 and 0 with a probability 0.5.

注意：此问题是练习题来自Cormen，Leiserson，Rivest，Stein的《算法介绍》。（clrs）

Note: this problem is an exercise problem from Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein.(clrs)

推荐答案

事件（p）（1 -p）和（1-p）（p）是等概率的。

The events (p)(1-p) and (1-p)(p) are equiprobable. Taking them as 0 and 1 respectively and discarding the other two pairs of results you get an unbiased random generator.

在代码中，将它们分别设为0和1并丢弃其他两对结果，将得到一个无偏的随机生成器。

In code this is done as easy as:

int UnbiasedRandom()
{
    int x, y;

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

    return x;
}

这篇关于使用有偏的无偏随机数生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！