专栏文章

概率论基础

JJunounly
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip76682
此快照首次捕获于
2025/12/03 07:16
3 个月前
此快照最后确认于
2025/12/03 07:16
3 个月前
查看原文

简介

本文主要介绍部分概率论 (theory of probability) 的基本概念，以及一些基础的概率不等式 (probability inequality) 及证明方法，并简述其在算法竞赛中的应用。

前置知识

  • 函数、和式、组合数学、导数、微积分、生成函数
如果出于学术原因阅读本文，建议先建立以上知识的基本素养再继续阅读。
  • exe^x 与 ln⁡(x)\ln(x) 的放缩公式
这里仅讲述本文需要用到的公式。
ex≥x+1,for all x≥0e^x \ge x+1,\text{for all }x \ge 0
证明： 对两边同时求导，可得上式。
ex≥x+1,for all x≥0⇐ex≥1,for all x≥0\begin{aligned} & e^x \ge x+1,\text{for all }x \ge 0 \\ \Leftarrow & e^x\ge 1,\text{for all }x \ge 0 \end{aligned}
ln⁡(x+1)≥2xx+2,for all x≥0\ln(x+1) \ge \frac{2x}{x+2},\text{for all }x \ge 0
证明： 同理，对两边同时求导。
ln⁡(x+1)≥2xx+2,for all x≥0⇐1x+1≥4(x+2)2,for all x≥0⇐(x+2)2≥4(x+1),for all x≥0⇐x2≥0,for all x≥0\begin{aligned} & \ln(x+1) \ge \frac{2x}{x+2},\text{for all }x \ge 0 \\ \Leftarrow & \frac{1}{x+1} \ge \frac{4}{(x+2)^2},\text{for all }x \ge 0 \\ \Leftarrow & (x+2)^2 \ge 4(x+1),\text{for all }x \ge 0 \\ \Leftarrow & x^2 \ge 0,\text{for all }x \ge 0 \\ \end{aligned}
ln⁡(1−x)≥1−x2−12(1−x),for all 0≤x<1\ln(1-x) \ge \frac{1-x}{2} - \frac{1}{2(1-x)},\text{for all } 0 \le x < 1
证明： 同理，对两边同时求导。
ln⁡(1−x)≥1−x2−12(1−x),for all 0≤x<1⇐−11−x≥−12−12(1−x)2,for all 0≤x<1⇐−21−x≥−1−1(1−x)2,for all 0≤x<1⇐(11−x)2≥0,for all 0≤x<1\begin{aligned} & \ln(1-x) \ge \frac{1-x}{2} - \frac{1}{2(1-x)},\text{for all } 0 \le x < 1 \\ \Leftarrow & -\frac{1}{1-x} \ge -\frac{1}{2} -\frac{1}{2(1-x)^2},\text{for all } 0 \le x < 1 \\ \Leftarrow & -\frac{2}{1-x} \ge -1 -\frac{1}{(1-x)^2},\text{for all } 0 \le x < 1 \\ \Leftarrow & \Big (\frac{1}{1-x} \Big )^2 \ge 0,\text{for all } 0 \le x < 1\\ \end{aligned}
  • 部分微积分公式
ddxeax=aeax\frac{\mathrm{d}}{\mathrm{d}x} e^{ax}=a e^{ax}
证明： 显然有
ddxeax=ln⁡(ea)⋅eax=aeax\frac{\mathrm{d}}{\mathrm{d}x} e^{ax}=\ln\big(e^a\big) \cdot e^{ax}=a e^{ax}
∫−∞∞e−x22dx=2π\int \limits_{-\infty}^{\infty} e^{-\frac{x^2}{2}} \mathrm{d} x = \sqrt{2 \pi}
证明： 考虑将原式平方后展开：
(∫−∞∞e−x22dx)2=∫−∞∞∫−∞∞e−x2+y22dxdy\bigg (\int \limits_{-\infty}^{\infty} e^{-\frac{x^2}{2}} \mathrm{d} x \bigg )^2 = \int \limits_{-\infty}^{\infty} \int \limits_{-\infty}^{\infty} e^{-\frac{x^2+y^2}{2}} \mathrm{d} x \mathrm{d} y
三角换元，令 x=rsin⁡θ,y=rcos⁡θx=r \sin \theta,y=r \cos \theta。
构造雅可比行列式：
J=(∂x∂r∂x∂θ∂y∂r∂y∂θ)=(cos⁡θ−rsin⁡θsin⁡θrcos⁡θ)\mathcal{J}= \begin{pmatrix} \frac{\partial x}{\partial r} & \frac{\partial x}{\partial \theta}\\ \frac{\partial y}{\partial r} & \frac{\partial y}{\partial \theta} \end{pmatrix} = \begin{pmatrix} \cos \theta & -r \sin \theta \\ \sin \theta & r \cos \theta \end{pmatrix}
则 dxdy=∣det⁡(J)∣drdθ=rdrdθ\mathrm{d}x \mathrm{d}y=|\det(\mathcal{J})|\mathrm{d}r \mathrm{d} \theta=r\mathrm{d}r \mathrm{d} \theta，即原式可以变换为
∫02πdθ∫0∞e−r22rdr=2π∫0∞e−r22rdr\begin{aligned} \int \limits_{0}^{2\pi} \mathrm{d} \theta \int \limits_{0}^{\infty} e^{-\frac{r^2}{2}} r \mathrm{d} r = 2\pi \int \limits_{0}^{\infty} e^{-\frac{r^2}{2}} r \mathrm{d} r \end{aligned}
换元，令 u=r22u=\frac{r^2}{2}，则 rdr=dur \mathrm{d} r=\mathrm{d} u，原式等价于：
2π∫0∞e−udu=−2πe−u∣0∞=2π2\pi \int \limits_{0}^{\infty} e^{-u} \mathrm{d} u = - 2\pi e^{-u} \bigg |_{0}^{\infty} = 2\pi
由于原等式左边为正数，所以可以两边同时开平方，得到：
∫−∞∞e−x22dx=2π\int \limits_{-\infty}^{\infty} e^{-\frac{x^2}{2}} \mathrm{d} x = \sqrt{2 \pi}

基本概念

  • 事件与概率
在概率论中，概率 (probability) 反映了一个事件 (event) 发生的可能性大小，一个事件的概率由其包含的所有基本事件 (elementary event) 确定，一般来讲，我们所讨论的事件都是基本事件。
在本文中，我们将基本事件 ω∈Ω\omega \in \Omega 发生的概率记为 Pr{ω}\textbf{Pr} \{ \omega \} 或 Pr(ω)\textbf{Pr}(\omega)，使用花括号表示事件。
对于给定的问题，我们将可能发生并赋予概率 Pr(ω)\textbf{Pr} ( \omega ) 的所有基本事件 ω\omega 所组成的集合 Ω\Omega 叫做概率空间 (probability space)。
对于每个离散的概率空间，我们给每个基本事件 ω\omega 赋予概率 Pr(ω)\textbf{Pr}(\omega) 后，必须满足规则：
Pr(ω)≥0,for all ω∈Ω\textbf{Pr}(\omega) \ge 0, \text{for all } \omega \in \Omega
∑ω∈ΩPr(ω)=1\sum \limits_{\omega \in \Omega} \textbf{Pr}(\omega) = 1
即总概率值恒为 11。
  • 随机试验
随机试验 (random experiment) 是在相同条件下对某随机现象进行的大量重复观测。
一个随机试验 EE 的所有可能结果的集合称为样本空间 (sample space)。试验的每一个可能结果称为样本点 (sample point)。
  • 随机变量
设随机试验 EE 的样本空间为 Ω\Omega，对于每一个样本点 ω\omega，都有唯一的实数 X(ω)X(\omega) 与之对应，且对于任意实数 xx，事件 {ω∣X(ω)≤x}\{ \omega | X(\omega) \le x \} 都有确定的概率 Pr{ω∣X(ω)≤x}\textbf{Pr} \{ \omega | X(\omega) \le x \} 与之对应，则称 X(ω)X(\omega) 为随机变量 (random variable)，记为 XX。
不难发现，XX 是一个定义在 Ω\Omega 上的单值函数 X=X(ω)X=X(\omega)。
随机变量分为离散型随机变量和连续型随机变量。顾名思义，分别代表着其值域 Ω\Omega 是离散的或连续的。
根据离散型随机变量 XX 的分布律，记 pkp_k 为 Pr{X=xk}\textbf{Pr} \{ X=x_k \}，其中 k∈N+k \in \mathbb{N}^+。
对于连续型随机变量 XX，记其概率密度 (probability density) 函数为 fX(x)=Pr{X=x}f_X(x)=\textbf{Pr} \{ X=x \}。
  • 数学期望
随机变量 XX 的数学期望 (expected value) 为其取值被概率加权后的和，简称期望，记为 μ\mu 或 E(X)\mathbb{E}(X)。可以理解为一种加权平均 (weighted average)。
对于离散型随机变量 XX，其数学期望为 ∑k=1∞xkpk\sum \limits_{k=1}^{\infty} x_kp_k。
对于连续型随机变量 XX，其数学期望为 ∫−∞∞xfX(x)dx\int \limits_{-\infty}^{\infty} xf_X(x) \mathrm{d} x。
当然，积分式更为一般化，离散型随机变量也可以用上述积分式表达，所以以下的一些推导会直接采用积分式。
期望能够描述随机变量平均取值的大小。
  • 方差与标准差
随机变量 XX 的方差 (variance) 描述了随机变量的取值与其数学期望的偏离程度，记为 σ2\sigma^2 或 Var(X)\mathrm{Var}(X)。
记随机变量 XX 的期望为 μ\mu。
若 XX 为离散型随机变量，其方差为 ∑k=1∞(xk−μ)2pk\sum \limits_{k=1}^{\infty} (x_k-\mu)^2 p_k。
若 XX 为连续型随机变量，其方差为 ∫−∞∞(x−μ)2fX(x)dx\int \limits_{-\infty}^{\infty} (x-\mu)^2 f_X(x) \mathrm{d} x。
与期望同理，以下的一些推导会直接采用积分式。
根据定义，容易推导出期望与方差的数量关系：
Var(X)=E((X−μ)2)=E(X2)−(E(X))2\text{Var}(X)=\mathbb{E}\big ( (X-\mu)^2 \big )=\mathbb{E}\big(X^2\big)-\big (\mathbb{E}(X) \big )^2
我们有时会引入标准差 (standard deviation)，记为 σ\sigma，满足 σ=Var(x)\sigma=\sqrt{\mathrm{Var}(x)}。
  • 概率分布
概率分布 (probability distribution) 指的是用于表述随机变量取值的概率规律。
概率分布能够刻画随机变量取值规律的概率测度。
  • Bernoulli\textbf{Bernoulli} 分布
对于随机试验 EE 中的随机变量 XX，若其值域 D={x1=1,x2=0}D=\{ x_1=1,x_2=0 \}，且 p1=p,p2=1−pp_1=p,p_2=1-p，则称 XX 服从 pp 的 Bernoulli\text{Bernoulli} 分布，记为 X∼B(1,p)X \sim \text{B}(1,p)。
其中满足以上条件的随机试验 EE 被称作 Bernoulli\textbf{Bernoulli} 试验，其中 X=1X=1 代表试验成功。
  • 二项分布
二项分布 (binomial distribution) 描述了一系列独立重复的 Bernoulli\text{Bernoulli} 试验的成功次数的概率分布，是 Bernoulli\text{Bernoulli} 分布的一般化。
考虑 nn 次独立重复，且每次都有 pp 的概率成功的 Bernoulli\text{Bernoulli} 试验：
对于随机变量 XX，若所有 0≤k≤n0 \le k \le n 的整数 kk 都满足 {X=k}\{ X=k \} 等价于 {n\{n 次 Bernoulli\text{Bernoulli} 试验中有 kk 次成功}\}，那么称 XX 服从 nn 和 pp 的二项分布，记为 X∼B(n,p)X \sim \text{B}(n,p)。
形式化地，若离散型随机变量 XX 的分布律满足
Pr(X=k)=(nk)pk(1−p)n−k\textbf{Pr}(X=k)= \binom{n}{k} p^k (1-p)^{n-k}
时，那么称 XX 服从 nn 和 pp 的二项分布。
当 n=1n=1 时，二项分布为 Bernoulli\text{Bernoulli} 分布。
容易发现，二者都是离散型随机变量的概率分布。
  • 正态分布
正态分布 (normal distribution) 是一种连续型随机变量的概率分布。
若连续型随机变量 XX 的概率密度函数为
fX(x)=12πσe−(x−μ)22σ2f_X(x)= \frac{1}{\sqrt{2 \pi} \sigma} e ^ {-\frac{(x-\mu)^2}{2\sigma^2}}
其中 σ>0\sigma>0，则称 XX 服从 μ\mu 和 σ2\sigma^2 的正态分布，记为 X∼N(μ,σ2)X \sim \text{N}\big(\mu,\sigma^2\big)。
现实世界中许多事物往往服从正态分布。
  • 矩生成函数
对于随机变量 XX 与随机数 ss，定义 XX 的矩生成函数 (moment generating function) 为：
MX(s)=E(esX)M_X(s)=\mathbb{E}\big(e^{sX}\big)
将期望展开，可得：
若 XX 为离散型随机变量，其矩生成函数为 ∑k=1∞esxkpk\sum \limits_{k=1}^{\infty} e^{sx_k} p_k。
若 XX 为连续型随机变量，其矩生成函数为 ∫−∞∞esxfX(x)dx\int \limits_{-\infty}^{\infty} e^{sx} f_X(x) \mathrm{d} x。
需要注意的是，生成函数 MX(s)M_X(s) 是关于随机数 ss 的函数，并不是随机变量 XX。
矩生成函数有良好的性质，对其微分，根据前面讲的微分公式可得：
ddsMX(s)=∫−∞∞ddsesxfX(x)dx=∫−∞∞xesxfX(x)dx\begin{aligned} \frac{\mathrm{d}}{\mathrm{d} s} M_X(s)&=\int \limits_{-\infty}^{\infty} \frac{\mathrm{d}}{\mathrm{d} s} e^{sx} f_X(x) \mathrm{d} x \\ &=\int \limits_{-\infty}^{\infty} x e^{sx} f_X(x) \mathrm{d} x \end{aligned} \\
取 s=0s=0，得：
∫−∞∞xesxfX(x)dx=∫−∞∞xfX(x)dx=E(X)\int \limits_{-\infty}^{\infty} x e^{sx} f_X(x) \mathrm{d} x = \int \limits_{-\infty}^{\infty} x f_X(x) \mathrm{d} x=\mathbb{E}(X)
故 XX 的矩生成函数在 s=0s=0 处的导数恰为 XX 的期望 E(X)\mathbb{E}(X)。
下面通过举例讲解矩生成函数的求法，此处我们选择使用刚才介绍的三种概率分布作为例子。
根据矩生成函数的定义可得：
对于 X∼B(1,p)X \sim \mathrm{B}(1,p)，其矩生成函数为
MX(s)=E(esX)=p⋅es+1−pM_X(s)=\mathbb{E}\big(e^{sX}\big)=p \cdot e^s + 1-p
对于 X∼B(n,p)X \sim \mathrm{B}(n,p)，其矩生成函数为
MX(s)=E(esX)=(p⋅es+1−p)nM_X(s)=\mathbb{E}\big(e^{sX}\big)=\big(p \cdot e^s + 1-p\big)^n
对于 X∼N(μ,σ2)X \sim \mathrm{N}(\mu,\sigma^2)，其矩生成函数为
MX(s)=E(esX)=∫−∞∞esxfX(x)dx=12πσ∫−∞∞esx−(x−μ)22σ2dx\begin{aligned}M_X(s) & =\mathbb{E}\big(e^{sX}\big) \\& = \int \limits_{-\infty}^{\infty} e^{sx} f_X(x) \mathrm{d} x \\& = \frac{1}{\sqrt{2 \pi} \sigma} \int \limits_{-\infty}^{\infty} e^{sx-\frac{(x-\mu)^2}{2\sigma^2}} \mathrm{d} x\end{aligned}
换元，令 u=x−μσu=\frac{x-\mu}{\sigma}，则 dxσ=du\frac{\mathrm{d}x}{\sigma}=\mathrm{d}u，代入得：
12πσ∫−∞∞esx−(x−μ)22σ2dx=12π∫−∞∞es(σu+μ)−u22du=esμ2π∫−∞∞esσu−u22du=esμ2π∫−∞∞e−(u−sσ)2−s2σ22du=esμ+s2σ222π∫−∞∞e−(u−sσ)22du\begin{aligned}\frac{1}{\sqrt{2 \pi} \sigma} \int \limits_{-\infty}^{\infty} e^{sx-\frac{(x-\mu)^2}{2\sigma^2}} \mathrm{d} x & =\frac{1}{\sqrt{2 \pi}} \int \limits_{-\infty}^{\infty} e^{s(\sigma u + \mu)-\frac{u^2}{2}} \mathrm{d} u \\& = \frac{e^{s\mu}}{\sqrt{2 \pi}} \int \limits_{-\infty}^{\infty} e^{s \sigma u-\frac{u^2}{2}} \mathrm{d} u \\& = \frac{e^{s\mu}}{\sqrt{2 \pi}} \int \limits_{-\infty}^{\infty} e^{-\frac{(u-s\sigma)^2-s^2\sigma^2}{2}} \mathrm{d} u \\& = \frac{e^{s\mu+ \frac{s^2\sigma^2}{2} }}{\sqrt{2 \pi}} \int \limits_{-\infty}^{\infty} e^{-\frac{(u-s\sigma)^2}{2}} \mathrm{d} u\end{aligned}
换元，令 v=u−sσv=u-s\sigma，代入得：
esμ+s2σ222π∫−∞∞e−(u−sσ)22du=esμ+s2σ222π∫−∞∞e−v22dv\frac{e^{s\mu+ \frac{s^2\sigma^2}{2} }}{\sqrt{2 \pi}} \int \limits_{-\infty}^{\infty} e^{-\frac{(u-s\sigma)^2}{2}} \mathrm{d} u = \frac{e^{s\mu+ \frac{s^2\sigma^2}{2} }}{\sqrt{2 \pi}} \int \limits_{-\infty}^{\infty} e^{-\frac{v^2}{2}} \mathrm{d} v
由前面讲的积分公式得
∫−∞∞e−v22dv=2π\int \limits_{-\infty}^{\infty} e^{-\frac{v^2}{2}} \mathrm{d} v=\sqrt{2\pi}
代入即
MX(s)=esμ+s2σ22M_X(s)=e^{s\mu+ \frac{s^2\sigma^2}{2} }

概率不等式

  • Union Bound\textbf{Union Bound}
又叫 Boole\textbf{Boole} 不等式，描述了一组互相约束事件的发生概率与互相独立的单一事件的发生概率的关系。
对于 nn 个事件 A1,A2,…,AnA_1,A_2,\ldots,A_n，有：
Pr(⋃k=1nAk)≤∑k=1nPr(Ak)\textbf{Pr} \bigg ( \bigcup \limits_{k=1}^{n} A_k \bigg ) \le \sum \limits_{k=1}^{n} \textbf{Pr}(A_k)
证明： 考虑数学归纳法，对于 n=1n=1，
Pr(A1)≤Pr(A1)\textbf{Pr}(A_1) \le \textbf{Pr}(A_1)
是显然的。对于一个满足该条件的 nn，由
Pr(A∪B)=Pr(A)+Pr(B)−Pr(A∩B)\textbf{Pr}(A \cup B) = \textbf{Pr}(A) + \textbf{Pr}(B) - \textbf{Pr}(A \cap B)
可知，
Pr(⋃k=1n+1Ak)=Pr(⋃k=1nAk)+Pr(An+1)−Pr((⋃k=1nAk)∩An+1)≤Pr(⋃k=1nAk)+Pr(An+1)≤(∑k=1nPr(Ak))+Pr(An+1)=∑k=1n+1Pr(Ak)\begin{aligned} \textbf{Pr} \bigg ( \bigcup \limits_{k=1}^{n+1} A_k \bigg ) & = \textbf{Pr}\bigg ( \bigcup \limits_{k=1}^{n} A_k \bigg ) + \textbf{Pr}(A_{n+1}) - \textbf{Pr} \bigg ( \big ( \bigcup \limits_{k=1}^{n} A_k \big ) \cap A_{n+1} \bigg ) \\ & \le \textbf{Pr}\bigg ( \bigcup \limits_{k=1}^{n} A_k \bigg ) + \textbf{Pr}(A_{n+1}) \\ & \le \bigg ( \sum \limits_{k=1}^{n} \textbf{Pr}(A_k) \bigg ) + \textbf{Pr}(A_{n+1}) \\ & = \sum \limits_{k=1}^{n+1} \textbf{Pr}(A_k) \end{aligned}
故原不等式成立。
该不等式的意义是：一组事件中，至少有一件发生的概率小于等于所有事件发生的概率之和。
  • Markov\textbf{Markov} 不等式
本质：对于一个非负随机变量 XX，感受一下，其与 E(x)\mathbb{E}(x) 相比时很大的概率是很小的。
对于非负随机变量 XX，我们有：
Pr(X≥a)≤E(X)a,for all a>0\textbf{Pr}(X \ge a) \le \frac{\mathbb{E}(X)}{a},\text{for all } a > 0
证明 I\textbf{I}： 构造离散型随机变量 YaY_a，满足：
\begin{cases} 0, & \text{if } X < a \\ a, & \text{if } X \ge a \end{cases}$$ 根据期望的定义， $$\mathbb{E}(Y_a)=\textbf{Pr}(X \ge a) \cdot a$$ 我们构造的 $Y_a$ 有性质 $Y_a \le X$，所以 $\mathbb{E}(Y_a) \le \mathbb{E}(X)$，代入得：
\begin{aligned} \textbf{Pr}(X \ge a) \cdot a & \le \mathbb{E}(X) \ \textbf{Pr}(X \ge a) & \le \frac{\mathbb{E}(X)}{a},\text{for all } a > 0 \end{aligned}
**证明 $\textbf{II}$：** 考虑期望的积分形式，
\begin{aligned} \frac{\mathbb{E}(X)}{a} & = \frac{1}{a} \int \limits_{0}^{\infty} xf_X(x) \mathrm{d} x \ & \ge \frac{1}{a} \int \limits_{a}^{\infty} af_X(x) \mathrm{d} x ,\text{for all } a > 0 \ & = \int \limits_{a}^{\infty} f_X(x) \mathrm{d} x ,\text{for all } a > 0 \ & = \textbf{Pr}(X \ge a) ,\text{for all } a > 0 \end{aligned}
即为原式。 将 $X=-X^{\prime}$ 代入，一般化地，我们还可以得到 $\text{Markov}$ 不等式在 $X$ 为非正随机变量时的形式： $$\textbf{Pr}(X^{\prime} \le -a) \le \frac{\mathbb{E}(-X^{\prime})}{a},\text{for all } a > 0$$ - **$\textbf{Chebyshev}$ 不等式** 可以看到的是，$\text{Markov}$ 不等式仅利用了期望这一信息，考虑把方差加入不等式的限制中。 对于一个随机变量 $X$，观察到其在 $\text{Var}(x)$ 较小时与 $\mathbb{E}(x)$ 差值很大的概率是很小的。 > 对于数学期望为 $\mu$，方差为 $\sigma^2$ 的随机变量 $X$，我们有： > > $$\textbf{Pr}\big(|X - \mu| \ge \varepsilon\big) \le \frac{\sigma^2}{\varepsilon^2},\text{for all } \varepsilon > 0$$ **证明：** 考虑 $\text{Markov}$ 不等式： $$\textbf{Pr}(X^{\prime} \ge a) \le \frac{\mathbb{E}(X^{\prime})}{a},\text{for all } a > 0$$ 将 $X^{\prime}=(X - \mu)^2,a=\varepsilon^2$ 代入，此时能够保证 $X^{\prime}$ 非负且 $a>0$： $$\textbf{Pr}\big ((X - \mu)^2 \ge \varepsilon^2 \big ) \le \frac{\mathbb{E}\big ( (X - \mu)^2\big )}{\varepsilon^2}$$ 左边开平方， $$\textbf{Pr}\big (|X - \mu| \ge \varepsilon \big ) \le \frac{\mathbb{E}\big ( (X - \mu)^2\big )}{\varepsilon^2}$$ 由期望与方差的关系得， $$\textbf{Pr}\big (|X - \mu| \ge \varepsilon \big ) \le \frac{\sigma^2}{\varepsilon^2}$$ 取 $\varepsilon=k\sigma$，即 $k$ 倍标准差时，可以得到 $\text{Chebyshev}$ 不等式的另一种形式： $$\textbf{Pr}\big (|X - \mu| \ge k \sigma \big ) \le \frac{\sigma^2}{k^2\sigma^2}=\frac{1}{k^2}$$ 继续对 $\text{Chebyshev}$ 不等式进行推广，考虑 $n$ 个独立的随机变量 $X_1,X_2,\ldots,X_n$，其中 $X_k$ 的期望为 $\mu_k$，方差为 $\sigma_k^2$。 将 $X=\sum \limits_{k=1}^{n} X_k,\mu=\sum \limits_{k=1}^{n} \mu_k,\sigma^2=\sum \limits_{k=1}^{n} \sigma_k^2$ 代入，就得到了**弱大数定律** (weak law of large numbers)。 > 对于 $n$ 个独立的随机变量 $X_1,X_2,\ldots,X_n$，令 $X_k$ 的期望为 $\mu_k$，方差为 $\sigma_k^2$，则有： > > $$\textbf{Pr}\bigg (|\sum \limits_{k=1}^{n} X_k - \sum \limits_{k=1}^{n} \mu_k| \ge \varepsilon \bigg ) \le \frac{\sum \limits_{k=1}^{n} \sigma_k^2}{\varepsilon^2}$$ - **$\textbf{Chernoff Bound}$** 我们可以利用前面所讲的矩生成函数来确定概率的范围。 > 对于非负随机变量 $X$，我们有： > > $$\textbf{Pr}(X \ge a) \le e^{-sa} M_X(s),\text{for all }s>0$$ > > $$\textbf{Pr}(X \le a) \le e^{-sa} M_X(s),\text{for all }s>0$$ **证明：** 由指数函数的性质，易得以下结论： $$\textbf{Pr}(X \ge a) = \textbf{Pr}(e^{sX} \ge e^{sa}),\text{for all }s>0$$ $$\textbf{Pr}(X \le a) = \textbf{Pr}(e^{sX} \ge e^{sa}),\text{for all } s<0$$ 考虑对上述式子代入 $\text{Markov}$ 不等式，并将矩生成函数代入： $$\textbf{Pr}(e^{sX} \ge e^{sa}) \le \frac{\mathbb{E}\big(e^{sX}\big)}{e^{sa}}= e^{-sa} M_X(s)$$ 代回原式，即得结论。 根据这一不等式，我们可以在一些特殊条件下，用期望确定一系列随机变量之和的概率分布的限制。 考虑 $n$ 个随机变量 $X_1,X_2,\ldots,X_n$，其中 $X_i \sim \text{B}(1,p_i)$。 对于这样的情况，此时 $\text{Chernoff Bound}$ 的推论被称为 **$\textbf{Multiplicative Chernoff Bound}$**。 > 对于 $n$ 个随机变量 $X_1,X_2,\ldots,X_n$，其中 $X_i \sim \text{B}(1,p_i)$，令 $X=\sum \limits_{k=1}^{n} X_i,\mu=\mathbb{E}(X)=\sum \limits_{k=1}^{n} p_i$，我们有： > > **Upper Bound :** > > $$\textbf{Pr}\big(X \ge (1+\varepsilon) \mu \big) \le e^{-\frac{\varepsilon^2 \mu}{\varepsilon +2}},\text{for all } \varepsilon > 0$$ > > **Lower Tail :** > > $$\textbf{Pr}\big(X \le (1-\varepsilon) \mu \big) \le e^{-\frac{\varepsilon^2 \mu}{2}},\text{for all } \varepsilon > 0$$ **证明：** 对于 **Lower Tail**，若 $\varepsilon \ge 1$，由于 $X \ge 0$，不等式左边值为 $0$，所以不等式一定成立，只需讨论 $0 < \varepsilon < 1$ 的情况。 分别令 $a$ 为 $(1+\varepsilon) \mu$ 和 $(1-\varepsilon) \mu$，代入 $\text{Chernoff Bound}$，得： $$\textbf{Pr}\big(X \ge (1+\varepsilon) \mu\big) \le e^{-(1+\varepsilon)s \mu} M_X(s),\text{for all }\varepsilon,s>0$$ $$\textbf{Pr}\big(X \le (1-\varepsilon) \mu\big) \le e^{-(1-\varepsilon) s \mu} M_X(s),\text{for all }0<\varepsilon<1,s<0$$ 考虑利用期望的性质，用 $M_{X_k}(s)$ 表示出 $M_X(s)$：
\begin{aligned} M_X(s) & = \mathbb{E}\big(e^{sX}\big) = \mathbb{E}\big(e^{s \sum \limits_{k=1}^{n} X_k}\big) \ & = \mathbb{E}\bigg(\prod \limits_{k=1}^{n} e^{s X_k}\bigg) = \prod \limits_{k=1}^{n} \mathbb{E}\big( e^{s X_k}\big) \ & = \prod \limits_{k=1}^{n} M_{X_k}(s) \end{aligned}
代入前面讲的 $\text{Bernoulli}$ 分布的矩生成函数，得：
\begin{aligned} \prod \limits_{k=1}^{n} M_{X_k}(s) & = \prod \limits_{k=1}^{n} p_i \cdot e^{s} + 1-p_i \ & = \prod \limits_{k=1}^{n} p_i \big(e^{s}-1\big) + 1 \ \end{aligned}
代入前面讲的指数函数 $e^x$ 的放缩公式，得：
\begin{aligned} \prod \limits_{k=1}^{n} p_i \big(e^{s}-1\big) + 1 & \le \prod \limits_{k=1}^{n} e^{p_i (e^{s}-1)} \ & = e^{\sum \limits_{k=1}^{n} p_i e^{(e^{s}-1)}} \ & = e^{(e^{s}-1) \mu} \ \end{aligned}
即 $M_X(s)=e^{\mu (e^{s}-1)}$，代回原式： $$\textbf{Pr}\big(X \ge (1+\varepsilon) \mu\big) \le e^{(e^{s}-1-(1+\varepsilon)s) \mu} ,\text{for all }\varepsilon,s>0$$ $$\textbf{Pr}\big(X \le (1-\varepsilon) \mu\big) \le e^{(e^{s}-1-(1-\varepsilon)s) \mu},\text{for all }0<\varepsilon<1,s<0$$ 对于 **Upper Bound**，取 $s=\ln(1+\varepsilon)$，此时满足 $s>0$： $$\textbf{Pr}\big(X \ge (1+\varepsilon) \mu\big) \le \bigg (\frac{e^{\varepsilon}}{(1+\varepsilon)^{1+\varepsilon}} \bigg )^ {\mu},\text{for all }\varepsilon>0$$ 对不等式右侧取对数，得：
\begin{aligned} \ln \bigg (\frac{e^{\varepsilon}}{(1+\varepsilon)^{1+\varepsilon}} \bigg )^ {\mu} & =\mu \ln \frac{e^{\varepsilon}}{(1+\varepsilon)^{1+\varepsilon}} \ & = \mu \big (\varepsilon-(1+\varepsilon)\ln (1+\varepsilon) \big ) \end{aligned}
代入前面讲的对数函数 $\ln(x)$ 的放缩公式，得：
\begin{aligned} \mu \big (\varepsilon-(1+\varepsilon)\ln (1+\varepsilon) \big ) & \le \mu \Big (\varepsilon-\frac{2\varepsilon^2+2\varepsilon}{\varepsilon +2} \Big ) \ & = - \frac{\varepsilon^2 \mu}{\varepsilon +2} \end{aligned}
代回原式，即 $$\textbf{Pr}\big(X \ge (1+\varepsilon) \mu\big) \le e^{- \frac{\varepsilon^2 \mu}{\varepsilon +2} },\text{for all }\varepsilon>0$$ 对于 **Lower Tail**，取 $s=\ln(1-\varepsilon)$，此时满足 $s<0$： $$\textbf{Pr}\big(X \le (1-\varepsilon) \mu\big) \le \bigg (\frac{e^{-\varepsilon}}{(1-\varepsilon)^{1-\varepsilon}} \bigg )^ {\mu},\text{for all }0<\varepsilon<1$$ 对不等式右侧取对数，得：
\begin{aligned} \ln \bigg (\frac{e^{-\varepsilon}}{(1-\varepsilon)^{1-\varepsilon}} \bigg )^ {\mu} & =\mu \ln \frac{e^{-\varepsilon}}{(1-\varepsilon)^{1-\varepsilon}} \ & = \mu \big (-\varepsilon-(1-\varepsilon)\ln (1-\varepsilon) \big ) \end{aligned}
代入前面讲的对数函数 $\ln(x)$ 的放缩公式，得：
\begin{aligned} \mu \big (-\varepsilon-(1-\varepsilon)\ln (1-\varepsilon) \big ) & \le \mu \Big ( -\varepsilon - \frac{(1-\varepsilon)^2}{2} + \frac{1}{2} \Big) \ & = - \frac{\varepsilon^2 \mu}{2} \end{aligned}
代回原式，即 $$\textbf{Pr}\big(X \le (1-\varepsilon) \mu \big) \le e^{-\frac{\varepsilon^2 \mu}{2}},\text{for all } 0 < \varepsilon < 1$$ 结合一下一开始的结论，最终得到： $$\textbf{Pr}\big(X \ge (1+\varepsilon) \mu\big) \le e^{- \frac{\varepsilon^2 \mu}{\varepsilon +2} },\text{for all }\varepsilon>0$$ $$\textbf{Pr}\big(X \le (1-\varepsilon) \mu \big) \le e^{-\frac{\varepsilon^2 \mu}{2}},\text{for all } \varepsilon > 0$$ 容易发现，二项分布的条件是强于该结论的前提条件的，所以该结论也可以在服从二项分布的问题中运用。 ## 应用 本文主要通过列举概率论在具体题目中应用的例子，来阐释概率论在算法竞赛中的应用。 - [P11918 [PA 2025] 考试 / Egzamin](https://www.luogu.com.cn/problem/P11918) > 有 $n$ 个随机变量 $X_1,X_2,\ldots,X_n$，其中 $X_i$ 有 $p_i$ 的概率为 $1$，否则为 $-1$。你选择一个 $k$，再选择其中的 $k$ 个随机变量，求最优决策下你选择的随机变量的和 $\ge t$ 的概率。 > > $1 \le t \le n \le 50000$，误差在 $10^{-6}$ 以内。 首先，可以贪心地选随机变量，因为希望和尽可能大，所以优先选 $p_i$ 大的随机变量。 将所有 $p_i$ 排完序后，最终答案一定是一段前缀。 可以设计一个简单的 $\text{DP}$，记 $f_{i,j}$ 为选长度为 $i$ 的前缀，和为 $j$ 的概率。 每一次和只会 $+1$ 或者 $-1$，则有转移式： $$f_{i,j}=p_i \cdot f_{i-1,j-1} + (1-p_i) \cdot f_{i-1,j+1}$$ 这样做是 $\Theta(n^2)$ 的。 考虑优化，令 $\varepsilon$ 为误差，我们断言，对于每一个 $i$，使得 $f_{i,j} > \varepsilon$ 的位置不会很多。 转移时只需舍去 $f_{i,j} \le \varepsilon$ 的状态，精细实现即可通过本题。 下面给出这个做法的复杂度证明。 考虑对于每一个 $i$ 分析复杂度。事实上，事件 $\{$所有随机变量取值为 $-1$ 或 $1$，且和 $\ge t\}$ 等价于事件 $\{$所有随机变量取值为 $0$ 或 $1$，且和 $\ge \frac{i+t}{2}\}$，这样我们就把问题转化为了若干次的 $\text{Bernoulli}$ 分布，此时和的期望 $\mu=\sum \limits_{k=1}^{i} p_i$。 容易注意到的是，满足 $f_{i,j} > \varepsilon$ 的 $j$ 应该是一段连续区间，不妨设这一段区间为 $\big[(1-B_1)\mu,(1+B_2)\mu\big]$，且 $B_1,B_2>0$。 代入 $\text{Multiplicative Chernoff Bound}$ 可以得到： $$\textbf{Pr}\big(X \ge (1+B_2) \mu \big) \le e^{-\frac{B_2^2 \mu}{B_2+2}} \le \varepsilon$$ $$\textbf{Pr}\big(X \le (1-B_1) \mu \big) \le e^{-\frac{B_1^2 \mu}{2}} \le \varepsilon$$ 不等式两边同时取对数的相反数： $$\frac{B_2^2 \mu}{B_2+2} \ge \ln \varepsilon^{-1}$$ $$\frac{B_1^2 \mu}{2} \ge \ln \varepsilon^{-1}$$ 解二次不等式组得： $$B_2 \ge \frac{\ln \varepsilon^{-1} + \sqrt{\ln^2 \varepsilon^{-1}-8\mu \ln \varepsilon^{-1}}}{2\mu}$$ $$B_1 \ge \sqrt{\frac{2\ln \varepsilon^{-1}}{\mu}}$$ 舍去常数，由于 $0 \le \mu \le i$，所以可以视为 $n,\mu$ 同阶，且 $\ln \varepsilon^{-1}$ 相对于 $n$ 是小量，所以： $$B_1,B_2 \ge \sqrt{\frac{\ln \varepsilon^{-1}}{n}}$$ 取等号时最优，得到满足条件的区间为 $\big[\mu - \sqrt{n \ln \varepsilon^{-1}},\mu + \sqrt{n \ln \varepsilon^{-1}}\big]$，即对于每个 $i$，合法状态数为 $\Theta(\sqrt{n \ln \varepsilon^{-1}})$ 个。 综上，总时间复杂度为 $\Theta(n \sqrt{n \ln \varepsilon^{-1}})$。 经过测试，实际 $\varepsilon$ 的值大约取到 $10^{-11}$，此时总时间复杂度不超过 $6 \times 10^7$。 核心代码： ```c++ constexpr int N=5e4+5; constexpr double eps=1e-11; namespace Junounly { int n,K; double p[N]; vector<pair<int,double> > q[2]; void main() { scanf("%d%d",&n,&K); for(int i=1;i<=n;i++) scanf("%lf",&p[i]); sort(p+1,p+n+1,greater<double>()); q[0].emplace_back(0,1); double res=0; for(int i=1,op=0;i<=n;i++,op^=1) { for(auto [X,Y]:q[op]) { int x=X-1;double y=Y*(1-p[i]); if(y>eps) { if(q[op^1].size()&&q[op^1][q[op^1].size()-1].first==x) q[op^1][q[op^1].size()-1].second+=y; else if(q[op^1].size()>1&&q[op^1][q[op^1].size()-2].first==x) q[op^1][q[op^1].size()-2].second+=y; else q[op^1].emplace_back(x,y); } x=X+1;y=Y*p[i]; if(y>eps) q[op^1].emplace_back(x,y); } q[op].clear(); double now=0; for(auto [X,Y]:q[op^1]) if(X>=K) now+=Y; res=max(res,now); } printf("%.11lf\n",res); } } ``` - [P7606 [THUPC 2021] 混乱邪恶](https://www.luogu.com.cn/problem/P7606) > 初始有两个变量 $L=G=0$。有一个蜂窝状网格，从原点出发，一共要走 $n$ 步，每步可以从 $6$ 个方向中任选一个，并朝该方向走 $1$ 单位长度，假设第 $i$ 步选择了第 $j$ 个方向，$L$ 和 $G$ 分别会变成 $(L+a_{i,2j-1}) \bmod p$ 和 $(G+a_{i,2j}) \bmod p$，问走 $n$ 步后回到原点，且此时 $L=L^{\ast},G=G^{\ast}$ 的可行性。 > > $1 \le n,p \le 100$。 发现蜂窝状网格性质不太好，而网格的形状不影响最终答案，所以进行变换，表示为直角三角形网格，如下图： ![](https://cdn.luogu.com.cn/upload/image_hosting/28tr35ly.png) 注意到 $p$ 很小，考虑设计一个暴力 $\text{DP}$，设 $f_{i,l,g,j,k} = 0/1$ 表示走到第 $i$ 步，坐标为 $(j,k)$，此时 $L=l , G=g$ 的可行性。 则转移式为： $$f_{i,l,g,j,k} = \bigvee \limits_{p=1}^{6} f_{i-1,(l-a_{i,2p-1}+p)\bmod p,(g-a_{i,2p}+p)\bmod p,j+dx_p,k+dy_p}$$ 其中 $dx=\{0,1,1,0,-1,-1\},dy=\{-1,0,1,1,0,-1\}$，分别表示对应方向 $\text{x}$ 坐标与 $\text{y}$ 坐标的增量。为避免越界，全部坐标都要加上一个偏移量。 考虑优化空间，第一维可以用滚动数组去掉。 注意到转移方式是整体可行性平移，然后合并，所以可以用 $\text{bitset}$ 优化。 此时的时间复杂度为 $\Theta(\frac{n^3 p^2}{\omega})$，空间复杂度为 $\Theta(\frac{n^2 p^2}{\omega})$。 注意到，我们最终的答案只与加和有关，与顺序无关，可以任意乱序。 于是就可以转化为一个随机游走模型，考虑将序列 $a$ 随机打乱，我们断言这样答案路径中距离原点最远的 $j,k$ 大概率不会很大。 接下来给出对于 $j,k$ 取值范围的分析。 考虑 $\text{x}$ 坐标 $j$，最劣情况下，会有 $n$ 步对 $\text{x}$ 坐标产生改动。 每一个坐标被改动的概率是相同的，考虑去掉改动为 $0$ 的位置，剩下有 $i$ 个位置，就是值为 $-1$ 或 $1$ 的二项分布。 同理，事件 $\{$所有随机变量取值为 $-1$ 或 $1$，且和为 $j\}$ 等价于事件 $\{$所有随机变量取值为 $0$ 或 $1$，且和为 $\frac{i+j}{2}\}$。 这样我们就把问题转化为了若干次的 $\text{Bernoulli}$ 分布。记随机变量 $X$ 反映 $\frac{i+j}{2}$ 的取值，且 $X$ 的期望值为 $\mu=iP$，其中 $P$ 为单个随机变量取 $1$ 的概率，为 $\frac{1}{2}$。 这个模型弱于上一题的模型，套用得满足条件的区间为 $X \in \big[\mu - \sqrt{n \ln \varepsilon^{-1}},\mu + \sqrt{n \ln \varepsilon^{-1}}\big]$，代入 $j=2X-i$，舍弃常数，得： 算法成功概率为 $1-\varepsilon$ 时， $$-\sqrt{n \ln \varepsilon^{-1}} \le j \le \sqrt{n \ln \varepsilon^{-1}}$$ 同时考虑 $\text{y}$ 坐标 $k$ ，即算法成功概率为 $(1-\varepsilon)^2$ 时， $$-\sqrt{n \ln \varepsilon^{-1}} \le j,k \le \sqrt{n \ln \varepsilon^{-1}}$$ 最终的时间复杂度为 $\Theta(\frac{n^2 p^2 \ln \varepsilon^{-1}}{\omega})$，空间复杂度为 $\Theta(\frac{n p^2 \ln \varepsilon^{-1}}{\omega})$。 这题轻微卡常，所以要加取模优化，实际可以取 $j,k$ 的范围为 $[-20,20]$，经测试，正确率非常高。 核心代码： ```c++ constexpr int N=105,M=42,B=20; namespace Junounly { int n,mod,L,G,a[N][15]; random_device rd; mt19937 rnd(rd()); bitset<M> f[2][N][N][M]; #define T(x,y) ((x)>=y?(x)-(y):(x)-(y)+mod) void main() { scanf("%d%d",&n,&mod); for(int i=1;i<=n;i++) for(int j=1;j<=12;j++) scanf("%d",&a[i][j]); scanf("%d%d",&L,&G); shuffle(a+1,a+n+1,rnd); f[0][0][0][B][B]=1; for(int i=1;i<=n;i++) for(int l=0;l<mod;l++) for(int g=0;g<mod;g++) for(int j=0;j<=B<<1;j++) { f[i&1][l][g][j].reset(); f[i&1][l][g][j]|=f[~i&1][T(l,a[i][1])][T(g,a[i][2])][j]<<1; f[i&1][l][g][j]|=f[~i&1][T(l,a[i][3])][T(g,a[i][4])][j+1]; f[i&1][l][g][j]|=f[~i&1][T(l,a[i][5])][T(g,a[i][6])][j+1]>>1; f[i&1][l][g][j]|=f[~i&1][T(l,a[i][7])][T(g,a[i][8])][j]>>1; if(j) f[i&1][l][g][j]|=f[~i&1][T(l,a[i][9])][T(g,a[i][10])][j-1]; if(j) f[i&1][l][g][j]|=f[~i&1][T(l,a[i][11])][T(g,a[i][12])][j-1]<<1; } printf(f[n&1][L][G][B][B]?"Chaotic Evil\n":"Not a true problem setter\n"); } } ```

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...