一副牌要洗幾次才算洗好

2023 年 3 月，Diaconis 在台大天文數學館講三天的《洗牌的數學》，主辦的是中華民國數學會與中研院數學所的許振榮講座。我隨機微積分的老師黃啟瑞公告停課一週，要大家去聽；他也是演講前兩天那場專訪的訪問人之一。場地在天數 202，我最喜歡的教室。

一副新牌拆封的時候，四種花色各自從 A 排到 K。開始洗，洗到第幾次可以發牌？

七次。這個答案出自 1992 年《Annals of Applied Probability》上的一篇論文，Dave Bayer 與 Persi Diaconis 在裡面給出洗 $m$ 次之後任一排列出現的機率的封閉式，並證明 $\frac{3}{2}\log_2 n$ 次足以把 $n$ 張牌洗亂。七這個數字有三個前提：牌堆是 52 張、洗法是鴿尾式（把牌分成兩疊，讓兩疊的牌交錯落下再併回去，打牌的人最常用的那種）、衡量「還差多遠」用的是全變異距離。牌堆換一種、距離換一種，算出來的都是別的數字。

Diaconis 1945 年生於紐約，十四歲離家跟著紙牌魔術師 Dai Vernon 巡演，1971 年 1 月拿到紐約市立學院的數學學士，1974 年在 Mosteller 指導下取得哈佛博士；Martin Gardner 當年寫給哈佛的推薦信說，這名學生是全國最好的紙牌技師之一。他要回答的問題來自牌桌：洗過的牌還留著多少原來的痕跡。

洗一次牌，還剩多少原來的順序

Gilbert 與 Shannon 提出、Reeds 獨立提出的模型把洗牌寫成兩個步驟：先依二項分佈把牌切成兩堆，再讓兩堆交錯落下，左右兩堆各剩 $A$ 與 $B$ 張時，下一張來自左堆的機率是 $A/(A+B)$。該文說明實驗顯示這個模型能描述人實際的洗法。後面每一個數字都算在這個模型底下。

一次洗牌把原來的順序拆成兩段：左半堆的牌彼此之間仍然由小到大，右半堆也是。這種極大的遞增段落叫遞增序列，洗第二次時每一段最多再被拆成兩段，所以洗 $k$ 次的牌堆最多只有 $2^k$ 段。

Levin 與 Peres 的教科書給了鴿尾式洗牌的第三種等價寫法：擲一次公正硬幣替每張牌貼一個 0 或 1，把貼 0 的全部抽到前面、彼此相對次序不動，這個動作正是一次洗牌的逆操作。連做 $k$ 次，每張牌就帶著一串 $k$ 位元的標籤，牌堆按標籤的字典序排好。標籤只有 $2^k$ 種，所以牌堆至多分成 $2^k$ 群，正著看就是至多 $2^k$ 段遞增序列。要等到每張牌的標籤都不重複，就是生日問題，該書用它證出上界 $t_{\mathrm{mix}} \le 2\log_2(4n/3)$。這個上界比 Bayer 與 Diaconis 的精確結果鬆，用到的機率工具卻只有生日問題。

均勻隨機的牌堆平均有 26.5 段，標準差 2.10，落在 16 段以內的機率是 $4.67 \times 10^{-7}$。洗四次的牌堆最多 16 段，數一下段數就分得出來，大約兩百萬次才會判錯一次。

「離隨機還有多遠」要怎麼量

把段數以外所有想得到與想不到的檢驗也算進去，得到的就是全變異距離：找一個事件，讓它在兩個分佈底下的機率差最多，這個最大差距即是

$$\|Q_m - U\| = \max_{A} |Q_m(A) - U(A)|$$

其中 $Q_m$ 是洗 $m$ 次之後的分佈，$U$ 是 52! 種排列上的均勻分佈。Aldous 與 Diaconis 用它來問一副牌洗 $k$ 次之後離均勻還有多遠，並且提醒這個距離對微小的偏離很不留情。他們舉的例子是有人瞄到了底牌：其餘 51 張確實隨機，距離卻立刻是 $1 - 1/52$。

同一個量也可以寫成一場賭局。桌上有兩副牌，一副洗過 $m$ 次，另一副由電腦排成真正隨機的順序，你不知道哪副是哪副，要指出洗過的那一副。檢查的方法隨你挑：數遞增序列、翻開最上面那張看是不是還是黑桃 A、看紅黑相間的模式、把 52 張全部攤開慢慢比對。瞎猜的成功率是 50%，而最好的那套方法能達到 $\frac{1}{2} + \frac{1}{2}\|Q_m - U\|$。這個式子就從定義來：挑 $A$ 為那個機率差最大的事件，看到結果落在 $A$ 裡就說它是洗過的。

洗五次是 96.2%，六次 80.7%，七次 66.7%，八次 58.4%，十次 52.1%。前四次都是 100%，因為光數段數就贏了：洗四次的牌堆最多 16 段，而隨機牌堆要兩百萬次才遇得到一次 16 段以內的。

這樣定義之後，還沒有人想到的檢驗也算在裡面。它取的是最大值，不取平均：瞄到底牌那個例子裡，其他幾乎所有事件的機率都沒怎麼變，距離照樣接近 1。

52 張牌的精確數字：從 1.000 掉到 0.043

定理 1 給出洗 $m$ 次之後排列 $\pi$ 出現的機率為 $\binom{2^m + n - r}{n} / 2^{mn}$，其中 $r$ 是 $\pi$ 的遞增序列數。整個排列只透過 $r$ 進入公式，52! 項的求和因此縮成 52 項，距離算得出精確值。

52 張牌的前四次都是 1.000，接著是 0.924、0.614、0.334、0.167、0.085、0.043。$\frac{3}{2}\log_2 52 = 8.55$。距離貼著 1 不動、到某一點才在很短的範圍內掉下來，這個形狀叫 cutoff 現象，Aldous 與 Diaconis 1986 年就在洗牌問題上指認過它。

圖上的數字是本站用同一條公式、以整數有理數運算獨立重算的，七種牌堆大小、$k$ 從 1 到 10 共 70 個數值，與原文表 3 相符。牌堆換成 312 張，前七次仍然是 1.000，第十次還有 0.565。

換個說法：能多猜中幾張牌

原文說全變異距離不好向非專業者解釋，於是提出另一個量：牌背朝上逐張猜，猜完翻開再猜下一張，看平均猜中幾張。均勻隨機的牌堆，最佳策略平均猜中 $H_{52} = 1/52 + 1/51 + \cdots + 1 = 4.54$ 張。

洗五次，猜中 6.56 張，比洗好的牌多兩張；洗六次是 5.51 張，多一張；之後每次大約減半。

一家賭場設備廠商曾經送來一台十層的洗牌機請三位作者評估，工程師自己跑的幾項檢查看起來都正常。作者算出單次通過之後，懂行的玩家平均能猜中 9.5 張，而洗好的牌是 4.5 張，這份數字說服了廠商。一組事先挑好的檢查全部通過，說明的只是那幾個統計量正常。

只看紅黑，就不必洗那麼多次

玩二十一點的人不在意黑桃 7 和紅心 7 誰在前面，玩紅黑的人連花色都不看；七次回答的是「整副牌的排列」這個問題。

Assaf、Diaconis 與 Soundararajan 處理的正是這種情形：只在意某些特徵時，所需次數從 $\frac{3}{2}\log_2 n$ 降到 $\log_2 n$。他們用的是分離距離，數值不能拿去和上一張圖比大小，同一張表內的五條線則可以互相比較：問全副牌序，洗十二次仍有 0.278；二十一點看得見的牌值，第九次是 0.366；只問紅黑，第六次是 0.317。

Trefethen 與 Trefethen 改用資訊量衡量，52 張牌洗五次剩 3.52% 的資訊、六次剩 0.92%，而且這條曲線平滑遞減，沒有 cutoff。該文沒有據此給出「該洗幾次」的建議，收尾寫的是哪一種衡量更要緊，要看玩的是哪一種遊戲。

三題自測

三題，各一個常見的講法。做完再看解釋。

哪些說法對，哪些是誤讀

同一個結果，哪些說法精確，哪些是常見的誤讀。每條誤讀都配一句該怎麼改。

本文不主張的事

上面每個數字都算在 Gilbert–Shannon–Reeds 模型底下。真人手上的牌會不會照這個模型走是另一個問題，該文引的是 Diaconis 1988 年的實驗，本站沒有核對過那批實驗的資料。牌堆有重複牌時（同時洗兩副、或發牌前只用一部分），這裡的表不適用。

逐張猜牌那組數字來自模擬，每個數字十萬次，用的策略是原文推測的最佳策略，最佳性未經證明。分離距離那張表除第一列外是近似公式的結果，原文說明紅黑那一列在洗一次、兩次時與精確值 0.8898、0.8897 有差距。

本文也不給操作建議。「該洗幾次」要先講清楚這副牌拿來做什麼，而這件事該由使用它的人決定。

資料來源

1. 1.劉太平、黃啟瑞（訪問）（2023）。有朋自遠方來——專訪 Persi Diaconis 教授，數學傳播 47 卷 2 期，中央研究院數學研究所。pp.3-26。訪問時間民國 112 年 3 月 6 日，地點中央研究院數學研究所；同期報導其應中華民國數學會與中研院數學所「許振榮講座」之邀，2023 年 3 月 8 日至 10 日在臺灣大學天文數學館以《洗牌的數學》為題演講三日。原文
2. 2.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
3. 3.J. J. O'Connor & E. F. Robertson（2023）。Persi Warren Diaconis，MacTutor History of Mathematics Archive, University of St Andrews。生年與出生地（1945 年 1 月 31 日，紐約市）、十四歲隨 Dai Vernon 離家、1971 年 1 月取得紐約市立學院數學學士、1974 年在 Mosteller 指導下取得哈佛博士、Martin Gardner 的推薦信。原文
4. 4.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 現象。原文 ↑1↑2
5. 5.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。原文 ↑1↑2
6. 6.Persi Diaconis, Jason Fulman & Susan Holmes（2013）。Analysis of Casino Shelf Shuffling Machines，The Annals of Applied Probability 23(4): 1692–1720。第 1 節：廠商送來的十層洗牌機、工程師自訂的檢查看起來沒問題，以及改用逐張猜牌算出的 9.5 張與 4.5 張（arXiv:1107.2961v2, pp.1–2）。原文
7. 7.Sami Assaf, Persi Diaconis & K. Soundararajan（2011）。A rule of thumb for riffle shuffling，The Annals of Applied Probability 21(3): 843–875。第 1 節表 1：52 張牌在分離距離下，全牌序、二十一點、只看花色、只看紅黑四種問法各自的收斂數字（arXiv:0908.3462v1, p.3）。原文
8. 8.Lloyd N. Trefethen & Lloyd M. Trefethen（2000）。How many shuffles to randomize a deck of cards?，Proceedings of the Royal Society A 456(2002): 2561–2568。p.2564 圖 2 的說明文字與同頁正文：改以資訊量衡量時沒有 cut-off，$\log_2 n$ 次就把資訊降到任意小的比例。原文