谁说懂数学的不懂扑克牌。

洗牌需要洗七次之说源于D Aldous, P Diaconis (1986) Shuffling cards and stopping times. [1] 这篇文章研究的是 Riffle Shuffle （鸽尾式洗牌法）（如 Picture 1.）

文章得到的结论是一副 52 张的牌堆通过 7 次数学模拟的 Riffle Shuffle 后，就可以认为已经达到了数学意义上的随机化。

洗牌问题是一个典型的数学问题，那么讨论数学问题的时候，我们第一步要做的就是定义。

为什么要定义？要知道，数学的优势就是把生活中习以平常的知识抽象为纯粹理性的概念，然后以纯粹理性的逻辑判断一步一步地推导出逻辑自洽的结果。明确的定义决定着一个问题是否能很好地抽象为可操作的数学概念。所以经常有人说，定义好了问题，问题就解决了一半。

这里就有一点小小的优越感，我们做数学的在一起讨论的时候，都得先明确在讨论什么问题，绝不会因为问题定义的不清晰而出现鸡同鸭讲的情况。

回到洗牌问题，我们要做的把这个生活上看起来很容易理解的『需要洗多少次牌才能将一叠扑克牌洗匀？』转化为数学上可以操作的准确定义。

大家也可以从以下的提出的一些问题看出来，我们为什么要这么慎重地去定义一个数学问题。

• 『什么是洗匀』：『洗匀』什么意思呢？一个『012』这 3 张牌的牌堆，如果经过几次洗牌后，达到了『210』这种状态，大家会觉得没有『洗匀』。而如果达到了『021』这种状态，大家是不是会觉得稍微『洗匀』些了？可是『210』『021』之间有什么区别？所以，『洗匀』不应该跟具体结果相关联。一次实际操作的最终结果只是出现的一种可能性。
• 『什么洗牌方法』：这个也很重要。洗牌的方法千千万，逮住一个就说所有洗牌都只需要花 7 次简直就是耍流氓。研究的是那种洗牌方法，就需要明确确定
• 『可以认为已经洗匀』：『洗匀』定义好之后，我们通过研究发现所有洗牌方法要完全达到『洗匀』状态需要花非常长的时间，而实际上生活中是不需要这么精确的『洗匀』的。所以我们也需要定义什么时候『可以认为已经洗匀』。

让我们再来看一个最简单例子。

一堆只有 2 张牌（A、B）的牌堆，它仅有 2 种排列方式（AB、BA）。

这堆牌怎样才是随机了的呢？按照常识，这堆牌的随机化就是指这 2 种排列方式都以相同的概率出现。

现在对这个牌堆，我们规定这样一种洗牌方式：

• 抛一枚硬币，若硬币字面朝上，则保持原状态；
• 若硬币字面朝下，则调换两张牌的位置。

那么，我们马上就可以知道不管初始状态如何，只要按这一方式洗过一次牌后，就可以准确地预期它的 2 种排列方式（AB、BA）出现的概率都将是 1/2。

也就是说，在这个模型里，只要洗 1 次牌，就将达到洗匀状态。

现在我们可以来看看这个简单的例子里是怎么定义的：

• 『什么是洗匀』：只有两张牌的牌堆，『洗匀』看起来十分好定义，按照上面的处理方式也特别容易理解。这样我们就可以抽象出『洗匀』的概念，『洗匀』就是指经过若干次『洗牌操作』后每一种排列方式预期的出现概率相同。注意，这里强调的是预期的出现概率，而不是某次洗牌的洗牌结果。也就是说，我们早在洗牌之前就可以算出按某种确定的洗牌操作经过若干次后每种排列方式出现的概率。我们只关心每种排列方式出现的概率相不相同，而不关心最终某一次洗牌结果是出现了那种排列方式。这样子，即使最终洗牌结果是出现了『210』，还是『012』，我们都是不关心的，因为某一次特殊的洗牌结果是没有意义的。我们会说，只要最终『012』『210』『021』等所有可能的排列方式出现的概率都相同，那我们就认为牌堆在那个时候已经达到了洗匀状态。
• 『什么洗牌方法』：上述例子中的洗牌方法是个很好的定义，它的意义确定，结果可预测，随机的概率确定，操作确定，不会引起任何的误解。我们在之后处理洗牌问题时，也应该这样严格确定洗牌的方式，将生活中概念可能会非常广的『洗牌』界定为非常准确的『洗牌方法』。
• 『可以认为已经洗匀』：这个例子牌数太少，可能看不出其必要性。对于 52 张牌，其排列方式有种，达到完全的每种排列方式出现的概率完全相同的完全『洗匀』状态，需要经过非常长的时间。而这个『完全洗匀状态』不论是在生活中，还是研究中，都是没有必要的。所以我们还是需要定义什么时候『可以认为已经洗匀』。

经过上面这么多准备，我们终于可以给出明确的定义了：

一堆每张牌都互不一样的牌堆，规定某一种具有随机性的洗牌法。那么在不考虑初始状态的情况下，经过重复进行该洗牌法若干次后，牌堆的每种排列出现的概率都相同或接近相同。问：对某一种确定的『洗牌法』，『若干次』是多少次？

这里稍微再解释下上面定义中加黑的部分。

『每张牌都互不一样』是为了规范我们所研究的问题。对有重复牌的牌堆，比如说同时洗两幅牌，每一张牌都与另一张牌一样。这样的洗牌问题与无重复牌堆的洗牌问题是不一样的，这方面的研究成果也有很多。

『不考虑初始状态』是要将初始状态的影响去除掉，一堆看起来非常无序的牌堆和一堆看起来非常有序的牌堆处理起来应该是一样的。当然，从数学上来看，『看起来非常无序』和『看起来非常有序』本身就是没有区别的。

『相同或接近相同』，其实这里『接近相同』是什么意思需要更严格一些的定义，但因为牵扯到概率分布的全变差距离等数学概念，这里就不必傲了。

剩下的就是建立洗牌模型，然后分析模型，解决问题了。

为了处理这些问题，我们可以构建洗牌模型模拟生活中的洗牌，同时研究得到结论。但模型与真实生活中洗牌几乎必然会有所区别，我们只能尽可能地提高建模水平，更加准确地模拟现实生活中的洗牌了。

目前已经处理解决的洗牌模型及结论如下：

// 一些洗牌法没有标准的翻译，在此我也就不一一翻译了。结论附在每一行的最后，指的是其达到洗匀所花的时间与牌数的阶关系。通过把实际的数据

代入，可以看到收敛时间的大概量级。

1. Top-to-Random Shuffle ：抽出顶部的牌，随机插入牌堆中任一位置。
2. Random-Transposition ：随机抽取两张牌，交换他们。
3. Random-Adjacent-Transposition ：随机抽取两张相邻的牌，交换他们。
4. Riffle Shuffle （鸽尾式洗牌法）： 将牌分成两叠，交错放下。（见 Picture. 1。）
5. Overhand Shuffle （过手洗牌法） & Hindu Shuffle （印度洗牌法）：即不断地从牌堆中抽出一叠，放置到整个牌堆上方。（见 Picture. 2, Picture. 3）// 两者只是手法不同，对牌的顺序的影响是一样的。
6. Rudvalis Shuffle, Thorp Shuffle, L-reversal chain 等其他洗牌法，此处就不详细说明了。

Overhand Shuffle (Picture. 2)

Hindu Shuffle (Picture. 3)

可以看到，我们的 Riffle Shuffle （鸽尾式洗牌法）是速度最快的。也正是从 Riffle Shuffle 这里，我们得到了洗牌七次就能达到『可以认为已经洗匀』的状态的结论。

在这里暂时就只粗略介绍一下大家争论最多的 Riffle Shuffle 的研究过程的前几步。

Riffle Shuffle 的研究成果可见 [1]。数学上定义 Riffle Shuffle 如下：

1. 按二项分布的概率将牌堆分成两堆；
2. 依次将两堆牌放下，而每次放下哪一堆的牌的概率与当时该堆牌中剩余的牌数成正比。

第一步模拟实际 Riffle Shuffle 过程中分成左右两堆的动作。第二步模拟 Riffle Shuffle 放牌的动作。

是不是与生活中的 Riffle Shuffle （鸽尾式洗牌法）有一定的区别？

但这些区别是可以容忍的，因为我们必须给 Riffle Shuffle 这些操作的数学定义。例如生活中，可以简单地说随机把牌切成两堆；但我们要研究的时候，就必须确定是以什么概率来切的，每种切法的具体概率是多少。而放牌时，实际生活中是用手指自然控制，让其依次落下，但在我们要实际处理时，就需要明确每次掉落的准确概率。

实际上，上述 Riffle Shuffle 的数学模型是一个非常好的模型，其各部分准确、自然，而且难得地跟实际生活经验非常切合。

当然仅仅是建立这样的模型，仍然不太好处理，所以我们换个思路，来处理 Riffle Shuffle 的逆过程。

// 可以证明，随机游动逆过程的混合时间与原过程的混合时间相同，即它的逆向洗牌过程和其本身，达到洗匀状态花的时间是一样的。

定义 Riffle Shuffle 的逆过程（Inverse Riffle Shuffle）如下：

1. 随机给每张牌标上『0、1』记号；
2. 将所有标记为『0』的牌放到标记为『1』的牌的上方，并保持同种标记的牌的排序不变。

// 可以证明，该过程的确是原过程的逆过程。

Picture. 4 展示了连续两次的 Inverse Riffle Shuffle.

对于 Inverse Riffle Shuffle ，数学上就容易处理得多了。

二项分布变成了布尔数标记，每一步都会发生概率变化的的随机放下变成直接按顺序排列。这些在数学上都是极大的简化。

// 大家可以稍微演算一下，为什么这种洗牌方式是原来的 Riffle Shuffle 的逆过程，很有意思。

做了这么多准备后，其实问题已经很简单了。接着需要做的就是求其收敛时间的上下限，只需要一些基础的随机过程和混合时间的知识，就能够完成相应的计算了，这里也就不详细展开了。

研究结果是 Riffle Shuffle 的混合时间的量级为

。同时对 52 张牌的牌堆，我们可以精确计算，得到结论如 Table. 1.

如上表所示，经过 7 次洗牌后，牌堆与洗匀之间的全变差距离已经达到 0.334，可以认为已达到洗匀状态。

最后，洗牌问题中还可能会出现 Cutoff 现象（截断现象）。

Cutoff 现象如 Picture. 5 所示。在临界点前，与均匀分布之间的距离（全变差距离）缓慢减小，即洗牌效果不明显，牌堆与洗匀状态相隔较远；经过临界点后与均匀分布之间的距离（全变差距离）迅速减小，能够迅速达到均匀状态。

Cutoff 现象在很多随机过程中都会出现。而针对洗牌问题的 Cutoff 现象，近年来已经得到了一些结论。像上表 Table. 1 中所示的，其实 Riffle Shuffle 就已经出现了 cutoff 现象，在洗牌次数达到 6-8 次时，全变差距离迅速从 0.924 降到 0.167，变化非常快。所以 cutoff 现象对洗多少次的问题也会很大的影响，发生 cutoff 现象的临界时间在实际问题讨论中可能也更有意义。

末了，闲扯两句洗牌问题的数学野史。早在 1986 年就解决了 Riffle Shuffle 模型混合时间的的数学家之一 Persi Diaconis 本身就是一个职业魔术师。而他们的研究成果也通过 New York Times. In Shuffling Cards, 7 Is Winning Number [6] 难得地走出了数学的殿堂，走进了大众的视野之中。

1. David Aldous and Persi Diaconis, Shu?ing cards and stopping times, The American Mathematical Monthly 93 (1986), no. 5, 333–348. http://statistics.stanford.edu/~ckirby/techreports/NSF/EFS%20NSF%20231.pdf
2. Picture. 1, 2, 3. Wikihow. 3 Ways to Shuffle a Deck of Playing Cards
3. Picture. 4. 尹一通, 随机算法 (Fall 2011)/Card Shuffling
4. Table. 1. 尹一通, 随机算法 (Fall 2011)/Card Shuffling
5. Picture. 5. David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer, Markov chains and mixing times, Amer Mathematical Society, 2009. http://scf.berkeley.edu/~aldous/260-FMIE/Levin-Peres-Wilmer.pdf
6. New York Times. Gina Kolata. January 09, 1990. http://www.nytimes.com/1990/01/09/science/in-shuffling-cards-7-is-winning-number.html