探讨两种常数卷积的结果与一种常见的洗牌算法错误及其影响

　　「洗牌」&＃xff0c;或者说随机打乱一个数组中元素的顺序&＃xff0c;是编程中的一个常见需求。标准的洗牌算法是 Fisher-Yates shuffle&＃xff0c;用 Javascript 实现如下&＃xff1a;

其基本思路是&＃xff0c;每次从未打乱的部分等可能地选一个元素&＃xff0c;把它与未打乱部分的最后一个元素交换。

　　Fisher-Yates 洗牌算法的实现十分简单&＃xff0c;并且它可以保证均匀性&＃xff0c;即元素的各种排列顺序出现的概率都相等。但是&＃xff0c;很多人闭门造车地发明了一些「错误」的洗牌算法实现&＃xff0c;它们不能保证均匀。例如&＃xff0c;最常见的一种错误实现如下&＃xff1a;

其原理是&＃xff0c;在第 i 次循环中&＃xff0c;从所有元素中等可能地选一个元素&＃xff0c;与第 i 个元素交换。这种算法的错误可以如下证明&＃xff1a;对于一个长度为

的数组&＃xff0c;算法创造了

个等可能的基本事件&＃xff0c;这些事件对应于

种排列顺序。在非平凡情况下&＃xff0c;

不能被

整除&＃xff0c;所以各种排列顺序不可能等概率。

　　另一种错误的洗牌算法是 &＃64;Lucas HC 在这篇答案中指出的&＃xff1a;

Javascript 中数组自带的 sort 方法允许提供一个比较器&＃xff0c;其返回值的正负号代表两个元素的大小关系。在上面的代码中&＃xff0c;比较器返回的是 -0.5 到 0.5 之间的一个随机数&＃xff0c;也就是说每次比较的结果是随机且均匀的。但是&＃xff0c;基于随机比较的整个洗牌算法是不均匀的&＃xff1a;它的各种运行结果的概率都形如

&＃xff08;

为算法执行过程中的比较次数&＃xff09;&＃xff0c;而我们希望每种顺序的概率都是

&＃xff0c;在非平凡情况下&＃xff0c;后者不能由前者通过加法组合出来。&＃64;Lucas HC 指出&＃xff0c;当 sort 函数采用

　　如果你不熟悉编程&＃xff0c;我在此可以用大白话把 &＃64;Lucas HC 答案中错误算法的流程叙述一下&＃xff1a;设想有

个人依次来到一个队伍。每个人到来之后&＃xff0c;都想向前插队&＃xff0c;但前面每一个人放他过去的概率都是 1/2。最终队伍的状态就是洗牌结果。

　　我对这种算法的结果分布感到好奇&＃xff0c;于是计算了一下洗牌后各个元素落在各个位置的概率。用

表示总共有

个元素时&＃xff0c;第

个元素洗牌后落在第

个位置的概率&＃xff08;这里

的范围为 1 到

&＃xff09;。给定

&＃xff0c;各个

可以排成一个

阶矩阵&＃xff0c;记作

。这些矩阵可以用递推法计算&＃xff1a;

• 当
  时&＃xff0c;显然有
  。
• 当
  时&＃xff1a;
  • 首先考虑
    号元素。它有 1/2 的概率停在
    号位置&＃xff0c;有 1/4 的概率向前插一位停在
    号位置&＃xff0c;有 1/8 的概率向前插两位停在
    号位置 …… 一般地&＃xff0c;若
    号元素要停在
    号位置&＃xff08;
    &＃xff09;&＃xff0c;它就需要越过
    个元素&＃xff0c;并被
    号位置的元素挡住&＃xff0c;故概率为
    &＃xff0c;但停在 1 号位置的概率跟停在 2 号位置的概率相同&＃xff0c;都是
    。
  • 然后考虑
    &＃xff08;
    &＃xff09;号元素。它落在
    号位置有两种可能&＃xff1a;
    • 在前
      个元素洗牌完毕后&＃xff0c;
      号元素就已经落在
      号位置&＃xff0c;并且
      号元素没能越过它。这种情况的概率为
      &＃xff1b;
    • 在前
      个元素洗牌完毕后&＃xff0c;
      号元素落在
      号位置&＃xff0c;但
      号元素越过了它&＃xff0c;使它后移到了
      号位置。这种情况的概率为
      。
    • 于是有递推式&＃xff1a;
      。

　　上面的递推式用 Matlab 可以如下计算。计算过程使用了大量的矩阵运算&＃xff0c;看不懂不必强求。

　　上述代码算出的

如下。左图直接显示了整个矩阵&＃xff0c;颜色深浅表示概率大小&＃xff1b;右图则是画出了矩阵的每一行&＃xff0c;即每个元素最终位置的分布。

&＃64;Lucas HC 的结论&＃xff0c;就是说

的对角线元素会显著大于

。上图说明&＃xff0c;

的对角线元素都大于 0.2&＃xff0c;印证了这个结论。从图中还能看出另外几个事实&＃xff1a;

• 是对称的&＃xff0c;即
  号元素落在
  号位置的概率&＃xff0c;等于
  号元素落在
  号位置的概率&＃xff1b;
• 的前两行、前两列分别相等&＃xff0c;也就是说 1、2 号元素的地位相同&＃xff0c;1、2 号位置的地位也相同。

　　把

增大&＃xff0c;可以发现一些更有趣的事情。例如&＃xff0c;下图画出的是

&＃xff1a;

从左图可以看到&＃xff0c;矩阵中元素沿垂直于对角线的方向迅速衰减&＃xff0c;所以「洗牌」后各个元素都倾向于留在初始位置或其附近。而右图则说明&＃xff0c;除了开头和结尾几个元素&＃xff0c;每个元素最终位置分布曲线的形状都几乎是一样的&＃xff0c;它们的最大值&＃xff08;即留在原位的概率&＃xff09;都比 0.2 大一点&＃xff0c;且这个值似乎与

无关&＃xff01;

　　在 Matlab 中执行 format long 命令&＃xff0c;可以让计算结果具有 15 位有效数字。用此方法可以观察到

的对角线中部元素趋向于一个常数

&＃xff0c;它约等于 0.220643036096533。尽管

的绝大多数对角元都只比常数

大一丁点儿&＃xff0c;不过如果要在矮子里面再挑矮子&＃xff0c;那么最小的对角元大约出现在第

个位置。当

时&＃xff0c;15 位有效数字就已经无法区分

与常数

了。

　　网上并没有找到对常数

的讨论&＃xff0c;所以我就暂且给它起个名字&＃xff0c;叫「乱排常数」。这个常数是有理数还是无理数呢&＃xff1f;它有什么样的数学表达式&＃xff1f;这些有趣的问题&＃xff0c;就留到下一篇中讨论。