朴素洗牌渐近有多糟糕？

Question

众所周知，这种通过将每个项目与另一个随机选择的项目交换来打乱数组的“天真的”算法无法正常工作：

for (i=0..n-1)
  swap(A[i], A[random(n)]);

具体来说，由于在每次 $n$ 迭代中，都会做出 $n$ 个选择之一（具有均匀概率），因此通过计算有 $n^n$ 可能的“路径”；因为可能的排列数 $n!$ 并不能均匀地划分为路径数 $n^n$，所以该算法不可能以相同的概率产生每个 $n!$ 排列。（相反，人们应该使用所谓的 费舍尔-耶茨 shuffle，本质上是将从 [0..n) 中选择随机数的调用更改为从 [i..n) 中选择随机数的调用；不过，这对我的问题来说毫无意义。）

我想知道的是，天真的洗牌有多“糟糕”？更具体地说，令 $P(n)$ 为所有排列的集合，$C( ho)$ 为通过朴素算法产生结果排列 $ ho\in P(n)$ 的路径数，则是函数的渐近行为

$\qquad \displaystyle M(n) = \frac{n!}{n^n}\max_{ ho\in P(n)} C( ho)$

和

$\qquad \displaystyle m(n) = \frac{n!}{n^n}\min_{ ho\in P(n)} C( ho)$?

主要因素是“标准化”这些值：如果朴素的洗牌是“渐近好的”那么

$\qquad \displaystyle \lim_{n o\infty}M(n) = \lim_{n o\infty}m(n) = 1$。

我怀疑（基于我见过的一些计算机模拟）实际值远离 1，但是否知道 $\lim M(n)$ 是否有限，或者 $\lim m(n)$是远离 0 的吗？关于这些量的行为我们知道什么？

Answer 1

我们将通过归纳法证明排列 $ ho_n = (2,3,4,\ldots, n,1)$ 是 $C( ho_n) = 2^{n-1}$ 的示例。如果这是最坏的情况，就像前几个 $n$ 一样（请参阅注释 OEIS 序列 A192053)，然后 $m(n) \approx (2/e)^{n}$。因此，归一化最小值与归一化最大值一样，都是“指数级糟糕”。

基本情况很简单。对于归纳步​​骤，我们需要一个引理：

引理： 在从 $(2,3,4, \ldots, n, 1)$ 到 $(1,2,3, \ldots, n)$ 的任何路径中，第一步移动会交换位置 $1$ 和 $n$，或者最后一步交换位置 $1$ 和 $n$。

证明草图： 假设没有。考虑涉及第 $n$ 个位置的第一步。假设这是第 $i$ 步，$i eq 1$ 和 $i eq n$。此移动必须将项目 $1$ 放置在第 $i$ 个位置。现在考虑触及$1$ 项目的下一步行动。假设这一步是第$j$步。此移动必须交换 $i$ 和 $j$，将项目 $1$ 移动到第 $j$ 个位置，且 $i < j$。类似的论点表明，项目 $1$ 只能随后移动到右侧。但$1$这个项目首先需要结束，这是一个矛盾。$\平方$

现在，如果第一步交换位置 $1$ 和 $n$，则其余的移动必须采用排列 $(1, 3,4,5, \ldots, n,2)$ 到 $(1,2,3, 4、\ldots,n)$。如果剩余的动作没有触及第一个位置，那么这就是位置 $2 \ldots n$ 的排列 $ ho_{n-1}$，通过归纳我们知道有 $C( ho_{n- 1})=2^{n-2}$ 执行此操作的路径。类似于引理证明的一个论点说，没有路径触及第一个位置，因为项目 $1$ 必须最终位于错误的位置。

如果最后一步交换位置 $1$ 和 $n$，则前 $n-1$ 步必须将排列 $(2,3,4,\ldots, n,1)$ 转换为排列 $(n,2 , 3,4, \点, n-1, 1)$。同样，如果这些移动没有触及最后一个位置，那么这就是排列 $ ho_{n-1}$，通过归纳有 $C( ho_{n-1})=2^{n- 2}$ 执行此操作的路径。再说一遍，如果第一个 $n-1$ 移动到这里触及最后一个位置，则 $1$ 永远不会到达正确的位置。

因此，$C( ho_n) = 2C( ho_{n-1}) = 2^{n-1}$。

Answer 2

经过一番挖掘，感谢 mhum 指向 OEIS 的指针，我终于找到了一个出色的分析和一个很好的（相对）基本论证（据我所知，归功于 Goldstein 和 Moews [1]），即 $M(n )$ 在 $n$ 中以超指数速度增长：

$\{1\ldots n\}$ 的任何对合 $\iota$ 对应于“朴素”洗牌算法的运行，该算法产生恒等排列作为其结果，因为该算法将用 $\iota( k)$ 并随后将 $\iota(k)$ 与 $k$ 交换，保持两者不变。这意味着产生恒等排列的算法的运行次数至少是对合次数 $Q(n)$ （事实上，稍微思考一下就会发现对应关系是 1-1，所以它恰好是 $Q( n)$)，因此 $M(n)$ 中的最大值从下面以 $Q(n)$ 为界。

$Q(n)$ 显然有很多名字，包括 电话号码 :看 http://oeis.org/A000085 和 http://en.wikipedia.org/wiki/Telephone_number_%28mathematics%29 。渐进性是众所周知的，事实证明 $Q(n) \approx C\left(\frac{n}{e} ight)^{n/2}e^\sqrt{n}$;从递推关系 $Q(n) = Q(n-1)+(n-1)Q(n-2)$ 可以归纳出比率 $R(n) = \frac{Q(n) }{Q(n-1)}$ 满足 $\sqrt{n}\lt R(n)\lt\sqrt{n+1}$ 并且从那里基本分析得到领先的 $n^{n/2}$渐进项，尽管其他项需要更仔细的努力。由于 $M(n)$ 定义中的“比例因子”$\frac{n!}{n^n}$ 仅约为 $C\sqrt{n}e^{-n}$，因此首项$Q(n)$ 占主导地位并产生（渐近）$M(n)\geq Cn^{(n+1)/2}e^{-3n/2+\sqrt{n}}$。

事实上，Goldstein 和 Moews 在 [1] 中继续表明，恒等排列对于大 $n$ 最有可能，因此 $\geq$ 实际上是 $\approx$ 以及 $M(n) 的行为$ 已全部结算。这仍然留下了 $m(n)$ 行为的问题；如果这也符合他们论文中的分析，我不会太惊讶，但我还没有机会仔细阅读它，还没有真正掌握他们的方法，只足以理解基本结果。

[1] 戈德斯坦，D.和莫伊斯，D.：“身份是大n最有可能的交换洗牌”， http://arxiv.org/abs/math/0010066