Knuth shuffle的变种

Question

这是一个与Knuth shuffle相关的非常困难但有趣的概率问题.

当循环每个元素时,使用整个数组中的任何随机元素(不在左边的元素内)对当前元素执行交换,那么原始第i个元素在第j个位置结束的概率是多少？

Answer 1

Knuth shuffle如下(在Python中,但它可能是伪代码)

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

天真的洗牌非常相似,但它不是 Knuth shuffle:

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

Knuth shuffle产生均匀分布的排列.天真的洗牌可以证明不是,因为有n ^个可能的随机数序列,每个都有相同的概率,而n!可能的排列,这不是n ⁿ的因素.(另一方面,Knuth shuffle涉及恰好n个可能的随机数序列,每个序列都可以证明产生一种独特的排列.)

上述证据并未表明幼稚洗牌中的个别排列位置是否均匀分布.尽管如此,排列的非均匀分布可能产生排列元素的均匀分布:例如,如果除了旋转之外的所有排列具有概率0,并且旋转具有相等的概率,则排列元素将被均匀地分布.(那将是比天真洗牌更糟糕的洗牌.)

事实证明,在天真的洗牌也不会产生均匀分布的元素位置.有两个规律性点:向量中第一个元素的最终位置是均匀分布的,最终位于最终位置的元素也是如此.

元素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处的交换涉及元素v _i和一些其他元素v _j.(有可能i = j.)虽然交换是对称操作,但区分这两个元素是有用的.我们将这个叫出来交换的元素v _我和掉期的v _Ĵ

注意,在元素k的交换之后,k不能再被交换掉,因为所有后面的交换都在k的新位置之后的位置.因此,如果k被交换掉,它必须在迭代k处交换掉 ; 换句话说,只有涉及元素的第一个交换可以在外部交换.

现在,在随机播放的任何迭代中,要交换的元素的最终目的地是均匀分布的.(最终目的地中的概率Ĵ是在所有的总和我的下一个位置中的概率的我倍的概率的下一个位置的最终目的地我是Ĵ.由于下一位置是均匀分布的,乘法器可以因为j必须来自某些i,所以余下的总和为1.)

此外,对于一个永远不会被交换的元素,它的最终目的地是它在交换中的最后一次发生的迭代.(元素不可能既不交换也不交换.如果在元素处于out交换位置之前没有交换,则它将被交换掉.)

有了这些,我们可以推导出过渡函数的公式.

首先,元素k将被交换的概率恰好是在k之前的任何迭代中不交换的概率,即(n -1)^k/n ^k.在其中k被交换的混洗中,最终目的地是均匀分布的,因此这对每个转移概率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.

如果Ĵ < ķ,然后ķ不能出去交换,但如果Ĵ ≥ ķ,我们只需要算到迭代交换之前,那里有案件ķ.这导致以下定义:

P _n(k,j)=(n -1)^k/n ^{k +1} +(1- O _n(k,j))×(n -1)^nj-1/n ^n-j

哪里

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