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

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中选择一个随机整数。如果你犯了这个错误怎么办？我知道由此产生的排列不是均匀分布的，但我不知道对于最终的分布有什么保证。特别是，有没有人有关于元素最终位置的概率分布的表达式？

Answer 1

让我们说吧

• a = 1/N

• b = 1-a

• B _i（k）是第th个元素i交换后的概率矩阵k。即问题的答案“ 交换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，在其他地方为零，例如：

• 我_我是单位矩阵，但是与该元素X = Y = I归零。例如，对于i = 2：

• 一个_我是

然后，

但是因为B _N（k = 1..N）形成单位矩阵，所以任何给定元素i最后都在位置j的概率由矩阵的矩阵元素（i，j）给出：

例如，对于N = 4：

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

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

• 第k个元素最可能的结束位置是k-1。

• 的至少可能的终止位置为k为ķ<N * LN（2） ，位置1否则