著名的 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 中随机选择一个整数。
如果你犯了这个错误会怎样?我知道生成的排列不是均匀分布的,但我不知道生成的分布有什么保证。特别是,有没有人有关于元素最终位置的概率分布的表达式?
最佳答案
实证方法。
让我们在 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/ 中找到这些序列(在某些情况下具有不同的符号)
解决一般问题比较困难,但我希望这是一个开始
关于algorithm - 你从这个 splinter 的随机洗牌中得到什么分布?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28912905/