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

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/Nb = 1-aB&nbsp;i（k）是第th个元素i交换后的概率矩阵k。即问题的答案“&nbsp;交换k后的位置是i什么？”。例如B&nbsp;0（3）=&nbsp;(0 0 1 0 ... 0)和B&nbsp;1（3）=&nbsp;(a 0 b 0 ... 0)。你想要的是每个k的B&nbsp;N（k）。K&nbsp;i是一个NxN矩阵，在第i列和第i行中有1，在其他地方为零，例如：我我是单位矩阵，但是与该元素X = Y = I归零。例如，对于i = 2：一个我是然后，但是因为B&nbsp;N（k = 1..N）形成单位矩阵，所以任何给定元素i最后都在位置j的概率由矩阵的矩阵元素（i，j）给出：例如，对于N = 4：作为N = 500的图表（颜色等级为100 *概率）：所有N> 2的模式都是相同的：第k个元素最可能的结束位置是k-1。的至少可能的终止位置为k为ķ<N * LN（2）&nbsp;，位置1否则