期望執行時間究竟是什麼意思
上一篇導覽把隨機演算法分成兩個陣營：拉斯維加斯演算法 永遠回傳正確答案，但它的執行時間是個隨機變數；而 蒙地卡羅演算法 在固定時間內執行完，但它的答案只是以高機率正確。在這兩個世界裡，我們都需要「一個數」來總結一個隨機量——它傾向跑多久，或它傾向失敗幾次。那個數就是 期望值，而學會好好計算它，正是分析隨機演算法的絕大部分內容。
隨機變數 X 不過是一個取決於那些硬幣的數：在固定輸入上的執行時間、比較次數、遞迴的深度。它的期望值 E[X] 是它所有可能取值的加權平均，每個值以它出現的機率為權：E[X] = 對所有結果 v 取 (v 乘以 Pr[X = v]) 的和。具體地說，若某程序以機率 1/2 花 10 步、以機率 1/2 花 30 步，則 E[X] = 10 乘以 1/2 + 30 乘以 1/2 = 20。期望值是一個平衡點，不是一個保證——X 自己可能永遠不等於 20。
讓一切變簡單的那條規則
這裡是整輪的主力——期望值的線性性質。對任意隨機變數 X 與 Y、任意常數 a 與 b，E[a*X + b*Y] = a*E[X] + b*E[Y]。用白話說：一個和的期望值，永遠等於各期望值的和。你可以把一個複雜的隨機總量拆成幾塊，分別對每一塊取期望值，再把答案加回去。
令人驚奇的部分——也是這條規則如此強大的原因——就是「永遠」這個詞。即使 X 與 Y 糾纏在一起、即使知道其一就能完全知道另一個、即使它們正相關或負相關，線性性質依然成立。把這和變異數、或和 E[X*Y] 比一比，那些都需要獨立性才能漂亮地拆開。獨立性是個強而脆弱的假設，隨機演算法很少滿足它；線性性質卻什麼都不要求。這道落差，正是它幾乎出現在你從此會遇到的每一個分析裡的原因。
為何它能毫無附帶條件地成立？把各結果分組時，不是依 X 和 Y 各自的值來分，而是依「所有硬幣」底下那個完整的結果來分。在每一個個別結果上，(X + Y) 就字面上是該結果處的數 X 加上數 Y；把「值乘以機率」對所有結果求和，會乾淨地拆成 X 部分與 Y 部分，因為數的加法對加權和有分配律。相關性只影響「哪些」結果一同發生，從不影響在單一結果內把兩個數相加的算術——所以它無法破壞線性性質。
指示變數：靠把零與一相加來計數
當線性性質與 指示隨機變數 搭配時，它就變成一台計數機器。指示變數 I_A 在某事件 A 發生時為 1、不發生時為 0。它的期望值美妙地簡單：E[I_A] = 1*Pr[A] + 0*Pr[不是 A] = Pr[A]。所以一個指示變數的期望值「就是」它那個事件的機率。這個微小的事實，是把機率轉換成期望計數的橋樑。
這個你會不斷重用的標準招式，有三個節拍。把你在意的量寫成一個指示變數的「和」，每個可能被計數的東西配一個。取期望值，讓線性性質把它滑進和裡面。現在你只需要每一個個別的機率 Pr[A_i]，那通常很容易，然後把它們加起來——不需獨立性、不需聯合分佈、毫不費事。
X = I_1 + I_2 + ... + I_n where I_i = 1 if event A_i occurs, else 0
E[X] = E[I_1] + ... + E[I_n] (linearity, no independence needed)
= Pr[A_1] + ... + Pr[A_n] (E of an indicator = probability)一個乾淨的暖身：把 n 張相異的卡牌均勻隨機洗牌；有幾張會落在它原本的位置（一個「不動點」）？令 I_i 指示卡 i 留在原位。由對稱性，Pr[卡 i 不動] = 1/n，因為它同樣可能落到任何地方。所以 E[不動點數] = 對 i 從 1 到 n 取 1/n 的和 = 1，無論 n 多大。這裡的指示變數「並不」獨立——固定一張卡會稍微改變其他卡的機率——但線性性質從沒在意，答案恰好就是 1。
一個真實例子：隨機快速排序裡的比較次數
現在來收成。考慮 隨機快速排序，它在每次遞迴呼叫時均勻隨機挑選樞紐。我們想要比較次數的期望值。這個漂亮的分析根本不寫遞迴關係式——它用指示變數直接計數。在心裡把那些值排序成 z_1 < z_2 < ... < z_n，令 I_ij 指示 z_i 與 z_j 在整個執行過程中是否曾被比較。總比較次數 X = 對所有 i < j 的配對取 I_ij 的和，所以 E[X] = 對各配對取 Pr[z_i 與 z_j 被比較] 的和。
整個巧妙之處都在一個機率裡。兩個元素 z_i 與 z_j 被比較，恰好發生在它們其中之一比任何嚴格介於它們之間的元素「更早」被選為樞紐時。看那一段值 z_i, z_(i+1), ..., z_j——那是 j - i + 1 個元素。它們之中第一個被選為樞紐的那個，決定了一切：若它是 z_i 或 z_j，這一對就被比較；若它是中間某一個，那個樞紐就把 z_i 與 z_j 分到不同的兩側，它們從此再不相遇。這 j - i + 1 個各自同樣可能是第一個樞紐，所以 Pr[被比較] = 2/(j - i + 1)。
把那些機率加總，現在純粹是算術。E[X] = 對 i<j 取 2/(j-i+1) 的和；按間距 j - i 把各項收攏，得到一串分數 2/2 + 2/3 + 2/4 + ...，跨所有配對加總起來，總和小於 2*n 乘以調和數 H_n。既然 H_n 約為 ln n，這就是 O(n log n)。那正是隨機快速排序著名的期望界——只用指示變數與線性性質導出，不需要 期望值遞迴，也不需要主定理。
陷阱，以及期望值不告訴你的事
線性性質很穩固，但有兩個陷阱會逮住初學者。其一，線性性質是給「和」的，不是給乘積的：一般而言 E[X*Y]「不」等於 E[X]*E[Y]。那種拆解需要 X 與 Y 獨立，而演算法裡多數隨機變數並不獨立。其二，函數的期望值不是期望值的函數——E[1/X] 通常不等於 1/E[X]，E[X^2] 也不等於 E[X]^2（兩者之差恰好就是變異數）。只有當你手上是一個誠實的和時，才去用線性性質。
還有一個值得內化的更深限制：期望值是單一個數，而單一個數能藏住巨大的散佈。一張期望獎金一元的彩券，可能幾乎總是賠零、百萬次裡中一次發大財。所以隨機快速排序的 E[X] = O(n log n)，告訴你的是「平均」行為，不是說壞的執行很罕見。要主張「執行時間以高機率落在 n log n 的常數倍之內」，你需要一個集中結果——一個尾界——那正是下一篇導覽用馬可夫、柴比雪夫與 切爾諾夫界 所要建立的。
即便如此，期望值常常就是你所需要的全部，而且不只用於計時。同樣的指示變數招式，能估計 通用雜湊 下一個雜湊表會碰到幾個桶、能界定 卡格最小割 一次執行成功前的期望嘗試次數，並支撐著組合學裡整套機率方法：若「壞」物件的期望數低於 1，那麼必有某個結果其壞物件數為零，這就證明了一個好的配置必定存在。一條關於把平均相加的規則，一再地套用，扛起了隨機演算法這門課相當可觀的一部分。