指示器随机变量

概述

指示器随机变量（Indicator Random Variable）是对某个事件 $A$ 定义的取值为 0 或 1 的随机变量：$A$ 发生时取 1，否则取 0。其核心优势在于将事件的概率转化为期望，并利用期望的线性性简化复杂概率计算。

定义

形式化定义

给定样本空间 $\Omega$ 上的事件 $A$，对应的指示器随机变量 $I\{A\}$ 定义为： $I\{A\}=\{\begin{array}{ll}1& \text{若事件 }A\text{ 发生}\\ 0& \text{若事件 }A\text{ 不发生}\end{array}$

也常记为 $1_A$ 或 $X_A$。

核心性质

期望与概率的关系

$E[I\{A\}]=1\cdot P(A)+0\cdot P(\bar{A})=P(A)$

这是指示器随机变量最重要的性质：期望等于概率。因此，计算某个量的期望时，可以先将其表示为指示器随机变量之和，再利用期望的线性性。

方差

$\text{Var}(I\{A\})=E[I\{A{\}}^2]-(E[I\{A\}]{)}^2=P(A)-P(A{)}^2=P(A)(1-P(A))$

期望的线性性（核心优势）

关键性质

对任意随机变量 $X_1,X_2,\dots ,X_n$（不要求独立），都有： $E\left[{\sum }_{i=1}^n{X}_i\right]={\sum }_{i=1}^{n}E[X_i]$

这意味着即使事件之间有依赖关系，仍然可以通过分别计算每个指示器变量的期望再求和来得到总和的期望。

求和的指示器表示

若 $X={\sum }_{i=1}^{n}I\{A_i\}$，则：

• $E[X]={\sum }_{i=1}^{n}P(A_i)$
• $X$ 的值表示事件 $A_1,\dots ,A_n$ 中发生的事件个数

经典应用：随机化快速排序的期望比较次数

问题建模

对 $n$ 个元素的数组执行 RANDOMIZED-QUICKSORT，求期望的总比较次数。

分析步骤

1. 定义指示器变量 $X_{ij}=I\{z_i\text{ 与 }{z}_j\text{ 被比较}\}$，其中 $z_1\le z_2\le \cdots \le z_n$ 为排序后的元素
2. 总比较次数 $X={\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^n{X}_{ij}$
3. 计算单个期望：$E[X_{ij}]=P(z_i\text{ 与 }{z}_j\text{ 被比较})$
4. $z_i$ 与 $z_j$ 被比较，当且仅当在递归过程中，$z_i$ 或 $z_j$ 是 $z_i,z_{i+1},\dots ,z_j$ 中第一个被选为 pivot 的元素
5. 因此 $P(z_i\text{ 与 }{z}_j\text{ 被比较})=\frac{2}{j-i+1}$
6. 利用期望的线性性： $E[X]={\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^n\frac{2}{j-i+1}\le {\sum }_{k=2}^{n}n\cdot \frac{2}{k}=2n{\sum }_{k=2}^n\frac{1}{k}=O(n\ln n)$

应用场景

• 随机化快速排序分析：如上所述，证明期望比较次数为 $O(n\ln n)$
• 哈希表分析：分析链地址法和开放寻址法中的期望冲突次数、期望探查次数
• 雇佣问题（Hiring Problem）：分析面试 $n$ 个候选人后期望的雇佣次数
• 随机算法分析：任何需要计算”满足某条件的事件个数”的期望的场景

参见

• 布尔代数