.　　上一篇说到，用插入排序 + 随机比较实现洗牌，其结果是不均匀的，各个元素留在原位的概率比较大。当元素个数较多时，除了开头和结尾几个元素，每个元素留在原位的概率都趋于一个常数 $C \approx 0.220643036096533$ ，我称之为「乱排常数」。这一篇就来试着找一下这个常数的表达式。

　　既然这个常数是在元素很多的时候才表现出来的，而且只适用于除开头、结尾外的元素，所以我们索性考虑元素无穷多的情况，这也就是元素有限多的情形的极限了。「乱排常数」，就是元素无穷多时，每个元素留在原位的概率。

　　我们来看一下一个元素是怎么留在原位的。下面是一个例子。首先，队伍里有一群路人：

然后，我们关注的那个元素（「轮子哥」）来到了队尾：

他向前插队，假设插过了两个元素：

然后，队尾来了新人：

他也向前插队，但并没有插过轮子哥：

然后又有新人来了，并且一下子插了好远：

下一个新人比较怂：

然后又有一个新人插到了轮子哥前面：

此时，轮子哥就回到了原位。之后的新人都不可以再插到轮子哥前面，因为一旦这样，轮子哥就回不到原位了。

　　总结一下，每一个元素都会经历一个先前进、再后退的过程，「前进」是自己插队的结果，「后退」是后来者插队的结果。若要留在原位，前进和后退的步数必须相等。要计算一个元素留在原位的概率，就要对前进和后退的步数分情况讨论。

　　先考虑最简单的情况：前进和后退的步数都是 0。在这种情况下，我们关注的元素（轮子哥）本身不能向前插队，其概率为 1/2 。同时，后面的每个元素也都不能插到它前面。后面的第 1 个元素（1 号球）不插到轮子哥前面的概率是 1/2 。2 号球到来时，它与轮子哥之间已经有了 1 号球，所以它不插到轮子哥前面的概率就是 1 - 1/4 = 3/4 。3 号球到来时，它与轮子哥之间已经有了 2 个球，所以它不插到轮子哥前面的概率是 1 - 1/8 = 7/8 。依此类推，号球不插到轮子哥前面的概率是 $1 - 2^{-n}$ 。由此，在轮子哥留在原位的各种情况中，前进和后退步数均为 0 的概率就是：

$P_0 = \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{3}{4} \cdot \frac{7}{8} \cdot \cdots = \frac{1}{2} \cdot \prod_{i=1}^\infty (1 - 2^{-i}) \\$

这个连乘式是收敛的，并且收敛得很快，但是它的结果却无法简单地写出来。不过我们不怕 —— 遇到这种算不出的级数，就把它的结果定义成一种特殊函数嘛！这种特殊函数叫 q-Pochhammer 符号；我在一周前第一次见过这个特殊函数，居然现在就用到了！

　　q-Pochhammer 符号的一般定义为：

$(a;q)_n = \prod_{i=0}^{n-1} (1 - aq^i) \\$

其中的也可以取无穷，此时连乘式有无限项。q-Pochhammer 符号的水很深，不过在这一篇中，你只需要知道它的定义就好。有了 q-Pochhammer 符号，前进和后退步数均为 0 的概率就可以简单地写成 $P_0 = 1/2 \cdot (1/2; 1/2)_\infty$ 了。

　　下面看稍微复杂一点的情况：前进和后退的步数均为 1。首先，前进步数为 1 的概率为 1/4 ：前面第一个路人要放轮子哥过去，但第二个路人不放。之后若要后退 1 步，则需要有且仅有 1 个新人插到轮子哥前面。设这个新人是号球。在它之前的任意一个号球，刚来时与轮子哥之间都有个球（ i-1 个有编号的球和 1 个路人），所以它不插过轮子哥的概率是 $1 - 2^{-(i+1)}$ 。然后号球来了，它与轮子哥之间有个球，它插过轮子哥的概率是 $2^{-(j+1)}$ 。号球之后的任意一个号球，刚来时与轮子哥之间都只有 i-1 个球了（少了号球），所以它不插过轮子哥的概率是 $1 - 2^{-i}$ 。把与「后退」有关的这些概率乘起来，是这样的：

$\left[ \prod_{i=1}^{j-1} (1 - 2^{-(i+1)}) \right] \cdot 2^{-(j+1)} \cdot \left[ \prod_{i=j+1}^\infty (1 - 2^{-i}) \right] \\$

它看起来非常复杂，但可以注意到，前后两个连乘式其实是可以连起来的，变得与无关：

$2^{-(j+1)} \cdot \prod_{i=2}^\infty (1 - 2^{-i}) \\$

「前进和后退的步数均为 1」的概率，就应该是上式对所有的求和，再乘上与「前进」有关的概率 1/4 ：

$P_1 = \frac{1}{4} \cdot \sum_{j=1}^\infty 2^{-(j+1)} \cdot \prod_{i=2}^\infty (1 - 2^{-i}) \\$

容易算出中间那个求和式的值是 1/2 。后面的连乘式我们暂时保留，故

$P_1 = \frac{1}{8} \cdot \prod_{i=2}^\infty (1 - 2^{-i}) \\$

　　下面计算「前进和后退步数均为 2」的概率 P_2 。设后来插到轮子哥前面的分别是 j_1, j_2 号球。仿照上一节，可以如下计算 P_2 ，各项的含义请读者自行思考，不再赘述。

$P_2 = \frac{1}{8} \cdot \sum_{j_1=1}^\infty \sum_{j_2 = j_1+1}^\infty \left[ \prod_{i=1}^{j_1-1} (1 - 2^{-(i+2)}) \cdot 2^{-(j_1+2)} \cdot \prod_{i=j_1+1}^{j_2-1} (1 - 2^{-(i+1)}) \cdot 2^{-(j_2+1)} \cdot \prod_{i=j_2+1}^\infty (1 - 2^{-i}) \right] \\$

类似地，括号中的三个连乘式也可以连起来并提到求和号外面：

$P_2 = \frac{1}{8} \cdot \left[ \sum_{j_1=1}^\infty 2^{-(j_1+2)} \cdot \sum_{j_2=j_1+1}^\infty 2^{-(j_2+1)} \right] \cdot \prod_{i=3}^\infty (1 - 2^{-i}) \\$

括号中的连加和计算如下：

$\begin{align} \sum_{j_1=1}^\infty 2^{-(j_1+2)} \cdot \sum_{j_2=j_1+1}^\infty 2^{-(j_2+1)} &= \sum_{j_1=1}^\infty 2^{-(j_1+2)} \cdot \frac{2^{-(j_1+2)}}{1 - 1/2} \\ &= \frac{1}{1 - 1/2} \cdot \sum_{j_1=1}^\infty 2^{-2(j_1+2)} \\ &= \frac{1}{1 - 1/2} \cdot \frac{1}{1 - 1/4} \cdot \frac{1}{2^6} \\ \end{align} \\$

代回去可得

$P_2 = 2^{-9} \cdot \frac{\prod_{i=3}^\infty (1 - 2^{-i})}{\prod_{i=1}^2 (1 - 2^{-i})} \\$

　　由上面的计算已经可以看出一些端倪了。「前进与后退步数均为」的概率 P_k 的通项为：

$P_k = 2^{-(k+1)^2} \cdot \frac{\prod_{i=k+1}^\infty (1 - 2^{-i})}{\prod_{i=1}^k (1-2^{-i})} \\$

而「乱排常数」，就是对 P_k 再求和：

$C = \sum_{k=0}^\infty P_k = \sum_{k=0}^\infty \left[ 2^{-(k+1)^2} \cdot \frac{\prod_{i=k+1}^\infty (1 - 2^{-i})}{\prod_{i=1}^k (1-2^{-i})} \right] \\$

这就是乱排常数的数学表达式。看起来很复杂是吧？我们来稍微化简一下。对中括号里那个分式的分子和分母同乘以分母，可以让分子与无关，从而提到求和号外面来：

$C = \prod_{i=1}^\infty (1 - 2^{-i}) \cdot \sum_{k=0}^\infty \frac{2^{-(k+1)^2} }{\prod_{i=1}^k (1-2^{-i})^2} \\$

采用 q-Pochhammer 符号，可以进一步把上式简记为：

$C = (1/2; 1/2)_\infty \cdot \sum_{k=0}^\infty \frac{2^{-(k+1)^2}}{(1/2; 1/2)_k^2} \\$

　　观察一下这个求和式：其分母快速趋于一个固定的极限，而分子急剧减小，所以求和式收敛很快。不难编程验证，上式给出的常数确实约等于 0.220643036096533。

　　—— 这个式子还是好复杂啊，能不能再化简？

　　—— 咱们下回分解。

ITPub博客

10810 一种错误的洗牌算法，以及乱排常数 (2)

最新文章