概率与期望

概率空间与随机变量

样本空间与事件

样本空间（Sample Space）是随机试验所有可能结果的集合，记作 $\Omega$。

• 抛一枚硬币：$\Omega =\{\text{正面},\text{反面}\}$
• 掷一枚骰子：$\Omega =\{1,2,3,4,5,6\}$
• 连续射击：$\Omega =\{(x,y):x,y\in \mathbb{R}\}$

事件是样本空间的子集：

• 基本事件：只包含一个样本点的集合
• 必然事件：$\Omega$ 本身
• 不可能事件：空集 $\varnothing$
• 复合事件：多个基本事件的并集

事件运算：

运算	记号	含义
和事件	$A\cup B$ 或 $A+B$	$A$ 或 $B$ 发生
积事件	$A\cap B$ 或 $AB$	$A$ 和 $B$ 同时发生
差事件	$A-B$	$A$ 发生而 $B$ 不发生
对立事件	$\bar{A}$ 或 $A^c$	$A$ 不发生
互不相容	$A\cap B=\varnothing$	$A$ 和 $B$ 不能同时发生

概率测度

概率是定义在事件域上的满足以下三条公理的函数 $P$：

概率公理化定义（Kolmogorov 公理）：

1. 非负性：$P(A)⩾0$，对任意事件 $A$
2. 正则性：$P(\Omega )=1$
3. 可列可加性：若 $A_1,A_2,\dots$ 两两互不相容，则

$$P\left(\bigcup _{i=1}^{\infty }{A}_i\right)=\sum _{i=1}^{\infty }P(A_i)$$

由这三条公理可以推导出：

性质	公式
互补律	$P(\bar{A})=1-P(A)$
有限可加	$P(A\cup B)=P(A)+P(B)-P(AB)$
单调性	若 $A\subseteq B$，则 $P(A)⩽P(B)$
容斥原理	$P(A\cup B)=P(A)+P(B)-P(AB)$
次可加性	$P(A\cup B)⩽P(A)+P(B)$

容斥原理的推广：

$$P\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{i}P(A_i)-\sum _{i<j}P(A_i{A}_j)+\sum _{i<j<k}P(A_i{A}_j{A}_k)-\cdots +(-1{)}^{n+1}P(A_1{A}_2\cdots A_n)$$

随机变量

随机变量（Random Variable）是从样本空间到实数的函数 $X:\Omega \to \mathbb{R}$。

离散随机变量

离散随机变量只能取有限个或可数个值。

概率质量函数（Probability Mass Function, PMF）：$p_X(x)=P(X=x)$

# 离散随机变量示例：掷骰子
import numpy as np
 
def dice_pmf():
    """掷骰子的概率质量函数"""
    outcomes = np.arange(1, 7)  # {1, 2, 3, 4, 5, 6}
    probabilities = np.array([1/6] * 6)  # 均匀分布
    return dict(zip(outcomes, probabilities))
 
pmf = dice_pmf()
print("P(X=3) =", pmf[3])  # 输出: P(X=3) = 0.16666666666666666

常见离散分布的PMF：

分布	PMF $P(X=k)$	参数
伯努利	$p^k(1-p{)}^{1-k}$	$p\in [0,1]$
二项	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k}$	$n\in \mathbb{N},p\in [0,1]$
泊松	$\frac{{\lambda }^k{e}^{-\lambda }}{k!}$	$\lambda >0$

连续随机变量

连续随机变量可以取区间内的任意值。

概率密度函数（Probability Density Function, PDF）：满足

$$P(a⩽X⩽b)={\int }_a^b{f}_X(x)dx$$

且 $f_X(x)⩾0$，${\int }_{-\infty }^{+\infty }{f}_X(x)dx=1$。

import numpy as np
from scipy import stats
 
# 高斯分布（正态分布）示例
def gaussian_pdf():
    """标准正态分布的概率密度函数"""
    x = np.linspace(-4, 4, 100)
    pdf = stats.norm.pdf(x, loc=0, scale=1)  # 均值=0, 标准差=1
    return x, pdf
 
x, pdf = gaussian_pdf()
# P(-1 < X < 1) = ?
prob = stats.norm.cdf(1) - stats.norm.cdf(-1)
print(f"P(-1 < X < 1) = {prob:.4f}")  # 输出: P(-1 < X < 1) = 0.6827

注意：对于连续随机变量，$P(X=x)=0$，因此：

$$P(a⩽X⩽b)=P(a<X<b)=P(a⩽X<b)=P(a<X⩽b)$$

分布函数

累计分布函数（Cumulative Distribution Function, CDF）：

$$F_X(x)=P(X⩽x)$$

CDF 的性质：

性质	说明
单调不减	$x_1<x_2\Rightarrow F(x_1)⩽F(x_2)$
右连续	$F(x)=F(x^{+})$
极限性质	${\lim }_{x\to -\infty }F(x)=0$，${\lim }_{x\to +\infty }F(x)=1$

离散与连续分布的 CDF：

// 离散分布的CDF（阶跃函数）
// 以二项分布 B(10, 0.3) 为例
#include <bits/stdc++.h>
using namespace std;
 
// 二项分布PMF
double binom_pmf(int n, int k, double p) {
    double res = 1.0;
    for (int i = 0; i < k; i++) {
        res *= (n - i) / (i + 1.0);
    }
    return res * pow(p, k) * pow(1 - p, n - k);
}
 
// 二项分布CDF
double binom_cdf(int n, double p, int k) {
    double sum = 0.0;
    for (int i = 0; i <= k; i++) {
        sum += binom_pmf(n, i, p);
    }
    return sum;
}
 
int main() {
    cout << "B(10, 0.3) 的分布函数：" << endl;
    for (int k = 0; k <= 10; k++) {
        cout << "F(" << k << ") = " << binom_cdf(10, 0.3, k) << endl;
    }
    return 0;
}

常见概率分布

离散分布

伯努利分布 (Bernoulli Distribution)

最简单的离散分布，只有两种结果。

$$X\sim \text{Bernoulli}(p)$$

参数	定义
$p$	成功概率，$p\in [0,1]$

概率质量函数：

$$P(X=k)=\{\begin{array}{ll}1-p& k=0\\ p& k=1\end{array}$$

数字特征：

特征	值
期望	$E[X]=p$
方差	$\text{Var}(X)=p(1-p)$
矩母函数	$M(t)=(1-p)+p{e}^t$

二项分布 (Binomial Distribution)

$n$ 次独立伯努利试验中成功次数的分布。

$$X\sim \text{Binomial}(n,p)$$

概率质量函数：

$$P(X=k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k},k=0,1,2,\dots ,n$$

数字特征：

特征	值
期望	$E[X]=np$
方差	$\text{Var}(X)=np(1-p)$
标准差	$\sigma =\sqrt{np(1-p)}$

import numpy as np
from scipy import stats
 
# 二项分布示例：抛10次硬币，5次正面的概率
n, p = 10, 0.5
prob = stats.binom.pmf(5, n, p)
print(f"P(X=5) = {prob:.4f}")  # 输出: P(X=5) = 0.2461
 
# 计算 P(X <= 5)
cdf = stats.binom.cdf(5, n, p)
print(f"P(X <= 5) = {cdf:.4f}")
 
# 期望和方差
mean, var = stats.binom.stats(n, p)
print(f"E[X] = {mean}, Var(X) = {var}")

二项分布的可加性：若 $X\sim \text{Binomial}(n_1,p)$，$Y\sim \text{Binomial}(n_2,p)$，且独立，则：

$$X+Y\sim \text{Binomial}(n_1+n_2,p)$$

泊松分布 (Poisson Distribution)

描述单位时间/空间内随机事件发生次数的分布。

$$X\sim \text{Poisson}(\lambda )$$

概率质量函数：

$$P(X=k)=\frac{{\lambda }^k{e}^{-\lambda }}{k!},k=0,1,2,\dots$$

数字特征：

特征	值
期望	$E[X]=\lambda$
方差	$\text{Var}(X)=\lambda$
矩母函数	$M(t)=\exp (\lambda (e^t-1))$

泊松分布的性质：

1. 可加性：若 $X\sim \text{Poisson}({\lambda }_1)$，$Y\sim \text{Poisson}({\lambda }_2)$，独立，则 $X+Y\sim \text{Poisson}({\lambda }_1+{\lambda }_2)$

2. 二项分布的极限：当 $n\to \infty$，$p\to 0$，$np\to \lambda$ 时：

   $$\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k}\to \frac{{\lambda }^k{e}^{-\lambda }}{k!}$$

3. 稀疏事件模型：适用于稀有事件，如：

   • 每分钟到达的电话次数
   • 每页书的印刷错误数
   • 放射性衰变的粒子数

from scipy import stats
import numpy as np
 
# 泊松分布示例：平均每小时到达5位顾客
lambda_val = 5
 
# P(X = 3)
prob = stats.poisson.pmf(3, lambda_val)
print(f"P(X=3) = {prob:.4f}")  # 输出: P(X=3) = 0.1404
 
# P(X <= 4)
cdf = stats.poisson.cdf(4, lambda_val)
print(f"P(X <= 4) = {cdf:.4f}")
 
# 可视化
x = np.arange(0, 15)
pmf = stats.poisson.pmf(x, lambda_val)
for k, p in zip(x, pmf):
    print(f"k={k}: {'*' * int(p * 100):50s} {p:.4f}")

多项分布 (Multinomial Distribution)

二项分布的多元推广。

$$(X_1,X_2,\dots ,X_k)\sim \text{Multinomial}(n,p_1,p_2,\dots ,p_k)$$

概率质量函数：

$$P(X_1=n_1,\dots ,X_k=n_k)=\frac{n!}{n_1!n_2!\cdots n_k!}{p}_1^{n_1}{p}_2^{n_2}\cdots p_k^{n_k}$$

其中 ${\sum }_{i=1}^k{n}_i=n$，${\sum }_{i=1}^k{p}_i=1$。

#include <bits/stdc++.h>
using namespace std;
 
// 多项分布概率计算
// n: 总试验次数
// k: 类别数
// counts[i]: 第i类出现的次数
// probs[i]: 第i类的概率
double multinomial_pmf(int n, const vector<int>& counts, const vector<double>& probs) {
    // 计算多项式系数: n! / (n1! * n2! * ... * nk!)
    double coeff = 1.0;
    int total = n;
    for (int cnt : counts) {
        for (int i = 2; i <= cnt; i++) {
            coeff *= 1.0 / i;
        }
        for (int i = 2; i <= total; i++) {
            coeff *= i;
        }
        total -= cnt;
    }
    
    // 计算 p1^n1 * p2^n2 * ... * pk^nk
    double prob = 1.0;
    for (int i = 0; i < counts.size(); i++) {
        prob *= pow(probs[i], counts[i]);
    }
    
    return coeff * prob;
}
 
int main() {
    // 投掷骰子60次，统计各面出现次数的分布
    // 每面期望出现10次
    vector<double> probs(6, 1.0/6.0);  // 均匀分布
    
    // 计算 (10, 10, 10, 10, 10, 10) 的概率
    vector<int> counts = {10, 10, 10, 10, 10, 10};
    double prob = multinomial_pmf(60, counts, probs);
    cout << fixed << setprecision(6);
    cout << "P(各面都出现10次) = " << prob << endl;
    
    return 0;
}

连续分布

正态分布 (Normal/Gaussian Distribution)

最重要的连续分布，自然界中大量现象近似服从正态分布。

$$X\sim N(\mu ,{\sigma }^2)$$

概率密度函数：

$$f(x)=\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp \left(-\frac{(x-\mu {)}^2}{2{\sigma }^2}\right)$$

数字特征：

特征	值
期望	$E[X]=\mu$
方差	$\text{Var}(X)={\sigma }^2$
矩母函数	$M(t)=\exp (\mu t+\frac{1}{2}{\sigma }^2{t}^2)$
偏度	$0$
峰度	$3$

标准正态分布：$Z\sim N(0,1)$

$$\varphi (z)=\frac{1}{\sqrt{2\pi }}{e}^{-z^2/2},\Phi (z)={\int }_{-\infty }^z\varphi (t)dt$$

标准化变换：若 $X\sim N(\mu ,{\sigma }^2)$，则

$$Z=\frac{X-\mu }{\sigma }\sim N(0,1)$$

3σ原则：

区间	概率
$[\mu -\sigma ,\mu +\sigma ]$	$68.27\%$
$[\mu -2\sigma ,\mu +2\sigma ]$	$95.45\%$
$[\mu -3\sigma ,\mu +3\sigma ]$	$99.73\%$

import numpy as np
from scipy import stats
import matplotlib.pyplot as plt
 
# 正态分布示例
mu, sigma = 100, 15  # IQ分数的典型参数
 
# P(85 < X < 115) = ?
prob = stats.norm.cdf(115, mu, sigma) - stats.norm.cdf(85, mu, sigma)
print(f"P(85 < X < 115) = {prob:.4f}")  # 输出约 0.6827
 
# 绘制正态分布PDF
x = np.linspace(mu - 4*sigma, mu + 4*sigma, 100)
y = stats.norm.pdf(x, mu, sigma)
plt.plot(x, y)
plt.axvline(mu, color='r', linestyle='--', label=f'μ={mu}')
plt.axvline(mu - sigma, color='g', linestyle=':', label=f'±1σ')
plt.axvline(mu + sigma, color='g', linestyle=':')
plt.legend()
plt.show()

指数分布 (Exponential Distribution)

描述两次事件发生间隔时间的分布。

$$X\sim \text{Exp}(\lambda )$$

概率密度函数：

$$f(x)=\lambda e^{-\lambda x},x⩾0$$

累计分布函数：

$$F(x)=1-e^{-\lambda x},x⩾0$$

数字特征：

特征	值
期望	$E[X]=\frac{1}{\lambda }$
方差	$\text{Var}(X)=\frac{1}{{\lambda }^2}$
标准差	$\sigma =\frac{1}{\lambda }$

无记忆性：指数分布具有无记忆性（Memoryless Property）：

$$P(X>s+t\mid X>s)=P(X>t)$$

from scipy import stats
import numpy as np
 
# 指数分布示例：平均每10分钟到达一位顾客
lambda_val = 0.1  # 每分钟到达的概率
 
# P(等待时间 <= 5分钟)
prob = stats.expon.cdf(5, scale=1/lambda_val)
print(f"P(等待 <= 5分钟) = {prob:.4f}")  # 输出: P(等待 <= 5分钟) = 0.3935
 
# P(等待时间 > 15分钟)
prob = 1 - stats.expon.cdf(15, scale=1/lambda_val)
print(f"P(等待 > 15分钟) = {prob:.4f}")
 
# 期望等待时间
expected_wait = 1 / lambda_val
print(f"E[等待时间] = {expected_wait} 分钟")

Gamma 分布 (Gamma Distribution)

指数分布的推广，描述等待 $k$ 次事件发生所需时间的分布。

$$X\sim \text{Gamma}(\alpha ,\beta )$$

概率密度函数：

$$f(x)=\frac{{\beta }^{\alpha }}{\Gamma (\alpha )}{x}^{\alpha -1}{e}^{-\beta x},x>0$$

其中 $\Gamma (\alpha )={\int }_0^{\infty }{t}^{\alpha -1}{e}^{-t}dt$ 是 Gamma 函数。

数字特征：

特征	值
期望	$E[X]=\frac{\alpha }{\beta }$
方差	$\text{Var}(X)=\frac{\alpha }{{\beta }^2}$

与指数分布的关系：

• 当 $\alpha =1$ 时，$\text{Gamma}(1,\lambda )=\text{Exp}(\lambda )$
• 当 $\alpha =n$（整数），$\text{Gamma}(n,\lambda )$ 是 Erlang 分布，描述 $n$ 次指数分布事件的总时间

与泊松分布的关系：

若事件到达服从参数为 $\lambda$ 的泊松过程，则第 $k$ 次事件到达的时间 $T_k\sim \text{Gamma}(k,\lambda )$，且 $P(T_k⩽t)=P(N(t)⩾k)$。

from scipy import stats
import numpy as np
 
# Gamma分布示例：等待3位顾客到达的时间
# 每分钟平均到达2位顾客
alpha, beta = 3, 2  # shape, rate
 
# P(等待3位顾客的时间 <= 2分钟)
prob = stats.gamma.cdf(2, a=alpha, scale=1/beta)
print(f"P(等待时间 <= 2分钟) = {prob:.4f}")
 
# P(等待3位顾客的时间 > 3分钟)
prob = 1 - stats.gamma.cdf(3, a=alpha, scale=1/beta)
print(f"P(等待时间 > 3分钟) = {prob:.4f}")
 
# 期望等待时间
expected = stats.gamma.mean(a=alpha, scale=1/beta)
print(f"E[等待时间] = {expected:.2f} 分钟")

Beta 分布 (Beta Distribution)

定义在 $[0,1]$ 区间上的连续分布，常用于表示概率的先验分布。

$$X\sim \text{Beta}(\alpha ,\beta )$$

概率密度函数：

$$f(x)=\frac{1}{B(\alpha ,\beta )}{x}^{\alpha -1}(1-x{)}^{\beta -1},0<x<1$$

其中 $B(\alpha ,\beta )=\frac{\Gamma (\alpha )\Gamma (\beta )}{\Gamma (\alpha +\beta )}$ 是 Beta 函数。

数字特征：

特征	值
期望	$E[X]=\frac{\alpha }{\alpha +\beta }$
方差	$\text{Var}(X)=\frac{\alpha \beta }{(\alpha +\beta {)}^2(\alpha +\beta +1)}$
众数	$\frac{\alpha -1}{\alpha +\beta -2}$（当 $\alpha ,\beta >1$）

与均匀分布的关系：$\text{Beta}(1,1)=U(0,1)$

与二项分布的关系：Beta 分布是二项分布的共轭先验。

from scipy import stats
import numpy as np
 
# Beta分布示例：硬币正面朝上概率的贝叶斯推断
# 先验: Beta(2, 2) — 认为硬币略可能均匀
# 观测: 7次正面，3次反面
# 后验: Beta(2+7, 2+3) = Beta(9, 5)
 
alpha_post, beta_post = 9, 5
 
# 后验均值（估计的正面概率）
mean = stats.beta.mean(alpha_post, beta_post)
print(f"后验均值（估计的p）= {mean:.4f}")
 
# 95%可信区间
ci = stats.beta.interval(0.95, alpha_post, beta_post)
print(f"95%可信区间: [{ci[0]:.4f}, {ci[1]:.4f}]")
 
# 绘制先验和后验
x = np.linspace(0, 1, 100)
prior = stats.beta.pdf(x, 2, 2)
posterior = stats.beta.pdf(x, alpha_post, beta_post)
# 可视化对比...

分布的性质汇总

均值、方差与协方差

均值（期望）：

$$E[X]=\{\begin{array}{ll}{\sum }_i{x}_i{p}_X(x_i)& \text{离散}\\ {\int }_{-\infty }^{+\infty }x{f}_X(x)dx& \text{连续}\end{array}$$

方差：

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

协方差：

$$\text{Cov}(X,Y)=E[(X-E[X])(Y-E[Y])]=E[XY]-E[X]E[Y]$$

协方差矩阵：对于随机向量 $\mathbf{X}=(X_1,X_2,\dots ,X_n{)}^T$，

$$\Sigma =\text{Cov}(\mathbf{X})=E[(\mathbf{X}-E[\mathbf{X}])(\mathbf{X}-E[\mathbf{X}]{)}^T]$$

其中 ${\Sigma }_{ij}=\text{Cov}(X_i,X_j)$。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    // 计算协方差矩阵示例
    // 假设有二维随机变量 (X, Y) 的样本
    
    // 样本数据：每行是一个样本点
    vector<pair<double, double>> data = {
        {1.0, 2.0},
        {2.0, 3.0},
        {3.0, 2.5},
        {4.0, 4.0},
        {5.0, 3.5}
    };
    
    int n = data.size();
    
    // 计算均值
    double mean_x = 0, mean_y = 0;
    for (auto [x, y] : data) {
        mean_x += x;
        mean_y += y;
    }
    mean_x /= n;
    mean_y /= n;
    
    // 计算协方差
    double cov_xx = 0, cov_yy = 0, cov_xy = 0;
    for (auto [x, y] : data) {
        double dx = x - mean_x;
        double dy = y - mean_y;
        cov_xx += dx * dx;
        cov_yy += dy * dy;
        cov_xy += dx * dy;
    }
    cov_xx /= (n - 1);
    cov_yy /= (n - 1);
    cov_xy /= (n - 1);
    
    cout << fixed << setprecision(4);
    cout << "协方差矩阵:" << endl;
    cout << "[[" << cov_xx << ", " << cov_xy << "]" << endl;
    cout << " [" << cov_xy << ", " << cov_yy << "]]" << endl;
    
    return 0;
}

常见分布汇总表

分布	记号	PMF/PDF	期望	方差
伯努利	$\text{Bern}(p)$	$p^k(1-p{)}^{1-k}$	$p$	$p(1-p)$
二项	$\text{Bin}(n,p)$	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k}$	$np$	$np(1-p)$
泊松	$\text{Pois}(\lambda )$	${\lambda }^k{e}^{-\lambda }/k!$	$\lambda$	$\lambda$
几何	$\text{Geom}(p)$	$(1-p{)}^{k-1}p$	$1/p$	$(1-p)/p^2$
均匀	$U(a,b)$	$1/(b-a)$	$(a+b)/2$	$(b-a{)}^2/12$
指数	$\text{Exp}(\lambda )$	$\lambda e^{-\lambda x}$	$1/\lambda$	$1/{\lambda }^2$
正态	$N(\mu ,{\sigma }^2)$	$\frac{1}{\sqrt{2\pi }\sigma }{e}^{-(x-\mu {)}^2/2{\sigma }^2}$	$\mu$	${\sigma }^2$
Gamma	$\Gamma (\alpha ,\beta )$	$\frac{{\beta }^{\alpha }}{\Gamma (\alpha )}{x}^{\alpha -1}{e}^{-\beta x}$	$\alpha /\beta$	$\alpha /{\beta }^2$
Beta	$\text{Beta}(\alpha ,\beta )$	$\frac{1}{B(\alpha ,\beta )}{x}^{\alpha -1}(1-x{)}^{\beta -1}$	$\frac{\alpha }{\alpha +\beta }$	$\frac{\alpha \beta }{(\alpha +\beta {)}^2(\alpha +\beta +1)}$

条件概率与独立性

条件概率

条件概率是在已知某事件发生的条件下，另一事件发生的概率。

$$P(A\mid B)=\frac{P(AB)}{P(B)},P(B)>0$$

条件概率的基本性质：

1. $0⩽P(A\mid B)⩽1$
2. $P(\Omega \mid B)=1$
3. 若 $A_1,A_2,\dots$ 两两互不相容，则 $P({\bigcup }_i{A}_i\mid B)={\sum }_{i}P(A_i\mid B)$

乘法公式：

$$P(AB)=P(A\mid B)\cdot P(B)=P(B\mid A)\cdot P(A)$$

推广到多个事件：

$$P(A_1{A}_2\cdots A_n)=P(A_1)\cdot P(A_2\mid A_1)\cdot P(A_3\mid A_1{A}_2)\cdots P(A_n\mid A_1\cdots A_{n-1})$$

# 条件概率示例：扑克牌问题
import itertools
 
# 计算 P(第二张是红心 | 第一张是红心)
deck = list(range(52))  # 0-12: 红心, 13-25: 方块, 26-38: 梅花, 39-51: 黑桃
 
# 模拟计算
import random
random.seed(42)
 
n_trials = 100000
count = 0
for _ in range(n_trials):
    deck_shuffled = deck.copy()
    random.shuffle(deck_shuffled)
    first, second = deck_shuffled[:2]
    # 已知第一张是红心
    if first < 13:
        if second < 13:  # 第二张也是红心
            count += 1
 
prob = count / n_trials
print(f"P(第二张是红心 | 第一张是红心) ≈ {prob:.4f}")  # 约 0.245
print(f"理论值 = 12/51 = {12/51:.4f}")  # 约 0.235

全概率公式与贝叶斯公式

全概率公式

设 $\{B_1,B_2,\dots ,B_n\}$ 是样本空间的一个划分（完备事件组），即：

• $B_i$ 两两互不相容
• ${\bigcup }_i{B}_i=\Omega$

则对任意事件 $A$：

$$P(A)=\sum _{i=1}^{n}P(A\mid B_i)\cdot P(B_i)$$

全概率公式的应用：将复杂事件 $A$ 分解为若干互不相容的简单事件之和。

# 全概率公式示例：医学诊断问题
# 某疾病在人群中的患病率为 0.1%
# 检验方法的准确率：
#   - 患病者检测阳性的概率（灵敏度）= 99%
#   - 健康者检测阴性的概率（特异度）= 95%
 
# 问题：检测结果为阳性时，真正患病的概率是多少？
 
# 已知
P_D = 0.001      # P(患病)
P_H = 0.999      # P(健康)
P_pos_D = 0.99   # P(阳性|患病)
P_neg_H = 0.95   # P(阴性|健康) = 特异度
 
# 需计算
P_pos_H = 1 - P_neg_H  # P(阳性|健康) = 5%
P_pos = P_pos_D * P_D + P_pos_H * P_H  # 全概率
 
# 贝叶斯公式
P_D_pos = P_pos_D * P_D / P_pos
 
print(f"P(患病|阳性) = {P_D_pos:.4f}")  # 约 0.0194 = 1.94%
print("""
解读：即使检测结果为阳性，真正患病的概率只有约2%！
这就是为什么医学检测需要考虑先验概率和假阳性率。
""")

贝叶斯公式

贝叶斯公式是概率论中最重要的公式之一：

$$P(B_i\mid A)=\frac{P(A\mid B_i)\cdot P(B_i)}{{\sum }_{j=1}^{n}P(A\mid B_j)\cdot P(B_j)}=\frac{P(A\mid B_i)\cdot P(B_i)}{P(A)}$$

术语解释：

术语	贝叶斯视角	频率学派视角
$P(B_i)$	先验概率（Prior）	未知参数的概率分布
$P(A\mid B_i)$	似然（Likelihood）	数据生成的概率
$P(B_i\mid A)$	后验概率（Posterior）	估计的参数分布
$P(A)$	边际似然（Marginal Likelihood）	归一化常数

更多内容参见 贝叶斯推断。

独立性

两个事件的独立性

事件 $A$ 与 $B$ 独立（Independent）当且仅当：

$$P(AB)=P(A)\cdot P(B)$$

与互不相容的关系：

• 若 $A$ 与 $B$ 互不相容，且 $P(A)>0$，$P(B)>0$，则 $P(AB)=0\ne P(A)P(B)$，所以它们不独立
• 独立意味着两个事件”互不影响”

独立性的等价表述：

若 $P(B)>0$，则 $A$ 与 $B$ 独立 $\iff P(A\mid B)=P(A)$

多个事件的独立性

事件 $A_1,A_2,\dots ,A_n$ 相互独立（Mutually Independent）当且仅当对任意子集 $\{i_1,i_2,\dots ,i_k\}$：

$$P\left(\bigcap _{j=1}^k{A}_{i_j}\right)=\prod _{j=1}^{k}P(A_{i_j})$$

需要注意：$n$ 个事件两两独立（Pairwise Independent）不一定相互独立。

# 两两独立但不相互独立的经典例子
# 投掷两枚均匀硬币，考虑事件：
# A: 第一次正面朝上
# B: 第二次正面朝上  
# C: 两次结果相同（都为正面或都为反面）
 
# 计算各事件的概率
# P(A) = P(B) = 0.5
# P(C) = P(两次都为正面) + P(两次都为反面) = 0.25 + 0.25 = 0.5
 
# P(A)P(B) = 0.25 = P(AB) = P(两次都为正面) ✓
# P(A)P(C) = 0.25 = P(AC) = P(两次都为正面) ✓
# P(B)P(C) = 0.25 = P(BC) = P(两次都为正面) ✓
 
# 但 P(ABC) = P(两次都为正面) = 0.25
# 而 P(A)P(B)P(C) = 0.125
# 所以三者不相互独立！
 
print("A, B, C 两两独立但不相互独立")
print("P(ABC) = 0.25 ≠ P(A)P(B)P(C) = 0.125")

条件独立性

条件独立（Conditional Independence）：

在事件 $C$ 发生的条件下，$A$ 与 $B$ 条件独立当且仅当：

$$P(AB\mid C)=P(A\mid C)\cdot P(B\mid C)$$

或等价地：

$$P(A\mid BC)=P(A\mid C)$$

条件独立与独立的关系：

• 独立不一定条件独立
• 条件独立也不一定独立
• 但条件独立在贝叶斯网络和概率图模型中非常重要

# 条件独立示例：朴素贝叶斯分类器
# 假设特征 X1, X2, ..., Xn 在给定类别 C 的条件下条件独立
# 则 P(C | X1, ..., Xn) ∝ P(C) * ∏ P(Xi | C)
 
# 示例：垃圾邮件分类
# P(垃圾|"免费","中奖") ∝ P(垃圾) * P("免费"|垃圾) * P("中奖"|垃圾)
#                       / [P(垃圾) * P("免费"|垃圾) * P("中奖"|垃圾)
#                        + P(正常) * P("免费"|正常) * P("中奖"|正常)]
 
# 简化的朴素贝叶斯计算
def naive_bayes_classify(words, class_probs, word_likelihoods):
    """
    朴素贝叶斯分类
    words: 观测到的词
    class_probs: 类别的先验概率
    word_likelihoods: P(word|class) 的字典
    """
    scores = {}
    for cls, prior in class_probs.items():
        score = prior
        for word in words:
            score *= word_likelihoods.get((cls, word), 0.001)  # 平滑
        scores[cls] = score
    
    # 归一化
    total = sum(scores.values())
    return {cls: s/total for cls, s in scores.items()}
 
# 示例
class_probs = {"spam": 0.3, "ham": 0.7}
word_likelihoods = {
    ("spam", "free"): 0.8,
    ("spam", "prize"): 0.6,
    ("ham", "free"): 0.1,
    ("ham", "prize"): 0.05,
}
 
result = naive_bayes_classify(["free", "prize"], class_probs, word_likelihoods)
print(f"P(spam|words) = {result['spam']:.4f}")  # 约 0.97
print(f"P(ham|words) = {result['ham']:.4f}")    # 约 0.03

条件期望与全期望公式

条件期望

条件期望是给定某信息条件下随机变量的期望。

离散情况：

$$E[X\mid Y=y]=\sum _{x}x\cdot P(X=x\mid Y=y)=\sum _{x}x\cdot \frac{P(X=x,Y=y)}{P(Y=y)}$$

连续情况：

$$E[X\mid Y=y]={\int }_{-\infty }^{+\infty }x\cdot f_{X|Y}(x|y)dx$$

其中 $f_{X|Y}(x|y)=\frac{f_{X,Y}(x,y)}{f_Y(y)}$ 是条件概率密度函数。

条件期望作为随机变量：$E[X\mid Y]$ 是 $Y$ 的函数，也是一个随机变量。

import numpy as np
 
# 条件期望示例：离散情况
# 设 (X, Y) 的联合分布为
# P(X=0, Y=0) = 0.1, P(X=0, Y=1) = 0.2
# P(X=1, Y=0) = 0.3, P(X=1, Y=1) = 0.4
 
joint = {
    (0, 0): 0.1,
    (0, 1): 0.2,
    (1, 0): 0.3,
    (1, 1): 0.4
}
 
# 计算边际分布
p_y = {}
for (x, y), p in joint.items():
    p_y[y] = p_y.get(y, 0) + p
 
# 计算条件期望 E[X | Y]
for y in [0, 1]:
    e_x_given_y = sum(x * joint[(x, y)] / p_y[y] for x in [0, 1])
    print(f"E[X | Y={y}] = {e_x_given_y:.2f}")
 
# E[X | Y] 作为随机变量，其期望等于 E[X]
e_x = sum(x * sum(p for (x2, y), p in joint.items() if x2 == x) for x in [0, 1])
print(f"E[X] = {e_x:.2f}")

全期望公式

全期望公式（Law of Total Expectation）：

$$E[X]=E[E[X\mid Y]]$$

或等价地：

$$E[X]=\sum _{y}E[X\mid Y=y]\cdot P(Y=y)\text{（离散）}$$ $$E[X]={\int }_{-\infty }^{+\infty }E[X\mid Y=y]\cdot f_Y(y)dy\text{（连续）}$$

全期望公式的应用：

1. 分解复杂期望：将期望按条件分解为加权平均
2. 递归计算：在概率DP中计算期望
3. 简化证明：证明其他概率恒等式

# 全期望公式示例：计算随机变量的期望
 
# 问题：掷两个骰子，X = 两个骰子点数的最大值，求 E[X]
 
# 方法1：直接计算
def direct_expectation():
    total = 0
    for i in range(1, 7):
        for j in range(1, 7):
            total += max(i, j)
    return total / 36
 
# 方法2：使用全期望公式
# E[X] = E[E[X | 第一个骰子的值]]
def total_expectation():
    # 给定第一个骰子为 k 时，E[X|k]
    def e_x_given_k(k):
        total = 0
        for j in range(1, 7):
            total += max(k, j)
        return total / 6
    
    # E[X] = sum_k E[X|k] * P(k)
    e_x = sum(e_x_given_k(k) * (1/6) for k in range(1, 7))
    return e_x
 
print(f"直接计算: E[X] = {direct_expectation():.4f}")
print(f"全期望公式: E[X] = {total_expectation():.4f}")
 
# 结果验证
assert abs(direct_expectation() - total_expectation()) < 1e-6

全期望公式在概率DP中的应用：

设 $E_i$ 为从状态 $i$ 到达目标的期望，则：

$$E_i=1+\sum _{j}P(i\to j)\cdot E_j$$

这正是全期望公式的具体应用。

极限定理

极限定理是概率论最深刻的结果之一，揭示了大量随机现象的统计规律性。

大数定律

弱大数定律

设 $X_1,X_2,\dots$ 是独立同分布（i.i.d.）的随机变量序列，$E[X_i]=\mu$，则：

$$\frac{1}{n}\sum _{i=1}^n{X}_i\stackrel{P}{\to }\mu (n\to \infty )$$

即样本均值依概率收敛于期望。

依概率收敛：$Y_n\stackrel{P}{\to }a$ 表示对任意 $\epsilon >0$，

$$\underset{n\to \infty }{\lim }P(|Y_n-a|>\epsilon )=0$$

import numpy as np
import matplotlib.pyplot as plt
 
# 大数定律的可视化演示
np.random.seed(42)
 
n_trials = 10000
n_samples_list = [10, 50, 100, 500, 1000, 5000, 10000]
 
for n_samples in n_samples_list:
    # 模拟：投掷n_samples次均匀骰子，计算平均点数
    samples = np.random.randint(1, 7, n_samples)
    sample_mean = np.mean(samples)
    print(f"n={n_samples:5d}: 样本均值 = {sample_mean:.4f} (真实期望 = 3.5)")
 
# 更详细的演示
print("\n--- 大数定律收敛演示 ---")
sample_means = []
cumulative_sum = 0
for n in range(1, n_trials + 1):
    cumulative_sum += np.random.randint(1, 7)
    sample_means.append(cumulative_sum / n)
 
print(f"最终样本均值: {sample_means[-1]:.4f}")
print(f"收敛到真实期望 3.5 的速度由大数定律保证")

强大数定律

在更弱的条件下，样本均值几乎必然收敛到期望：

$$\frac{1}{n}\sum _{i=1}^n{X}_i\stackrel{a.s.}{\to }\mu (n\to \infty )$$

几乎必然收敛：$Y_n\stackrel{a.s.}{\to }a$ 表示 $P({\lim }_{n\to \infty }{Y}_n=a)=1$

强大数定律是更深刻的结果，由 Kolmogorov 证明。

大数定律的意义

1. 频率的稳定性：大量重复试验中，事件发生的频率趋于稳定在概率附近
2. 蒙特卡洛方法：用样本均值近似期望的理论基础
3. 统计估计：样本均值是总体期望的强一致估计

# 蒙特卡洛方法：大数定律的应用
import numpy as np
 
def estimate_pi_monte_carlo(n_points):
    """
    用蒙特卡洛方法估计圆周率 π
    在单位正方形 [0,1]×[0,1] 中随机投点，
    点落在单位圆内的概率 = π/4
    """
    x = np.random.uniform(0, 1, n_points)
    y = np.random.uniform(0, 1, n_points)
    
    # 判断点是否在单位圆内 (x^2 + y^2 <= 1)
    inside = (x**2 + y**2) <= 1
    
    # 圆内点的比例 ≈ π/4
    pi_estimate = 4 * np.sum(inside) / n_points
    return pi_estimate
 
# 不同样本量的估计
print("蒙特卡洛估计圆周率：")
for n in [100, 1000, 10000, 100000, 1000000]:
    estimate = estimate_pi_monte_carlo(n)
    error = abs(estimate - np.pi)
    print(f"n = {n:>8}: π ≈ {estimate:.6f}, 误差 = {error:.6f}")
 
print(f"\n真实 π = {np.pi:.6f}")
print("随着样本量增加，估计值越来越接近真实值（体现了大数定律）")

中心极限定理

定理陈述

设 $X_1,X_2,\dots$ 是独立同分布的随机变量序列，$E[X_i]=\mu$，$\text{Var}(X_i)={\sigma }^2$（有限且非零），则：

$$Z_n=\frac{{\sum }_{i=1}^n{X}_i-n\mu }{\sigma \sqrt{n}}\stackrel{d}{\to }N(0,1)(n\to \infty )$$

即标准化后的和依分布收敛于标准正态分布。

依分布收敛：$Y_n\stackrel{d}{\to }Y$ 表示 $F_{Y_n}(y)\to F_Y(y)$（在 $F_Y$ 的连续点上）。

等价形式：

$$\frac{{\bar{X}}_n-\mu }{\sigma /\sqrt{n}}\stackrel{d}{\to }N(0,1)$$

或

$${\bar{X}}_n\approx N\left(\mu ,\frac{{\sigma }^2}{n}\right)$$

import numpy as np
import matplotlib.pyplot as plt
from scipy import stats
 
# 中心极限定理演示：无论原分布是什么，和的分布趋近正态分布
 
def visualize_clt(dist_type='uniform', n_samples=30, n_experiments=10000):
    """
    演示中心极限定理
    绘制样本均值的分布，逐渐趋近正态分布
    """
    if dist_type == 'uniform':
        # 均匀分布 [0, 1]
        samples = np.random.uniform(0, 1, (n_experiments, n_samples))
    elif dist_type == 'exponential':
        # 指数分布
        samples = np.random.exponential(1, (n_experiments, n_samples))
    elif dist_type == 'bernoulli':
        # 伯努利分布
        samples = np.random.randint(0, 2, (n_experiments, n_samples))
    
    # 计算每个实验的样本均值
    sample_means = np.mean(samples, axis=1)
    
    # 绘制直方图和理论正态曲线
    mu = np.mean(samples[0])  # 真实均值
    sigma = np.std(samples[0]) / np.sqrt(n_samples)  # 标准误差
    
    return sample_means, mu, sigma
 
# 对比不同样本量
print("中心极限定理演示（均匀分布 → 样本均值的分布）：\n")
for n in [1, 5, 30, 100]:
    means, mu, sigma = visualize_clt('uniform', n_samples=n)
    print(f"n = {n:3d}: 均值 = {np.mean(means):.4f}, 标准差 = {np.std(means):.4f}")
    print(f"         理论值: 均值 = {mu:.4f}, 标准差 = {sigma:.4f}\n")
 
print("观察：随着 n 增加，样本均值的分布越来越接近正态分布 N(μ, σ²/n)")

中心极限定理的意义

1. 解释正态分布的普适性：大量微小独立因素的和近似正态分布
2. 近似计算：可用于近似计算难以精确求解的概率
3. 假设检验：许多统计检验基于正态近似的理论

# 中心极限定理的应用：近似计算概率
 
# 问题：某考试有100道选择题，每题5个选项，正确率为40%
# 求总分超过45分的概率
 
# 精确方法（二项分布）
from scipy import stats
 
n, p = 100, 0.4
exact_prob = 1 - stats.binom.cdf(45, n, p)
print(f"精确解（二项分布）: P(X > 45) = {exact_prob:.4f}")
 
# 近似方法（中心极限定理）
# X ≈ N(np, np(1-p))
mu = n * p  # 40
sigma = np.sqrt(n * p * (1 - p))  # 4.899
 
# P(X > 45) = P(Z > (45.5 - 40) / 4.899)（使用连续性修正）
clt_prob = 1 - stats.norm.cdf(45.5, mu, sigma)
print(f"CLT近似: P(X > 45) = {clt_prob:.4f}")
 
print(f"差异: {abs(exact_prob - clt_prob):.4f}")

与机器学习的联系

统计学习理论

机器学习中的许多理论结果基于大数定律和中心极限定理：

1. 经验风险最小化：当样本量趋于无穷时，经验风险趋近于期望风险
2. 泛化误差界：基于浓度不等式和极限定理
3. 参数估计的渐近分布：如逻辑回归参数的渐近正态性

# 机器学习中的中心极限定理应用
import numpy as np
from scipy import stats
 
def asymptotic_confidence_interval(data, confidence=0.95):
    """
    构建均值的渐近置信区间
    基于中心极限定理，当样本量足够大时，样本均值近似正态分布
    """
    n = len(data)
    sample_mean = np.mean(data)
    sample_std = np.std(data, ddof=1)
    standard_error = sample_std / np.sqrt(n)
    
    # 置信区间
    z = stats.norm.ppf((1 + confidence) / 2)
    margin = z * standard_error
    
    return sample_mean - margin, sample_mean + margin
 
# 示例：估计某模型预测误差的置信区间
np.random.seed(42)
prediction_errors = np.random.normal(loc=0.1, scale=0.05, size=1000)
 
ci = asymptotic_confidence_interval(prediction_errors, confidence=0.95)
print(f"95% 置信区间: [{ci[0]:.4f}, {ci[1]:.4f}]")
print(f"样本均值: {np.mean(prediction_errors):.4f}")

蒙特卡洛方法

# 蒙特卡洛估计及其误差分析
import numpy as np
 
def monte_carlo_with_confidence(f, n_samples, alpha=0.05):
    """
    蒙特卡洛估计及其渐近置信区间
    
    基于中心极限定理，估计量的渐近分布为：
    sqrt(n) * (estimator - true_value) / std ≈ N(0, 1)
    """
    samples = f(n_samples)
    estimate = np.mean(samples)
    std_error = np.std(samples, ddof=1) / np.sqrt(n_samples)
    
    z = stats.norm.ppf(1 - alpha/2)
    margin = z * std_error
    
    return estimate, (estimate - margin, estimate + margin)
 
# 示例：估计高维积分
def high_dim_integration(n):
    """
    估计 I = ∫_{[0,1]^d} exp(-sum(x_i^2)) dx
    """
    dim = 10  # 10维
    points = np.random.uniform(0, 1, (n, dim))
    values = np.exp(-np.sum(points**2, axis=1))
    return values
 
# 计算估计和置信区间
np.random.seed(42)
estimate, ci = monte_carlo_with_confidence(high_dim_integration, 10000)
print(f"估计值: {estimate:.6f}")
print(f"95% 置信区间: [{ci[0]:.6f}, {ci[1]:.6f}]")
print(f"相对误差: ±{((ci[1]-ci[0])/2/estimate)*100:.2f}%")

Bootstrap 方法

Bootstrap 是现代统计中一种通用的重采样方法，其理论依据包含大数定律和中心极限定理。

# Bootstrap 方法演示
import numpy as np
 
def bootstrap_ci(data, statistic_func, n_bootstrap=10000, confidence=0.95):
    """
    Bootstrap 置信区间
    
    1. 从原始数据中有放回地抽取 n 个样本（Bootstrap 样本）
    2. 计算每个 Bootstrap 样本的统计量
    3. 用统计量的分布构建置信区间
    """
    n = len(data)
    bootstrap_stats = []
    
    for _ in range(n_bootstrap):
        # 有放回抽样
        boot_sample = np.random.choice(data, size=n, replace=True)
        boot_stat = statistic_func(boot_sample)
        bootstrap_stats.append(boot_stat)
    
    alpha = 1 - confidence
    lower = np.percentile(bootstrap_stats, 100 * alpha / 2)
    upper = np.percentile(bootstrap_stats, 100 * (1 - alpha / 2))
    
    return np.mean(bootstrap_stats), (lower, upper)
 
# 示例：估计中位数的置信区间
np.random.seed(42)
data = np.random.exponential(scale=2, size=100)
 
median, ci = bootstrap_ci(data, np.median)
print(f"样本中位数: {np.median(data):.4f}")
print(f"Bootstrap 估计: {median:.4f}")
print(f"95% Bootstrap CI: [{ci[0]:.4f}, {ci[1]:.4f}]")

基础概念

概率定义与基本公式

设样本空间为 $\Omega$，事件 $A$ 的概率记为 $P(A)$，满足：

• $0⩽P(A)⩽1$
• $P(\Omega )=1$
• 若 $A_1,A_2,\dots ,A_n$ 互不相容，则 $P\left({\bigcup }_{i=1}^n{A}_i\right)={\sum }_{i=1}^{n}P(A_i)$

独立事件：若 $P(AB)=P(A)P(B)$，则称事件 $A$ 与 $B$ 独立。

期望的线性性质

期望满足线性性质，这是概率 DP 的核心基础：

$$E(X+Y)=E(X)+E(Y)$$

注意：对于独立事件的乘积有 $E(XY)=E(X)\cdot E(Y)$，但这一性质在大多数概率 DP 问题中不直接使用。¹

条件概率与贝叶斯公式

条件概率：在事件 $B$ 已发生的条件下，事件 $A$ 发生的概率

$$P(A\mid B)=\frac{P(AB)}{P(B)}$$

贝叶斯公式：

$$P(B\mid A)=\frac{P(A\mid B)\cdot P(B)}{P(A)}$$

更多内容参见 贝叶斯推断。

概率 DP

概率 DP 是指在动态规划中引入概率和期望，用于求解在随机过程中达到某种状态的概率或期望值。

顺推法（求概率）

顺推法从初始状态出发，按照状态转移逐步计算到达目标状态的概率。

适用场景：已知初始状态概率分布，求解到达目标状态的概率。

设 $dp[i]$ 表示经过 $i$ 步后到达目标状态的概率，转移方程为：

$$dp[i+1][j]=\sum _{k}dp[i][k]\cdot P(k\to j)$$

逆推法（求期望）

逆推法从目标状态反推回初始状态，利用期望的线性性质构建方程。

适用场景：求从初始状态到达目标状态的期望步数或期望代价。

设 $E[i]$ 表示从状态 $i$ 到达目标状态的期望步数，则：

$$E[i]=1+\sum _{j}P(i\to j)\cdot E[j]$$

其中 $1$ 表示当前这一步。

高斯消元法

当状态转移存在环（即后效性）时，逆推法构建的方程组可能包含多个未知数，需要使用高斯消元求解。

适用场景：状态转移图存在环，无法直接用 DAG 上的 DP 求解。

设期望向量为 $\mathbf{E}$，转移矩阵为 $\mathbf{P}$，则：

$$\mathbf{E}=1+\mathbf{P}\cdot \mathbf{E}$$

整理得：

$$(\mathbf{I}-\mathbf{P})\cdot \mathbf{E}=1$$

典型问题类型

到达目标的期望步数

常见于游走类问题，如掷骰子、移动棋子等。

问题模式：从起点出发，每次随机移动，求首次到达目标的期望步数。

解法：逆推法 + 方程组建立 + 高斯消元

期望收益最大化

在随机环境中做决策，使得期望收益最大化。

问题模式：每一步有多种选择，每种选择有对应的概率分布和收益，求最大期望收益。

解法：概率 DP 求得所有状态的期望收益后取最大值

概率最大化决策

在不确定环境下做出决策，使得达到目标的概率最大。

问题模式：与期望收益最大化类似，但目标是概率而非收益。

代码实现

基础概率 DP 模板

以下模板展示顺推法求解概率问题：

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;  // n: 状态数, m: 转移方式数
    vector<vector<pair<int, double>>> g(n);
    
    // 构建转移图：g[i] = {(next_state, probability), ...}
    for (int i = 0; i < m; i++) {
        int u, v;
        double p;
        cin >> u >> v >> p;
        g[u].push_back({v, p});
    }
    
    vector<double> dp(n, 0.0);
    dp[0] = 1.0;  // 初始状态概率为 1
    
    for (int i = 0; i < n; i++) {
        for (auto [v, p] : g[i]) {
            dp[v] += dp[i] * p;
        }
    }
    
    // 输出到达各状态的概率
    for (int i = 0; i < n; i++) {
        cout << "State " << i << ": " << dp[i] << "\n";
    }
    
    return 0;
}

期望 DP 与方程组

以下模板展示使用高斯消元求解期望 DP：

#include <bits/stdc++.h>
using namespace std;
 
const double EPS = 1e-8;
 
int gauss(vector<vector<double>>& a, vector<double>& ans) {
    int n = a.size();
    int m = a[0].size() - 1;
    
    for (int col = 0, row = 0; col < m && row < n; col++, row++) {
        // 选主元
        int max_row = row;
        for (int i = row; i < n; i++) {
            if (fabs(a[i][col]) > fabs(a[max_row][col]))
                max_row = i;
        }
        if (fabs(a[max_row][col]) < EPS) return 0;  // 无解
        
        swap(a[row], a[max_row]);
        
        // 消元
        for (int i = 0; i < n; i++) {
            if (i != row && fabs(a[i][col]) > EPS) {
                double factor = a[i][col] / a[row][col];
                for (int j = col; j <= m; j++) {
                    a[i][j] -= factor * a[row][j];
                }
            }
        }
    }
    
    // 回代
    for (int i = 0; i < m; i++) {
        ans[i] = a[i][m] / a[i][i];
    }
    return 1;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;  // 状态数
    cin >> n;
    vector<vector<pair<int, double>>> g(n);
    vector<int> out_degree(n, 0);
    
    // 构建转移图
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        out_degree[i] = k;
        for (int j = 0; j < k; j++) {
            int v;
            double p;
            cin >> v >> p;
            g[i].push_back({v, p});
        }
    }
    
    // 建立方程组: E[i] = 1 + sum(P[i->j] * E[j])
    // 移项得: E[i] - sum(P[i->j] * E[j]) = 1
    vector<vector<double>> a(n, vector<double>(n + 1, 0.0));
    
    for (int i = 0; i < n; i++) {
        a[i][i] = 1.0;
        a[i][n] = 1.0;  // 常数项
        for (auto [v, p] : g[i]) {
            a[i][v] -= p;
        }
    }
    
    vector<double> ans(n);
    if (gauss(a, ans)) {
        cout << "期望值:\n";
        for (int i = 0; i < n; i++) {
            cout << "State " << i << ": " << ans[i] << "\n";
        }
    }
    
    return 0;
}

例题

骰子期望问题

问题：掷一枚均匀六面骰子，求首次掷出 6 的期望掷骰次数。

分析：设期望为 $E$。第一次掷骰：

• 若掷出 6（概率 $1/6$），结束，步数为 1
• 若未掷出 6（概率 $5/6$），步数为 $1+E$

列方程：

$$E=\frac{1}{6}\cdot 1+\frac{5}{6}\cdot (1+E)$$

解得 $E=6$。

游走类问题

问题：在一维数轴上，从位置 0 出发，每次等概率向左或向右走一步，求首次到达位置 $n$ 的期望步数。

分析：设从位置 $i$ 出发的期望为 $E_i$，有：

$$E_i=1+\frac{1}{2}{E}_{i-1}+\frac{1}{2}{E}_{i+1}$$

边界条件：$E_0=0$，$E_n=0$（假设 $n$ 为目标）。

解此方程组得 $E_i=i(n-i)$。

状态压缩概率 DP

问题：给定 $n$ 枚硬币，每枚硬币正面朝上的概率为 $p_i$，求恰好有 $k$ 枚正面朝上的概率。

分析：设 $dp[mask]$ 表示状态 $mask$ 下正面朝上的概率，状态转移：

$$dp[mask\cup \{i\}]+=dp[mask]\cdot p_i$$ $$dp[mask]\ast =(1-p_i)\text{（不选第 }i\text{ 枚）}$$

复杂度 $O(n\cdot 2^n)$。

参考资料

Footnotes

1. 本段内容来自 概率期望 DP - OI Wiki ↩