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

Question

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

Note：这个问题是Cormen，Leiserson，Rivest，Stein等人从算法介绍到的练习问题。

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 )一次得到两个位，01对应于0和10比1，并且重复了00或11，这一技巧已经出现了。使用该方法提取单个比特所需提取的位的期望值是1/p(1-p)，如果p特别小或很大，它可能会变得相当大，因此值得问一问，该方法是否可以改进，特别是因为很明显，它丢弃了大量信息(所有00和11种情况)。

谷歌搜索"von欺骗有偏见“产生了本论文，为这个问题开发了一个更好的解决方案。我们的想法是，一次仍然取两个位，但是如果前两次尝试只产生00s和11s，那么就把一对0看作一个0，一对1s作为一个1，并将von的技巧应用于这些配对。如果这也不起作用，继续在这个级别的配对中进行类似的组合，以此类推。

进一步地，本文把它发展成从偏置源产生多个无偏位，实质上使用了两种不同的方式从位对生成比特，并给出了一个草图，说明这是最优的，因为它产生的比特数正是原始序列中的熵。

Answer 3

您需要从RNG中绘制成对的值，直到得到一系列不同的值，即零，后面跟着一个或一个，然后是零。然后，获取该序列的第一个值(或最后一个值，不重要)。(即，只要所绘制的对为两个零或两个1，就重复)

这背后的数学很简单:0然后1序列的概率和1然后0序列的概率是一样的。通过始终将这个序列的第一个(或最后一个)元素作为新RNG的输出，我们就可以得到一个零或一个1的偶数。