你从这个破碎的随机洗牌中得到什么分配？
着名的Fisher-Yates shufflealgorithm可以用来随机排列长度为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中选取一个随机整数。
如果你犯了这个错误会怎么样？ 我知道由此产生的排列不是均匀分布的，但是我不知道什么样的结果会是什么保证。 特别是，有没有人有一个概率分布在元素的最终位置的expression？
实证方法。
让我们在Mathematica中实现错误的algorithm：
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）。
- 概率matrix相对于大的反对angular线是对称的
- 所以，最后一位数字的概率也是一致的（1 / n）
你可以看到从同一点（第一个属性）和最后一个水平线（第三个属性）开始的所有行的属性。
第二个属性可以从以下matrix表示示例中看出，其中行是位置，列是占有者编号，颜色代表实验概率：
对于100x100matrix：
编辑
为了好玩，我计算了第二个对angular元素的精确公式（第一个是1 / n）。 其余的可以完成，但是这是很多工作。
h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n)
从n = 3到6validation的值（{8 / 27,57 / 256,564 / 3125,7105 / 46656}）
编辑
在@wnoise的答案中稍作一般的显式计算，我们可以得到更多的信息。
用p [n]代替1 / n，所以计算保持不被评估，例如对于n = 7的matrix的第一部分（点击查看更大的图像）。
在与其他n值的结果进行比较之后，让我们确定matrix中的一些已知整数序列：
{{ 1/n, 1/n , ...}, {... .., A007318, ....}, {... .., ... ..., ..}, ... ...., {A129687, ... ... ... ... ... ... ..}, {A131084, A028326 ... ... ... ... ..}, {A028326, A131084 , A129687 ... ....}}
你可以在奇妙的http://oeis.org/上find这些序列（在某些情况下有不同的符号）;
解决一般问题比较困难，但我希望这是一个开始
你提到的“常见错误”是随意转换的洗牌。 这个问题在Diaconis和Shahshahani 的随机置换生成随机排列（1981）中有详细的研究 。 他们对停工时间和趋同性进行了全面的分析。 如果您无法获得该文件的链接，请给我发一封电子邮件，我可以向您转发一份副本。 这实际上是一个有趣的阅读（与大多数Persi Diaconis的论文一样）。
如果数组有重复的条目，则问题稍有不同。 作为一个无耻的插件，这个更一般的问题是由我自己，Diaconis和Soundararajan在Riffle Shuffling（2011）的“经验法则”附录B中讨论的 。
我们说
-
a = 1/N -
b = 1-a - B i （k）是第
i个元素交换后的概率matrix。 即对于“i换掉后在哪里？”这个问题的答案。 例如B 0 （3）=(0 0 1 0 ... 0)和B 1 （3）=(a 0 b 0 ... 0)。 你想要的是每N个 B（k）。 - K i是一个NxNmatrix，在第i列和第i行中为1，在其他地方为零，例如：
- 我是单位matrix，但元素x = y = i归零。 例如，对于i = 2：
- 我是
然后，
但是因为B N （k = 1..N）形成单位matrix，所以任何给定的元素i在末端的位置在位置j的概率由matrix的matrix元素（i，j）给出：
例如，对于N = 4：
作为N = 500（颜色等级是100 *概率）的图表：
所有N> 2的模式是相同的：
- 第k个元素最可能的结束位置 是k-1 。
- 对于k <N * ln（2） ， 最不可能的结束位置是k ，否则位置1
我知道我之前看过这个问题
“ 为什么这个简单的洗牌algorithm产生有偏见的结果呢？有什么简单的原因？ ”在答案中有很多好东西，特别是在“编码恐怖”中杰夫·阿特伍德的博客链接。
正如你可能已经猜到的那样，根据@belisarius的回答，确切的分配高度依赖于要洗牌的要素数量。 这里是阿特伍德6层甲板的情节：
多么可爱的问题！ 我希望我有一个完整的答案。
Fisher-Yates很好分析，因为一旦它决定了第一个元素，它就离开它。 有偏见的人可以反复交换一个元素进出任何地方。
我们可以用与马尔可夫链相同的方式来分析这一点，通过描述作为随机转移matrix的线性作用于概率分布的行为。 大多数元素都是孤立的，对angular线通常是（n-1）/ n。 在通过k时，当他们不被孤立时，它们与元素k交换（或者如果元素k是随机元素）。 这是行或列k中的1 /（n-1）。 行和列k中的元素也是1 /（n-1）。 当k从1到n时，将这些matrix相乘是很容易的。
我们知道最后一个地方的元素原本就是在任何地方，因为最后一个地方和其他地方的地方相同。 同样，第一个元素将被放置在任何地方。 这种对称性是因为转置颠倒了matrix乘法的顺序。 事实上，matrix在行i与列（n + 1 – i）相同的意义上是对称的。 除此之外，这些数字并没有显示出太多明显的模式。 这些确切的解决scheme确实与belisarius运行的模拟结果一致：在第i个时隙中，获得j的概率随着jboost到i而下降，在i-1时达到最低值，然后跳跃到i的最高值，直到j达到n。
在Mathematica中，我生成了每一步
step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]]
（我没有在任何地方find它，但是使用了第一个匹配规则。）最终的转换matrix可以用下面的公式计算：
Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]
ListDensityPlot是一个有用的可视化工具。
编辑（belisarius）
只是一个确认。 下面的代码给出了与@ Eelvex的答案相同的matrix：
step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]]; r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]; Last@Table[r[4, i], {i, 1, 4}] // MatrixForm
关于Fisher-Yates shuffle的维基百科页面有一个在这种情况下会发生什么的描述和例子。
你可以使用随机matrix来计算分布。 让matrixA（i，j）描述原来在位置i的卡片结束于位置j的概率。 那么第k个交换有一个由Ak(i,j) = 1/N给出的matrixAk Ak(i,j) = 1/N如果i == k或者j == k ，（位置k中的卡片可以在任何地方结束，任何卡片都可以结束于位置k （N-1）/ N），所有其他元素将保持在相同的位置，并且所有其他元素为零Ak(i,i) = (N - 1)/N等于概率）， Ak(i,i) = (N - 1)/N （N-1）/ N 。
然后完整的混洗的结果由matrixAN ... A1的乘积给出。
我希望你正在寻找一个概率的代数描述; 你可以通过扩展上面的matrix产品来获得一个，但是我想它会相当复杂！
更新：我刚刚发现了上面的wnoise的等效答案！ 糟糕！
我进一步研究了这一点，结果发现这个分布已经被详细研究了。 感兴趣的原因是因为这个“破碎的”algorithm已经（或已经）在RSA芯片系统中使用了。
在半随机转换中 ，Elchanan Mossel，Yuval Peres和Alistair Sinclair研究了这个和更普遍的洗牌类。 这篇论文的结果似乎是，为了实现近乎随机的分配，需要log(n)破碎的洗牌。
在三个伪随机洗牌 （ Aequationes Mathematicae ，22,1981,268-292）的偏见中，Ethan Bolker和David Robbins分析了这个洗牌，并且确定一遍之后的总均匀距离为1，表明它不是很好随机的。 他们也给予asympotic分析。
最后，Laurent Saloff-Coste和Jessica Zuniga发现了他们研究非均匀马尔可夫链的一个很好的上界。
这个问题是乞求一个交互式的视觉matrix图分析破碎洗牌提到。 这样的工具是在页面上它会随机？ – 为什么随机比较是坏的迈克·博斯托克。
博斯托克汇集了一个分析随机比较的优秀工具。 在该页面的下拉列表中，selectnaïveswap（随机随机）以查看破碎的algorithm及其生成的模式。
他的页面是信息性的，因为它可以让人看到逻辑上的改变对洗牌数据的直接影响。 例如：
这个使用非均匀和非常偏向的混洗的matrix图是使用一个简单的交换（我们从“1到N”中select）用这样的代码生成的：
function shuffle(array) { var n = array.length, i = -1, j; while (++i < n) { j = Math.floor(Math.random() * n); t = array[j]; array[j] = array[i]; array[i] = t; } }
但是，如果我们实现一个无偏置的随机播放，我们可以从“k到N”中select一个这样的图表：
分配是统一的，并且由代码产生，例如：
function FisherYatesDurstenfeldKnuthshuffle( array ) { var pickIndex, arrayPosition = array.length; while( --arrayPosition ) { pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) ); array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ]; } }
迄今为止所给出的优秀答案都集中在分配上，但你也问“如果你犯这个错误会发生什么？” – 这是我还没有看到的答案，所以我会解释一下：
Knuth-Fisher-Yates shufflealgorithm从n个元素中选出1个，然后从n-1个剩余元素中选出1个，等等。
您可以使用两个数组a1和a2来实现它，您可以从a1中移除一个元素并将其插入到a2中，但是该algorithm可以实现（也就是说，它只需要一个数组），如下所述（Google：“ Shuffling Algorithms Fisher-Yates DataGenetics“）。
如果不删除元素，可以随机select它们，从而产生偏向的随机性。 这正是你所描述的第二个例子。 第一个例子是Knuth-Fisher-Yatesalgorithm，它使用一个从k到N的游标variables，它记住哪些元素已经被使用了，因此避免了多次拾取元素。
