使用偏置的无偏随机数发生器

Question

你有一个有偏差的随机数发生器,它产生概率为1的1和概率为1的0(1-p).你不知道p的值.使用它可以产生一个无偏的随机数发生器,它产生1的概率为0.5和0,概率为0.5.

注意:这个问题是Cormen,Leiserson,Rivest,Stein的算法导论中的一个练习问题.(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;
}

Answer 2

从有偏的硬币中产生无偏硬币的过程首先归因于冯·诺伊曼（Von Neumann）（他在数学和许多相关领域做了大量工作）。程序非常简单：

• 抛硬币两次。
• 如果结果匹配，则从头开始，忘记两个结果。
• 如果结果不同，则使用第一个结果，而忽略第二个结果。

该算法之所以起作用，是因为获得HT的概率p(1-p)与获得TH 的概率相同(1-p)p。因此，两个事件的可能性相同。

我也在读这本书，它询问了预期的运行时间。两次掷不相等的概率为z = 2*p*(1-p)，因此预期的运行时间为1/z。

前面的示例看起来很令人鼓舞（毕竟，如果您有一个偏向硬币，其偏向为p=0.99，则您将需要掷硬币约50次，这不是很多）。因此，您可能会认为这是一种最佳算法。不幸的是，事实并非如此。

这是它与香农的理论界限进行比较的方式（图像取自此答案）。它表明该算法是好的，但远非最优。

如果您认为此算法将丢弃HHTT，则可以做出改进，但实际上它与TTHH的可能性相同。因此，您也可以在这里停止并返回H。HHHHTTTT等也是如此。使用这些情况可以改善预期的运行时间，但在理论上并没有使其达到最佳状态。

最后-python代码：

import random

def biased(p):
    # create a biased coin
    return 1 if random.random() < p else 0

def unbiased_from_biased(p):
    n1, n2 = biased(p), biased(p)
    while n1 == n2:
        n1, n2 = biased(p), biased(p)

    return n1

p = random.random()
print p

tosses = [unbiased_from_biased(p) for i in xrange(1000)]
n_1 = sum(tosses)
n_2 = len(tosses) - n_1
print n_1, n_2

这是不言自明的，下面是示例结果：

0.0973181652114
505 495

正如你看到的，但是我们有一个偏见0.097，我们得到了大约相同数量的1和0