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

著名的 Fisher-Yates 洗牌算法可以用来随机排列一个长度为 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 选择一个随机整数。

如果你犯了这个错误会发生什么？我知道由此产生的排列不是均匀分布的，但是我不知道对于由此产生的分布有什么保证。特别是，有没有人知道元素最终位置的概率分布的表达式？

7085 次浏览
小开

维基百科关于 Fisher-Yates shuffle 的页面上有一个描述和例子，确切地说明在这种情况下会发生什么。

小开
最佳答案

经验主义方法

让我们实现 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，频率分布是:

enter image description here

位置5(中)

enter image description here

第10位(最后一位) :

enter image description here

这是所有位置的分布图:

enter image description here

这里你有一个更好的8个职位的统计数据:

enter image description here

一些观察:

  • 对于所有的位置 “1”是相同的(1/n)。
  • 转移矩阵是对称的 关于大反对角线
  • 最后一个数的概率 位置也是均匀的(1/n)

您可以通过查看同一点(第一个属性)和最后一个水平线(第三个属性)的所有行的开始来可视化这些属性。

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

enter image description here

对于100x100的矩阵:

enter image description here

编辑

为了好玩，我计算了第二个对角线元素的精确公式(第一个是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})

剪辑

我们在这个问题的回答中做了一些一般的显式计算，我们可以得到更多的信息。

用 p [ n ]代替1/n，因此计算保持不变，例如 n = 7的矩阵的第一部分(点击查看大图) :

enter image description here

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

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

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

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

小开

多么有趣的问题! 我希望我有一个完整的答案。

Fisher-Yates 很容易分析，因为一旦它决定了第一个元素，就不会去管它了。有偏差的元素可以在任何地方反复交换元素。

我们可以像分析马尔可夫链一样，把这些行为描述为对概率分布线性作用的随机转移矩阵。大多数元素被单独留下，对角线通常是(n-1)/n。在传递 k 时，当它们没有被单独留下时，它们与元素 k 交换，(或者如果它们是元素 k，则与随机元素交换)。这是行或列 k 中的1/(n-1)。行和列 k 中的元素也是1/(n-1)。对于 k 从1到 n，把这些矩阵相乘是很容易的。

我们知道最后一个位置的元素最初可能在任何地方，因为最后一个位置与其他位置交换的可能性相等。类似地，第一个元素同样可能被放置在任何地方。这种对称性是因为移位颠倒了矩阵乘法的顺序。实际上，矩阵是对称的，即行 i 与列(n + 1-i)相同。除此之外，这些数字没有显示出太多明显的规律。这些精确的解决方案与 Belisarius 的模拟结果一致: 在插槽 i 中，当 j 上升到 i 时，得到 j 的概率减小，在 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}]]

(我没有在任何地方找到它的文档，但是使用了第一个匹配规则。) 最后的转移矩阵可用以下方法计算:

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
小开

我知道我以前见过这个问题..。

“ 为什么这个简单的洗牌算法会产生有偏差的结果? 一个简单的原因是什么？”在答案中有很多好东西，特别是一个到 作者: Jeff Atwood的链接。

正如您可能已经猜到的，基于@belisarius 的答案，确切的分布高度依赖于要洗牌的元素数量。下面是阿特伍德关于六元素甲板的构思:

enter image description here

小开

你提到的“常见错误”是随机换位。Diaconis 和 Shahshahani 在 用随机换位生成随机排列(1981)中对这个问题进行了详细的研究。他们做了一个完整的停止时间和收敛到一致性的分析。如果你找不到这篇文章的链接，那么请给我发一封电子邮件，我可以转发给你一份。这实际上是一本有趣的读物(就像 Persi Diaconis 的大部分论文一样)。

如果数组有重复的条目，那么问题就略有不同。作为一个不知羞耻的插头，这个更普遍的问题是由我，Diaconis 和 Soundararajan 在 Riffle Shuffling 的经验法则(2011)的附录 B 中解决的。

小开

您可以使用 随机矩阵随机矩阵计算分布。让矩阵 A (i，j)描述卡最初在位置 i 结束在位置 j 的概率。然后，如果 i == k或 j == k，(位置 k 的卡可以在任何地方结束，任何卡可以在位置 k 结束，概率相等) ，则 kth 掉期有一个由 Ak(i,j) = 1/N给出的矩阵 Ak，对于所有 i != k，Ak(i,i) = (N - 1)/N(所有其他卡将以概率(N-1)/N)停留在同一个位置，所有其他元素为零。

然后由矩阵 AN ... A1的乘积给出完全洗牌的结果。

我希望您正在寻找概率的代数描述; 您可以通过展开上面的矩阵积来得到一个概率，但是我认为它将是相当复杂的！

更新: 我刚刚在上面找到了与“噪音”等价的答案。

小开

这么说吧

  • a = 1/N
  • b = 1-a
  • B我(k)是在 i与第1个元素交换后的转移矩阵。即回答“ i掉期后 k在哪里?”.例如 B0(3) = (0 0 1 0 ... 0)和 B1(3) = (a 0 b 0 ... 0)。你需要的是每个 k 的 BN(k)。
  • K我是一个 NxN 矩阵，第 i 列和第 i 行中都有1，其他地方都是0，例如:

kappa_2

  • I我是恒等矩阵，但元素 x = y = i 为零。例如 i = 2:

I_2

  • A我是

Ai= bIi + aKi

然后,

B_n

而是因为 BN(k = 1。.N)构成恒等矩阵，矩阵的矩阵元素(i，j)给出了任意给定元素 i 在末端位置 j 的概率:

solution matrix

例如，对于 N = 4:

B_4

作为 N = 500(颜色级别为100 * 概率)的图表:

B_500

所有 N > 2的模式都是一样的:

  • K 元 是 K-1的 最可能的结束位置。
  • 可能性最小的结束位置 是 K为 K < N * ln (2)，否则为 1
小开

我进一步研究了这个问题，发现这个分布已经被详细研究过了。它之所以引起人们的兴趣，是因为 RSA 芯片系统中使用了(或曾经使用过)这种“破碎的”算法。

在 通过半随机换位进行洗牌中，埃尔坎南 · 莫塞尔、尤瓦尔 · 佩雷斯和阿利斯泰尔·辛克莱尔们研究了这个以及一个更普遍的洗牌类别。这篇文章的结论似乎是，它需要 log(n)破碎的洗牌，以实现近乎随机分布。

在 三种伪随机洗牌的偏差(等式数学,22,1981,268-292)中，Ethan Bolker 和 David Robbins 分析了这种洗牌，并且确定了单次通过后到均匀性的总变化距离为1，表明它根本不是非常随机的。他们也给出了不对称分析。

最后，Laurent Saloff-Coste 和 Jessica Zuniga 在他们对非齐次马氏链的研究中发现了一个很好的上界。

小开

到目前为止给出的优秀答案都集中在分布上，但是你也问了 “如果你犯了这个错误，会发生什么?”——这是我还没有看到的答案，所以我将对此作出解释:

Knuth-Fisher-Yates 洗牌算法从 n 个元素中选择1个，然后从 n-1个剩余元素中选择1个，以此类推。

你可以用两个数组 a1和 a2来实现它，从 a1中移除一个元素并将其插入 a2中，但是算法可以在适当的位置实现它(这意味着它只需要一个数组) ，正如解释 给你(Google: “ Shuffling  算法 Fisher-Yates DataGenetics”)非常好。

如果你不删除元素，他们可以随机选择再次产生偏见的随机性。这正是你所描述的第二个例子所做的。第一个例子是 Knuth-Fisher-Yates 算法，它使用一个从 k 到 N 的游标变量，该变量会记住哪些元素已经被取走，因此避免不止一次地选择元素。

小开

这个问题是乞求一个 交互式可视矩阵图交互式可视矩阵图分析的破碎洗牌提到。这样一个工具是在页面 它会洗牌吗?-为什么随机比较器是坏的由迈克博斯托克。

Bostock 提供了一个分析随机比较器的优秀工具。在该页面的下拉列表中，选择 初始交换(随机 something 随机)查看破碎的算法及其生成的模式。

他的页面信息量很大，因为它允许人们看到逻辑变化对混乱数据的直接影响。例如:

这个矩阵图使用一个非均匀和非常有偏见的洗牌生成使用一个天真的交换(我们从“1到 N”挑选)与代码如下:

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;
}
}

biased shuffle

但是如果我们实现一个无偏移的洗牌，我们从“ k 到 N”中选择，我们应该看到这样一个图:

enter image description here

其分布是统一的，并由以下代码产生:

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 ];
}
}

提交答案