關於洗牌的研究（二）——你的撲克洗亂了嗎？

• 2019 年 10 月 8 日
• 筆記

寫再前面：本系列作品由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的確定過程進行建模描述，進而才能更加細緻地估算洗牌帶來的熵來作為洗牌評價準則的具體方案，或者跳出熵的限定，有沒有別的容易計算的方案。