4

这是一个与 Knuth/Fisher-Yates shuffle 相关的非常困难但有趣的概率问题。

当对每个元素进行循环时，将当前元素与整个数组中的任何随机元素（不在左边的元素内）进行交换，那么原始第 i个元素在第 j个位置结束的概率是多少？

4

3 回答 3

5

Knuth shuffle 如下（在 Python 中，但可能是伪代码）

for i in range(len(v)):
  swap(v, i, randrange(i, len(v))

naïve shuffle 非常相似，但它不是Knuth shuffle：

for i in range(len(v)):
  swap(v, i, randrange(0, len(v))

Knuth shuffle 产生均匀分布的排列。naïve shuffle 可以被证明不是，因为有n n 个可能的随机数序列，每个序列具有相等的概率，并且n ! 可能的排列，这不是n n的一个因素。（另一方面，Knuth shuffle 恰好包含n ! 个可能的随机数序列，每个序列都可以被证明产生一个唯一的排列。）

上述证明并未表明朴素洗牌中的各个排列位置是否均匀分布。尽管如此，排列的非均匀分布仍有可能产生排列元素的均匀分布：例如，如果除了旋转之外的所有排列的概率为 0，并且旋转具有相等的概率，那么排列元素将是均匀分布的。（这将是比天真的洗牌更糟糕的洗牌。）

事实证明，naïve shuffle 不会产生均匀分布的元素位置。有两点规律性：向量中第一个元素的最终位置是均匀分布的，最终位于最终位置的元素也是如此。

元素i ( i ≠0)最可能的最终位置是位置i -1。

这是n = 8的转移概率表，计算为转移矩阵的乘积：

from/to     0       1       2       3       4       5       6       7
  0      .125    .125    .125    .125    .125    .125    .125    .125
  1      .158    .116    .117    .118    .119    .121    .123    .125
  2      .144    .151    .110    .112    .115    .118    .121    .125
  3      .132    .139    .147    .107    .111    .115    .119    .125
  4      .122    .129    .137    .146    .107    .112    .118    .125
  5      .113    .120    .128    .137    .147    .110    .117    .125
  6      .105    .112    .120    .129    .139    .151    .116    .125
  7      .098    .105    .113    .122    .132    .144    .158    .125

可以推导出P n ( i , j ) 的封闭形式——n 个元素的向量中的元素i将被打乱到位置j的概率。

在该算法中，迭代i处的交换涉及元素vi和其他一些元素v j。（有可能i = j。）虽然交换是一种对称操作，但区分这两个元素是有用的；我们称其为元素v i的出交换和v j的入交换

请注意，在元素k的in 交换之后，k不能再被交换，因为所有后续out 交换都位于k的新位置之后的位置。因此，如果k曾经被交换出去，它必须在迭代k时被交换出去；换句话说，只有第一个涉及元素的交换可以在out swap。

现在，在洗牌的任何一次迭代中，即将被交换的元素的最终目的地都是均匀分布的。（最终目的地为j的概率是所有i的总和，下一个位置为i的概率乘以下一个位置i的最终目的地为j的概率。由于下一个位置是均匀分布的，因此乘数可以被分解出来，剩余的总和为 1，因为j必须来自某个i。）

此外，对于一个从不out swapped的元素，它的最终目的地是它最后一次in swap发生的迭代。（一个元素不可能既不是out swapped也不是in swapped。如果在元素处于out swap位置之前没有in swap发生，它将被out swapped。）

综上所述，我们可以推导出转移函数的公式。

首先，元素k被交换出去的概率恰好是它在k之前的任何迭代中没有被交换的概率，即 ( n -1) k / n k。在其中k被交换出来的 shuffle 中，最终目的地是均匀分布的，所以这对每个转移概率P n ( k , j ) 贡献了 ( n -1) k / n k +1。

现在让我们考虑交换中的最后一个在迭代j处（因此到位置j）的情况。在每次迭代中，给定元素将以1/ n的概率进行交换。因此，最后一个交换发生在迭代j的概率是在j乘以在迭代j发生交换的概率之后没有交换发生的概率，即 ( n -1) n−j−1 / n n−j .

如果j < k，那么k不能被交换出去，但是如果j ≥ k ，我们只需要计算在迭代k之前有交换的情况。这导致以下定义：

P n ( k , j ) = ( n −1) k / n k +1 + (1− O n ( k , j ))×( n −1) nj-1 / n n−j

在哪里

O n ( k , j ) = 0 如果j < k，否则 ( n -1) k / n k

于 2015-03-31T21:40:49.320 回答
2

此页面将您提到的算法与 Knuth 的算法进行了比较，说明了为什么 Knuth 的算法更好。

注意：以下内容可能有误，请看评论。

我不知道计算您询问的概率的简单方法，我似乎也找不到任何简单的解释，但想法是您的算法（通常称为天真的洗牌算法）考虑n^n了数组而不是n!. 这是因为 elementi可以在 step 的每个n位置结束i。由于您n在每个步骤和n步骤中都有可能，因此加起来就是n^n. 由于n^n并非总是可以被整除，n!因此并非所有排列都具有相同的概率，这就是该算法被认为是糟糕的洗牌的原因。

由于并非所有排列都具有相同的概率，因此您询问的概率对于 和 的不同值是不同的i，j但我不知道计算它的公式。

于 2015-03-30T20:22:09.413 回答
-1

在适当的 Knuth shuffle 中，您循环遍历i元素，选择 52 个中的一个与元素 1 交换，然后选择剩余 51 个中的一个与元素 2 交换，剩余 50 个中的一个与元素 3 交换，等等。一旦放置了一个元素进入增长的集合 1,2,3...它永远不会再移动。所以元素i最终出现在位置 1 的几率正好是 1/52——它只能发生在第一个循环中。它最终进入单元格 2 的几率是它不在单元格 1 中的几率 (51/52) 乘以它在第二次通过时被选中的几率 (1/51)。51s 取消，留下 1/52。同样，元素i在位置 3 结束的机会是 51/52 * 50/51 * 1/50，同样是 1/52。因此，每个元素都有相同的机会出现在每个单元格中。

在您的洗牌中，可能会再次选择已经放置的元素以供以后切换，这使得计算赔率非常困难。

于 2015-03-30T20:44:23.333 回答