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

Question

你有一个有偏倚的随机数发生器，产生1概率为p，0为概率（1-p）。你不知道p的价值。使用它可以产生一个无偏的随机数发生器，其产生1的概率为0.5，0的概率为0.5。

注意：这个问题是从介绍由Cormen，Leiserson，维斯特，斯坦算法的练习题（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

您需要从RNG画对值直到你得到不同值的序列，即，零后面紧跟着一个或一个零。然后，您获取该序列的第一个值（或最后一个，无关紧要）。

（只要引出的一对或者是两个零或两个1即重复）这背后的数学很简单：0然后1序列具有非常相同的概率为1，则零序。通过总是将这个序列的第一个（或最后一个）元素作为新的RNG的输出，我们有机会得到一个零或一个。

Answer 3

下面是一种方法，可能不是最有效的。咀嚼一堆随机数，直到得到[0 ...，1，0 ...，1]形式的序列（其中0 ...是一个或多个0）。计数0的数量。如果第一个序列较长，则生成一个0，如果第二个序列较长，则生成一个1.（如果它们相同，则再试一次。）

这就像HotBits从放射性生成随机数粒子衰变：

由于任何给定衰变的时间是随机的，因此两个连续衰变之间的间隔也是随机的。我们所做的是测量一对这样的间隔，并根据两个间隔的相对长度发出一个零位或一位。如果我们测量两个衰变相同的间隔，我们丢弃测量并再次尝试

HotBits: How It Works

Answer 4

归因于冯·诺伊曼同时获得两个比特的特技，具有01对应于0和10到1，重复00或11已经出现。使用此方法需要提取以获取单个位的位的预期值为1/p(1-p)，如果p特别小或大，则该位可能会变得非常大，因此值得问一问该方法是否可以改进，特别是因为它是它显然会抛出很多信息（全部是00和11）。

谷歌搜索“冯·诺伊曼特技偏置”产生this paper，开发针对该问题的更好的解决方案。这个想法是，你仍然需要一次两位，但如果前两次尝试只产生00秒和11秒，你把一对0作为单个0和一对1作为一个1，并且应用冯诺依曼的技巧对这些对。如果这也不起作用，那么在这个级别的对上继续类似的组合，等等。

此外，本文将此发展为从偏置源生成多个无偏位，本质上使用两种不同的方法从位对生成位，并给出一个草图，表明这是最优的，原始序列在其中熵的位数。

Answer 5

produce an unbiased coin from a biased one的程序首先归因于Von Neumann（一个在数学和许多相关领域做了大量工作的人）。程序非常简单：

• 投掷硬币两次。
• 如果结果一致，重新开始，忘记两个结果。
• 如果结果不同，请使用第一个结果，忘记第二个结果。

这个算法工作的原因是因为越来越HT的概率p(1-p)，这是与获取TH (1-p)p。因此两个事件同样可能。

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

---

前面的例子看起来令人鼓舞的（毕竟，如果你有一个偏见硬币的p=0.99偏见，你需要把你的硬币大约50倍，这是没有那么多）。所以你可能会认为这是一个最佳算法。可悲的是，事实并非如此。

这是它与Shannon's theoretical bound（图片取自answer）的比较。它表明算法很好，但远不是最优的。

你能想出的改善，如果你会考虑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