17

您有一个有偏差的随机数生成器，它以概率 p 生成 1，以概率 (1-p) 生成 0。你不知道 p 的值。使用它可以生成一个无偏随机数生成器，它以 0.5 的概率生成 1，以 0.5 的概率生成 0。

注意：这个问题是 Cormen，Leiserson，Rivest，Stein 的算法介绍中的一个练习问题。（clrs）

4

7 回答 7

28

事件 (p)(1-p) 和 (1-p)(p) 是等概率的。将它们分别作为 0 和 1 并丢弃其他两对结果，您将得到一个无偏随机生成器。

在代码中，这很简单：

int UnbiasedRandom()
{
    int x, y;

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

    return x;
}
于 2009-12-31T19:51:42.850 回答
9

从有偏见的硬币中生产出无偏见的硬币的过程首先归功于冯诺依曼（一个在数学和许多相关领域做了大量工作的人）。程序超级简单：

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

这个算法之所以有效，是因为得到 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

于 2016-04-24T21:51:58.970 回答
4

冯·诺依曼（von Neumann）的技巧是一次获取两个位，01 对应于 0，10 对应于 1，并且重复 00 或 11 已经出现。1/p(1-p)使用这种方法获得单个位需要提取的位的期望值p为它丢弃了很多信息（所有 00 和 11 案例）。

谷歌搜索“von neumann trick biased”产生了这篇论文，为这个问题开发了一个更好的解决方案。这个想法是您仍然一次取两个位，但如果前两次尝试只产生 00 和 11，您将一对 0 视为单个 0，将一对 1 视为单个 1，并应用 von Neumann 的技巧到这些对。如果这也不起作用，请在此级别的配对中继续类似地组合，依此类推。

进一步，本文将其发展为从有偏源生成多个无偏位，本质上使用两种不同的方式从位对生成位，并给出一个草图，即这是最佳的，因为它可以准确地产生位数原始序列中包含熵。

于 2009-12-31T20:37:27.440 回答
2

您需要从RNG 中绘制成对的值，直到获得一系列不同的值，即0 后接1 或1 后接0。然后，您获取该序列的第一个值（或最后一个，无关紧要）。（即重复，只要绘制的对是两个零或两个一）

这背后的数学很简单：从 0 到 1 的序列与从 1 到 0 的序列具有相同的概率。通过始终将此序列的第一个（或最后一个）元素作为新 RNG 的输出，我们有机会获得 0 或 1。

于 2009-12-31T19:52:50.213 回答
1

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

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

由于任何给定衰减的时间是随机的，因此两次连续衰减之间的间隔也是随机的。然后，我们要做的是测量一对这些间隔，并根据两个间隔的相对长度发出一个零或一个位。如果我们测量两次衰减的相同间隔，我们放弃测量并重试

HotBits：它是如何工作的

于 2009-12-31T19:53:09.777 回答
1

除了其他答案中给出的冯诺依曼程序外，还有一整套技术，称为随机提取（也称为去偏、去偏斜或白化），用于从未知偏差的随机数中产生无偏随机位。它们包括 Peres (1992) 的迭代 von Neumann 程序，以及 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.，“迭代 von Neumann 提取随机位的过程”，统计年鉴 1992,20,1, p。590-597。
  • Zhou, H. 和 Bruck, J.，“用于优化随机比特生成的流算法”，arXiv:1209.0730 [cs.IT]，2012。
  • S. Pae，“二值化树和随机数生成”，arXiv:1602.06058v2 [cs.DS]。
  • Camion, Paul，“用有偏见的骰子滚动的无偏见的骰子”，北卡罗来纳州立大学。统计系，1974 年。
于 2020-11-18T18:48:03.157 回答
-1

我只是用一些运行证明来解释已经提出的解决方案。无论我们改变概率多少次，这个解决方案都是无偏的。在头尾抛掷中，连续head n tail或的排他性tail n head始终是无偏的。

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)
于 2020-08-15T16:52:11.497 回答