期望值的線性性質（linearity of expectation）

假設一群朋友各自點餐，你想知道帳單總額的期望。你不需要知道他們的點餐是否相關——某人點甜點是否會讓另一人更可能點。你只要把每個人的期望花費加起來就好。期望值的線性性質正是這個日常動作：和的期望值等於各期望值之和，無論各部分彼此如何相依。

精確地說：對任意隨機變數 X 與 Y，E[X + Y] = E[X] + E[Y]，更一般地 E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + ... + E[Xn]，再加上對常數 c 有 E[cX] = c E[X]。令人驚訝的是這不需要獨立性——即使變數彼此糾纏很深它仍成立。兩變數之和的標準證明：對結果取平均，E[X+Y] = 對所有結果求和：Σ (X+Y) 乘以其機率，再把這個和拆成 X 的部分與 Y 的部分。它在演算法中的威力來自把一個複雜的計數拆成許多微小指示變數之和（每個事件一個），各取其容易的期望，再相加。例如隨機排列中不動點數目的期望：令 X_i 在第 i 項留在原位時為 1，於是 E[X_i] = 1/n；不動點總數的期望為 Σ_{i=1}^{n} 1/n = 1，即使這些 X_i 並不獨立。

這個單一工具悄悄驅動了大部分隨機分析：隨機快速排序的期望比較次數、雜湊碰撞的期望數目、最長連段的期望長度，全都靠把指示變數相加而得。它之所以重要，是因為就計算平均值而言，它完全繞過了機率中最難的部分——相依性。誠實的提醒：線性只算出平均值；它對變異數或偏離平均多遠的機率隻字不提。那要靠像馬可夫、切比雪夫或切爾諾夫這樣的尾界，而它們反過來常常確實需要獨立性。