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

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

实证方法.

让我们在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答案中进行一些明确的计算,我们可以获得更多信息.

用p [n]代替1/n,所以计算保持未评估,我们得到例如矩阵的第一部分,其中n = 7(点击查看更大的图像):

其中,在与n的其他值的结果进行比较后,让我们在矩阵中识别一些已知的整数序列:

{{  1/n,    1/n      , ...},
 {... .., A007318, ....},
 {... .., ... ..., ..},
 ... ....,
 {A129687, ... ... ... ... ... ... ..},
 {A131084, A028326 ... ... ... ... ..},
 {A028326, A131084 , A129687 ... ....}}

您可以在精彩的http://oeis.org/中找到这些序列(在某些情况下具有不同的符号)

解决一般问题比较困难,但我希望这是一个开始

Answer 2

你提到的"常见错误"是随机转换的混乱.Diaconis和Shahshahani在随机转置生成随机置换(1981)中详细研究了这个问题.他们对停止时间和趋同性进行了全面分析.如果您无法获得该论文的链接,请发送电子邮件给我,我可以转发给您.这实际上是一个有趣的阅读(就像大多数Persi Diaconis的论文一样).

如果数组有重复的条目,那么问题就会略有不同.作为一个无耻的插件,这个更普遍的问题由我自己,Diaconis和Soundararajan在Riffle Shuffling(2011)的经验法则的附录B中解决.

Answer 3

让我们说吧

• 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否则

Answer 4

我知道我之前见过这个问题......

" 为什么这个简单的shuffle算法产生有偏见的结果？这是一个简单的原因吗？ "答案中有很多好东西,尤其是Jeff Atwood关于Coding Horror的博客链接.

正如您可能已经猜到的那样,基于@belisarius的答案,确切的分布很大程度上取决于要洗牌的元素数量.这是阿特伍德对6元素牌组的情节:

Answer 5

多么可爱的问题!我希望我有一个完整的答案.

Fisher-Yates很好分析,因为一旦它决定了第一个元素,它就会让它独自存在.有偏见的人可以反复交换元素进出任何地方.

我们可以通过描述作为线性地对概率分布起作用的随机转移矩阵的动作,以与马尔可夫链相同的方式对此进行分析.大多数元素都是单独存在的,对角线通常是(n-1)/ n.在通过k时,当它们不被单独留下时,它们与元素k交换(或者如果它们是元素k则是随机元素).这在行k或列k中是1 /(n-1).行k和列k中的元素也是1 /(n-1).很容易将这些矩阵相乘,k从1变为n.

我们确实知道最后一个位置的元素同样可能最初位于任何地方,因为最后一个传递与最后一个传递的位置相同.同样,第一个元素同样可能放在任何地方.这种对称性是因为转置反转了矩阵乘法的顺序.实际上,矩阵在行i与列(n + 1-i)相同的意义上是对称的.除此之外,这些数字并没有显示出明显的模式.这些确切的解决方案确实与belisarius运行的模拟一致:在时隙i中,当j升至i,在i-1处达到其最低值,然后在i处跳到其最高值时,获得j的概率减小,并且减少直到j到达n.

在Mathematica中,我生成了每个步骤

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, 
                      {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]]

(我没有在任何地方找到它,但是使用了第一个匹配规则.)最终的转换矩阵可以用以下公式计算:

Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]

ListDensityPlot 是一个有用的可视化工具.

编辑(由belisarius)

只是一个确认.以下代码给出了与@Eelvex答案中相同的矩阵:

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