鴿尾式洗牌

把一副牌分成兩疊、讓兩疊交錯落下的洗法，也是撲克牌最常見的洗法。

又稱：riffle shuffle、鴿尾洗牌、GSR 模型、Gilbert–Shannon–Reeds

本頁目次

它在說什麼

把一副牌大致分成兩疊，兩手各拿一疊，用拇指讓兩疊的牌交錯落下再併回去。這是打牌的人最常用的洗法，數學上寫成兩個步驟：先依二項分佈把 $n$ 張牌切成兩堆，再讓兩堆交錯落下，左右兩堆各剩 $A$ 與 $B$ 張時，下一張來自左堆的機率是 $A/(A+B)$ 。這個模型由 Gilbert 與 Shannon 提出、Reeds 獨立提出，一般稱作 GSR 模型。

同一件事還有一個反過來的寫法：擲一次公正硬幣替每張牌貼 0 或 1，把貼 0 的全部抽到前面、彼此相對次序不動，這正是一次洗牌的逆操作。倒過來想常常比正著想好算。

它從哪來

Bayer 與 Diaconis 1992 年用這個模型算出洗 $m$ 次之後任一排列出現的機率，並證明 $\frac{3}{2}\log_2 n$ 次足以把 $n$ 張牌洗亂。「52 張牌要洗七次」這個說法就是從這裡來的，它只在這個洗法底下成立。

一個具體例子

一次洗牌把原來的順序拆成兩段，各自仍然由小到大。這種極大的遞增段落叫遞增序列，洗 $k$ 次的牌堆最多只有 $2^k$ 段。均勻隨機的 52 張牌平均有 26.5 段，而洗四次最多 16 段，數一下段數就分得出洗過幾次。

常見的誤讀

把它當成唯一的洗法。 「把最上面那張插進隨機位置」是另一個常被分析的模型，臨界次數是 $n\log n$ 量級，與這裡的 $\frac{3}{2}\log_2 n$ 不是同一個數量級。

把模型當成真人的手。 GSR 是對人怎麼洗牌的近似；原文說明實驗顯示這個模型描述得了人實際的洗法，本站沒有核對過那批實驗的資料。

資料來源

1.Dave Bayer & Persi Diaconis（1992）。Trailing the Dovetail Shuffle to its Lair，The Annals of Applied Probability 2(2): 294–313。p.294 定理 1（洗 m 次後某個排列出現的機率）與 GSR 模型的描述；p.296 表 1（52 張牌的全變異距離）；p.309 表 3（七種牌堆大小的精確值）與表 4（1.5 log2 n）；p.310 表 5（逐張猜牌的平均猜中數）與 5.1 節。原文 ↑1 ↑2 ↑3 ↑4
2.David A. Levin & Yuval Peres（2017）。Markov Chains and Mixing Times，2nd ed. Providence: American Mathematical Society。第 8.3 節「Riffle Shuffles」pp.107-110：鴿尾式洗牌的三種等價描述（其中第三種是逆洗牌的位元標籤法）、命題 8.11 的強停止時間，以及命題 8.12 的上界 $t_{\mathrm{mix}} \le 2\log_2(4n/3)$ 。第 4.1 節 p.47 定義全變異距離，第 18 章 p.261 處理 cutoff 現象。原文
3.David Aldous & Persi Diaconis（1986）。Shuffling Cards and Stopping Times，The American Mathematical Monthly 93(5): 333–348。p.335：全變異距離的三個等價定義（2.3）、看見底牌就使距離等於 $1-1/n$ 的例子，以及 cut-off 現象的定義與圖 2。原文

相鄰術語

全變異距離——兩個機率分佈之間，在同一個事件上機率差距的最大值。
cutoff 現象——距離幾乎不動地貼著 1，到某個次數附近才在很短的區間內掉到接近 0。

出現在

一副牌要洗幾次才算洗好