Knuth随机播放的变体 [英] An variant of Knuth shuffle

问题描述

这是一个与Knuth洗牌有关的非常困难但有趣的概率问题。

This is a very hard but interesting probability question related to Knuth shuffle.

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

When looping for each element, the swap is performed for the current element with any random element from the whole array (not within the elements left), then what is the probabilty of the original i th element ending up at the j th position?

推荐答案

Knuth随机播放如下（在Python中，但它可能是伪代码）

The Knuth shuffle is as follows (in Python, but it could be pseudocode)

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

幼稚的洗牌非常相似，但不是Kemth洗牌的不是：

The naïve shuffle is very similar, but it is not the Knuth shuffle:

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

Knuth随机排列产生均匀分布的排列，因为存在 n ⁿ 可能的随机数序列，每个序列都有一个相等的概率和 n ！可能的排列，而不是 n ⁿ 的因数。 （另一方面，Knuth随机播放恰好涉及 n ！个可能的随机数序列，每个序列都可以证明产生唯一的排列。）

The Knuth shuffle produces uniformly-distributed permutations. The naïve shuffle can be proven not to, because there are nⁿ possible sequences of random numbers, each of which has an equal probability, and n! possible permutations, which is not a factor of nⁿ. (The Knuth shuffle, on the other hand, involves precisely n! possible random number sequences, each of which can be proven to produce a unique permutation.)

以上证明并未表明幼稚混洗中各个排列位置是否均匀分布。排列的不均匀分布仍然有可能产生排列元素的均匀分布：例如，如果除旋转之外的所有其他排列的概率为0，而旋转具有相等的概率，则排列元素将均匀分布。 （那会比纯朴的混洗更糟糕。）

The above proof does not indicate whether or not the individual permutation positions in the naïve shuffle are uniformly distributed. It is possible for a non-uniform distribution of permutations to nonetheless produce a uniform distribution of permutation elements: for example, if all permutations other than rotations have probability 0, and rotations have equal probability, then the permutation elements will be uniformly distributed. (That would be an even worse shuffle than the naïve shuffle.)

事实证明，纯朴的混洗不会不会产生均匀分布的元素职位。规律性有两点：向量中第一个元素的最终位置是均匀分布的，而最终位置中的元素也是如此。

As it turns out, the naïve shuffle does not produce uniformly distributed element positions. There are two points of regularity: the final position of the first element in the vector is uniformly distributed, as is are the elements which end up in the final position.

i （ i ≠ 0）的最可能最终位置是位置 i − 1。

The most likely final position of element i (i≠0) is the position i−1.

以下是 n = 8的转换概率表，计算公式为转换矩阵的乘积：

Here's a table of transition probabilities for n=8, computed as a product of transition matrices:

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 。

It's possible to derive a closed-form for P_n(i, j) -- the probability that element i in a vector of n elements will be shuffled to position j.

在算法中， i 迭代中的 swap 涉及元素 v _i 和其他一些元素 v _j 。 （ i = j 很有可能。）尽管 swap 是对称操作，但区分这两个元素还是很有用的。我们将其称为元素 v _i 的 out swap 和 in swap v _j

In the algorithm, the swap at iteration i involves the element v_i and some other element v_j. (It's possible that i=j.) Although swap is a symmetric operation, it's useful to distinguish the two elements; we'll call this an out swap of the element v_i and an in swap of v_j

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

Note that after an in swap of element k, k can no longer be out swapped, because all the following out swaps are at positions following the new position of k. So if k is ever out swapped, it must be out swapped at iteration k; in other words, only the first swap involving an element can be at out swap.

现在，在随机播放的任何迭代中，即将换出的元素的最终目的地是均匀分布的。 （最终目的地为 j 的概率是下一个位置为 i 的概率在所有 i 上的总和乘以下一个位置 i 的最终目标是 j 。由于下一个位置是均匀分布的，因此可以将乘数分解为因，因为 j 必须来自某些 i 。）

Now, at a any iteration of the shuffle, the final destinations of the element about to be out swapped are uniformly distributed. (The probability of the final destination being j is the sum over all i of the probability of the next position being i times the probability that the final destination of the next position i being j. Since the next positions are uniformly distributed, the multiplier can be factored out, and the remaining sum is 1 since j must come from some i.)

此外，对于从未被交换过的元素 ，其最终目的地是最后一次交换时发生的迭代。 （元素不可能既不被交换掉 也不被交换 。如果没有 in swap 发生在元素位于 out swap 位置，它将被 out swapped 。）

Also, for an element which is never out swapped, its final destination is the iteration at which its last in swap occurred. (It's not possible for an element to be neither out swapped nor in swapped. If no in swap occurs before the element is in the out swap position, it will be out swapped.)

有了这些，我们可以得出过渡的公式

With all that, we can derive the formula for the transition function.

首先，元素 k 被交换出 的概率恰好是元素不被交换的概率。在 k 之前的任意迭代中 in swapped ，即（ n -1） ^k / n ^k 。在 k 被换出 的洗牌中，最终目的地是均匀分布的，因此这有助于（ n − 1） ^k / n ^{k +1} 到每个过渡概率 P _n （ k ， j ）。

First, the probability that element k will be out swapped is precisely the probability that it is not in swapped in any of the iterations prior to k, which is (n-1)^k/n^k. Among the shuffles in which k is out swapped, the final destination is uniformly distributed, so this contributes (n−1)^k/n^k+1 to every transition probability P_n(k, j).

现在，让我们考虑交换中最后一个 在迭代 j （并因此定位 j ）的情况。在每次迭代中，给定元素将以1 / n 的概率被交换。因此，交换中最后一个 在迭代 j 中的概率是 j 之后没有交换发生的概率乘以交换发生的概率在迭代 j 时，即（ n − 1） ^{n− j− 1} / n ^{n− j} 。

Now let's consider the cases in which the last in swap is at iteration j (and hence to position j). At every iteration, a given element will be in swapped with probability 1/n. Consequently, the probability that the last in swap is at iteration j is the probability that no swap occurs after j times the probability that the swap occurs at iteration j, which is (n−1)^n−j−1/n^n−j.

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

If j<k, then k cannot be out swapped, but if j≥k, we need to only count the cases where there was a swap prior to iteration k. This leads to the following definition:

P _n （ k ， j ）=（ n − 1） ^k / n ^{k +1} +（1− O _n （ k ， j ））×（ n − 1） ^nj-1 / n ^{n− j}

P_n(k, j) = (n−1)^k/n^k+1 + (1−O_n(k, j))×(n−1)^n-j-1/n^n−j

其中

O _n （ k ， j ）= 0 j < k ，否则（ n − 1） ^k / n ^k

O_n(k, j) = 0 if j<k, and otherwise (n−1)^k/n^k

这篇关于Knuth随机播放的变体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！