為了最後十天的內容，我們今天先來聊一下隨機演算法。絕對不是拖台前，絕對不是，絕對（被拖走）。

假想一下，我們有真正的隨機位元產生器。每詢問一次這個產生器，拿到 0 和拿到 1 的機率保證都是 0.5。有了這個公正的位元產生器，我們就可以進行丟隨機銅板的實驗了。假設我們丟 N 枚公正的銅板，令 X1, … XN 表示每一次丟銅板的結果：1 表示人頭朝上、0 表示背面朝上。令 X = X1+X2+...+XN，通常在機率的世界裡面我們會令 µ = E[X] 表示 X 的期望值，在這個例子中會是個精準的 N/2。

期望值與實驗

實際丟銅板的結果自然不會每次都 N/2： µ = N/2 只是說如果你進行無窮多次實驗，那麼逐次平均起來的結果會趨近於 N/2。想像一下：如果你交錯地不斷反覆實驗（每次實驗丟 N 個銅板）出現 0, N, 0, N, …, 這樣平均起來也是 N/2，但顯然不會符合你的直覺，畢竟這些銅板是機率上獨立被丟出的。

Chernoff Bounds

那我們該如何刻劃「其實 N 很大的話，實驗結果真的會很接近 N/2 唷」呢？事實上這件事情會牽涉到另一個機率上的觀念：集中性 (Concentration)。而事實上，我們對於丟銅板問題而言，只能說「其實 N 很大的話，實驗結果會有極高的機率 X 的值會落在 (0.5-ε)N 和 (0.5+ε)N 之間唷」而這個極高的機率，大概會是與 N 呈現指數遞減的（也就是說：如果你希望達到 1-δ 的正確率的話，你只需要進行 N=ϴ(log(1/δ) / ε) 次的實驗就行了～

以上的機率論述我們統稱為 Chernoff Bounds。

這東西有什麼有趣的地方呢？讓我們回想一下基於隨機挑選衛兵 (pivot) 的快速排序法。傳統的證明僅能利用期望值的線性組合性質，得出快速排序法的期望遞迴深度是 O(log n)，這個會導出快速排序法的期望時間複雜度是 O(n log n)。但我們可以利用 Chernoff Bounds 證明「有很高的機率，該演算法執行時所有遞迴深度都不超過 24 log n」，而這個很高的機率是至少 1 - 1/n^2，很酷吧！