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

Question

著名的 Fisher-Yates 洗牌算法可用于随机排列长度为 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 中随机选择一个整数。

如果你犯了这个错误会怎样？我知道生成的排列不是均匀分布的，但我不知道生成的分布有什么保证。特别是，有没有人有关于元素最终位置的概率分布的表达式？

Answer 1

实证方法。

让我们在 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 answer 中进行一些一般的显式计算，我们可以获得更多信息。

将 1/n 替换为 p[n]，因此计算保持不变，例如我们得到矩阵的第一部分 n=7(点击查看大图):

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

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

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

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