打牌必须洗八次

2017 年 10 月 25 日 中科院物理所 antares

拿一副52张的扑克牌，切成两部分，然后将它们交错叠成一副（又称交错式洗牌法）。连续洗8次，会发生什么？

答案是这样的：如果你使用最严格的洗牌法，那么洗8次正好可以让这副牌恢复成没洗之前的排列。如果洗牌时带有随机性，那么8次正好是能让你洗匀这副牌的次数（注：一般其实说7次，不过根据对结论的解读说8次也可以）。

这个答案我以前就有所耳闻。出于好奇，我去搜索了这两个答案的证明法。作为一个数学系毕业之后很久没碰正经数学的人，我被这两个证明法、尤其是后一个的精妙打动了。所以，这期TIL对于数学恐惧的读者们来说可能会很无聊。话说回来，即使对证明不感兴趣，这两个结论本身也是很有趣的豆知识。

——警告：以下内容包含数学证明，不想看的朋友可以直接去下一条分割线后点赞了——

问题一：洗多少次牌能洗回最初的排列呢？

完美洗牌的要求是切牌时完全严格地切成每副26张的两部分（去掉大小王），然后将两部分完美交错地叠在一起。根据先叠哪一部份分为内外两种：如果洗牌前头尾两张仍然在头尾，称为外完美洗牌法。如果头尾两张被洗到了第二张和倒数第二张，称为内完美洗牌法。对于“8次恢复”来说，专指8次外完美洗牌法。如果把原始的52张牌编号成：

0 1 2 3 … 50 51

这样的形式，那么洗完一次以后会变成

0 26 1 27 … 25 51

这样的排列。

这个变换有没有简单的描述法呢？是有的。洗牌前0-25号牌的编号乘以2，就是洗牌后的位置。而26-51号洗牌后的位置，则需要乘以2之后减去51。换言之，如果用f(x)代表x号牌洗牌后的位置，那么

f(x)=(2*x)%51 <-------%代表除以51之后取余数。

用公式表示以后洗两次牌以后x的公式也可以算出来了：

f(f(x))=(4*x)%51

以此类推，洗8次牌就会变成

f(f(f(f(f(f(f(f(x))))))))=(256*x) %51

由于256除以51的余数正好是1，所以上面这个式子正好等于x。换言之，洗8次牌之后，x号牌还是在x号的位置，回到了起点。

也正是因为此，这个“8次洗回去”的做法只对52张牌成立。如果使用54张牌的一副，就需要52次才能洗回去了，是不是感觉差距巨大……当然，如果允许使用内洗牌，还是可以用更少的次数来把54张牌的一副洗回去的。

问题二：洗多少次牌能洗匀呢？

这其实取决于我们对“洗牌法”的描述和对“洗匀”的定义。洗牌虽然是个直观的过程，精确定义却很难。对洗牌比较准确的描述是1955年提出的Gilbert-Shannon-Reeds模型——对，就是那个著名的香农。这个模型可以描述如下：

——对张数为n的一副牌，首先切上面的j张分给左手，剩下的分给右手，其中j由0到n的二项分布随机决定。之后每次数左手和右手的牌。如果左手有a张，右手有b张，那么以a/(a+b)的概率将左手这堆最下面的牌放到洗后牌堆顶上，否则将右手这堆最下面的牌放到洗后牌堆顶上。重复到双手无牌为止。

定义完了洗牌，我们来考虑“洗匀”。52张牌洗完以后共有52!这么多排列方式。如果每种排列的出现概率都是1/52!，那么肯定是洗匀了，但是实际上肯定会有误差。误差越小，“洗匀程度”越高。数学上常用的一种描述两个概率分布之间差距的方式叫全变差，就是把对应的每个事件的概率差绝对值加起来除以2，得到的结果越小，说明概率分布越接近。如果完全没洗，那么全变差会非常接近1。不过，如果你不喜欢全变差，想用另外一种方法计算误差的话也没关系，因为洗完后出现某种排列的概率是可以精确算出来的。

怎么算呢？事实上，洗m次牌以后的洗牌法也是可以用类似的方法描述出来的。我们考虑“切成2堆洗牌”的一种推广，“切成M堆洗牌”。这个过程可以用几种不同的方法来描述，并且都是等价的：换言之，你问洗完以后得到某个排列的概率是多少，那么这几种方法得到的概率相同。

一、步骤描述：对n张的一副牌，选择M个和为n的随机变量j_1... j_M，符合多项式分布。按照顺序将牌切成j_1...j_M张的堆。之后每次随机选其中一堆的底牌放下，选某堆的概率正比于这堆的张数。直到所有堆都无牌为止。

二、最大熵描述：考虑切成M堆牌和将这M堆叠成一堆牌所构成的所有事件集合：也就是说，切牌方式不同而叠牌后结果相同的情况视为不同的事件。等可能地选择其中一个事件。

最大熵描述的直观表示：首先对洗后牌堆的n张牌分别随机决定它是来自1-M的哪堆，并按照数目和顺序将原始牌堆切成M堆。将这M堆的牌按顺序放到洗后牌堆里。

三、几何描述：以0到1之间的均匀分布独立取n个数，并将它们按照从小到大顺序排列成x_1... x_n。令y_i=M*x_i除以1的余数。如果y_i在所有的y里面是第j小的，那么将第i张牌放到洗后牌堆的第j张去。

论文证明了这三种描述是等价的。并且根据几何描述，“切成M_1堆洗牌”后再“切成M_2堆洗牌”等价于“切成M_1*M_2堆洗牌”。因此，“切成2堆洗牌”重复n次就等价于“切成M=2^m堆洗牌”。而计算洗成某种排列的概率需要利用最大熵描述：既然所有事件的概率一致，那么洗成某种特定排列的概率正比于能产生这种排列的切牌法的数目。切牌法是有限制的：比如洗牌之前是1-52按顺序排列，如果洗完的牌是9在8前面，那么8和9必然在切牌的时候被分在了两堆里。如果洗完的排列有r-1个逆序，就自然地把牌“切断”成了r堆。将n张牌分成M堆（可能有空）并且逆序处至少有一个分割的方式共有C(M+n-r, n)种，而这除以总事件数M^n就是需要的概率。

由这里开始，就可以在n=52的情况下计算洗牌次数不同的时候全变差是多少了。洗5次以下的时候全变差接近1，而洗6，7，8次牌时全变差分别是0.614, 0.334和0.167。洗8次牌就可以认为是洗匀了。当n趋近于无穷的时候，需要的洗牌次数接近1.5*log_2(n)。

从精确描述洗牌方式，到找到洗牌方式的等价表述，再到计算概率。整个证明一气呵成神乎其技，令人不禁拍案叫绝。

———数学证明结束的分割线———

当然，实际打牌的时候，并不需要整副牌的排列重新分布得那么均匀。而完美洗牌反而是一种会被各种魔术师和赌博漫画使用的魔术手法。所以，如果有人坚持要在打牌前洗8次，那真的就要小心了。

PS：保证均匀的洗牌法是这样的：先从52张牌里面随机选一张放到洗后牌堆顶上，再从剩下的51张里面随机选一张放去，以此类推直到所有牌放完为止。如果能保证每次选牌的时候是完全随机的，那么可以保证最后出现任何排列的概率都一样。不过除了计算机以外，应该不会有人真的会这么做吧……

原文链接：

http://projecteuclid.org/euclid.aoap/1177005705

编辑：Aprilis

近期热门文章Top10

↓ 点击标题即可查看 ↓

1. 听说香蕉和枣一起吃会看到人生的走马灯？实验揭秘最最最恶心的吃法配方

2. 看 10 米女子跳台能乐一天：或许这就是物理大佬吧