跳到主要内容

概率、随机化算法与期望建模 (Probability & Expectation)

本篇章构建了从离散概率基础到复杂状态空间期望建模的完备体系。我们将深入探讨期望的线性性、条件期望、Min-Max 容斥以及随机化算法在处理大数问题中的工业级应用。

1. 期望的线性性与指示变量​

1.1 期望线性性的严密证明与一致性​

定理：对于任意随机变量 X,YX, Y（即使它们不独立），均有 E[X+Y]=E[X]+E[Y]E[X+Y] = E[X] + E[Y]。

证明 (连续型随机变量视角)： 设 X,YX, Y 的联合概率密度函数为 f(x,y)f(x, y)。

E[X+Y]=∫−∞∞∫−∞∞(x+y)f(x,y) dx dy=∫−∞∞∫−∞∞xf(x,y) dx dy+∫−∞∞∫−∞∞yf(x,y) dx dy=∫−∞∞x(∫−∞∞f(x,y) dy) dx+∫−∞∞y(∫−∞∞f(x,y) dx) dy=∫−∞∞xfX(x) dx+∫−∞∞yfY(y) dy=E[X]+E[Y]\begin{aligned} E[X+Y] &= \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} (x+y) f(x, y) \, dx \, dy \\ &= \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} x f(x, y) \, dx \, dy + \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} y f(x, y) \, dx \, dy \\ &= \int_{-\infty}^{\infty} x \left( \int_{-\infty}^{\infty} f(x, y) \, dy \right) \, dx + \int_{-\infty}^{\infty} y \left( \int_{-\infty}^{\infty} f(x, y) \, dx \right) \, dy \\ &= \int_{-\infty}^{\infty} x f_X(x) \, dx + \int_{-\infty}^{\infty} y f_Y(y) \, dy \\ &= E[X] + E[Y] \end{aligned}

其中 fX(x)f_X(x) 和 fY(y)f_Y(y) 分别为 XX 和 YY 的边缘概率密度。

性质补充：该性质的强大之处在于其不依赖变量间的独立性。

1.2 指示随机变量 (Indicator Random Variables)​

对于事件 AA，定义指示变量 I{A}={1A 发生0A 未发生I\{A\} = \begin{cases} 1 & A \text{ 发生} \\ 0 & A \text{ 未发生} \end{cases}。 性质：E[I{A}]=P(A)E[I\{A\}] = P(A)。 应用示例：随机排列中的逆序对期望： 设 Xi,jX_{i,j} 为位置 i,ji, j 构成逆序对的指示变量。由于对称性，P(Xi,j=1)=1/2P(X_{i,j}=1) = 1/2。 则总逆序对数 X=∑i<jXi,jX = \sum_{i<j} X_{i,j}。 E[X]=∑i<jE[Xi,j]=(n2)⋅12=n(n−1)4E[X] = \sum_{i<j} E[X_{i,j}] = \binom{n}{2} \cdot \frac{1}{2} = \frac{n(n-1)}{4}。

1.3 全期望公式 (Law of Total Expectation)​

E[X]=E[E[X∣Y]]=∑yE[X∣Y=y]P(Y=y)E[X] = E[E[X|Y]] = \sum_y E[X|Y=y] P(Y=y)。 这在解决多阶段随机过程中极度有效。

1.4 期望线性收敛验证 (Expected Linear Convergence)​

在随机化优化（如随机梯度下降 SGD 或随机增量算法）中，我们关注期望意义下的收敛速度。

定义 (期望线性收敛)：若随机序列 XtX_t 满足： E[∥Xt+1−X∗∥2]≤ρE[∥Xt−X∗∥2]+σt2E[\|X_{t+1} - X^*\|^2] \le \rho E[\|X_t - X^*\|^2] + \sigma_t^2 且 0<ρ<10 < \rho < 1，则称序列在期望意义下线性收敛到最优解 X∗X^*（受限于噪声项 σt\sigma_t）。

验证：随机增量法的复杂度收敛： 对于最小覆盖圆问题，第 ii 个点引起外层循环更新的概率为 Pi=3/iP_i = 3/i。

  • 层 1：O(n)O(n)。
  • 层 2：∑i=1nPi⋅O(i)=∑3i⋅i=O(n)\sum_{i=1}^n P_i \cdot O(i) = \sum \frac{3}{i} \cdot i = O(n)。
  • 层 3：∑i=1nPi⋅(∑j=1iPj⋅O(j))=O(n)\sum_{i=1}^n P_i \cdot \left( \sum_{j=1}^i P_j \cdot O(j) \right) = O(n)。 这种层层递进的线性期望结构保证了算法在 O(n)O(n) 时间内收敛。

2. 随机化算法与收敛分析​

2.1 随机增量法 (Randomized Incremental Construction)​

分析框架： 以最小覆盖圆为例。若随机打乱点集顺序，则第 ii 个点在前面的最小覆盖圆外的概率为 3/i3/i。 由此推导，算法的期望复杂度为 ∑O(1)⋅3i (内部递归)=O(n)\sum O(1) \cdot \frac{3}{i} \text{ (内部递归)} = O(n)。

2.2 模拟退火 (Simulated Annealing)​

接受准则：Metropolis 准则。 收敛性：若降温系数 ΔT≈1\Delta T \approx 1 且初温足够高，根据马尔可夫链理论，系统将收敛到 Boltzmann 分布，即最低能量态（全局最优）的概率最大。

3. 期望 DP 与状态消元​

对于带有环的状态转移 Eu=∑PuvEv+WuvE_u = \sum P_{uv} E_v + W_{uv}，通常有两种处理方式：

  1. 高斯消元：处理一般图，O(n3)O(n^3)。
  2. 树形递推：对于树结构，设 Eu=AuEfa+BuE_u = A_u E_{fa} + B_u，利用子节点信息递推 Au,BuA_u, B_u，O(n)O(n)。

3.1 马尔可夫链状态转移校验 (Markov Chain Validation)​

状态转移矩阵 PP： 设 Pij=P(Xt+1=j∣Xt=i)P_{ij} = P(X_{t+1}=j \mid X_t=i)，则 PP 为随机矩阵（行和为 1）。 稳态分布证明 (Stationary Distribution)： 若 πP=π\pi P = \pi，且 ∑πi=1\sum \pi_i = 1，则称 π\pi 为稳态分布。

  1. 存在性：根据 Perron-Frobenius 定理，随机矩阵 PP 的最大特征值为 1，对应的左特征向量即为稳态。
  2. 唯一性与收敛性：若马尔可夫链满足不可约性 (Irreducibility) 和 非周期性 (Aperiodicity)，则从任意初始分布 π(0)\pi^{(0)} 出发，均有 lim⁡n→∞π(0)Pn=π\lim_{n \to \infty} \pi^{(0)} P^n = \pi。

校验方法： 对于大规模离散系统，可使用矩阵快速幂 P2kP^{2^k} 或解线性方程组 (I−PT)π=0(I - P^T)\pi = 0 进行数值验证或精确解析。

4. 综合练习与 C++ 解答​

练习 1：[P1850] 换教室 (期望 DP)​

nn 个时段，申请第 ii 个时段成功的概率为 k[i]k[i]，求最小期望路程。

Check Solution (C++)
// f[i][j][0/1] 前 i 节课换 j 次，第 i 节是否换
for (int i = 2; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        f[i][j][0] = min(f[i - 1][j][0] + dist[c[i - 1]][c[i]], 
                         f[i - 1][j][1] + k[i - 1] * dist[d[i - 1]][c[i]] + (1 - k[i - 1]) * dist[c[i - 1]][c[i]]);
        if (j > 0)
            f[i][j][1] = min(f[i - 1][j - 1][0] + k[i] * dist[c[i - 1]][d[i]] + (1 - k[i]) * dist[c[i - 1]][c[i]],
                             f[i - 1][j - 1][1] + k[i - 1] * k[i] * dist[d[i - 1]][d[i]] 
                                              + k[i - 1] * (1 - k[i]) * dist[d[i - 1]][c[i]]
                                              + (1 - k[i - 1]) * k[i] * dist[c[i - 1]][d[i]]
                                              + (1 - k[i - 1]) * (1 - k[i]) * dist[c[i - 1]][c[i]]);
    }
}

练习 2：[P4316] 绿豆蛙的归宿 (DAG 期望)​

给定一个 DAG，起点 1，终点 nn，求从 1 到 nn 的期望路径长度。

Check Solution (C++)
// 拓扑排序 + 倒推
for (int i = n; i >= 1; i--) {
    int u = q[i];
    for (int j = h[u]; ~j; j = ne[j]) {
        int v = e[j];
        f[u] += (f[v] + w[j]) / out_degree[u];
    }
}

练习 3：[P3803] 最小覆盖圆 (随机增量)​

给定 nn 个点，求覆盖所有点的最小圆。

Check Solution (C++)
random_shuffle(p + 1, p + n + 1);
Circle c = {p[1], 0};
for (int i = 2; i <= n; i++) {
    if (dist(c.o, p[i]) > c.r + eps) {
        c = {p[i], 0};
        for (int j = 1; j < i; j++) {
            if (dist(c.o, p[j]) > c.r + eps) {
                c.o = {(p[i].x + p[j].x) / 2, (p[i].y + p[j].y) / 2};
                c.r = dist(p[i], p[j]) / 2;
                for (int k = 1; k < j; k++) {
                    if (dist(c.o, p[k]) > c.r + eps)
                        c = get_circle(p[i], p[j], p[k]);
                }
            }
        }
    }
}

练习 4：[P4550] 收集邮票 (期望平方建模)​

有 nn 种邮票，第 ii 次购买需支付 ii 元，求收集全套的期望花费。 解析：设 f[i]f[i] 为收集 ii 种到 nn 种的期望步数，g[i]g[i] 为期望花费。 g[i]=in(g[i]+f[i]+1)+n−in(g[i+1]+f[i+1]+1)g[i] = \frac{i}{n}(g[i] + f[i] + 1) + \frac{n-i}{n}(g[i+1] + f[i+1] + 1)。

练习 5：[CF 235B] Let's Play Osu! (期望线性性应用)​

给定 nn 次点击成功的概率，kk 连击得分为 k2k^2，求期望得分。 解析：维护 E[L]E[L] 和 E[L2]E[L^2]。E[Li]=pi(E[Li−1]+1)E[L_i] = p_i(E[L_{i-1}] + 1)。 E[Li2]=pi(E[(Li−1+1)2])=pi(E[Li−12]+2E[Li−1]+1)E[L_i^2] = p_i(E[(L_{i-1}+1)^2]) = p_i(E[L_{i-1}^2] + 2E[L_{i-1}] + 1)。

练习 6：[P3232] 游走 (高斯消元求期望)​

无向图，求边权分配使得期望总得分最小。 解析：先求点被经过的期望次数 f[u]=∑v∈adj(u)f[v]d(v)f[u] = \sum_{v \in adj(u)} \frac{f[v]}{d(v)}。然后计算边的期望次数 g(u,v)=f[u]d(u)+f[v]d(v)g(u, v) = \frac{f[u]}{d(u)} + \frac{f[v]}{d(v)}。贪心分配权值。

练习 7：[ABC 297G] Constrained Nim 2 (马尔可夫链稳态思想)​

虽然 Nim 是组合博弈，但状态转移分析可抽象为马尔可夫过程。考虑从 ii 转移到 jj 的路径，求 SG(n)SG(n)。

Check Solution (矩阵快速幂求稳态/转移 C++)
// 示例：计算状态转移矩阵的 n 次幂以达到稳态
struct Matrix {
    double mat[MAXN][MAXN];
    Matrix() { memset(mat, 0, sizeof mat); }
    Matrix operator * (const Matrix &b) const {
        Matrix res;
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++)
                for (int j = 0; j < n; j++)
                    res.mat[i][j] += mat[i][k] * b.mat[k][j];
        return res;
    }
};

Matrix qpow(Matrix a, ll b) {
    Matrix res; for (int i = 0; i < n; i++) res.mat[i][i] = 1;
    while (b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

练习 8：[P1297] 单选错位 (Expectation of Matching)​

nn 道题，第 ii 道有 aia_i 个选项。某人做完后将答案错位（第 ii 道的答案填到了第 i+1i+1 道，第 nn 道填到第 1 道），求期望得分。

Check Solution (思路)
  1. 定义指示变量 XiX_i：第 ii 道题（错位后对应的题）是否正确。
  2. 考虑第 ii 题和第 i+1i+1 题。错位后，原第 ii 题的答案填到了第 i+1i+1 题。
  3. 只有当原第 ii 题选的项在第 i+1i+1 题的选项范围内，且该项正好是第 i+1i+1 题的正确答案时才得分。
  4. 概率 P(Xi+1=1)=1max⁡(ai,ai+1)P(X_{i+1}=1) = \frac{1}{\max(a_i, a_{i+1})}。
  5. 总期望 E=∑P(Xi)=∑i=1n−11max⁡(ai,ai+1)+1max⁡(an,a1)E = \sum P(X_i) = \sum_{i=1}^{n-1} \frac{1}{\max(a_i, a_{i+1})} + \frac{1}{\max(a_n, a_1)}。
Check Solution (C++)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 10000005;
int a[MAXN];

void solve() {
    int n, A, B, C;
    scanf("%d %d %d %d %d", &n, &A, &B, &C, &a[1]);
    for (int i = 2; i <= n; i++)
        a[i] = ((long long)a[i - 1] * A + B) % 100000001;
    for (int i = 1; i <= n; i++)
        a[i] = a[i] % C + 1;

    double ans = 0;
    for (int i = 1; i < n; i++)
        ans += 1.0 / max(a[i], a[i + 1]);
    ans += 1.0 / max(a[n], a[1]);
    printf("%.3f\n", ans);
}

大师寄语：在不确定性的迷雾中，期望是我们唯一的罗盘。只要步数足够多，大数定律终将让随机回归必然。