期望的线性性

概述

期望的线性性 是概率论中一个强大且基础的定理：无论随机变量之间是否独立，它们的和的期望等于期望的和。这一性质是算法概率分析中最核心的数学工具。

定义

期望的线性性

对于任意两个随机变量 $X$ 和 $Y$（无论是否独立），有： $E[X+Y]=E[X]+E[Y]$ 更一般地，对于 $n$ 个随机变量 $X_1,X_2,\dots ,X_n$： $E\left[{\sum }_{i=1}^n{X}_i\right]={\sum }_{i=1}^{n}E[X_i]$ 这一性质不要求随机变量之间相互独立。

核心性质

• 独立性不是必要条件：这是期望线性性最强大的特征。即使随机变量之间存在复杂的依赖关系，期望的线性性仍然成立。这使得我们可以在不知道联合分布的情况下计算期望。
• 与指示器随机变量的天然配合：将复杂随机变量分解为若干指示器随机变量之和，再利用期望的线性性求和，是算法分析的标准范式。
• 期望的齐次性：对于任意常数 $c$，$E[cX]=cE[X]$。
• 方差不具备线性性：$Var(X+Y)=Var(X)+Var(Y)+2Cov(X,Y)$，只有当 $X$ 和 $Y$ 不相关时才有 $Var(X+Y)=Var(X)+Var(Y)$。

章节扩展

第5章：概率分析与随机化算法

• 5.2 指示器随机变量 利用期望的线性性分析雇佣问题，将总费用表示为指示器随机变量之和。
• 期望的线性性是 概率分析 的核心数学基础。

第7章：快速排序

• 7.4 快速排序的分析 将快速排序的总比较次数分解为指示器随机变量之和，利用期望的线性性推导出 $O(n\lg n)$ 的期望运行时间。

第8章：线性时间排序

• 8.4 桶排序 使用期望的线性性分析每个桶中元素个数的期望值。

参见

• 指示器随机变量
• 概率分析