附录 C 计数与概率 (Counting and Probability)

核心结论

计数基础：加法原理（不交并）、乘法原理（笛卡尔积）、k-字符串、k-排列 \(n!/(n-k)!\)、k-组合（二项式系数）\(\binom{n}{k} = n!/(k!(n-k)!)\)。
二项式系数性质：对称性 \(\binom{n}{k} = \binom{n}{n-k}\)、Pascal 恒等式、加法恒等式；上下界（式 C.5, C.6）——是组合数学的核心工具。
概率公理：\(\Pr\{A\} \geq 0\)、\(\Pr\{S\} = 1\)、可加性（互斥事件）；推出补事件、合并公式、Boole 不等式。
条件概率与独立性：\(\Pr\{A \mid B\} = \Pr\{A \cap B\} / \Pr\{B\}\)；独立 ⟺ \(\Pr\{A \cap B\} = \Pr\{A\} \Pr\{B\}\)；pairwise vs mutually independent 不同。
Bayes 定理：\(\Pr\{A \mid B\} = \Pr\{A\} \Pr\{B \mid A\} / \Pr\{B\}\)；式 C.18 全概率形式——更新先验为后验。
期望与方差：线性性 \(E[X + Y\) = E[X] + E[Y]]（无论独立）；独立时乘积；Jensen 不等式（凸函数）；方差 \(\text{Var}[X\) = E[(X - \mu)^2]]；标准差。
Bernoulli 试验：二项分布 \(B(n, p)\)、几何分布 \(\text{Geom}(p)\)；第 5 章「指示随机变量」是核心技术。

附录主旨

本附录是随机算法分析（第 5 章雇用问题、12 章随机 BST、第 26 章最大流随机化、第 27 章并行随机算法等）的数学基础。计数工具（排列组合、二项式系数）用于「量化事件空间」；概率公理与条件概率用于「建模不确定性」；期望与方差用于「分析随机算法平均情况」。掌握这些工具后，第 5 章雇用问题（指示变量 + 期望线性）、第 7 章 quicksort 平均时间（调和数 + 几何分布）等分析才会变得自然。

一、核心概念

本附录围绕 6 个核心概念展开：基本计数、二项式系数、概率公理、条件概率与独立性、Bayes 定理、期望与方差。

概念	定义 + 重要性	实现提示
加法与乘法原理	加法：不交并的势 = 各部分之和；乘法：笛卡尔积的势 = 各因子之积。	§C.1；所有计数的基石。
排列与组合	k-排列 \(P(n, k) = n!/(n-k)!\)；k-组合（二项式系数）\(\binom{n}{k} = n!/(k!(n-k)!)\)。	§C.1；式 C.1, C.2。
二项式系数性质	对称性、Pascal 恒等式、上下界（式 C.5, C.6）；二项展开（式 C.4）。	§C.1；分析「组合选择」类问题必备。
概率公理与基本运算	三条公理；不交并、补、合并公式（式 C.12, C.13）；Boole 不等式（式 C.19）。	§C.2；离散概率空间的基础。
条件概率与独立性	\(\Pr\{A \mid B\} = \Pr\{A \cap B\}/\Pr\{B\}\)（式 C.14）；独立 vs mutually independent vs pairwise independent。	§C.2；Bayes 定理是特例。
期望与方差	期望定义、线性性、Jensen 不等式、方差、独立性下乘积分解。	§C.3；第 5 章指示随机变量是核心技术。
Bayes 定理	\(\Pr\{A \mid B\} = \Pr\{A\}\Pr\{B \mid A\} / \Pr\{B\}\)；式 C.18 全概率形式。	§C.2；后验概率更新。
二项与几何分布	二项 \(B(n, p)\)（n 次独立成功/失败试验）；几何 \(\text{Geom}(p)\)（首次成功时间）。	§C.4；常用分布。

概念

定义 + 重要性

实现提示

加法与乘法原理

加法：不交并的势 = 各部分之和；乘法：笛卡尔积的势 = 各因子之积。

§C.1；所有计数的基石。

排列与组合

k-排列 \(P(n, k) = n!/(n-k)!\)；k-组合（二项式系数）\(\binom{n}{k} = n!/(k!(n-k)!)\)。

§C.1；式 C.1, C.2。

二项式系数性质

对称性、Pascal 恒等式、上下界（式 C.5, C.6）；二项展开（式 C.4）。

§C.1；分析「组合选择」类问题必备。

概率公理与基本运算

三条公理；不交并、补、合并公式（式 C.12, C.13）；Boole 不等式（式 C.19）。

§C.2；离散概率空间的基础。

条件概率与独立性

\(\Pr\{A \mid B\} = \Pr\{A \cap B\}/\Pr\{B\}\)（式 C.14）；独立 vs mutually independent vs pairwise independent。

§C.2；Bayes 定理是特例。

期望与方差

期望定义、线性性、Jensen 不等式、方差、独立性下乘积分解。

§C.3；第 5 章指示随机变量是核心技术。

Bayes 定理

\(\Pr\{A \mid B\} = \Pr\{A\}\Pr\{B \mid A\} / \Pr\{B\}\)；式 C.18 全概率形式。

§C.2；后验概率更新。

二项与几何分布

二项 \(B(n, p)\)（n 次独立成功/失败试验）；几何 \(\text{Geom}(p)\)（首次成功时间）。

§C.4；常用分布。

二、详细笔记

2.1 加法原理与乘法原理

What：加法原理说「若 A 与 B 不相交，则 \(\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert\)」；乘法原理说「\(\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert\)」。

Why：把复杂计数问题分解为不交子集（加法）或有序选择（乘法），是最基本的组合计数策略。

How：

场景	用法
选 A 或 B（A, B 互斥）	加法
选 A 且选 B	乘法
排列（顺序有关）	乘法
组合（顺序无关）	除以顺序数

场景

用法

选 A 或 B（A, B 互斥）

加法

选 A 且选 B

乘法

排列（顺序有关）

乘法

组合（顺序无关）

除以顺序数

When：所有「分类」「枚举」问题。

Example：车牌每位置是字母（26）或数字（10），6 位：每位置 36 种，6 位总 = \(36^6\)。

2.2 排列与组合

What：从 n 个元素中有序选取 k 个（排列）或无序选取 k 个（组合）是两种最基本的离散计数模式。

k-排列：从 n 元素中有序选 k 个，不重复：\(P(n, k) = n(n-1)\cdots(n-k+1) = n!/(n-k)!\)（式 C.1）
k-组合：从 n 元素中无序选 k 个：\(\binom{n}{k} = n!/(k!(n-k)!)\)（式 C.2）

Why：排列组合是几乎所有离散计数问题的「词汇」。

How：

概念	计数
n-排列	\(n!\)
n-字符串	\(\lvert \Sigma \rvert^n\)
k-排列	\(n!/(n-k)!\)
k-组合	\(\binom{n}{k} = n!/(k!(n-k)!)\)
0-组合	1（空集）

概念

计数

n-排列

\(n!\)

n-字符串

\(\lvert \Sigma \rvert^n\)

k-排列

\(n!/(n-k)!\)

k-组合

\(\binom{n}{k} = n!/(k!(n-k)!)\)

0-组合

1（空集）

When：建模「选择」「排序」「子集」类问题。

Example：4 元素集 {a,b,c,d} 的 2-排列数 = 12，2-组合数 = 6。

2.3 二项式系数

What：\(\binom{n}{k}\) 满足对称性（式 C.3）、Pascal 恒等式（练习 C.1-7）：\(\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\)；上下界（式 C.5, C.6）。

Why：二项式系数连接组合学与概率（二项分布）、算法分析（quicksort 平均情况、随机抽样）等。

How：

性质	公式
对称性	\(\binom{n}{k} = \binom{n}{n-k}\)
Pascal 恒等式	\(\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\)
上界（式 C.5）	\(\binom{n}{k} \leq (en/k)^k\)
上界（式 C.6）	\(\binom{n}{k} \leq n^n / (k^k (n-k)^{n-k})\)
二项展开（式 C.4）	\((x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}\)
特殊	\(\sum_{k=0}^n \binom{n}{k} = 2^n\)

性质

公式

对称性

\(\binom{n}{k} = \binom{n}{n-k}\)

Pascal 恒等式

\(\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\)

上界（式 C.5）

\(\binom{n}{k} \leq (en/k)^k\)

上界（式 C.6）

\(\binom{n}{k} \leq n^n / (k^k (n-k)^{n-k})\)

二项展开（式 C.4）

\((x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}\)

特殊

\(\sum_{k=0}^n \binom{n}{k} = 2^n\)

When：分析「组合数规模」「二项分布尾概率」「n 选 k」类问题。

Example：\(\binom{2n}{n} = 2^{2n} / \sqrt{\pi n} \cdot (1 + O(1/n))\)（式 C.10，Stirling 近似）。

2.4 概率公理与基本性质

What：概率分布 \(\Pr\{\cdot\}\) 满足三条公理： 1. 非负性：\(\Pr\{A\} \geq 0\) 2. 归一化：\(\Pr\{S\} = 1\) 3. 可加性：互斥事件 \(\Pr\{A \cup B\} = \Pr\{A\} + \Pr\{B\}\)

Why：所有概率论的基础；从中推出补事件、合并公式（式 C.12, C.13）、Boole 不等式（式 C.19）。

How：

性质	公式
空事件	\(\Pr\{\emptyset\} = 0\)
补事件	\(\Pr\{\bar{A}\} = 1 - \Pr\{A\}\)
合并（一般）	\(\Pr\{A \cup B\} = \Pr\{A\} + \Pr\{B\} - \Pr\{A \cap B\}\)（式 C.12）
上界	\(\Pr\{A \cup B\} \leq \Pr\{A\} + \Pr\{B\}\)（式 C.13）
离散概率	\(\Pr\{A\} = \sum_{s \in A} \Pr\{s\}\)
均匀分布	\(\Pr\{s\} = 1/\lvert S \rvert\) for each s
连续均匀	\(\Pr\{[c, d\)\} = (d-c)/(b-a)] for \(c, d \in [a, b\)]

性质

公式

空事件

\(\Pr\{\emptyset\} = 0\)

补事件

\(\Pr\{\bar{A}\} = 1 - \Pr\{A\}\)

合并（一般）

\(\Pr\{A \cup B\} = \Pr\{A\} + \Pr\{B\} - \Pr\{A \cap B\}\)（式 C.12）

上界

\(\Pr\{A \cup B\} \leq \Pr\{A\} + \Pr\{B\}\)（式 C.13）

离散概率

\(\Pr\{A\} = \sum_{s \in A} \Pr\{s\}\)

均匀分布

\(\Pr\{s\} = 1/\lvert S \rvert\) for each s

连续均匀

\(\Pr\{[c, d\)\} = (d-c)/(b-a)] for \(c, d \in [a, b\)]

When：所有涉及概率建模的场景；很多公式直接由公理 + 集合论推出。

Example：抛两硬币，至少一个正面：\(\Pr\{\text{HH, HT, TH}\}\) = 3/4；或用补事件：\(1 - \Pr\{\text{TT}\}\) = 3/4。

2.5 条件概率与独立性

What：本节讨论三类「有先验信息」或「无信息」情况下的概率工具。

条件概率：\(\Pr\{A \mid B\} = \Pr\{A \cap B\}/\Pr\{B\}\)（式 C.14）
独立：\(\Pr\{A \cap B\} = \Pr\{A\} \Pr\{B\}\)（式 C.15）；等价于 \(\Pr\{A \mid B\} = \Pr\{A\}\)
互独立（mutually independent）：每个 k 子集的交的概率等于各概率之积（k ≥ 2）

Why：很多随机过程「部分信息已知」需用条件概率；独立性是简化分析的关键假设。

How：

概念	关键点
条件概率	已知 B 发生后重规范化样本空间
独立	信息 B 不改变 A 的概率
pairwise independent	每对独立
mutually independent	每子集独立（更强）

概念

关键点

条件概率

已知 B 发生后重规范化样本空间

独立

信息 B 不改变 A 的概率

pairwise independent

每对独立

mutually independent

每子集独立（更强）

反例：两硬币事件「正 1」「正 2」「两币不同」是 pairwise independent 但非 mutually independent（§C.2 例）。

When：随机算法的独立性假设；Bayesian 更新；信息论建模。

Example：抛两公平硬币：已知至少一个正面，两币都正面的条件概率 = 1/3。

2.6 Bayes 定理与全概率

What：Bayes 定理（式 C.17）：\(\Pr\{A \mid B\} = \Pr\{A\} \Pr\{B \mid A\} / \Pr\{B\}\)；展开分母为全概率（式 C.18）。

Why：「先验 × 似然 = 后验」——更新对未知事件 A 的信念基于新证据 B。

How：

形式	公式
基本	\(\Pr\{A \mid B\} = \Pr\{A\} \Pr\{B \mid A\} / \Pr\{B\}\)
全概率形式	\(\Pr\{A \mid B\} = \frac{\Pr\{A\} \Pr\{B \mid A\}}{\Pr\{A\} \Pr\{B \mid A\} + \Pr\{\bar{A}\} \Pr\{B \mid \bar{A}\}}\)
链式法则	\(\Pr\{A_1 \cap \cdots \cap A_n\} = \Pr\{A_1\} \prod_{i=2}^n \Pr\{A_i \mid A_1 \cap \cdots \cap A_{i-1}\}\)

形式

公式

基本

\(\Pr\{A \mid B\} = \Pr\{A\} \Pr\{B \mid A\} / \Pr\{B\}\)

全概率形式

\(\Pr\{A \mid B\} = \frac{\Pr\{A\} \Pr\{B \mid A\}}{\Pr\{A\} \Pr\{B \mid A\} + \Pr\{\bar{A}\} \Pr\{B \mid \bar{A}\}}\)

链式法则

\(\Pr\{A_1 \cap \cdots \cap A_n\} = \Pr\{A_1\} \prod_{i=2}^n \Pr\{A_i \mid A_1 \cap \cdots \cap A_{i-1}\}\)

When：从「先验 + 证据」推断「后验」；spam 分类、医学诊断、贝叶斯网络。

Example：公平硬币 + 偏向硬币各半选一，连续两次正面，偏向概率 = 4/5（§C.2 例）。

2.7 期望、方差、独立性

What：本节讨论随机变量的核心数字特征——期望、线性性、凸性、方差。

期望：\(E[X\) = \sum_x x \cdot \Pr\{X = x\}]（式 C.20）
线性性：\(E[X + Y\) = E[X] + E[Y]]（无论独立，式 C.21）
Jensen 不等式：凸函数 \(f\)，\(E[f(X)\) \geq f(E[X])]（式 C.26）
方差：\(\text{Var}[X\) = E[(X - \mu)^2] = E[X^2] - E[X]^2]
独立乘积：\(E[X_1 X_2 \cdots X_n\) = E[X_1] \cdots E[X_n]]（式 C.24）

Why：期望线性性是随机算法分析的「杀手锏」——常通过指示随机变量把复杂量分解为独立项求和。

How：

性质	公式
期望定义	\(E[X\) = \sum_x x \Pr\{X = x\}]（式 C.20）
线性性（和）	\(E[X + Y\) = E[X] + E[Y]]（式 C.21）
标量乘法	\(E[aX\) = a E[X]]（式 C.22）
线性组合	\(E[aX + Y\) = a E[X] + E[Y]]（式 C.23）
独立乘积	\(E[XY\) = E[X] E[Y]]（式 C.24）
Jensen	\(E[f(X)\) \geq f(E[X])] for convex f
自然数期望	\(E[X\) = \sum_{i=1}^\infty \Pr\{X \geq i\}]（式 C.25）
方差	\(\text{Var}[X\) = E[X^2] - (E[X])^2]
标准差	\(\sigma = \sqrt{\text{Var}[X\)}]

性质

公式

期望定义

\(E[X\) = \sum_x x \Pr\{X = x\}]（式 C.20）

线性性（和）

\(E[X + Y\) = E[X] + E[Y]]（式 C.21）

标量乘法

\(E[aX\) = a E[X]]（式 C.22）

线性组合

\(E[aX + Y\) = a E[X] + E[Y]]（式 C.23）

独立乘积

\(E[XY\) = E[X] E[Y]]（式 C.24）

Jensen

\(E[f(X)\) \geq f(E[X])] for convex f

自然数期望

\(E[X\) = \sum_{i=1}^\infty \Pr\{X \geq i\}]（式 C.25）

方差

\(\text{Var}[X\) = E[X^2] - (E[X])^2]

标准差

\(\sigma = \sqrt{\text{Var}[X\)}]

When：随机算法的平均情况分析；用指示变量技术分析复杂事件（§5.2）。

Example：抛两公平硬币，每正面 +3 元，每反面 -2 元，期望收益 = 6·1/4 + 1·1/2 - 4·1/4 = 1 元。

2.8 常用分布

What：本节给出三类最常见的概率分布——几何、二项、均匀。

几何分布 \(\text{Geom}(p)\)：首次成功时间 X，\(\Pr\{X = k\} = (1-p)^{k-1} p\)；\(E[X\) = 1/p]
二项分布 \(B(n, p)\)：n 次独立成功/失败试验的成功次数；\(E[X\) = np]、\(\text{Var}[X\) = np(1-p)]
均匀分布：连续 \(U[a,b\)]，\(E[X\) = (a+b)/2]

Why：随机算法分析中的「现成工具」——很多问题可化为几何分布或二项分布的尾概率。

How：

分布	关键性质
几何（首次成功）	期望 = 1/p，无记忆性
二项 B(n, p)	期望 = np，n=1 时为伯努利
泊松（极限）	二项 n→∞, p→0, np=λ
均匀连续	期望 = (a+b)/2

分布

关键性质

几何（首次成功）

期望 = 1/p，无记忆性

二项 B(n, p)

期望 = np，n=1 时为伯努利

泊松（极限）

二项 n→∞, p→0, np=λ

均匀连续

期望 = (a+b)/2

When：分析随机算法的迭代次数（几何）、成功次数（二项）、负载（均匀）。

Example：投公平硬币直到首次正面——几何分布，期望投掷次数 = 2。

三、关键图表

核心公式对照表

公式编号

内容

式 C.1

k-排列：\(P(n, k) = n!/(n-k)!\)

式 C.2

k-组合：\(\binom{n}{k} = n!/(k!(n-k)!)\)

式 C.3

对称性：\(\binom{n}{k} = \binom{n}{n-k}\)

式 C.4

二项展开：\((x+y)^n = \sum \binom{n}{k} x^k y^{n-k}\)

式 C.5

上界：\(\binom{n}{k} \leq (en/k)^k\)

式 C.6

上界：\(\binom{n}{k} \leq n^n / (k^k (n-k)^{n-k})\)

式 C.12

合并：\(\Pr\{A \cup B\} = \Pr\{A\} + \Pr\{B\} - \Pr\{A \cap B\}\)

式 C.13

合并上界：\(\Pr\{A \cup B\} \leq \Pr\{A\} + \Pr\{B\}\)

式 C.14

条件概率：\(\Pr\{A \mid B\} = \Pr\{A \cap B\}/\Pr\{B\}\)

式 C.15

独立：\(\Pr\{A \cap B\} = \Pr\{A\} \Pr\{B\}\)

式 C.17

Bayes：\(\Pr\{A \mid B\} = \Pr\{A\} \Pr\{B \mid A\} / \Pr\{B\}\)

式 C.18

Bayes 全概率形式

式 C.19

Boole 不等式：union ≤ sum

式 C.20

期望定义

式 C.21

期望线性性

式 C.24

独立乘积：\(E[X_1\cdots X_n\) = \prod E[X_i]]

式 C.25

期望（自然数）：\(E[X\) = \sum_{i \geq 1} \Pr\{X \geq i\}]

式 C.26

Jensen 不等式

四、思维导图

mindmap
  root((附录 C 计数与概率))
    计数基础
      加法乘法原理
      排列组合
      k-字符串
    二项式系数
      对称性
      Pascal恒等
      上下界
      二项展开
    概率公理
      三条公理
      离散连续
      补合并公式
    条件概率
      条件定义
      独立性
      pairwise与mutual
    Bayes定理
      基本形式
      全概率展开
      后验更新
    期望方差
      期望定义
      线性性
      独立乘积
      Jensen不等式
      方差标准差
    常用分布
      几何分布
      二项分布
      均匀分布

五、重点与易错点

组合数记号 \(\binom{n}{k}\)：当 k > n 时值为 0（不能选多于全部）；当 k = 0 或 k = n 时值为 1；这与「空组合」「全集组合」一致。
Pascal 恒等式 \(\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\)：两种证明——代数（展开 factorial）和组合（「指定元素是否在组合中」）；后者更直观。
概率的「连续」vs「离散」：连续情形不是所有子集都是事件（必须有有限/可数开闭区间结构）；离散情形所有子集都是事件。
条件概率的归一化：\(\Pr\{\cdot \mid B\}\) 本身是合法概率分布；忘记分母归一化是常见错误。
独立 vs 互斥：互斥 ⟹ \(\Pr\{A \cap B\} = 0\)，独立 ⟹ \(\Pr\{A \cap B\} = \Pr\{A\} \Pr\{B\}\)；两者不等价，互斥 + 独立仅当其中一个概率为 0。
pairwise vs mutually independent：pairwise 仅要求每对独立，mutual 要求每个子集独立；后者更强；反例：两硬币「正1」「正2」「不同」。
期望线性性无需独立：这是核心定理，比独立乘积分解弱（后者需要独立）；指示随机变量技术依赖此性质。
Jensen 不等式方向：凸函数 \(f\) 有 \(E[f(X)\) \geq f(E[X])]；凹函数方向相反；Markov、Chernoff 界都基于此。
几何分布的「无记忆性」：\(\Pr\{X > m + n \mid X > m\} = \Pr\{X > n\}\)——给定已等待 m 次仍失败的条件下，再等 n 次的条件分布与从头开始相同。
Bayes 定理易混淆：先验是 \(\Pr\{A\}\)（不知 B 时对 A 的信念）；似然是 \(\Pr\{B \mid A\}\)（A 为真时观察到 B 的概率）；后验是 \(\Pr\{A \mid B\}\)（看到 B 后对 A 的更新信念）。
Boole 不等式（union bound）：\(\Pr\{\bigcup A_i\} \leq \sum \Pr\{A_i\}\)；是概率分析最常用的「上界工具」，无需互斥假设。
样本空间的大小影响均匀分布概率：均匀分布下「事件概率 = 满足条件的结果数 / 总结果数」；如 7 张牌抽 3 张特定组合的概率 = 3/7（不是 3/21）。