指示器随机变量

概述

指示器随机变量是一种取值仅为 0 或 1 的离散随机变量，用于将事件的发生与否转化为可计算的数学对象，是算法概率分析中最基础的工具之一。

定义

指示器随机变量

对于与一次试验相关的事件 $A$ ，关联的指示器随机变量 $I {A}$ 定义为： $I {A} = {10 如果事件 A 发生如果事件 A 不发生$

期望等于概率（引理 5.1）： $E [I {A}] = P r {A}$ 。这是指示器随机变量最重要的性质，直接将概率问题转化为期望计算。
期望的线性性不需要独立性：即使多个指示器随机变量之间存在依赖关系，它们的期望之和仍然等于各自期望的和。这一性质使得我们可以在不计算联合分布的情况下分析复杂算法。
方差的计算： $V a r (I {A}) = P r {A} (1 - P r {A})$ ，因为 $I {A}$ 服从参数为 $P r {A}$ 的伯努利分布。
求和的期望：若 $X_{A} = \sum_{i} I {A_{i}}$ ，则 $E [X_{A}] = \sum_{i} P r {A_{i}}$ ，无论事件 $A_{i}$ 之间是否独立。