# 洗牌的數學

Author : Xin

## 簡介

當我們在玩各式牌類遊戲的時候，為了保證遊戲的公平性，洗牌往往是不可或缺的一步。理論上來說，一個好的洗牌方式應當將牌堆的排列順序打亂，使每張牌出現的機率都是均勻的。但是在現實中，受限於物理條件等種種因素，常見洗牌方式通常都不會太複雜，也很難將牌堆洗得完全隨機。
儘管如此，Diaconis等人利用數學證明了，就算只使用交錯式洗牌(Riffle Shuffle)也能將牌洗得足夠隨機。本文將會詳細介紹下列問題：
- 交錯式洗牌是甚麼?怎麼用數學來描述它?
- 洗牌的次數不同真的有差嗎?知道這些東西又有甚麼用處呢?
- Diaconis等人是如何證明此結論的?

理論上，本文只會涉及到高中程度的排列組合、機率相關知識。本文將依次介紹
1. 描述交錯式洗牌的數學模型，以及實驗結果。
1. 利用了一個魔術技法來舉例說明，洗牌次數太少的影響。
1. 證明基礎和進階版本的結論來說明幾次洗牌才足夠。

## 交錯式洗牌

### GSR模型

交錯式洗牌是一種常見的洗牌方法，如果不知道的話，與其用一堆文字解釋，不如直接看演示 [(連結)](https://commons.wikimedia.org/wiki/File:Riffle_shuffle.gif)，看過一次應該就知道怎麼進行。
這種洗牌方式經常在賭場中使用，因為它降低了洗牌期間暴露牌卡的風險。但也有因為過度彎曲而損壞公平性的疑慮，因此在賭場中會經常替換牌。
回到正題，考慮一副 $n$ 張牌的牌堆，我們可以使用GSR模型(Gilbert-Shannon-Reeds model)來描述交錯式洗牌，包含以下步驟:
1. 首先，我們必須將整副牌切牌為兩堆，GSR模型使用 $\operatorname{Bin}(n , 1/2)$ 來決定切牌的數量，也就是說，我們切了 $k$ 張牌的機率為 $\frac{1}{2^n}\binom{n}{k}$。
1. 切牌完成後，我們將牌鬆開依序交疊在一起，其中如果左手有 $x$ 張牌，右手有 $y$ 張牌，那麼左手邊的牌先落下的機率為 $x/(x+y)$，而右手邊的牌先落下的機率為 $y/(x+y)$。

舉例來說，假設一開始我們有這樣的一副牌。


- 先切牌將牌分為兩部分。


在此情況下，第一張落下的牌有 $6/13$ 的機率為6:heart:，而有 $7/13$ 的機率為K:heart:。假設第一張落下的牌為6:heart:，那麼第二張落下的牌有 $5/12$ 的機率為5:heart:，而有 $7/12$ 的機率為K:heart:，之後以此類推。
- 最終我們利用交錯式洗牌得到了

實際上，可以證明下列三種洗牌方式有相同的機率分布：
1. 上面所描述的GSR模型。
1. 同樣使用 $\operatorname{Bin}(n , 1/2)$ 來決定切牌的數量。假設我們切了 $c$ 張牌，隨機從 $\binom{n}{c}$ 種所有可能的牌序中挑選一種作為洗牌結果。
1. 將每張牌均勻且獨立的分給兩個組別，將組別一的牌維持原順序放置於牌堆上方，組別二的牌維持原順序放置於牌堆下方。

我把第三種洗牌方式叫做反交錯式洗牌，讓我們先對第三種方式舉個例子示範一次。
- 假設同上述例子的洗牌結果，牌堆為A:heart:7:heart:8:heart:2:heart:3:heart:9:heart:10:heart:4:heart:J:heart:5:heart:Q:heart:K:heart:6:heart:
- 假設分組結果為
$$0,1,1,0,0,1,1,0,1,0,1,1,0$$ 其中第一個位置為0就代表A:heart:這張牌被分配到第一組，第二個位置為1就代表7:heart:這張牌被分配到第二組，以此類推。由此分別得到兩個組別
- 第一組：A:heart:2:heart:3:heart:4:heart:5:heart:6:heart:
- 第二組：7:heart:8:heart:9:heart:10:heart:J:heart:Q:heart:K:heart:

分別將結果為0和1的牌以原順序分別放置到牌堆上方及下方會得到原牌堆
- A:heart:2:heart:3:heart:4:heart:5:heart:6:heart:7:heart:8:heart:9:heart:10:heart:J:heart:Q:heart:K:heart:

:::spoiler 證明
證明分為兩部分，首先證明第二種方式和第三種方式等價，接著證明第一種方式和第二種方式等價。
- 不難看出，第二種方式和第三種方式是等價的，因為每張牌都有各1/2機率被分到第一組和第二組，相當於是做了一次 $\operatorname{Bin}(n , 1/2)$ 試驗決定第一組有幾張牌，且第一組牌的位置都是隨機分布的。
- 接著，我們證明第一種方式和第二種方式是等價的。假設我們切了 $c$ 張牌，在GSR模型洗牌的過程實際可由序列 $D_1,D_2,...,D_n$ 決定，其中每個 $D_i$ 的值只有0或1，且只有 $c$ 個 $D_i$ 是0、$n-c$ 個 $D_i$ 是1。
舉例來說，在之前的例子中，$D_{13}$ 就是0，代表第一張落下的牌為第一組的牌，而 $D_{12}$ 就是1，代表第二張落下的牌為第二組的牌。
由簡單計算可知，$D_n$ 為0和1的機率分別為 $c/n$ 和 $(n-c)/n$，
- 若 $D_n$ 為0，則 $D_{n-1}$ 為0和1的機率分別為 $(c-1)/(n-1)$ 和 $(n-c)/(n-1)$
- 若 $D_n$ 為1，則 $D_{n-1}$ 為0和1的機率分別為 $c/(n-1)$ 和 $(n-c-1)/(n-1)$

以此類推，相乘後可知，任何一種牌序出現的機率皆為 $c!(n-c)!/n! = \binom{n}{c}$。
:::

### 實驗結果

有了模型後，自然地我們必須搞清楚這個模型真的符合現實中洗牌的結果嗎?根據模型的預測，同一邊落下單張牌的機率為1/2，而落下兩張連續的牌的機率為1/4，落下三張連續的牌的機率為1/8：
1. 由反交錯式洗牌可看出，同一邊落下單張牌也就是第二張牌硬幣結果必須和第一張牌不同，因此機率為1/2
1. 落下兩張連續的牌也就是第二張牌硬幣結果必須和第一張牌一致且第三張牌硬幣結果必須和第一和第二張牌不同，因此機率為1/4
1. 最後，落下三張連續的牌也就是第三張牌硬幣結果必須和第一、二張牌一致且第四張牌硬幣結果必須和第一、二、三張牌不同，因此機率為1/8。

在 [1] 裡做實驗讓一個普通人洗牌了100次，並記錄結果如下

| 切牌數量 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31|
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| 出現次數 | 2 | 2 | 8 | 16 | 23 | 26 | 16 | 5 | 2 |

| 同一邊連續掉落張數 | 1 | 2 | 3 | 4 | 5 | 6 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| 出現次數 | 2102 | 931 | 228 | 68 | 24 | 12 |
| 佔總數比例 | 0.62 | 0.28 | 0.07 | 0.02 | 0.01 | 0.00

由表中可看出，同一邊連續落下單張牌、兩張牌、三張牌的機率各為0.62、0.28、0.07，這與模型預測的0.5、0.25、0.125相差並不大，因此GSR模型與現實中洗牌的情形相差不大。
除了交錯式洗牌外，還有另一種常見的簡單洗牌方式，我把它叫做切洗。簡單來說，就是先切牌將牌分為兩堆，之後交換兩個牌堆的順序。

## 魔術戲法

一名魔術師拿出一副全新的撲克牌讓你檢查，此時魔術師轉身背對著你同時讓你用交錯式洗牌將這副牌打亂。在你洗完牌後再切洗一次，完成後翻開最上方的卡並記住這張牌，之後將其隨機放回牌堆的任意位置。一切塵埃落定後，魔術師轉過身來將整副牌攤開，仔細端詳後便指出了你記住的牌。魔術師是如何辦到的?其實一切只需利用交錯式洗牌的基本性質，破解此魔術的關鍵就在於「遞增序列」。

### 遞增序列

簡單來說，遞增序列就是數字連續的牌的最大序列。舉例來說，
A:heart:5:heart:10:heart:2:heart:3:heart:J:heart:Q:heart:4:heart:6:heart:K:heart:就包含了三個遞增序列：
- A:heart:2:heart:3:heart:4:heart:、5:heart:6:heart:、10:heart:J:heart:Q:heart:K:heart:

給定 $n$ 張牌的牌堆，假設我們在交錯式洗牌過程中將牌分為了兩堆
$$1,2,...,c ~~\text{和}~~c+1,c+2,...,n$$ 經過洗牌後，牌堆通常由原來的一個遞增序列 $1,2,...,n$ 變為了兩個遞增序列 $$1,2,...,c ~~\text{和}~~c+1,c+2,...,n$$ 一般來說，每經過一次交錯式洗牌，牌堆中遞增序列的數量將翻倍。因此洗一次牌將有兩個遞增序列，洗兩次牌將有四個，洗三次牌將有八個。同樣考慮之前出現過的例子


- 經過一次交錯式洗牌後，我們得到

此時的遞增序列有兩個：
- A:heart:2:heart:3:heart:4:heart:5:heart:6:heart:、7:heart:8:heart:9:heart:10:heart:J:heart:Q:heart:K:heart:

- 假設再進行一次洗牌，將牌分為

之後洗牌得到

此時的遞增序列增加到四個：
- 4:heart:5:heart:6:heart:、A:heart:2:heart:3:heart:、7:heart:8:heart:9:heart:10:heart:、J:heart:Q:heart:K:heart:

### 魔術分析

讓我們回到魔術的分析上，先從簡單的情況開始，假設觀眾只有使用交錯式洗牌而並無切洗。魔術師攤開牌後只需要觀察有幾個遞增序列。
- 假設觀眾洗了三次牌，那麼應該要有八個遞增序列，每個序列平均有6.5張牌。但是觀眾洗完牌後「將牌堆上方第一張牌隨機放回牌堆往往會製造出第九個遞增序列」。因此，魔術師很容易就能辨認出觀眾記住的牌。
- 以之前提到過的例子為例

假設將第一張牌4:heart:插入至5:heart:和Q:heart:中間。那麼遞增序列就變為五個：
- A:heart:2:heart:3:heart:、4:heart:、5:heart:6:heart:、7:heart:8:heart:9:heart:10:heart:、J:heart:Q:heart:K:heart:

因此，可以看出被選中的牌為多出來的遞增序列4:heart:。

假如觀眾使用了切洗，還是一定的規律可觀察的。事實上，切洗只會改變牌的循環位置。
- 舉例來說，考慮A:heart:2:heart:3:heart:4:heart:5:heart:6:heart:7:heart:8:heart:9:heart:10:heart:J:heart:Q:heart:K:heart:，從第一張牌出發，只需要一圈便可以走完所有數字。假設切洗牌後變為6:heart:7:heart:8:heart:9:heart:10:heart:J:heart:Q:heart:K:heart:A:heart:2:heart:3:heart:4:heart:5:heart:，基本上牌是沒改變的，從第九張牌A:heart:出發還是只需一圈就可以走過所有的數字。

雖然此魔術並非百分百會成功，但[3]中提出了一演算法即使在觀眾使用三次交錯式洗牌再切洗的情況下，此魔術仍然有接近六成的成功率。考慮到觀眾往往不會洗那麼多次牌，這個方法跟完全亂猜相比下成功率還是足夠高的。

||
|:--:|
|不同洗牌次數下程式模擬的魔術成功率|

## 洗牌幾次才夠？

假設洗一副 $n$ 張牌的牌堆。理想上我們希望經過洗牌後，牌堆服從均勻分布，也就是說，每種牌序出現的機率都是 $1/n!$。但我們都知道這只是理想情況，洗過的牌堆並非是均勻隨機的，所以需要一個方法來衡量它與均勻分布的差距。
在機率論中，常常使用全變差距離(Total Variation Distance)來做為衡量標準。
- 假設 $Q^k$ 是洗牌 $k$ 次後的機率分布、$S_n$ 為 $n$ 張牌的牌堆的所有可能牌序。那麼 $Q^k$ 和均勻分布的全變差距離為
$$
\frac{1}{2}\sum_{x\in S_n}\left |Q^k(x) - \frac{1}{n!}\right |
$$ 簡單來說，就是把洗牌後所有可能牌序的發生機率和均勻分布的發生機率$(1/n!)$的差距全部相加起來。至於為甚麼要除以2，這與全變差距離的性質有關，這裡不多贅述。
- 觀察後可看出，若全變差距離接近零(也就是說，對於每種牌序 $x$，$Q^k(x)\sim 1/n!$ )，則 $Q^k$ 與均勻分布十分相近。

我們可以利用程式模擬來算出全變差距離，但是由於階乘的成長速度過快，當 $n$ 很大時就很難利用程式模擬了。此時就是數學派上用場的時候，下面將介紹一個數學論證，可以簡單的算出全變差距離的上界。
||
|:--:|
|$n=8$ 時，利用程式模擬得出的不同洗牌次數下的全變差距離|

### 基礎論證

此章節，我們將要利用之前說明過的反交錯式洗牌來證明較弱的結論。首先從一個例子觀察起。
給定五張牌A:heart:2:heart:3:heart:4:heart:5:heart:，我們要利用反交錯式洗牌對這五張牌洗三次牌，每張牌的分組結果分別為$$(1,0,0) ~,~ (0,1,0) ~,~ (1,0,1) ~,~ (0,0,1) ~,~ (1,1,0)$$ 其中第一個序列(1,0,0)代表A:heart:在三次洗牌過程中組別依序為第二組、第一組、第一組。可以把洗牌過程用下圖表示。

||
|:--:|
|牌堆洗牌示意圖，由上到下代表牌堆中的第一張牌、第二張牌、第三張牌 ···。|

由左至右牌堆依序為
A:heart:2:heart:3:heart:4:heart:5:heart:、2:heart:4:heart:A:heart:3:heart:5:heart:、4:heart:A:heart:3:heart:2:heart:5:heart:、A:heart:2:heart:5:heart:4:heart:3:heart:
從左至右看是做了三次反交錯式洗牌，而從右至左則可以看成是做了三次交錯式洗牌。
在所有牌的二元序列都不重複的條件下，反交錯式洗牌其實是對這些二元序列的字典排序，比大小時由右至左且0優先於1。
以上述例子來說，字典排序給出的大小關係為
$$
(0,0,0) > (1,0,0) > (0,1,0) > (1,1,0) > (0,0,1) > (1,0,1) > (0,1,1) > (1,1,1).
$$
- 在所有牌的二元序列都不重複的條件下，由於這些二元序列都是均勻且獨立生成的，因此經過字典排序後每張牌都有同樣的機率會是字典排序中最大的(也就是處於牌堆最上方)。
- 同理可證，經過字典排序後。每種牌序出現的機率皆相同。因此只要所有牌的二元序列都不重複，經過反交錯式洗牌後的結果會是均勻隨機的。
- 由於反交錯式洗牌反過來可以看做交錯式洗牌，因此只要所有牌的二元序列都不重複，經過交錯式洗牌後的結果也會是均勻隨機的。
- 因此，交錯式洗牌後和均勻分布的差距至多是所有二元序列並非全部相異的機率。

假設牌堆數量為 $n$、洗牌次數為 $k$，我們要從 $2^k$ 種可能的二元序列中挑出 $n$ 個序列，問這 $n$ 個序列不重複的機率有多少？
- 若我們想要所有序列不重複。第一個序列共有 $2^k$ 種選擇，第二個序列則剩下 $2^k-1$ 種選擇，第三個序列剩下 $2^k-2$ 種選擇，以此類推，第 $n$ 個序列剩下 $2^k-(n-1)$ 種選擇。
因此，這 $n$ 個序列不重複的機率為
$$
\frac{2^k}{2^k}\times\frac{2^k-1}{2^k}\times\frac{2^k-2}{2^k}\times\cdots\times\frac{2^k-(n-1)}{2^k}
$$ 所以這 $n$ 個序列並非全部相異的機率為
$$
1 - \frac{2^k}{2^k}\times\frac{2^k-1}{2^k}\times\frac{2^k-2}{2^k}\times\cdots\times\frac{2^k-(n-1)}{2^k}
$$ 考慮單副撲克牌的情況$(n = 52)$，可以用電腦對不同洗牌次數計算出上述值，如下圖。

||
|:--:|
|$n=52$ 時，二元序列並非全部相異的機率|

事實上，我們所得出的結論只是較弱的結果[2]，Bayer和Diaconis在[3]用較複雜的方法得出了更好的結果，這也是著名的「七次洗牌就足夠」的出處。

| 洗牌次數 | 4 | 5 | 6 | 7 | 8 | 9 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| 全變差距離 | 1.000 | 0.924 | 0.614 | 0.334 | 0.167 | 0.085 |

### 進階論證
此章節，我們將要簡略說明[3]中的結果是怎麼得出的。首先先考慮交錯式洗牌的推廣。
- 在之前的章節中我們所考慮的交錯式洗牌都是將牌分為兩堆之後交疊，自然的我們也可以考慮將牌分為三堆、四堆等更多堆之後再交疊。我們把這種將牌堆先分為 $a$ 堆之後再交疊的交錯式洗牌命名為 $a$-shuffle。舉例來說，交錯式洗牌為 2-shuffle。

洗牌方式如下:
首先根據下列分布來決定每個牌堆的張數，$a$ 堆中每堆牌的張數分別為 $j_1,j_2,...,j_a$ 出現的機率為
$$
\binom{n}{j_1,j_2,...,j_a}\frac{1}{a^n} = \frac{n!}{j_1!j_2!\cdots j_a!}\frac{1}{a^n}
$$ 觀察後可看出，$0\leqslant j_i\leqslant n ~,~ \sum_{i=1}^a j_i = n$，其中 $j_i$ 的分佈與下列相同：
- 將 $n$ 顆球均勻的隨機分配到 $a$ 個箱子裡，第 $i$ 個箱子中所含的球數。

決定了 $j_1,...,j_a$ 後，將牌堆由上至下依序切 $j_1$ 張牌，$j_2$ 張牌，$j_3$ 張牌，以此類推。這樣我們就得到了 $a$ 個牌堆。
將第一個牌堆與第二個牌堆先進行交錯式洗牌，將洗完的牌堆再與第三個牌堆進行交錯式洗牌，之後再將洗完的牌堆與第四個牌堆進行交錯式洗牌，以此類推。這樣就完成了一次 $a$-shuffle。

>[!Note]
我們也可以將 $a$ 個牌堆同時交疊洗牌如下: 假設每個牌堆剩下的牌數為 $N_1,N_2,...,N_a$，那麼下一張落下的牌為第 $i$ 個牌堆的機率為$$N_i / (N_1+N_2+\cdots + N_a)$$ 此種洗牌方式與上述「將第一個牌堆與第二個牌堆先進行交錯式洗牌，將洗完的牌堆再與第三個牌堆進行交錯式洗牌 ···」有相同的機率分布。
>:::spoiler 證明
>假設每堆牌的張數分別為 $j_1,j_2,...,j_a$。在同時洗牌方式下，一共有 $\binom{n}{j_1,j_2,...,j_a}$ 多種可能牌序。
>另一方面，將第一個牌堆與第二個牌堆先進行交錯式洗牌後一共有 $\binom{j_1+j_2}{j_2}$ 多種可能牌序，而將洗完的牌堆再與第三個>牌堆進行交錯式洗牌後一共有 $\binom{j_1+j_2 + j_3}{j_3}$ 多種可能牌序，以此類推。
>因此洗完所有牌後總共有
>$$
>\binom{j_1+j_2}{j_2}\binom{j_1+j_2 + j_3}{j_3}\cdots\binom{j_1+j_2 + \cdots + j_a}{j_a} = \frac{n!}{j_1!j_2!\cdots j_a!}
>$$ 多種可能牌序，與同時洗牌方式相同。
>:::

與交錯式洗牌時相同，我們也可以考慮反 $a$-shuffle如下：
- 將每張牌均勻且獨立的分給 $a$ 個組別，將組別一的牌維持原順序放置於牌堆上方，組別二的牌維持原順序放置於組別一下方，組別三的牌維持原順序放置於組別二下方，以此類推。
- 同樣的，反 $a$-shuffle與 $a$-shuffle有著相同的機率分布。

可以證明，將牌堆接連進行 $a$-shuffle和 $b$-shuffle的機率分布與將牌堆進行一次 $ab$-shuffle的機率分布相同。
:::spoiler 證明
假設牌堆接連進行了反 $a$-shuffle和反 $b$-shuffle。可以利用反 $a$-shuffle和反 $b$-shuffle組合的字典排序來定義反 $ab$-shuffle。
- 舉例來說，可以讓同時被分配至反 $a$-shuffle的第一組及反 $b$-shuffle的第一組的牌作為反 $ab$-shuffle的第一組，而同時被分配至反 $a$-shuffle的第二組及反 $b$-shuffle的第一組的牌作為反 $ab$-shuffle的第二組，以此類推。
- 由於反 $a$-shuffle和反 $b$-shuffle分組的選取方式都是均勻且獨立的，因此利用反 $a$-shuffle和反 $b$-shuffle來組合出的反 $ab$-shuffle的選取方式也是均勻且獨立的。
:::

對於任一種牌序 $\pi$，假設 $r$ 為 $\pi$ 中遞增序列的數量。在經過一次 $a$-shuffle後 $\pi$ 出現的機率為
$$
\frac{1}{a^n}\binom{a + n - r}{n}
$$
:::spoiler 證明
- 首先注意到，對於任意一種將牌堆分成 $a$ 堆的方式，若此分堆方式在洗牌後有可能將牌序變為 $\pi$，那麼只存在唯一一種牌落下的順序能讓牌序變為 $\pi$。
- 因此，在計算經過一次 $a$-shuffle後 $\pi$ 出現的機率時，只需要統計有幾種將牌堆分成 $a$ 堆的方式能夠使牌序變為 $\pi$，之後再將這個數量除以 $a^n$ (所有可能的分堆總數)。
- 由於洗牌後每堆中牌的相對順序依舊不變，因此每個遞增序列都會是 $a$ 個牌堆中某些牌堆的聯集。所以我們只需要統計有幾種將 $r$ 個遞增序列放到 $a$ 個分堆中的方式。
- 要將牌分為 $a$ 堆需要有 $a-1$ 個間隔，而兩個相鄰的遞增序列之間都需要至少一個間隔隔開，因此剩下的自由的間隔數為 $a-1 - (r-1) = a - r$ 個。

將剩下的間隔與 $n$ 張牌排列，因此總共有 $\binom{a + n - r}{n}$ 個排列方式。
:::

對任意牌序 $\pi$，假設 $r$ 為 $\pi$ 中遞增序列的數量。在經過 $m$ 次交錯式洗牌後 $\pi$ 出現的機率為
$$
\frac{1}{2^{mn}}\binom{2^{m} + n - r}{n}
$$

注意到 $m$ 次交錯式洗牌相當 $m$ 次 2-shuffle，而 $m$ 次 2-shuffle跟一次 $2^m$-shuffle相同。因此將 $a=2^m$ 帶入後便得到了上述結果。

有了上述結果後，唯一重要的就只剩下來估計
$$
\left |\frac{1}{2^{mn}}\binom{2^{m} + n - r}{n} - \frac{1}{n!}\right|
$$ 但是由於計算過程太複雜了，因此這裡就不列出來。有興趣的讀者可以自行參考[3]中的推導過程。

## 參考資料

[1] Persi Diaconis. “Group Representations in Probability and Statistics.” Lecture Notes-Monograph Series, vol. 11, 1988, pp. i–192.

[2] Aldous, David, and Persi Diaconis. “Shuffling Cards and Stopping Times.” The American Mathematical Monthly, vol. 93, no. 5, 1986, pp. 333–48.

[3] Dave Bayer and Persi Diaconis. "Trailing the Dovetail Shuffle to its Lair." Ann. Appl. Probab. 2 (2) 294 - 313, May, 1992.