algorithm - 你从这个破碎的随机洗牌中得到什么分布？

Question

著名的 Fisher-Yates shuffle 算法可用于随机排列长度为 N 的数组 A：

For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]

我一再被告知不要犯的一个常见错误是：

For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]

也就是说，不是从 k 到 N 中选择一个随机整数，而是从 1 到 N 中选择一个随机整数。

如果你犯了这个错误会发生什么？我知道得到的排列不是均匀分布的，但我不知道对得到的分布有什么保证。特别是，有人对元素最终位置的概率分布有一个表达式吗？

score 55 · Accepted Answer

一种经验方法。

让我们在 Mathematica 中实现错误的算法：

p = 10; (* Range *)
s = {}
For[l = 1, l <= 30000, l++, (*Iterations*)
   a = Range[p];
   For[k = 1, k <= p, k++, 
     i = RandomInteger[{1, p}];
     temp = a[[k]];
     a[[k]] = a[[i]];
     a[[i]] = temp
   ];
   AppendTo[s, a];
]

现在得到每个整数在每个位置的次数：

r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s]

让我们在结果数组中取三个位置，并绘制该位置每个整数的频率分布：

对于位置 1，频率分布为：

对于位置 5（中）

对于位置 10（最后一个）：

在这里，您可以将所有位置的分布绘制在一起：

在这里，您对 8 个职位有更好的统计数据：

一些观察：

对于所有位置，“1”的概率是相同的 (1/n)。
概率矩阵关于大对角线对称
所以，任何数字在最后一个位置的概率也是一致的（1/n）

您可以从同一点（第一个属性）和最后一条水平线（第三个属性）查看所有行的起点来可视化这些属性。

第二个属性可以从下面的矩阵表示示例中看出，其中行是位置，列是乘员数量，颜色代表实验概率：

对于 100x100 矩阵：

编辑

只是为了好玩，我计算了第二个对角元素的确切公式（第一个是 1/n）。其余的可以完成，但工作量很大。

h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n)

从 n=3 到 6 验证的值（{8/27、57/256、564/3125、7105/46656}）

编辑

在@wnoise 答案中进行一些一般的显式计算，我们可以获得更多信息。

将 1/n 替换为 p[n]，因此计算不会被计算，例如，我们得到 n=7 的矩阵的第一部分（点击查看大图）：

其中，在与其他 n 值的结果进行比较之后，让我们识别矩阵中的一些已知整数序列：

{{  1/n,    1/n      , ...},
 {... .., A007318, ....},
 {... .., ... ..., ..},
 ... ....,
 {A129687, ... ... ... ... ... ... ..},
 {A131084, A028326 ... ... ... ... ..},
 {A028326, A131084 , A129687 ... ....}}

您可以在精彩的http://oeis.org/中找到这些序列（在某些情况下具有不同的符号）

解决一般问题比较困难，但我希望这是一个开始

score 31 · Accepted Answer

您提到的“常见错误”是随机换位。Diaconis 和 Shahshahani 在使用随机转置生成随机排列 (1981)中详细研究了这个问题。他们对停止时间和收敛到均匀性进行了完整的分析。如果您无法获得论文的链接，请给我发送电子邮件，我可以将副本转发给您。这实际上是一本有趣的书（就像 Persi Diaconis 的大多数论文一样）。

如果数组有重复的条目，那么问题会略有不同。作为一个无耻的插件，我、Diaconis 和 Soundararajan 在A Rule of Thumb for Riffle Shuffle (2011)的附录 B 中解决了这个更普遍的问题。

score 15 · Accepted Answer

比方说

a = 1/N
b = 1-a
B _ii (k) 是交换k第 th 个元素后的概率矩阵。即“交换k后在哪里？”这个问题的答案。i例如 B ₀ (3) =(0 0 1 0 ... 0)和 B ₁ (3) = (a 0 b 0 ... 0)。你想要的是每个 k 的 B _N (k)。
K _i是一个 NxN 矩阵，第 i 列和第 i 行为 1，其他地方为零，例如：

kappa_2

I _i是单位矩阵，但元素 x=y=i 归零。例如对于 i=2：

I_2

是_ _{_}

Ai=bIi + aKi

然后，

B_n

但是因为 B _N (k=1..N) 形成单位矩阵，所以任何给定元素 i 最终位于位置 j 的概率由矩阵的矩阵元素 (i,j) 给出：

解矩阵

例如，对于 N=4：

B_4

作为 N = 500 的图表（颜色级别为 100*概率）：

B_500

对于所有 N>2，模式都是相同的：

第k 个元素最可能的结束位置是 k-1。
对于k < N*ln(2) ，最不可能的结束位置为 k，否则为位置1

score 13 · Accepted Answer

我知道我以前看过这个问题...

“为什么这个简单的洗牌算法会产生有偏差的结果？一个简单的原因是什么？ ”答案中有很多好东西，尤其是Jeff Atwood 在 Coding Horror 上的博客链接。

正如您可能已经猜到的那样，根据@belisarius 的回答，确切的分布在很大程度上取决于要洗牌的元素数量。这是 Atwood 的 6 元素甲板图：

在此处输入图像描述

score 9 · Accepted Answer

多么可爱的问题啊！我希望我有一个完整的答案。

Fisher-Yates 很适合分析，因为一旦它决定了第一个元素，它就会不理会它。有偏见的人可以在任何地方反复交换一个元素。

我们可以像分析马尔可夫链一样分析这一点，将动作描述为线性作用于概率分布的随机转移矩阵。大多数元素都被单独留下，对角线通常是 (n-1)/n。在通过 k 时，当它们没有被单独留下时，它们将与元素 k 交换（如果它们是元素 k，则与随机元素交换）。这是行或列 k 中的 1/(n-1)。行和列 k 中的元素也是 1/(n-1)。很容易将这些矩阵相乘以使 k 从 1 变为 n。

我们确实知道，最后一位的元素将同样可能最初出现在任何地方，因为最后一次通过与其他任何地方交换最后一位的可能性相同。同样，第一个元素也有可能被放置在任何地方。这种对称性是因为转置颠倒了矩阵乘法的顺序。事实上，矩阵在第 i 行与第 (n+1 - i) 列相同的意义上是对称的。除此之外，这些数字并没有显示出太多明显的模式。这些精确解确实显示出与 belisarius 运行的模拟一致：在槽 i 中，得到 j 的概率随着 j 上升到 i 而减小，在 i-1 处达到其最低值，然后在 i 处跃升至其最高值，并且递减直到 j 达到 n。

在 Mathematica 中，我生成了每一步

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, 
                      {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]]

（我没有在任何地方找到它，但使用了第一个匹配规则。）最终的转换矩阵可以用以下公式计算：

Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]

ListDensityPlot是一个有用的可视化工具。

编辑（贝利撒留）

只是一个确认。以下代码给出了与@Eelvex 的答案相同的矩阵：

step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), 
                      {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]];
r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]];
Last@Table[r[4, i], {i, 1, 4}] // MatrixForm

score 3 · Accepted Answer

维基百科关于 Fisher-Yates shuffle 的页面有一个描述和示例，说明在这种情况下会发生什么。

score 3 · Accepted Answer

您可以使用随机矩阵计算分布。让矩阵 A(i,j) 描述最初在位置 i 的牌最终在位置 j 的概率。然后第 k 次交换有一个矩阵 Ak 由Ak(i,j) = 1/Nifi == k或给出j == k（位置 k 的牌可以在任何地方结束，任何牌都可以以相等的概率结束在位置 k），Ak(i,i) = (N - 1)/N对于所有i != k（每张其他牌将保持在同一个位置概率 (N-1)/N) 和所有其他元素为零。

然后由矩阵的乘积给出完全洗牌的结果AN ... A1。

我希望您正在寻找概率的代数描述；您可以通过扩展上述矩阵产品来获得一个，但我想它会相当复杂！

更新：我刚刚在上面发现了 wnoise 的等效答案！哎呀...

score 3 · Accepted Answer

我对此进行了更深入的研究，结果证明已经对这种分布进行了深入研究。它之所以有趣，是因为这种“损坏的”算法已（或曾经）用于 RSA 芯片系统中。

在半随机转置洗牌中，Elchanan Mossel、Yuval Peres 和 Alistair Sinclair 研究了这个和更一般的洗牌类别。那篇论文的结果似乎是需要log(n)打破洗牌才能实现近乎随机的分布。

在The bias of three pseudorandom shuffle ( Aequationes Mathematicae , 22, 1981, 268-292) 中，Ethan Bolker 和 David Robbins 分析了这种 shuffle 并确定单遍后到均匀性的总变化距离为 1，表明它不是很完全随机。他们也给出了渐近分析。

最后，Laurent Saloff-Coste 和 Jessica Zuniga 在他们对非齐次马尔可夫链的研究中找到了一个很好的上限。

score 2 · Accepted Answer

这个问题正在乞求对提到的破碎洗牌进行交互式视觉矩阵图分析。这样的工具在页面上会随机播放吗？- Mike Bostock 为什么随机比较器不好。

Bostock 已经整合了一个分析随机比较器的优秀工具。在该页面的下拉列表中，选择naïve swap (random ↦ random)以查看损坏的算法及其产生的模式。

他的页面内容丰富，因为它可以让人们看到逻辑变化对洗牌数据的直接影响。例如：

这个使用非均匀且非常有偏见的随机播放的矩阵图是使用简单交换（我们从“1 到 N”中选择）生成的，代码如下：

function shuffle(array) {
    var n = array.length, i = -1, j;
    while (++i < n) {
        j = Math.floor(Math.random() * n);
        t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

但是，如果我们实现一个无偏差的随机播放，我们从“k 到 N”进行选择，我们应该会看到如下图：

其中分布是均匀的，并且由以下代码生成：

function FisherYatesDurstenfeldKnuthshuffle( array ) {
    var pickIndex, arrayPosition = array.length;
    while( --arrayPosition ) {
        pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) );
        array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ];
    }
}

score 1 · Accepted Answer

到目前为止给出的优秀答案都集中在分布上，但你也问过“如果你犯了这个错误会发生什么？” - 这是我还没有看到回答的问题，所以我将对此进行解释：

Knuth-Fisher-Yates 洗牌算法从 n 个元素中选择 1 个，然后从 n-1 个剩余元素中选择 1 个，依此类推。

您可以使用两个数组 a1 和 a2 来实现它，在其中从 a1 中删除一个元素并将其插入 a2，但算法会在适当的位置执行它（这意味着它只需要一个数组），如此处所述（ Google：“洗牌算法 Fisher-Yates DataGenetics") 非常好。

如果您不删除元素，则可以再次随机选择它们，这会产生有偏的随机性。这正是您所描述的第二个示例所做的。第一个示例，Knuth-Fisher-Yates 算法，使用从 k 到 N 运行的游标变量，它记住哪些元素已经被选取，因此避免多次选取元素。

algorithm - 你从这个破碎的随机洗牌中得到什么分布？

10 回答 10

Related

Reference