cutoff 現象

它在說什麼

一個隨機程序重複跑，離均勻分佈的距離 $d(k)$ 隨次數遞減。直覺會以為它從 1 平滑地滑到 0。Aldous 與 Diaconis 指出，他們分析得動的洗牌模型全部不是這樣：存在一個臨界次數 $k_0$，使得 $d(k_0 + o(k_0)) \approx 0$ 而 $d(k_0 - o(k_0)) \approx 1$。曲線在 $k_0$ 前後幾乎垂直。

這對「要跑幾次」這個問題有直接的後果。在 $k_0$ 之前多跑幾次，距離幾乎不動，等於白跑；越過 $k_0$ 之後每多一次，距離大約減半，收益很快遞減。

它從哪來

這個名字與定義來自 Aldous 與 Diaconis 1986 年的〈Shuffling Cards and Stopping Times〉，他們對「頂牌插入隨機位置」的洗法證出 $n \log n$ 這個臨界值。六年後 Bayer 與 Diaconis 對鴿尾式洗牌算出精確的距離，臨界位置在 $\frac{3}{2}\log_2 n$，並證明距離的極限形狀是 $1 - 2\Phi(-2^{-\theta}/(4\sqrt{3}\,))$。

一個具體例子

52 張牌的鴿尾式洗牌，前四次的全變異距離都是 1.000，接著是 0.924、0.614、0.334、0.167、0.085、0.043。$\frac{3}{2}\log_2 52 = 8.55$。同一張表換成 312 張牌，前七次都是 1.000，第十次還有 0.565。

常見的誤讀

把陡降讀成門檻。 距離從未等於 0。「洗七次就夠」講的是那一次落在陡降段裡，不是那一次跨過了一條線。

以為每個隨機程序都長這樣。 同一副牌改用資訊量衡量，曲線是平滑遞減的，沒有 cutoff。有沒有 cutoff 取決於用哪一種距離。

拿它當停止規則。 臨界位置是漸近結果，實際要洗幾次得看牌堆多大、在意的是哪一種問題。

資料來源

1. 1.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
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. 3.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$ 次就把資訊降到任意小的比例。原文