给定一个无限的随机 0 和 1 流，它来自一个有偏的（例如，1 比 0 更常见的已知因子），但在其他方面是理想的随机数生成器，我想将它转换成一个（更短的）无限流，就像理想但不偏不倚。
查找熵的定义会发现这张图显示了理论上我应该能够从每一位输入中获得多少位输出。
问题：是否有任何实用的方法来实际实现几乎理想高效的转换器？
问问题
95 次
3 回答
4
由于冯诺依曼，有一个众所周知的装置可以将不公平的硬币变成公平的硬币。我们可以在这里使用这个设备来解决我们的问题。
反复从偏置源中抽取两位，直到获得一对不同的位。现在返回第一位，丢弃第二位。这会产生一个无偏的来源。之所以可行，是因为无论来源如何，01 的概率与 10 的概率相同。因此，以 01 或 10 为条件的 0 的概率为 1/2，以 01 为条件的 1 的概率或 10 是 1/2。
于 2010-03-10T20:27:31.367 回答
2
请参见
于 2010-03-10T20:43:03.683 回答
0
霍夫曼对输入进行编码。
假设输入具有已知偏差，您可以计算每个 n 位段的校验和的概率分布。从中构造一个霍夫曼代码，然后对序列进行编码。
我不确定，但一个潜在的问题是这可能会在顺序位之间引入一些相关性。
于 2010-05-26T18:09:49.210 回答