全變異距離

它在說什麼

兩個機率分佈 $P$ 與 $Q$ 落在同一個群體上，全變異距離取遍所有事件 $A$，看它們給 $A$ 的機率最多差多少：

$$\|P - Q\| = \max_{A} |P(A) - Q(A)| = \frac{1}{2}\sum_{x} |P(x) - Q(x)|$$

兩個寫法等價，取到最大值的事件是 $\{x : P(x) > Q(x)\}$。距離永遠落在 0 與 1 之間。

把「事件 $A$」想成一個檢驗，看到結果落在 $A$ 裡就宣告它來自 $P$，距離就是最好的那個檢驗能拿到的優勢。距離 0.334，任誰設計檢驗，正確率最多比亂猜高三成三；距離 0.01，沒有任何檢驗分得出來。

它從哪來

它是機率論裡衡量兩個分佈差距的標準工具，在洗牌與馬可夫鏈的收斂問題上被用來定義「還要多久才算隨機」。Aldous 與 Diaconis 1986 年那篇把它寫成 $d(k) = \|Q^{k*} - U\|$，用來問一副牌洗 $k$ 次之後離均勻還有多遠。

一個具體例子

三個例子從一眼看穿排到幾乎看不出來。

瞄到底牌，距離 0.98。 一副洗好的 $n$ 張牌，你剛好瞄到底牌是哪一張。在你所知的條件下，分佈在「底牌是它」的那些排列上均勻，與均勻分佈的距離是 $1 - 1/n$。52 張牌就是 0.98，而其餘 51 張的次序確實是隨機的：一個事件（「底牌是那一張」）的機率從 $1/52$ 變成 1，最大差距就到了 0.98。

洗四次的牌堆，距離 1.000。 洗 $k$ 次的牌堆最多只有 $2^k$ 段遞增序列，四次至多 16 段，而均勻隨機的 52 張牌平均有 26.5 段，落在 16 段以內的機率是 $4.67 \times 10^{-7}$。取「段數不超過 16」當事件，兩邊的機率是 1 與千萬分之四點七，距離因此貼著 1。這裡的檢驗只要數段數，不必是什麼精巧的方法。

洗七次的牌堆，距離 0.334。 把洗過的牌與電腦排的隨機牌擺在一起要你指認，瞎猜的成功率是 50%，最好的那套檢查是 $\frac{1}{2} + \frac{1}{2} \times 0.334 = 66.7\%$。同一副牌洗到第十次是 0.043，成功率剩 52.1%，已經接近瞎猜。

同一個距離，52 張牌用鴿尾式洗七次是 0.334，洗十次是 0.043。

常見的誤讀

把它讀成「平均差多少」。 它取的是最大值。上面那個例子裡，絕大多數事件的機率幾乎沒變，距離照樣接近 1。原文的說法是這個距離對微小的偏離「很不留情」。

把小距離讀成「一樣」。 距離 0.043 表示沒有檢驗能拿到超過 4.3% 的優勢，不表示兩個分佈相同。

拿它和別的距離比大小。 分離距離、$l_\infty$ 距離、資訊量各有各的定義，數值不能互相比較；同一個分佈的全變異距離不會大於分離距離，換一種距離，「要幾次」的答案就換一個。

資料來源

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↑3↑4
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.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）。原文