问题描述
著名的费雪耶茨洗牌算法可以用来随机重排的长度为N的数组答：
The famous Fisher-Yates shuffle algorithm can be used to randomly permute an array A of length N:
For k = 1 to N
Pick a random integer j from k to N
Swap A[k] and A[j]
这是我一直在说一遍又一遍不要让一个常见的错误是这样的：
A common mistake that I've been told over and over again not to make is this:
For k = 1 to N
Pick a random integer j from 1 to N
Swap A[k] and A[j]
也就是说，不是选择一个随机整数k以N，你从1挑到N的随机整数。
That is, instead of picking a random integer from k to N, you pick a random integer from 1 to N.
如果你犯了这种错误会发生什么情况？我知道，所产生的置换不是均匀分布的，但我不知道是什么，保证有什么产生的分配会。特别是，没有任何人有一个前pression超过元素的最终位置？
What happens if you make this mistake? I know that the resulting permutation isn't uniformly distributed, but I don't know what guarantees there are on what the resulting distribution will be. In particular, does anyone have an expression for the probability distributions over the final positions of the elements?
推荐答案
的实证方法。
让我们实现了错误的算法数学：
Let's implement the erroneous algorithm in 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];
]
现在得到的次数每个整数是在每一个位置：
Now get the number of times each integer is in each position:
r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s]
让我们三个位置中所产生的阵列和绘制的频率分布在这个位置上的每个整数：
Let's take three positions in the resulting arrays and plot the frequency distribution for each integer in that position:
对于位置1的频率分布为：
For position 1 the freq distribution is:
有关位置5（中）
和为10位（去年）：
在这里你有分布的所有位置绘制在一起：
and here you have the distribution for all positions plotted together:
在这里，你有超过8个位置较好的统计数据：
Here you have a better statistics over 8 positions:
有些意见：
- 对于所有位置的概率1是相同的（1 / n）中。
- 的概率矩阵是对称的相对于大反角
- 因此，对于任意数量的过去的概率位置也是一致的（1 / N）
- For all positions the probability of"1" is the same (1/n).
- The probability matrix is symmetricalwith respect to the big anti-diagonal
- So, the probability for any number in the lastposition is also uniform (1/n)
您可以形象化那些性质看从同一点（第一属性）的所有行的开始和最后水平线（第三属性）。
You may visualize those properties looking at the starting of all lines from the same point (first property) and the last horizontal line (third property).
第二属性可从下面的矩阵重新presentation例如，当行是位置，列是乘员数和颜色再presents实验概率看出：
The second property can be seen from the following matrix representation example, where the rows are the positions, the columns are the occupant number, and the color represents the experimental probability:
对于一个100×100矩阵：
For a 100x100 matrix:
修改
只是为了好玩，我计算了第二个对角元素的精确公式（第一个是1 / N）。其余的都可以做，但它是一个大量的工作。
Just for fun, I calculated the exact formula for the second diagonal element (the first is 1/n). The rest can be done, but it's a lot of work.
h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n)
从n个验证= 3〜6个值（{8/27，第57/256号决议，三千一百二十五分之五百六十四，四万六千六百五十六分之七千一百○五}）
Values verified from n=3 to 6 ( {8/27, 57/256, 564/3125, 7105/46656} )
修改
工作出一点一般的显式计算在@wnoise答案，我们可以得到一些更多的信息。
Working out a little the general explicit calculation in @wnoise answer, we can get a little more info.
更换的1 / n用p [n]的，所以计算保持未计算，我们得到例如用于矩阵，其中n = 7的第一部分（点击以看到一个更大的图片）：
Replacing 1/n by p[n], so the calculations are hold unevaluated, we get for example for the first part of the matrix with n=7 (click to see a bigger image):
其中，其结果对n的其它值进行比较后，我们确定基质一些已知的整数序列：
Which, after comparing with results for other values of n, let us identify some known integer sequences in the matrix:
{{ 1/n, 1/n , ...},
{... .., A007318, ....},
{... .., ... ..., ..},
... ....,
{A129687, ... ... ... ... ... ... ..},
{A131084, A028326 ... ... ... ... ..},
{A028326, A131084 , A129687 ... ....}}
您可能会发现，在美妙的 http://oeis.org/
You may find those sequences (in some cases with different signs) in the wonderful http://oeis.org/
解决普遍的问题是比较困难的，但我希望这是一个开始。
Solving the general problem is more difficult, but I hope this is a start
这篇关于你从这个破碎的随机洗牌得到什么分布？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！