为什么von校正器只在输入比特相互独立且具有相同的偏差时才能工作？

Question

我读过一些提到冯·诺依曼矫正者的论文。他们总是认为，对于von校正器，输入比特是相互独立的，并且具有相同的偏差。

为什么von校正器只在输入比特相互独立且具有相同的偏差时才能工作？

Answer 1

为什么Von Neumann校正器只在输入比特相互独立且具有相同的偏差时才能工作？

基本的Von Neumann dibiaser的工作方式如下:生成两个位X，Y，然后用这个逻辑输出一点(或不输出一点)：

X=0 Y=0 -> No output
X=0 Y=1 -> Output a 0
X=1 Y=0 -> Output a 1
X=1 Y=1 -> No output

如果X和Y是不相关的，并且有相同的偏差(即它们的概率是p，1的概率是(1-p))，那么，立即得出输出a 0的上述过程的概率是p(1-p)，而a 1的概率是p(1-p)，这是相同的(并且存在不输出任何东西的概率p^2 + (1-p)^2 --我们将用更多的输入位再次运行它)。另外，由于我们假设输入位是独立的，所以在独立的输入位上多次运行减法器将产生独立的输出。

然而，你的问题是“如果比特不独立或不具有相同的偏见”)。

在这种情况下，上述逻辑不成立。

如果比特包含不同的偏差，即如果第一位与概率p为0，第二比特与概率q \ne p为0)，则a 0的概率为p(1-q) = p - pq，a 1的概率为q(1-p) = q - pq，如我们假定的p \ne q，它们明显不同，因此dibiaser的输出是有偏的。

如果比特具有相同的平均偏差，但它们是相关的，则可能发生的情况是，来自去偏置器的序列比特可能是相关的。例如，如果一个01序列在90%的时间内被另一个01序列跟随(与10序列类似)，那么来自debiaser的相邻输出本身将是强相关的，也就是说，dibiaser没有将原始输入字符串转换为‘随机’。

先前的答复(刚才给出了反例)：

假设偶数输入位是时间的0 90%，奇数输入位是时间的1 90%。

在这种情况下，Von Neumann校正器的输出比输入的偏差更大。

练习:设计一个类似的反例，其中位元不是相互独立的.

保罗抱怨我的例子“太极端了”(不管这意味着什么--我以为任何反例都适用)。无论如何，我会用另一个更极端的例子来回应。

考虑生成具有此概率分布的位对的原始源：

• 00，概率为1/3
• 01，概率为1/3
• 11，概率为1/3

(每对与其他对不相关)。

简单的计算表明，每对都有log_2(3) \approx 1.5850比特的香农熵(或每比特约有0.7925熵比特)。

然而，如果我们通过Von Neumann校正器运行它，我们会得到一个具有0位熵的流.