重复有偏差的随机混乱会减少偏差吗？

Question

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

众所周知,只要基础随机数发生器(RNG)是无偏的,Fisher-Yates shuffle就是无偏的.

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元素阵列在每次应用混洗算法之前从相同的状态开始.例如,一个问题是如果RNG只有2 ^ 32~10 ^ 9的周期,我们就不能产生25个元素的每个可能的排列,因为这是25!~10 ^ 25个排列.

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

我的猜测是它通常会产生更好的结果,但似乎如果重复洗牌的阵列有许多与基础RNG相关的元素,那么排列实际上可能比预期更频繁地重复.

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

作为一个子问题,如果我只想重复排列数组中25个元素中的5个元素,那么我使用Fisher-Yates算法选择5个元素并在完成一个完整的shuffle之前停止？(我使用交换的数组末尾的5个元素.)然后我重新使用前面部分改组的25个元素数组来选择另一个5的排列.再次,看起来这比从如果基础RNG有偏差,则原始的25个元素数组.有什么想法吗？

我认为测试部分shuffle案例会更容易,因为25个元素中有5个元素只有6,375,600个可能的排列,所以有没有简单的测试来检查偏差？

Answer 1

有几点：

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