你从这个破碎的随机洗牌中得到了什么分布? [英] What distribution do you get from this broken random shuffle?

问题描述

著名的Fisher-Yates shuffle算法可用于随机排列长度为N的数组A:

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.

如果你犯了这个错误会怎样?我知道结果排列不是均匀分布的，但我不知道对结果分布有什么保证.特别是，有没有人有关于元素最终位置的概率分布的表达式?

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?

推荐答案

经验方法.

让我们在 Mathematica 中实现错误算法:

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 for position 10 (last):

在这里，您将所有位置的分布绘制在一起:

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)

您可以通过查看来自同一点(第一个属性)和最后一条水平线(第三个属性)的所有线的起点来可视化这些属性.

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).

第二个属性可以从下面的矩阵表示示例中看出，其中行是位置，列是占用人数，颜色表示实验概率:

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:

对于 100x100 矩阵:

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、564/3125、7105/46656})

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/

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

Solving the general problem is more difficult, but I hope this is a start

这篇关于你从这个破碎的随机洗牌中得到了什么分布?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！