扑克牌洗牌 玩扑克洗牌洗几次？

关注微信:多多数学每天都有更多有趣的数学文章

打牌时，洗牌必须是一项必要的技能。反洗牌是一种常用的洗牌方法。主要过程是把牌分成两半，用拇指把牌扣紧，再把牌弯过来。拇指逐渐松开向内的扑克牌，使两叠牌交错叠放在一起(注1)。

今天我们要问一个数学问题:一副牌要用二分法洗几次？

这个问题的答案分为两部分:第一部分是给出切牌洗牌的数学描述，第二部分是给出“洗匀”的数学定义。为了讨论方便，我们假设一副牌中有n张牌，当我们将结果应用于现实时，n=54。

我们先把二分法洗牌的过程数学化。

假设我们把一副扑克牌面朝下。

二分法洗牌有两个步骤:

第一步是把牌分成两堆，第二步是以某种方式把两堆混在一起。

现在第一步的两叠牌叫“上叠”和“下叠”，上叠牌标为1，下叠牌标为0。

假设栈中有k张牌，即k张牌标为1，(n-k)张牌标为0。这样，当我们完成洗牌时，我们会从上到下观察牌堆，我们会看到一个长度为n的0和1的序列，其中只有k个1和(n-k)个0。

我们可以把上述过程颠倒过来，称之为“反向洗牌”。

反向洗牌对应于两个相反顺序的步骤:

第一步，用0或1标记牌堆中的每张牌；

第二步，从牌堆中取出标有1的牌，按原来的相对顺序叠放在标有0的牌上面。

所以每一种洗牌方法(由牌堆数量和两堆牌如何混合决定)对应一个长度为n的0和1的序列，一一对应。

下面我们给出一个理想化的二分法洗牌法，其中随机生成长度为n的对应的0和1序列。也就是说，在反向洗牌的第一步，对于牌堆中的每张牌，我们用1/2的概率标记为1，用1/2的概率标记为0。

这种洗牌方法也被称为GSR(吉尔伯特-香农-里德)洗牌方法。一个GSR洗牌是一种特殊的洗牌方法。

第一步，堆叠中的牌数为k的概率为c (n，k)/2 n(注2)，这只是随机分配0和1给n个数的概率，而且只有k个1和(n-k)个0。

根据概率中的中心极限定理，k很可能服从N(n/2，N)，即均值为n/2，方差为根数N的正态分布；也可以说是卡几乎均匀的分成两堆。

混合的第二步，我们从牌堆的n个位置中随机选取k个位置，然后把牌堆上的牌按原来的顺序放入这k个位置；然后，把下一叠的牌保持原来的顺序，放在剩下的(n-k)位置。可以说GSR洗牌不仅很好的模拟了实际情况，而且数学上非常简单。

进一步，我们可以考虑m连续GSR洗牌的逆过程。

我们把m GSR洗牌前的扑克牌顺序称为“初始顺序”，m GSR洗牌后的顺序称为“最终顺序”。那么m连续GSR洗牌的逆过程就是从一个最终的牌序恢复初始牌序的过程。

那么m GSR洗牌的反向过程是怎样的呢？

经过简单的思考，我们发现需要给每张牌随机分配一个长度为m的0和1的数组。数组的第一个0或1表示第一次洗牌时牌是来自上层还是下层，第二个0或1表示第二次洗牌时牌是来自上层还是下层，以此类推。

举个例子吧。我们假设有五张牌，两次GSR洗牌后得到的最终牌序是DBACE。现在，我们为每张卡分配一个长度为2的0和1数组，如下所示

D: (0，1)

B: (1，0)

答:(1，1)

C: (1，0)

E: (0，0)

当然，如果指定的0和1数组不同，恢复的初始卡顺序也不同。我们先来看看上面0和1数组的初始卡顺序是怎样的。

在第一次反向洗牌中，我们需要看这五个数组的第二个组成部分，它指示在第一次反向洗牌(对应于第二次洗牌)中，每张牌是被分成上层牌堆还是下层牌堆。因为AD的第二个分量是1，BCE的第二个分量是0，所以我们在第一次反向洗牌后得到DABCE。

在第二次反向洗牌中，我们需要查看数组的第一个组件。因为ABC的第一个分量是1，DE的第一个分量是0，所以我们应该把ABC移到前面，得到ABCDE。(当然，这个例子是设计出来的，不然得到ABCDE也不会这么聪明。)

当我们仔细思考这个过程的时候，我们发现m反向洗牌可以一次性完成！

如果我们通过二进制对应一个长度为m的0 ~ (2 m-1)整数，如下

D: (0，1)-& gt；0*2 + 1 = 1

B: (1，0)-& gt；1*2 + 0 = 2

答:(1，1)->；1*2 + 1 = 3

C: (1，0)-& gt；1*2 + 0 = 2

E: (0，0)-& gt；0*2 + 0 = 0

那么我们可以一步完成m次反向洗牌:首先把最大整数3对应的A叫到前面，然后整数2对应的BC紧接着A后面(此时同一个整数2对应有两个字母B和C，必须保持B和C在最终牌序DBACE中的相对顺序)，然后把整数1对应的D移到ABC后面，最后把0对应的字母E移到ABCD后面。瞧，我们又抓到ABCDE了！

一般来说，一次完成m个反向洗牌分为两步。

第一步，“指定数字”:每张卡随机分配一个从0到(2 m-1)的整数。

第二步，“重新排序”:按照每张卡片指定的数量大小，将所有卡片由大到小重新排序；如果多张卡被分配了相同的号码，原始订单必须保留在排列中。

值得指出的是，m次GSR洗牌和m次反向洗牌之间是一一对应的，也是与n张牌从0到(2 m-1)分配整数的不同方式一一对应的。根据乘法原理，指定整数有2 nm的方式，所以完成m GSR洗牌也有2 nm的方式。同时，这2 nm方式都是同样可能的，概率1/2 nm。另一方面，对于相同的初始牌序和最终牌序，也可能对应多种洗牌方法。

完美解决了第一个问题之后，就要搞清楚什么是“洗匀”。

先对这个问题有个感性的认识。

在一次完成m个反向洗牌的过程中，我们可以看到，当两个以上的牌被分配相同的整数时，它们在初始顺序和最终顺序中的相对顺序将完全相同。我们还看到，当m足够大时，赋给n张牌的n ^ 0 ~(2m-1)中的整数很可能互不相同，从而初始牌序和最终牌序完全无关。所以合理的洗牌次数m应该有一定的概率(比如25%)，可以让n张牌的指定整数完全不同。

数学上这样的生日问题和这个很像。假设一个班有N个人(比如N=30)，每个人的生日都是独立的。任何两个人的生日不一样的概率是多少？

我们可以这样思考这个问题。给n个人1，2，...，n。

第一个人的生日可以随意选择；为了避免第一个生日，第二个人的生日只能从剩余的364天中选择；第三个人的生日只能从剩余的363天中选择，以避免前两个人的生日...

最后根据乘法原理，用(1-1/365) (1-2/365)给出N个人所有生日都不一样的概率...(1-(n-1)/365)，n不太大时等于(1-1/365) n。

回到我们的洗牌问题。我们需要为n张卡片中的每一张指定一个从0到(2 m-1)的整数。那么所有指定的整数都不一样的概率是多少呢？这时,“生日”的数量是time；而n相当于卡片总数n..根据前面的公式，所有n个“生日”不相等的概率约等于(1-1/2 m) n。

根据微积分中的重要极限(1-1/x) x = 1/e，x→∞，我们知道为了使(1-1/2 m) n不是一个太小的数(比如在数量级意义上，我们可以认为0.01是一个比较小的数，0.1是一个比较大的数)，必须有2。这样，我们得到第一个估计:2m >；n，即m >: log_2 n .

n=54时，log_2(n)约为5.5。至少我们的感性认识给出了洗牌次数的正确数量级！

为了给数学中“洗涤均匀性”一个更准确的定义，我们引入了两个概率分布之间距离的概念。

对于两个概率p和q，对应的分布列表是(p1，p2，...，pN)和(q1，q2，...，qN)，所以我们将它们前面的(总变化)距离定义为d (p，q) = | P1-Q1 |+| p2-Q2 |+...+| pn-。

这如何适用于我们的洗牌？

首先，让我们总是假设我们把n张卡编号为1，2，3，...，n，初始卡顺序是1，2，...最终顺序由{1，2，...，n}到{1，2，...，n}:

对于编号为I的牌，经过m次GSR洗牌后，其位置成为h(i)牌。我们经常用同一个字母h来表示最后的订单。

我们知道N张卡有N=n！排序方式的一种。h显然是通过m次GSR洗牌的n种排序方法之一。实际上，H以一定的概率得到一个给定的排序方法，它实际上对应一个分布列表(p1，p2，...，pN)，表示H采取各种排名方式的概率。另一方面，我们可以考虑另一个通讯组列表(1/n！，1/n！,...，1/n！)，也就是说每种排序都有相同的1/n的概率！出现。

显然，我们可以将“洗涤均匀性”定义为两个概率分布p和q之间的距离d(p，q)足够小(这里，“足够小”可以理解为例如小于1/2)。

接下来，我们的问题转化为，对于给定的最终牌序H，从初始牌序1，2开始，...n，通过m次GSR洗牌，我们可以得到H作为最终牌序的概率(记录为p(h))。

由于m个GSR洗牌的2个nm洗牌模式具有1/2 nm的相等概率，我们只需要计算从1，2，...n .等价的，我们只需要计算多少个反向洗牌方法就可以得到1，2，...，n来自h。

现在我们用f(i)表示数字I牌，在反向洗牌的第一步，“指定数字”，0 ~ (2 m-1)中指定的整数。f可以看作{1，2，...，n}到{0，1，2，...，2 m-1}。

现在我们的问题是，对于给定的最终阶H，有多少个F可以把H变成1，2，...，n到m次反向洗牌？

让我们首先考虑如何通过两次反向洗牌从DBACE获得ABCDE。

为了得到ABCDE，显然我们需要f (a) >: = f(B)>;= f(C)>;= f(D)>;= f(E)，表示f是递减函数。

其次，因为A在最终顺序中B之后，f(A)不能等于f(B)，所以f(A)>:f(B)；同理，c在D之后，我们必须有f (c) >: f(D).可以验证，只要f满足f (a) >: f(B)>即可；= f(C)>;f(D)>;= f(E)，我们都可以通过两次反向洗牌从DBACE得到ABCDE。

现在把问题转化为求所有函数{1，2，3，4，5}到{0，1，2，3}的函数F(我们把A和1，B和2等化)，这样F就是一个减函数，当f(1)和f(2)，f(3)和F (3)实际上可以把F转化为一个严格减函数。

设g (1) = f (1)+2，g (2) = f (2)+2，g (3) = f (3)+1，g (4) = f (4)+1，g (5) = f (5)，那么g是由{

{0，1，2，3，4，5}的严格减函数，每一个这样的g都一一对应我们需要的f。显然，这样的函数g的个数与{0，1，2，3，4，5}中选取五个不等整数的方法相同，由组合数C(6，5)=6给出。

我们把上述情况推广到一般n阶和最终h阶，首先，f必须是递减函数。如果h (i) >: H(i+1)，也就是说标记为I的牌位于最终牌序列中标记为i+1的牌之后，那么f(i)必须严格大于f(i+1)，也就是f (I) >: f(i+1).

现在，我们把h对应的“逆序量”R=R(h)定义为所有满足h(I)>:h(I+1)的I的个数。那么满足条件的函数f的个数等于从{1，2，...，n}到{0，1，...，2 m-1+r}，此外，n个不同的整数选自{0，1，...，2 m-1+r}所以，有c (2 m+r，n) F..

所以得到最终卡单h的概率是

这里我们使用一个近似值:当x1，...，xk小，(1+x1)...(1+xk)等于1+x1+...+xk。

进一步，我们得到总变化距离为

上面求和公式的最后一项恰好是h等于来自n的概率的时候！当从所有可能的排序中随机选择时，对应的逆序数量与n/2之间的偏差的期望值。

进一步分析表明，R(h)几乎服从N(n/2，N)，即均值为n/2，方差为根数为N的正态分布，因此，逆序量与n/2的偏差期望约等于根数N，这样我们得到d(p，q)等于n (3/2)/2 m。

由n (3/2)/2 m : 3/2* log_2(n) +1定义.当n=54时，这个数约为9.6。

当然有句话叫洗牌洗牌七次只是一个粗略的数字，也可能叫顺利。不同的计算表明，洗牌少则5、6次，多则9、10次，就能把牌洗均匀。同时，我们的计算也表明，洗牌次数只取决于n的对数，也就是说，洗两副牌只需要比洗一副牌多一两次就够了！

注1:描述来自https://zh.wikipedia.org/wiki/%E6%B4%97%E7%89%8C维基百科

注2 :C(n，k) = n！/k！(n-k)！是组合数。

关注微信:多多数学每天都有更多有趣的数学文章