为什么这个简单的洗牌算法（通过 random() 排序）存在偏差？

Question

在这个线程中，我们看到了这个简单而漂亮的随机数组算法：

function shuffle<T>(array: T[]): T[] {
  return array.sort(() => Math.random() - 0.5);
}

我们可以看到评论说这个算法有偏见。但我制作了一个简单的脚本来创建数组最后一个元素在洗牌后结束的索引的经验概率分布：

function shuffle<T>(array: T[]): T[] {
  return array.sort(() => Math.random() - 0.5);
}

我们期望无偏算法具有均匀分布，并且结果非常接近该分布，即使对于具有 100 个元素的数组也是如此。那么为什么这个算法会有偏差呢？

Answer 1

JavaScript 没有为 指定特定的算法sort，并且根据所使用的特定排序算法，这种改组算法可能会给出非常有偏差的结果。下面，我描述了一些简单的、众所周知的排序算法，这些算法给出了非常有偏差的结果；我证明 Firefox 和 Chrome 对于长度为 4 的数组都给出了非常有偏差的结果；我给出了一个一般性的论据，说明为什么任何排序算法都会给出有偏差的结果（尽管不一定像这些明确的示例那样有偏差）。

\n\n

示例 #1 \xe2\x80\x94选择排序。在选择排序中，我们首先找到最小的元素并将其放在索引 0 处，然后找到第二小的元素并将其放在索引 1 处，依此类推。需要注意的重要一点是，使用比较函数() => Math.random() - 0.5，比较的每个参数都有相同的机会被视为“较少”。因此，如果您通过迭代数组并将每个元素与之前的最小元素进行比较来找到最小元素，那么您有 50% 的机会认为最后一个元素是最小的，有 25% 的机会认为最后一个元素是最小的。你会认为倒数第二个元素是最少的，你有 12.5% 的机会认为倒数第三个元素是最少的，等等，因此给出了哪个元素的有偏分布首先。

\n\n

示例 2 \xe2\x80\x94插入排序。在插入排序中，我们通过依次取出每个元素并将其插入到该排序部分中的正确位置（将所有较大的元素移动一位以为其腾出空间）来构建数组的“已排序”部分。这意味着最后一个元素有 50% 的机会被视为最少，25% 的机会被视为第二少，12.5% 的机会被视为第三少，等等。

\n\n

示例 #3 和 #4 \xe2\x80\x94 无论 Firefox 和 Chrome 使用四元素数组。

\n

现在，实际上，我不希望任何实现完全sort使用选择排序或插入排序，因为还有其他算法对于大输入更有效。但是复杂的现代排序算法（例如Timsort）结合了多种不同的排序算法，根据输入（或部分输入，因为它们可以以复杂的方式组合这些算法）的大小和特征在它们之间进行自适应选择。因此，作为一个实验，我在数组 \xe2\x80\x94 上尝试了这种洗牌算法，这是一个足够短的数组，看起来该实现可能只是对整个数组使用插入排序。[1, 2, 3, 4]sort

\n

这是我使用的代码：

\n

const counts = {};\nfor (let i = 0; i < 1_000_000; ++i) {\n  const permutation = [1, 2, 3, 4].sort(() => Math.random() - 0.5).join(\'\');\n  counts[permutation] = (counts[permutation]||0) + 1;\n}\n\nconst result = [];\nfor (let permutation in counts) {\n  result.push(permutation + \': \' + counts[permutation]);\n}\n\nresult.join(\'\\n\')\n

\n

我在 Firefox 和 Chrome 中都尝试过这个。

\n

在 Firefox 中，我得到了这样的结果：

\n

1234: 125747\n1243: 62365\n1324: 62299\n1342: 31003\n1423: 31320\n1432: 15635\n2134: 125380\n2143: 62216\n2314: 62615\n2341: 31255\n2413: 31509\n2431: 15608\n3124: 62377\n3142: 31166\n3214: 62194\n3241: 31293\n3412: 15631\n3421: 15782\n4123: 31056\n4132: 15672\n4213: 31231\n4231: 15319\n4312: 15727\n4321: 15600\n

\n

这与我对插入排序的期望不符，因此它必须做一些不同的事情，但无论如何，它显示出非常明显的偏差。有些排列发生的时间为 1/64（一百万次中有 15,625 次，加上/减去随机噪声），有些排列发生的时间为 1/32 (31,250)，有些排列的发生时间为 1/16 (62,500)，有些排列的发生时间为 1/16 (62,500)。发生次数为 1/8 (125,000)；因此，某些排列的出现频率是其他排列的八倍。

\n

在 Chrome 中，我得到了这样的结果：

\n

1234: 187029\n1243: 62380\n1324: 15409\n1342: 15679\n1423: 62476\n1432: 15368\n2134: 31280\n2143: 31291\n2314: 15683\n2341: 15482\n2413: 31482\n2431: 15732\n3124: 15786\n3142: 15692\n3214: 47186\n3241: 47092\n3412: 15509\n3421: 46600\n4123: 62825\n4132: 15595\n4213: 31091\n4231: 15763\n4312: 15624\n4321: 171946\n

\n

这也不符合我对插入排序的期望，并且比 Firefox 中的分布要复杂一些（我想我在那里看到了一些 3/16（187,500）和 3/64（46,875）？ ），但实际上偏差更大，最常见的排列和最不常见的排列之间存在十二倍的差异。

\n\n

示例 #5 \xe2\x80\x94任何确定性排序算法。上面我已经给出了相当极端的偏见的各种例子；但实际上，任何排序算法都会产生一些偏差，因为如果该算法对长度为n的数组进行最坏情况k次比较，并且每次比较都有 50\xe2\x80\x9350 分割，那么任何概率给定的排列必须是¹ / _{2 ^k}的倍数，而无偏洗牌器必须为每个排列提供概率¹ / _n！，如果n \xc2\xa0\xe2\x89\xa5\xc2\xa03 则不会是¹ / _{2 ^k}的倍数（因为这样n ! 将是 3 的倍数）。

\n

也就是说，我应该承认这些偏见可能足够小，以至于无关紧要；毕竟，even 并1.0 / 3.0不能精确计算1/3，而是将其四舍五入为二进制近似值。更直接的相关性是，典型的实现Math.random()保存 64 或 128 位内部状态，这意味着它甚至没有 21 位！或 35！不同的内部状态，这意味着用于对 21 或 35 或更多元素的数组进行混洗的算法不可能以非零概率产生每个排列。所以我认为一些偏见是不可避免的！Math.random()

\n\n

即使您使用的sort实现提供了您认为足够好的结果，也没有理由这样做，因为Fisher\xe2\x80\x93Yates 洗牌编码简单，并且比任何洗牌都快基于比较的排序算法。

\n\n

\n

但我制作了一个简单的脚本来创建数组最后一个元素在洗牌后结束的索引的经验概率分布： [\xe2\x80\xa6]

\n

\n

请注意，可能存在更微妙的偏差，即使最后一个元素出现在任何位置的可能性相同，但并非所有排列的可能性都相同。即使sort实现保持固定，您也需要在依赖此洗牌算法给出无偏差结果之前进行更彻底的分析（可能包括查看其源代码）。

\n