為什麼只有平均值還不夠
上一篇給了我們一項超能力：期望值的線性性質讓我們把一堆微小的指示變數加起來，就能算出幾乎任何東西的期望值，而不必去釐清它們彼此之間如何相依。但期望值只是一個數字——是跑無限多次後的長期平均。它本身並不告訴你：某一次單獨的執行，會貼近這個平均，還是離譜地偏離。一個期望執行時間為 O(n log n) 的隨機演算法，單看期望值，誰也不能保證你真正在意的那一次不會慢上一百萬倍。
舉個樸實的畫面。兩個村莊，每人平均收入都是一枚硬幣。第一個村莊裡，每個人剛好賺一枚。第二個村莊裡，有一個人囤了十億枚，其餘人一無所有。平均相同，生活卻天差地別。尾界正是用來區分這兩個世界的工具：它界定一個隨機量落在分布尾端、遠離平均值的機率。對隨機演算法而言，尾端正是災難所在之處——那些慢到崩潰的罕見執行，或那些罕見地答錯的情況。
馬可夫：最鈍的那把鎚子
第一個、也是最弱的工具，是馬可夫不等式。它適用於任何永不為負的隨機變數 X，而且對你幾乎沒有要求：你只需要知道期望值 E[X]。它的主張是：X 不可能太常變大，理由很簡單——若它太常變大，平均值就會被往上拖、超過 E[X]。形式上，對任意門檻 a > 0，X 至少為 a 的機率至多是 E[X] 除以 a。用符號寫：Pr[X >= a] <= E[X] / a。
為什麼它成立？把 E[X] 想成 X 各個取值的加權平均。每一個 X >= a 的結果，都至少貢獻 a 乘上它的機率到這個平均裡。所以平均值至少是 a 乘以 Pr[X >= a]。既然平均值等於 E[X]，我們就得到 E[X] >= a * Pr[X >= a]，兩邊除以 a 便得到該不等式。非負性很關鍵：若 X 在其他結果上可以很負，那些負值就能抵消掉那些大值，論證便會垮掉。這短短一行的證明，就是馬可夫的全部內容。
馬可夫之所以鈍，是因為它只用了平均值。一個具體用法：假設某個拉斯維加斯演算法的期望執行時間 E[T] = 5n。馬可夫說它跑至少 50n 步的機率至多是 5n / 50n = 1/10。所以至少有 90% 的時候，它在平均的 10 倍之內完成——有用，但弱。我們完全沒用上關於 T 離散程度的任何資訊，只用了它的中心，這正是為什麼這個保證如此鬆。要做得更好，我們得餵給下一個工具第二個數字：變異數。
柴比雪夫：把離散程度也算進去
柴比雪夫不等式是馬可夫加上一個巧妙轉折。我們想界定 X 偏離其平均 mu = E[X] 有多遠。訣竅是：不把馬可夫套在 X 上，而套在平方偏差 (X - mu)^2 上，它永遠非負——正適合馬可夫。而這個平方偏差的期望值，依定義就是變異數 Var[X]。對 (X - mu)^2 以門檻 k^2 走一遍馬可夫，就得到這個乾淨的結論：X 偏離平均達 k 個標準差以上的機率，至多是 1/k^2。用符號寫，sigma 為標準差，則 Pr[ |X - mu| >= k*sigma ] <= 1/k^2。
注意這次升級。馬可夫的界像 1/a 那樣縮小——很慢。柴比雪夫的界像 1/k^2 那樣縮小——是平方級的。偏離 10 個標準差的機率至多 1/100，偏離 100 個至多 1/10000。換取這個更銳利的界所付的代價是：你必須知道（或界定）變異數，而它通常比平均值更難算。但這裡有個與期望值線性性質相親的性質：當你的量是一堆互相獨立的指示變數之和時，變異數也會相加，所以變異數往往仍然算得出來。
切爾諾夫：當許多硬幣各自獨立地翻動
切爾諾夫界是重型火炮，它適用於一個非常常見的特例：當 X 是一堆獨立的 0/1 變數之和時——正是期望值線性性質最愛的那種指示變數和。想像翻 n 枚有偏的硬幣，令 X 數出正面的次數，平均為 mu = E[X]。切爾諾夫說：X 超出其平均哪怕只是一個適度比例的機率，衰減的速度不是多項式級，而是隨 mu 指數級衰減。一個代表性的形式：對 0 < delta <= 1，Pr[ X >= (1 + delta) * mu ] <= exp( - delta^2 * mu / 3 )，並有一個對稱的界管「遠低於平均」的情況。
Bounding Pr[X >= a] for X = sum of independent 0/1 vars, mean mu: Markov : Pr[X >= a] <= mu / a (shrinks like 1/a) Chebyshev : Pr[|X - mu| >= k*sigma] <= 1 / k^2 (shrinks like 1/k^2) Chernoff : Pr[X >= (1+delta)*mu] <= exp(-delta^2*mu/3) (shrinks like e^-mu) More assumptions ==> much sharper bound.
用數字感受差別。翻 n = 100 枚公平硬幣，所以 mu = 50。拿到至少 75 個正面（delta = 1/2）的機率是多少？柴比雪夫用變異數 25、故 sigma = 5，把 75 放在離平均 5 個標準差處，給出 1/25 = 0.04 的界——已經很小。切爾諾夫給出約 exp(-(1/4)(50)/3) = exp(-4.17)，約 0.015，而且隨 n 增長收緊得快如疾風：在 n = 10000 時，同樣的相對超出比例會變得天文數字級地不可能。正是這種指數級衰減，讓我們能說一個蒙地卡羅演算法不只是平均正確，而是以壓倒性的機率正確。
誠實看待這份威力的代價：切爾諾夫帶著一個馬可夫與柴比雪夫都不需要的實在假設。那些 0/1 變數必須互相獨立（或至少是負相關的）。若你的指示變數糾纏在一起——比方說，它們描述某些桶是否超載，而一個桶滿了會讓另一個更可能是空的——那麼基本的切爾諾夫界可能根本不適用。獨立性，就是換取那個指數的代價。這恰是期望值線性性質的誠實對照：線性性質完全不需要獨立性；而在這裡，更強的結論要求更強的前提。
把尾界化為一個保證
尾界不只是裝飾；它正是讓「期望時間」結果變成「高機率」結果的方式。拿隨機快速排序為例，我們知道它的期望執行時間是 O(n log n)。它的最壞情況仍然是 Theta(n^2)——這一點永遠不會消失，因為一連串不走運的樞紐選擇總是有可能發生。但尾界讓我們得以證明：那些不走運的情形稀有到趨近於無——可以證明，隨機快速排序以 O(n log n) 時間執行，不僅是平均如此，而是以至少 1 - 1/n 的機率如此，因此連「稍微變糟」的機會都隨輸入變大而縮小。
- 把你害怕的那個量（執行時間、錯誤數、最大負載）寫成指示隨機變數之和，就像上一篇教的那樣。
- 用期望值的線性性質算出它的期望值——這給了你用來衡量偏差的中心。
- 挑選仍然夠用的最弱工具：只知道平均就用馬可夫，能界定變異數就用柴比雪夫，各項獨立且需要指數級小的尾端就用切爾諾夫。
- 讀出失敗機率，若它還不夠小，就獨立地重複執行演算法、再合併多次結果，把它逼向零。
最後那一步，正是隨機演算法的引擎。一個正確機率只有比方說 2/3 的蒙地卡羅演算法聽起來搖搖欲墜——但獨立地跑 k 次、取多數決，再對「正確次數」套一個切爾諾夫界，就能證明多數決出錯的機率隨 k 指數級地小。寥寥幾次重複，就能把三分之一的錯誤率壓到十億分之一以下。這就是機率放大，而它之所以嚴謹，正是因為一個尾界擔保了那個走運的多數會以壓倒性的姿態出現。
在你攀向接下來幾篇時，請守住一個誠實的觀點。尾界從不廢除壞情況——隨機快速排序的 Theta(n^2) 最壞情況仍然真的可能發生，只是機率天文數字級地小。尾界買到的，是一個關於「有多不可能」的精確、可證明的承諾。這就是隨機化整筆交易的本質：你用一個硬性的最壞情況保證，換來一個機率性的保證，而這個保證——多虧了馬可夫、柴比雪夫與切爾諾夫——能被做到任你願意付出多少次重複、就有多接近確定。