概率论、数学期望与随机化算法 (Probability & Expectation)¶
概率论与数学期望是算法竞赛与工业级系统设计中极具思维美感的核心工具。在算法领域中，它不仅衍生出了概率动态规划与逆推期望动态规划，更是洗牌算法、蓄水池抽样、拒绝采样等现代海量数据处理技术的理论基石。
1. 概率与期望的数学基石¶
1.1 基础概念与条件概率¶
- 样本空间 \(\Omega\) 与事件：样本空间是随机试验所有可能结果的集合。每个子集称为一个随机事件。
- 全概率公式：设事件组 \(B_1, B_2, \dots, B_n\) 构成样本空间的一个划分，则对任意事件 \(A\)：
- 贝叶斯公式 (Bayes' Theorem)：已知结果推断原因的逆向概率：
1.2 数学期望与核心性质¶
离散随机变量 \(X\) 的数学期望（均值）定义为其可能取值与对应概率的加权和：
期望的线性性质 (Linearity of Expectation)¶
对于任意两个随机变量 \(X\) 和 \(Y\)（无论它们是否相互独立），均严格满足：
- 核心洞察：独立性并非期望线性的前提条件！这一极其优美的性质是求解复杂随机过程期望的核心破局利器。
指示变量法 (Indicator Variables)¶
对于某个特定事件 \(A\)，定义指示变量：
显然有 \(\mathbb{E}[I_A] = 1 \cdot P(A) + 0 \cdot P(\bar{A}) = P(A)\)。 当需要统计某个随机试验中某类事件发生发生的总次数 \(S = \sum I_{A_i}\) 时，直接利用线性性质拆解：
从而将复杂的联合期望转化为计算各个微观单项事件发生的概率之和！
2. 概率动态规划 (Probability DP)¶
概率 DP 用于计算某个系统在经历若干随机转移后，最终到达目标状态或满足特定性质的概率值。
2.1 顺推转移模型 (Forward DP)¶
- 状态设计：通常定义 \(dp[step][state]\) 表示在进行了 \(step\) 步后，系统处于状态 \(state\) 的概率；
- 初始化：初始状态设为 \(1.0\)（即 \(dp[0][start] = 1.0\)），其余不可达状态初值设为 \(0.0\)；
- 出度分流转移：当前状态以概率转移矩阵向下一阶段的所有后继状态扩散分配概率：
2.2 大数阈值截断分析 (以 LeetCode 808 分汤为例)¶
题目有四种等概率操作，每次分别消耗两种汤 \((100, 0), (75, 25), (50, 50), (25, 75)\) 毫升。 求汤 A 先分配完的概率加上同时分配完概率的一半。
-
期望漂移分析： 单次操作中，A 汤消耗量的期望值为 \((100 + 75 + 50 + 25) / 4 = 62.5\text{ ml}\)； B 汤消耗量的期望值为 \((0 + 25 + 50 + 75) / 4 = 37.5\text{ ml}\)。
-
大数定律截断： A 汤的消耗速度在期望上显著快于 B 汤。随着初始汤量 \(N\) 的增长，A 汤先被分完的概率以指数级速度向 \(1.0\) 收敛； 当 \(N \ge 4800\) 时，该概率与 \(1.0\) 的误差已经小于 \(10^{-5}\)（超过浮点精度允许阈值），因此对大数直接常数截断返回 \(1.0\)，使得 DP 只需在极小的状态空间 \([0, 200] \times [0, 200]\) 内运行记忆化搜索即可。
2.3 滑动窗口优化概率转移 (以 LeetCode 837 新 21 点为例)¶
玩家从 0 分开始抽取，只要分数小于 \(K\)，就等概率抽取 \([1, W]\) 分。求最终分数不超过 \(N\) 的概率。
- 逆推状态定义：\(dp[x]\) 表示当前分数为 \(x\) 时，最终获胜的概率；
- 边界条件：
- 当 \(x \ge K\) 时：游戏停止。若 \(x \le N\)，获胜概率为 \(1.0\)；若 \(x > N\)，失败概率为 \(0.0\)；
- 转移方程：当 \(x < K\) 时，从当前点等概率抽取 \(1 \sim W\)：
- 滑窗优化：求和项是长度为 \(W\) 的连续区间和。使用滑动窗口维护动态区间和 \(window\_sum\)，每次转移 \(\mathcal{O}(1)\)，将总复杂度由 \(\mathcal{O}(K \cdot W)\) 压缩至严格 \(\mathcal{O}(K + W)\)。
#include <vector>
#include <algorithm>
double new21Game(int n, int k, int maxPts) {
if (k == 0 || n >= k + maxPts) return 1.0;
std::vector<double> dp(k + maxPts, 0.0);
for (int i = k; i <= std::min(n, k + maxPts - 1); ++i) {
dp[i] = 1.0;
}
// 维护长度为 maxPts 的窗口和
double window_sum = 0.0;
for (int i = k; i < k + maxPts; ++i) {
window_sum += dp[i];
}
for (int i = k - 1; i >= 0; --i) {
dp[i] = window_sum / maxPts;
window_sum += dp[i] - dp[i + maxPts];
}
return dp[0];
}
3. 期望动态规划 (Expectation DP)¶
期望 DP 用于计算从某个状态出发，到达终止状态所需要的平均步数、代价或时间。
3.1 逆向倒推原则 (Backward Induction)¶
- 为什么期望 DP 通常采用逆推？
- 起点的不确定性 vs 终点的确定性：从起点出发，到达不同终点的概率难以同时归一化；而在终点处，到达终点所需的额外剩余代价确凿无疑为 0（边界：\(E[\text{target}] = 0\)）；
- 全期望公式展开：设从状态 \(u\) 转移到下一个状态 \(v\) 的概率为 \(P(u \to v)\)，单步转移消耗代价为 \(w(u, v)\)：
由于概率归一性 \(\sum_v P(u \to v) = 1\)，若单步代价均为 1，则化简为标准的期望递推式：
3.2 几何分布与自环方程求解¶
当状态转移中存在自环（自己转移到自己）时，递推式左右两边同时出现 \(E[u]\)：
- 移项解方程：将含 \(E[u]\) 的项移至等号左侧：
- 几何分布期望推导：单次成功的概率为 \(p\)，不断尝试直到首次成功所需的期望尝试次数：\(E = 1 + (1 - p) E \implies p E = 1 \implies E = \frac{1}{p}\)。
3.3 赠券收集问题 (Coupon Collector's Problem)¶
有 \(n\) 种互不相同的卡片，每次随机等概率抽取一张，求集齐全部 \(n\) 种不同卡片所需要的期望抽取总次数。
阶段分解与期望线性性证明¶
将收集过程划分为 \(n\) 个互斥阶段：设已收集了 \(k\) 种不同的卡片（\(0 \le k < n\)），从此时起到抽到第 \(k+1\) 种全新卡片所需的抽取次数记为随机变量 \(X_k\)。
- 当前抽中一张全新卡片的概率为：\(p_k = \frac{n - k}{n}\)；
-
这是一个参数为 \(p_k\) 的几何分布，其期望值为：\(\mathbb{E}[X_k] = \frac{1}{p_k} = \frac{n}{n - k}\)；
-
根据期望的线性性质，集齐所有卡片的总期望抽取次数为各阶段期望之和：
其中 \(H_n = \sum_{i=1}^{n} \frac{1}{i}\) 为第 \(n\) 个调和数。利用渐进展开：
4. 经典随机化与采样算法 (Randomization & Sampling)¶
4.1 Fisher-Yates / Knuth 原地洗牌算法¶
如何将一个长度为 \(n\) 的数组完全随机打乱，保证全排列的所有 \(n!\) 种可能以严格相等的概率 \(1/n!\) 出现？
算法执行流程¶
从数组末尾下标 \(i = n - 1\) 倒序遍历至 \(1\)：
- 在当前区间 \([0, i]\) 中以完全等概率随机选取一个下标 \(j\)；
- 交换元素
std::swap(nums[i], nums[j])； - 将 \(i\) 减 1，已就位的末尾元素不再参与后续洗牌。
#include <vector>
#include <random>
#include <algorithm>
class Solution {
std::vector<int> original;
std::mt19937 rng;
public:
Solution(std::vector<int>& nums) : original(nums), rng(std::random_device{}()) {}
std::vector<int> reset() {
return original;
}
std::vector<int> shuffle() {
std::vector<int> shuffled = original;
int n = shuffled.size();
for (int i = n - 1; i > 0; --i) {
std::uniform_int_distribution<int> dist(0, i);
int j = dist(rng);
std::swap(shuffled[i], shuffled[j]);
}
return shuffled;
}
};
严格等概率证明 (Mathematical Induction)¶
对于任意特定元素 \(x\)，它最终落在位置 \(i\) 的概率：
- 在第 \(i\) 轮抽取中被选中的概率为 \(\frac{1}{i + 1}\)；
-
在随后的各轮 \(k = i - 1, i - 2, \dots, 0\) 中均未被挑中交换的概率为：\(\frac{i}{i + 1} \times \frac{i - 1}{i} \times \dots \times \frac{1}{2}\)；
-
连乘望远消去：所有中间项全部对消，最终概率恒为 \(\mathbf{\frac{1}{n}}\)！全排列概率恒为 \(1/n!\)。
4.2 蓄水池抽样 (Reservoir Sampling)¶
核心挑战：面对一个数据流极大或长度未知的单向流式输入，在只能单遍遍历（\(\mathcal{O}(N)\) 时间）且额外辅助空间受限（\(\mathcal{O}(k)\)）的条件下，如何保证流中每个元素被选中的概率严格相等？
选 1 个元素的核心法则¶
遍历数据流，设当前为第 \(i\) 个元素（\(i \ge 1\)）：
- 以 \(1/i\) 的概率决定用第 \(i\) 个元素替换当前蓄水池中的候选数；
- 以 \(1 - 1/i\) 的概率保留原蓄水池中的元素。
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
#include <random>
class ReservoirSampling {
ListNode* head;
std::mt19937 rng;
public:
ReservoirSampling(ListNode* h) : head(h), rng(std::random_device{}()) {}
int getRandom() {
int chosen = head->val;
int count = 1;
ListNode* cur = head->next;
while (cur) {
count++;
// 生成 [1, count] 的随机整数，若为 1 则替换 (概率为 1/count)
std::uniform_int_distribution<int> dist(1, count);
if (dist(rng) == 1) {
chosen = cur->val;
}
cur = cur->next;
}
return chosen;
}
};
严格数学证明¶
当整个数据流共有 \(N\) 个元素时，第 \(i\) 个元素（\(1 \le i \le N\)）最终留在蓄水池中的概率等于：
- 该元素在第 \(i\) 步被选中的概率 \(\frac{1}{i}\)；
- 乘以在其后的第 \(i+1, i+2, \dots, N\) 步中均未被替换掉的概率：
每个元素最终被选中的概率均为严格的 \(1/N\)！
4.3 拒绝采样 (Rejection Sampling)¶
核心挑战：手头仅有一个生成 \([1, A]\) 均匀随机整数的黑盒发生器 randA()，如何等概率生成 \([1, B]\) 的随机数？
核心三步法则¶
-
多进制扩展拼装大范围：调用两次
randA()组合生成一个 \(A \times A\) 的等概率网格编号：\(num = (randA() - 1) \times A + randA() \in [1, A^2]\)； -
拒绝丢弃截断：选取一个最接近 \(A^2\) 且为 \(B\) 的整数倍的阈值 \(Limit = \lfloor A^2 / B \rfloor \times B\)。若 \(num > Limit\)，则拒绝并重新采样；
- 等概率映射取模：若 \(num \le Limit\)，则返回 \((num - 1) \pmod B + 1\)。
示例：用 rand7() 实现 rand10()¶
调用两次 rand7() 产生 \(1 \sim 49\)：
- 49 不是 10 的倍数，取 \(Limit = 40\)；
- 若生成数在 \(1 \sim 40\) 内，直接返回 \((num - 1) \% 10 + 1\)；
- 若落在 \(41 \sim 49\)（共 9 个数），抛弃重来（期望调用次数仅为 \(2 \times \frac{49}{40} = 2.45\) 次）。
// 假设 rand7() 已实现
int rand7();
int rand10() {
while (true) {
int num = (rand7() - 1) * 7 + rand7(); // 等概率 [1, 49]
if (num <= 40) {
return (num - 1) % 10 + 1;
}
}
}
4.4 几何采样与微元面积补偿¶
在半径为 \(R\) 的圆盘内均匀随机生成点：
- 直觉陷阱：若直接在极坐标下独立均匀抽取角度 \(\theta \in [0, 2\pi)\) 和半径 \(r \in [0, R)\)，采样出的点会在圆心附近异常密集！
- 本质原因：极坐标下的面积微元为 \(\mathrm{d}A = r \, \mathrm{d}r \, \mathrm{d}\theta\)。半径越大，对应圆环的面积与 \(r\) 呈正比，而非均匀分布。
- 开根号逆变换补偿： 设 \(U \sim \text{Uniform}(0, 1)\)，圆内累积面积占比为 \(F(r) = \frac{\pi r^2}{\pi R^2} = \left(\frac{r}{R}\right)^2\)。 令 \(U = \left(\frac{r}{R}\right)^2 \implies \mathbf{r = R \sqrt{U}}\)！ 因此，半径必须取均匀随机数的平方根，才能实现真正的二维面积均匀分布！
5. LeetCode 经典真题精选与题解提示¶
-
LeetCode 688 - 骑士在棋盘上的概率 (Knight Probability in Chessboard)
中等提示
二维网格正向概率 DP。
- 状态定义：\(dp[k][r][c]\) 为骑士在位置 \((r, c)\) 且剩余 \(k\) 步未走时留在棋盘内的概率。
- 倒序递推或记忆化搜索：每个格子等概率走向 8 个方向，单步概率贡献为 \(\frac{1}{8} \sum dp[k - 1][nr][nc]\)。若下一步走出棋盘则贡献 0。
-
LeetCode 808 - 分汤 (Soup Servings)
中等提示
大数阈值截断分析 + 记忆化搜索。
- 观察四种分汤策略的期望损耗：A 汤期望每轮消耗 62.5ml，B 汤期望每轮消耗 37.5ml。
- 当 \(N \ge 4800\) 时，A 汤先被分完的概率已极度趋近于 1（与 1 的误差小于 \(10^{-5}\)），直接返回 1.0。将数据规模量化缩小 25 倍运行二维记忆化搜索。
-
LeetCode 837 - 新 21 点 (New 21 Game)
中等提示
逆推概率 DP + 滑动窗口优化。
- 定义 \(dp[x]\) 为当前得分为 \(x\) 时获胜的概率。
- 转移方程为后方 \(maxPts\) 个连续状态的算术平均值。使用变量 \(window\_sum\) 动态滑动维护窗口概率和，总复杂度压至 \(\mathcal{O}(K + maxPts)\)。
-
LeetCode 470 - 用 Rand7() 实现 Rand10()
中等提示
拒绝采样标准题。
- 两次调用生成 \(1 \sim 49\)。保留 \(1 \sim 40\)，拒绝丢弃 \(41 \sim 49\)。
- 进阶：被拒绝的 9 个数可以进一步配合新的
rand7()产生 \(9 \times 7 = 63\)，保留前 60 个数，进一步压减拒绝率。
-
LeetCode 382 - 链表随机节点 (Linked List Random Node)
中等提示
单元素蓄水池抽样标准模板。
- 单向链表长度未知，要求只遍历一次。
- 遍历节点时维护计数器 \(cnt\)。遇到第 \(cnt\) 个节点以 \(1 / cnt\) 的概率替换当前保留的答案值。
-
LeetCode 384 - 打乱数组 (Shuffle an Array)
中等提示
Fisher-Yates 原地洗牌算法。
- 从末尾 \(i\) 倒序至 1，每次在 \([0, i]\) 中均匀随机一个下标 \(j\) 并交换。严格 \(\mathcal{O}(N)\) 原地打乱且每种排列概率严格相等。
-
LeetCode 478 - 在圆内随机生成点 (Generate Random Point in a Circle)
中等提示
拒绝采样与几何微元开方逆变换。
- 方法一（拒绝采样）：在外接正方形内均匀随机生成点，若到圆心距离大于 \(R\) 则抛弃重来（命中率 \(\pi / 4 \approx 78.5\%\)）；
- 方法二（开方逆变换）：随机角度 \(\theta \in [0, 2\pi)\)，随机半径取 \(r = R \sqrt{U}\)（其中 \(U \in [0, 1)\)），直接生成绝对均匀点。
-
LeetCode 1227 - 飞机座位分配概率 (Airplane Seat Assignment Probability)
中等提示
对称性博弈与数学归纳法。
- 当 \(n = 1\) 时，概率为 1.0；
- 当 \(n \ge 2\) 时，第 1 位乘客若选了 1 号位，则后续所有人归位，最后一人必定坐在自己位子上；若选了 \(n\) 号位，最后一人必定无法坐在自己位子上；若选了中间任意座位，该座位的主人又会面临与第 1 位乘客完全对称的抉择。
- 1 号位与 \(n\) 号位具有完全的镜像对称性，因此当 \(n \ge 2\) 时答案恒为 0.5。