9

我想以最小的偏差反复产生快速的随机洗牌。

众所周知，只要底层随机数生成器 (RNG) 是无偏的， Fisher-Yates 洗牌就是无偏的。

To shuffle an array a of n elements:
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

但是，如果 RNG 有偏差（但速度很快）怎么办？

假设我想生成一个包含 25 个元素的数组的许多随机排列。如果我使用带有偏差 RNG 的 Fisher-Yates 算法，那么我的排列将会有偏差，但我相信这假设 25 元素数组在每次应用 shuffle 算法之前从相同状态开始。例如，一个问题是，如果 RNG 只有 2^32 ~ 10^9 的周期，我们不能产生 25 个元素的所有可能排列，因为这是 25！~ 10^25 排列。

我的一般问题是，如果我在开始 Fisher-Yates 洗牌的每个新应用之前让洗牌的元素洗牌，这会减少偏差和/或允许算法产生每个排列吗？

我的猜测是它通常会产生更好的结果，但似乎如果被反复洗牌的数组有许多与底层 RNG 相关的元素，那么排列实际上可能比预期的更频繁地重复。

有谁知道解决这个问题的任何研究？

作为一个子问题，如果我只想重复排列数组中 25 个元素中的 5 个，那么我使用 Fisher-Yates 算法选择 5 个元素并在进行完全洗牌之前停止怎么办？（我使用被交换的数组末尾的 5 个元素。）然后我重新开始使用之前部分洗牌的 25 元素数组来选择另一个 5 的排列。同样，这似乎比从如果底层 RNG 有偏差，则为原始 25 元素数组。对此有什么想法吗？

我认为测试部分洗牌情况会更容易，因为 25 个元素中的 5 个只有 6,375,600 种可能的排列，那么是否有任何简单的测试可用于检查偏差？

4

5 回答 5

3

如果 RNG 只有 2^32 ~ 10^9 的周期，我们不能产生 25 个元素的所有可能排列，因为这是 25！~ 10^25 排列

这只有在种子决定了每一个连续的选择时才是正确的。只要可以期望您的 RNG 在为每个下一个选择指定的范围内提供精确均匀的分布，那么它就可以产生每个排列。如果您的 RNG 无法做到这一点，那么拥有更大的种子基地将无济于事。

至于你的附带问题，你不妨为每次平局重新播种。但是，只有在重新播种包含足够熵的情况下，重新播种生成器才有用。时间戳不包含太多熵，算法计算也不包含。

我不确定这个解决方案是什么的一部分，因为您没有列出它，但是如果您尝试使用随机输入从更大的域计算某些东西，可能有更好的方法。

于 2010-09-29T23:23:40.487 回答
2

我的感觉是，对于有偏见的 RNG，Knuth shuffle 的重复运行会产生所有的排列，但我无法证明这一点（这取决于 RNG 的周期以及它有多大的偏见）。

所以让我们把问题反过来：给定一个需要随机输入和有偏差的 RNG 的算法，去偏斜算法的输出还是去偏斜 RNG 的输出更容易？

毫不奇怪，后者更容易做到（并且具有更广泛的兴趣）：有几种标准技术可以做到这一点。Von Neumann 提出的一个简单技术是：给定来自有偏差的 RNG 的比特流，成对获取比特，丢弃每对 (0,0) 和 (1,1)，每 (1,0) 返回一个 1对，每个 (0,1) 对都有一个 0。该技术假定位来自流，其中每个位与流中的任何其他位具有相同的 0 或 1 概率，并且位不相关。Elias 将 von Neumann 的技术推广到一种更有效的方案（丢弃的比特更少）。

但即使是强烈偏差或相关的位，也可能包含有用的随机性，例如使用基于快速傅立叶变换的技术。

另一种选择是将有偏差的 RNG 输出提供给加密强大的函数，例如消息摘要算法，并使用它的输出。

有关如何消除随机数生成器偏差的更多参考资料，我建议您阅读Randomness Recommendations for Security RFC。

我的观点是，如果基于随机的算法的输出是由 RNG 提供的熵上限的质量：如果它极度有偏差，那么无论你做什么，输出都会有极大的偏差。该算法不能压缩比包含在有偏随机比特流中的熵更多的熵。更糟糕的是：它可能会丢失一些随机位。即使假设该算法适用于有偏差的 RNG，为了获得良好的结果，您必须付出至少与消除 RNG 偏差所需的努力一样大的计算工作（但可能需要更多的努力，因为您必须同时运行算法并“击败”偏差）。

如果你的问题只是理论上的，那么请忽略这个答案。如果可行，那么请认真考虑去偏斜你的 RNG，而不是对算法的输出做出假设。

于 2010-09-30T00:30:20.697 回答
2

几点：

1) 任何使用 Fisher Yates shuffle 的人都应该阅读本文并确保他们的实施是正确的。
2）重复洗牌不会破坏使用更快的随机数生成器的目的吗？当然，如果您必须每次洗牌重复 5 次以获得所需的熵，那么您最好使用低偏差生成器。
3）你有一个可以测试这个的设置吗？如果是这样，请开始尝试 - Jeffs 图表清楚地表明，您可以通过使用小卡片组并直观地描绘结果来轻松检测到相当多的错误。

于 2010-09-29T22:44:52.017 回答
1

这完全取决于偏见。一般来说，我会说“不要指望它”。

收敛到无偏的有偏算法：

一半时间什么都不做，另一半时间正确洗牌。以指数方式向无偏收敛。在 n 次洗牌之后，洗牌有 1-1/2^n 的机会是无偏的，并且有 1/2^n 的机会选择了输入序列。

保持有偏的有偏算法：

随机播放除最后一个元素之外的所有元素。永久偏向于不移动最后一个元素。

更一般的例子：

将洗牌算法视为置换的加权有向图，其中一个节点的权重对应于洗牌时从一个排列转换到另一个排列的概率。有偏差的 shuffle 算法将具有不均匀的权重。

现在假设您用水填充了该图中的一个节点，并且水根据权重从一个节点流到下一个节点。如果无论起始节点如何，水的分布都收敛到均匀，则该算法将收敛到无偏。

那么在什么情况下水不会均匀分布呢？好吧，如果您有一个高于平均重量的循环，则循环中的节点往往会互相喂食并保持在平均水量之上。他们不会把所有的水都拿走，因为随着他们得到更多的水，进来的水量减少，流出的水量增加，但它会高于平均水平。

于 2010-09-30T04:39:32.600 回答
1

我不能完全回答你的问题，但这个观察似乎太长了，无法发表评论。

如果您确保每次Fisher-Yates 迭代从RNG 中提取的随机数数量与RNG 周期具有较高的最小公倍数，会发生什么情况？这可能意味着您在算法结束时“浪费”了一个随机整数。改组 25 个元素时，需要 24 个随机数。如果最后再拉一个随机数，生成 25 个随机数，则不能保证重复的时间比 RNG 周期长得多。现在，当然，您可以随机地在到达期间之前连续出现相同的 25 个数字。但是，由于 25 除了 1 和 2^32 之外没有公因数，因此在 25*(2^32) 之前，您不会达到保证重复。现在，这并不是一个巨大的改进，但你说这个 RNG 很快。如果“废物” 价值大得多？获得每个排列可能仍然不切实际，但您至少可以增加可以达到的数量。

于 2010-09-29T22:47:54.480 回答