計數期望值的指示變數技巧

機率裡許多計數問題問的是「平均有多少？」——多少人生日相同、多少封信落進正確的信封、丟球後有多少空箱子。計算這種計數的完整分布常是惡夢。指示變數技巧繞過整個分布，幾乎免費地得到期望的計數。

指示變數是最簡單的隨機變數：一個 1/0 開關，若某事件發生就等於 1、不發生就等於 0。它的期望值美得乾淨——E[A 的指示] = 1 P(A) + 0 P(非 A) = P(A)。一個指示變數的期望值就是它事件的機率。訣竅是：把你的計數寫成指示變數之和，每個可能被數到的東西一個。那麼由期望值的線性性，期望的計數就只是那些機率之和。用白話的步驟：(1) 對每個項目 i，定義 I_i = 1 若項目 i 被數到、否則為 0；(2) 總計數是 X = I_i 之和；(3) E[X] = E[I_i] 之和 = P(項目 i 被數到) 之和。

神奇之處在於期望值的線性性不需要獨立性，所以這些指示變數可以用複雜的方式糾纏在一起，完全沒關係——你永遠不必把它們解開。想要 n 個項目的一次隨機排列中固定點的期望數目？每個位置有 1/n 的機率是固定的，共有 n 個位置，所以固定點的期望數目是 n 乘以 1/n = 1，與 n 無關，即使「位置 i 是固定的」這些事件彼此相依。這一個想法用一行就破解了生日問題、配對（領帽）問題以及無數其他問題。