关于洗牌的研究（二）——你的扑克洗乱了吗？

写再前面：本系列作品由MathMagician独家首发，一共有七篇，从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万，是因为无论数学还是魔术，洗牌中的任何一个小点都够写几篇了。所以，本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍，包括洗牌分类，混乱度评价，过程建模，近似计算，以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后，会在数学和魔术上，都对“洗牌”这一现象有着更加深入的认识。

本篇是第二篇：你的扑克洗乱了吗？

在上一篇文章中，我们介绍了基本的洗牌分类，那这些洗牌是否真的洗乱了呢？

按照数学建模的思路，首先我们要定义混乱的数学概念，然后描述洗牌的过程，进而计算这个值（包括本篇在内的接下来三篇文章正解决这三个问题），以此来量化地表示洗乱程度，这应该是最初级的人工智能形态吧，告诉机器公式，让它算出准确的答案而防止人的主观偏好和经验不足。本篇我们来解决第一个问题：

如何定义混乱

显然，对于一个系统的混乱程度，应该用其所有关心状态（不关心的往往被合并考虑）的分布有关（这个分布我们对该系统的描述）。我们认为，一个系统服从的状态分布状态数量越多，每个状态的概率越平均，这个系统就越混乱，你想象一下在世界杯初选赛期间如果各个国家的球队水平相当或者未知的时候，你是不是越难以预测哪支球队夺冠？到了决赛，仅剩两支球队且你对他们的实力了如执掌，一支伤兵满营首次进入决赛，另一支则是全员健康的豪门，预测起冠军来会不会更简单呢？

针对这个问题，对于用概率分布描述的系统，我们定义熵：

H(X) = - E(log(f(x))) = - sum(f(x) *log(f(x)))

其数学本质是，平均来看，对每一种特定状态的信息量的大小。这里所谓信息量，计算上看，是概率值的对数标度I(X) = - log(f(x))，对数下方便求和；信息论上看，是理想状态下，最优传输该信息所用的比特数；直观上理解，就是对随机系统确定为某一状态的难易程度的度量，显然概率越小的越难得。

比如，你只喜欢一支球队，甚至买了它赢的彩票，它夺冠了，那这个信息量就可以来描述这件事情的理性惊喜程度或中奖难易度（呵呵，直接告诉我中奖概率岂不是更好理解，但是不够高大上啊），理性的人对发生概率越小的事越激动，如果你内心估计概率无误的话，那这个就是你的惊喜程度应该无误了；如果你对球队实力有所把握，但是没有什么喜好，纯粹看热闹，也不赌球，那么在知道哪支球队夺冠以前，你的受吸引程度或者比赛对你的精彩程度应该就是平均信息量，即熵，直到可能一只你认为冷门球队夺冠那么你很惊喜，热门夺冠则没有什么感觉了；

可惜人的感受远远比这复杂，这些数学公式的度量建建模就好，没必要较真啦~

于是，我们暂且用熵的概念，来描述一副扑克牌的混乱程度了。

这里我们至少有一点可以确定，即，对于样本空间给定的系统，当所有状态服从均匀分布的时候，熵达到最大值：

H(X)max = log|S|

（这个结论可以用lagrange multiplier或者Jenson inequality证明，这里省略，感兴趣可以参考https://www.cnblogs.com/dahu-daqing/p/8399032.html）

这一点与我们对扑克完全洗乱的直觉也是一致的。

故对于一副54张扑克牌来说，其熵的最大值为：

H(Deck) = log A(54, 54) = log(2.31 * 10 ^ 71) = 237.06

别小看这200多的熵，这个可是指数标度的，其值相当于的平均分布下的状态数的量级为71，这可不是一个小数目，因此，我们才有Perplexity = 2 ^ H(X)这种概念，来让你理解其中变化幅度之大。

那我们平常简单的洗牌几次到底洗乱了没有呢，不妨我们先针对最常用的Hindu Shuffle和Riffle Shuffle做一个估算，我们先假设：

假设在一次洗牌能够达到的样本空间内能够达到均匀分布，且累积洗牌后不会达到相同的空间。

注意这是个很强到根本在瞎说的假设，即使在这样的假设下，我们仍能说明一些问题，这是数学里的放缩法思想。

Hindu(overhand) Shuffle

由于reverse部分是一个确定性操作，不带来熵增，且使得每一个切牌位置都有意义。故其一次洗牌结果中变量空间大小等价为各排列数的和，也可看作在53个牌间位置上的cut与否的选择，即：

C(53, 0) + C(53, 1) + ... + C(53, 53) = 2 ^53 = 9.01 * 10 ^ 15

Riffle Shuffle

若考虑分开成两叠和随机洗牌的两个过程，那么可以看作所有分成两叠的数量方法的排列数之和即：

C(54, 0) + C(54, 1) + ... + C(54, 54) = 2 ^54 = 1.80 * 10 ^ 16

这两个数，是一次洗牌的perplexity的上限，取对数之后即熵的上限，而对于多次洗牌的最终结果来说，计算的是其边缘分布的熵，实际要远小于叠加的条件熵，即：

由此来看，对于Hindu shuffle和Riffle shuffle而言，要完全洗乱，其洗牌次数下界都至少是5次，即：

Ceiling(loga / logb) = 5

这样才能至少在样本空间上触及每一个点。至于真正的熵是不是可以达到，其实差距还远着呢。

所以，这两个方式洗一次牌都和总混乱度差距很大，而从解空间的大小上来看，这个结论很反直觉，Hindu Shuffle只比Riffle Shuffle差1倍的perplexity而已？但是我能明显感觉到前者混乱度低得多啊，且这个界和真实分布的差距到底有多少？如何才能进一步精确估计呢？

2.31 * 10 ^ 71这么庞大的样本空间下，哪怕是采样，能够保证每个样本至少采样一次都需要2.31 * 10 ^ 71次实验，这个开销应该是目前硅基的计算机所承受不了的。更别说去计算推导，或者以比较高的精度估计这个分布了。随着扑克牌张数成O(n!)复杂度的运算量，受不起。

这里就需要对每一种洗牌过程对应的离散随机过程进行精确的统计建模，才能进行更细粒度的分析。另外，这里比较特殊，因为虽然是离散空间，但由于是O(n!)级别的复杂度，根本无法直接计算，所以我们要从两个方面来考虑：

1. 无法直接计算熵，具体原因就是吃不消的指数级别的样本空间，而以上估算的假设又太强，有没有其他折衷的方案？

2. 除了熵，我们可不可以找到一些其他准则来度量基本洗乱的结果，而这个结果是比较容易计算的？

篇幅关系，这些内容我们将会在下面的《关于洗牌的研究（三）——洗牌过程建模》和《关于洗牌的研究（四）——洗牌混乱度计算》中予以详细阐述，你也可以先自己想下如何对Hindu Shuffle和Riffle Shuffle的随机过程以及Faro Shuffle的确定过程进行建模描述，进而才能更加细致地估算洗牌带来的熵来作为洗牌评价准则的具体方案，或者跳出熵的限定，有没有别的容易计算的方案。