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

Question

您有一个带偏差的随机数生成器，它以概率p产生1和(1-p)的概率产生0。您不知道p的值。使用它制作一个无偏的随机数生成器，该生成器以概率0.5产生1和概率0.5产生0。 注意: 这个问题是《算法导论》（clrs）中的练习问题。

- Rohit Banga

---

我猜答案与使用有偏生成器有关，一次使用标准方式，一次作为反函数，这样你就有了一个概率为p的0，第二次迭代则有(1-p)的概率为0，并混合两个结果以平衡分布。虽然我不知道确切的数学原理。 - Eric J.

Eric- 是的，如果你使用(rand() + (1-rand()))/2，你可以合理地期望得到一个无偏结果。请注意，在上述代码中，你应该调用rand()函数两次，否则你将始终得到0.5。 - JohnE

@JohnE：基本上这就是我所想的，但这并不能给你一个直接的0或1，这是被要求的。我认为pau的回答正中要害。 - Eric J.

@Eric。嗯- 很好的观点。如果我们将1和0视为布尔值，你仍然可以做类似(rand() xor !rand())的事情吗？ - JohnE

这看起来像是我最近提出的问题的完全相反：https://dev59.com/S0vSa4cB1Zd3GeqPd1wa - finnw

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;
}

- pau.estalella

---

完美。历史上，这个设备归功于冯·诺伊曼，我们都对他很熟悉（也许并没有意识到）。 - jason

如果偏差本身随时间变化，这仍然有效吗？ - 2501

J. Von Neumann：与随机数字相关的各种技术。收录于：国家标准局应用数学系列12，第36-38页。（1951年） - yoyo

Answer 2

从一个有偏的硬币制造一个无偏的硬币的过程最初被归因于冯·诺伊曼（一个在数学和许多相关领域做出巨大贡献的人）。该过程非常简单：

• 抛两次硬币。
• 如果结果相同，则重新开始，忘记两个结果。
• 如果结果不同，则使用第一个结果，忘记第二个结果。

这个算法有效的原因是因为得到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

- Salvador Dali

---

如果偏差本身随着时间变化，这个方法仍然有效吗？ - 2501

@2501 不，它不是这样的。 - Salvador Dali

谢谢回复。很明显，概率不再相同。我想知道现实生活中的生成器是如何处理这个问题的。 - 2501

Answer 3

von Neumann的技巧是一次获取两个比特，其中01对应0，10对应1，并针对00或11重复。使用此方法提取单个位所需提取的比特数的期望值为1/p(1-p)，如果p特别小或大，则可以变得非常大，因此值得问一下该方法是否可以改进，特别是因为显然它会丢失很多信息（所有00和11情况）。

在Google上搜索“ von neumann trick biased”会产生this paper，该文件为该问题开发了更好的解决方案。其思想是仍然每次获取两个比特，但如果前两次尝试仅产生00和11，则将一对0视为单个0，将一对1视为单个1，并对这些对使用von Neumann的技巧。如果这也不起作用，请继续在此级别的对中类似地组合，以此类推。

进一步地，该论文将这个问题扩展为从有偏差的源中生成多个无偏差的比特，基本上使用两种不同的方式从比特对中生成比特，并提供了一个概述，表明这是最优的，因为它产生的比特数正好等于原始序列中的熵。

- JaakkoK

Answer 4

你需要从随机数生成器中抽取一对值，直到得到不同值的序列，即零后跟一或一后跟零。然后你可以选择该序列的第一个值或最后一个值作为输出结果。（也就是说，只要抽取到两个零或两个一，就重复上述过程）

这样做的数学原理很简单：0和1交替出现的序列与1和0交替出现的序列具有相同的概率。通过始终将这个序列的第一个（或最后一个）元素作为新随机数生成器的输出，我们有平等的机会获得零或一。

- mjv

Answer 5

除了其他答案中提供的冯·诺伊曼程序之外，还有一整个技术家族，称为随机抽取（也称为去偏、去斜或白化），用于从未知偏差的随机数生成无偏的随机比特。它们包括 Peres 的（1992 年）迭代冯·诺伊曼过程，以及 Zhou 和 Bruck（2012）的“抽取树”。这两种方法（以及其他几种方法）都是渐近最优的，也就是说，它们的效率（以输出比特数每输入比特数计算）随着输入数量的增加而接近最优限制（Pae 2018）。

例如，Peres 抽取器将零和一的位列表（具有相同偏差）作为输入，并描述如下：

将英语翻译为中文：

1. 创建两个名为U和V的空列表。然后，当输入中还剩下两个或更多位时：
   • 如果接下来的两位是0/0，则将0附加到U并将0附加到V。
   • 否则，如果那些位是0/1，则将1附加到U，然后写一个0。
   • 否则，如果那些位是1/0，则将1附加到U，然后写一个1。
   • 否则，如果那些位是1/1，则将0附加到U并将1附加到V。
2. 从放置在U中的位读取，递归运行此算法。
3. 从放置在V中的位读取，递归运行此算法。

这还没有提及从有偏差的随机数（不仅仅是有偏差的位）生成无偏差随机位的过程；例如，参见Camion（1974）。

我在关于随机性提取的注释中更详细地讨论了随机性提取器。

参考文献：

• Peres, Y.，“迭代冯·诺伊曼提取随机比特的过程”，《统计学年鉴》1992，20，1，590-597页。
• Zhou, H.和Bruck, J.，“流算法用于最优随机比特生成”，arXiv:1209.0730 [cs.IT]，2012年。
• S. Pae，“二值化树和随机数生成”，arXiv:1602.06058v2 [cs.DS]。
• Camion, Paul，“使用有偏骰子进行无偏掷骰子”，北卡罗来纳州立大学。统计系，1974年。

- Peter O.

Answer 6

这里有一种方法，可能不是最有效的。通过一堆随机数，直到你得到一个形如[0...，1，0...，1]（其中0...是一个或多个0）的序列。计算0的数量。如果第一个序列更长，则生成0，如果第二个序列更长，则生成1。（如果它们相同，请重试。）

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

由于任何给定衰变的时间都是随机的，因此两个连续衰变之间的时间间隔也是随机的。那么我们所做的就是测量一对这些间隔，并根据两个间隔的相对长度发出零或一位。如果我们为两个衰变测量相同的间隔，则丢弃该测量并重试。

HotBits：它是如何工作的

- user240438

Answer 7

我只是用一些运行的证明来解释已经提出的解决方案。这个解决方案将是公正的，无论我们改变概率的次数有多少次。在抛硬币的头和尾上，连续的"头和尾"或"尾和头"的排他性始终是公正的。

import random

def biased_toss(probability):
    if random.random() > probability:
        return 1
    else:
        return 0
    
def unbiased_toss(probability):
    x = biased_toss(probability)
    y = biased_toss(probability)
    while x == y:
        x = biased_toss(probability)
        y = biased_toss(probability)
    else:
        return x

# results with contain counts of heads '0' and tails '1'
results = {'0':0, '1':0}
for i in range(1000):
    # on every call we are changing the probability
    p = random.random()
    results[str(unbiased_toss(p))] += 1

# it still return unbiased result
print(results)
    

- nandal