要洗多少次牌才能把牌彻底洗开？ - 生活 - 知乎

要洗多少次牌才能把牌彻底洗开？ - 生活 - 知乎

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

洗牌需要洗七次之说源于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 等其他洗牌法，此处就不详细说明了。

Read full article from 要洗多少次牌才能把牌彻底洗开？ - 生活 - 知乎