关于洗牌的研究（四）——洗牌混乱度计算
关于洗牌的研究（四）——洗牌混乱度计算
写再前面：本系列作品由MathMagician独家首发，一共有七篇，从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万，是因为无论数学还是魔术，洗牌中的任何一个小点都够写几篇了。所以，本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍，包括洗牌分类，混乱度评价，过程建模，近似计算，以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后，会在数学和魔术上，都对“洗牌”这一现象有着更加深入的认识。
历史文章请戳：
本篇是第四篇：洗牌混乱度计算
对于扑克牌是否洗乱的问题，我们建模了评价指标和函数——熵，构建了各种洗牌方式的随即过程模型，终于到最后一步，如何计算这个值？如果无法精确计算，怎样运用数学工具来近似解决？
下面的分析都以相对较复杂的Riffle Shuffle为例，这是一条不断试错又不断有收获的艰难旅程。
方案一：精确计算每一次Riffle Shuffle带来的精确熵，仍假设熵可以独立累加
按照上一篇文章的估算思路，我们把多次洗牌的熵增放大到独立相加的地步，可估算的每一步的熵增变成了57.05bit，但是对于237.06bit的总熵，还是免不了至少5次的下限，因此，这种放缩方法还是太狠，也与真实情况相去甚远，并无法评估。其具体计算公式如下：
方案二：求取解析表达式
近似仍然失效以后我们想看能否回到解析的方案，经过思考调研，有以下几点结论：
1. 这个离散时间离散变量的随机过程是马尔可夫链，其无后效性在整个链条上完美满足；
2. 状态转移矩阵维度是A(54, 54) ^2。根据对称群知识，该矩阵是是稀疏的，仅有A(54) * 2 ^ 54个元素有非0值，而且不同的元素综述只有A(54, 54)个，无奈这仍然是个海量，并不好直接计算；
3. 我们假设条链必然收敛，故除了1为最大特征值以外如果求得求取第二大特征值，那么该值大小是收敛快慢的唯一因素，但是面对这么大规模的矩阵特征值，无能为力；
4. 这个矩阵不是个对称矩阵，根据对称群，对于symmetric group S(n)中的元素A，其变换到B所需的操作为C，则A * C = B，C= A ^ -1 * B，则B * C ^ - 1 = A，故矩阵上的对称元素互为逆排列，并不相等；
虽然有这些结论，但仍然绕不开指数级别的运算量而很难求出解析式，故打住，思考新的方案。
方案三：分布的近似表示后再计算熵
上篇文章已经提到，我们无法直接根据这个随机过程的规律去计算熵的值，因此必须做近似计算，一方面我们没有这个随机过程的解析式，故采用模拟方式得到大量样本来估计是比较好的思路，但这就必须把变量空间降低到样本量足够的程度，故有两个基本的思路：
1. 变分法近似
在统计学习中，经常遇到后验分布维度高而难以估计的问题。而前辈给我们提供的思路一是Gibbs采样得到估计解，另一个就是变分法。前者是以条件分布样本近似联合分布，当前场景下不具备方便求取条件分布的条件；另一个则是降低变量间的关联度使得问题简化，而这种做法确实会在分布形式上有偏，却也是在复杂度和效果上一个不坏的折中。变分法的基本假设是：
这样本来无法计算的排列空间，维度很高且互相强相关而不独立，此时像变分法那样，假设各个维度是独立的，那么只需要考察相对容易追踪地每个位置牌点数的边缘分布就可以了（反过来也可以计算牌点的位置分布，二者等价）。于是样本空间变小到通过采样就可以精确计算此时的熵，问题就得到解决了。一般地，这个量应该对任意位置的熵都恒定为logN的时候，应该就可以视作“基本洗乱”了。因为独立变量的联合熵为各个变量熵之和，此时也可得估计的总熵，但数值并没有什么意义，这个结果与真实值想去甚远，因为扑克牌的位置是及其互相相关的。
我们对Riffle Shuffle做了如下实验，看到对一副54张的牌，其每个位置的牌的值（索引）分布熵对增加的洗牌次数变化如图：
（这些实验都是模拟实验，能成立的前提是样本量相对于分类分布的样本空间足够大，实验效果才具有可信度。以下实验的模拟次数都是100k次。）
图2 单位置熵随洗牌次数变化图
可以看到，大约8次左右，每个位置的熵就接近相等都为每张牌在此位置选择的均匀分布熵了。我们取这个最大差的阈值为0.01，更直观地展示了这一结果：
图3 最大熵差随洗牌次数增加的变化图
这个结论也和数学魔术大师Perci Diaconis的分析结果相当，他论文中的结果是7次，但这并没有什么可比性，因为这是完全不同的准则下的结论。
当然这里用的边缘分布是一阶的，为了更高的精度和逼近真实熵值，我们可以提高阶次（如HMM，CRF模型的阶次选取，是数据量和模型参数量的折中），即任意m个位置组合的牌点分布或者任意m个牌点组合的位置分布，实践表明，当m > 1时，需要准确估计的样本量也是阶乘级别的上升，且仍然和精确值有不小的差距，故从相对大小考察来看，一阶的分析是最经济划算的。
2. 我们可以用“伪数学归纳”的想法，计算张数较少时候的规律，进而用函数拟合出54张的规律。
图4 不同张数随洗牌次数增加熵的采样估计值
而经过试验方案2在Riffle Shuffle中n = 12时候所需的样本量就指数爆炸到无法计算了，这样就难以收集到足够的样本点来做靠谱的近似推断，当然也可以像方案二那样直接去推算第二特征值大小随n的变化规律，但是仍然难以得到足够的可计算的样本点，因此本方案暂不可行。
这些方案中，只有方案三中变分法的思路求得了在计算熵可行，理论上可靠的方案，但是其他的思考也是极具价值的，让我们对这些思路的本质有了更清晰的认识，下次说不定就能用上了。正如爱迪生所说，他发明灯泡过程中最大的收获是发现了上千种不适合的材料。
本篇仅给出最具代表性的Riffle Shuffle的边缘熵分析结果，Hindu Shuffle的暂时留给同学们自行完成，可以完全参照上一篇的洗牌模型以及本篇近似计算熵的思路来。
以上分析是我拿到这个问题的建模和求解思路。其中又一个问题是，我用熵来度量混乱度虽然看起来完美无缺，但是实际的混乱并没有这么高的要求，其度量的序没有问题，但却不是一个好的测度。比如可能熵不那么大，甚至远小于最大值，但是仍然满足我们的混乱需求。我们不妨看看前辈的做法。
Perci Diaconis的混乱定义和计算方案
好在关于Riffle Shuffle到底要洗多少次才乱的问题定义和计算早就有先驱Perci Diaconis分析过，最早也是他提出来，Riffle Shuffle洗牌需要7次左右才能基本混乱，而他这里的混乱度的描述为：
图5 Perci Diaconis定义的洗牌混乱度
其意思是去度量经过t次洗牌以后，其分布于均匀分布U的距离||Q ^ k - U||，来表明其均匀程度，即对于所有排列Sn的子集A中，其在各个可能排列上的差的和的一半的最大值。1 / 2的系数仅仅用来限定距离在[0, 1]，而大体意思就是两个分布各个元素概率差的绝对值之和。显然，完全不洗牌时，差距为|1 - 1 / n!|，而完全洗成了均匀分布时候，差距就为0了，这个值看起来至少才方向上是可用的。并且，如果度量的是和均匀分布的距离，那么其值约莫等于最大的若干序列的概率的累积分布的大小，由此可窥探该值的具体意义。
当然了，数学上的定义有时候是为了好解决才这么做的，而这个式子的形式也方便了后面的一些放缩处理。最后经过证明，n = 52时，k = 7时候该距离的上限是0.33，可以约莫看作大致均匀了。这个结论大体可以视作O(logn)的洗牌复杂度，而hindu和overhand则为O(n ^ 2 * logn)，Top-to-Random Shuffle和Random-Transposition居然有O(nlogn)甚至快于前者，真实让人不可思议，可见hindu shuffle真的不是一类好的方法；Random-Adjacent-Transposition仅有O(n ^ 3 * logn)的洗牌次数，可见每一次行为的熵增量也是极其的重要。
图6 随洗牌次数增加混乱度降低的规律
以上详细资料可参考：
http://www.ams.org/publicoutreach/feature-column/fcarc-shuffle
https://www.zhihu.com/question/21503093
本篇文章对洗牌从混乱度评价到过程建模到近似计算，这里就告一段落了，无论是成功或者失败的思路，以及前辈对这个问题的研究成果和想法，都对深入理解问题大有裨益。这其中涉及了一定的概率统计，随机过程，排列组合等基础内容，相信你一定能体验到数学建模的美妙。