概率分析

概述

概率分析（Probabilistic Analysis）是利用概率论分析算法期望运行时间的方法。其核心工具是指示器随机变量和期望的线性性。即使算法本身是确定性的，只要输入服从某种概率分布，就可以使用概率分析。概率分析不同于随机化算法——前者分析输入的随机性，后者在算法中引入随机性。

定义

概率分析（Probabilistic Analysis）

概率分析是在假设输入服从某种概率分布的前提下，分析算法的期望性能。它不修改算法本身，而是对输入建立概率模型。

核心工具：

1. 指示器随机变量（Indicator Random Variable）：对事件 $A$，定义

$I_A=\{\begin{array}{ll}1& \text{若事件 }A\text{ 发生}\\ 0& \text{若事件 }A\text{ 不发生}\end{array}$

则 $E[I_A]=\mathrm{Pr}[A]$。

2. 期望的线性性：对任意随机变量 $X_1,X_2,\dots ,X_n$（不必独立）：

$E\left[{\sum }_{i=1}^n{X}_i\right]={\sum }_{i=1}^{n}E[X_i]$

核心性质

性质	描述	备注
期望的线性性	和的期望等于期望之和，不要求独立性	概率分析中最常用的工具
指示器随机变量	将复杂事件的计数分解为简单事件的期望之和	大大简化分析过程
输入分布假设	需要对输入的概率分布做出假设	不同分布可能导致不同的期望复杂度
期望 vs 最坏	期望时间是平均情况，最坏时间是上界	期望时间通常优于最坏时间

应用场景

• 随机化快速排序：

  • 假设所有排列等概率出现，或使用随机 pivot
  • 期望比较次数 $2n\ln n+O(n)=O(n\log n)$
  • 通过指示器随机变量分析：$X_{ij}$ 表示 $z_i$ 与 $z_j$ 是否比较，$E[X_{ij}]=2/(j-i+1)$

• 哈希表：

  • 简单均匀散列假设下，成功搜索的期望时间为 $O(1+\alpha )$（$\alpha$ 为装载因子）
  • 不成功搜索的期望时间为 $O(1+\alpha )$

• 雇佣问题：面试 $n$ 个候选人，期望雇佣次数为 $H_n=\ln n+O(1)$

概率分析 vs 摊还分析

比较维度	概率分析	摊还分析
是否使用概率	是	否
分析对象	单次操作的期望代价	操作序列的平均代价
假设	输入服从概率分布	不假设输入分布
保证	期望意义下的保证	最坏情况下的平均保证

参见

• 期望值 — 概率分析的数学基础
• 快速排序 — 概率分析的经典应用
• 散列表 — 哈希表性能的概率分析
• 蒙特卡洛方法 — 随机化算法的一种范式
• 伯努利试验 — 概率分析中的基本概率模型
• 摊还分析 — 不使用概率的另一种平均分析技术