概率论

· · 学习·文化课

对于一个随机试验 E,我们将其所有可能的基本结果称为样本点,记为 \omega。所有样本点组成的集合称作样本空间 \Omega。

定义事件 A 是 \Omega 的子集。当且仅当 \exists \omega \in A, \omega 出现,称为事件 A 发生。此时有:

事件是一个集合,因此集合的交 & 并 & 补 & 对称差操作都可以推广到事件上。具体地:

如果满足 \Omega 是有限集,且每个样本点出现的可能性相等,则可以用古典概型定义事件 A 发生的概率

P(A)=\dfrac{|A|}{|\Omega|}

概率函数满足如下性质:

定义事件 A,B 相互独立,当且仅当

P(AB)=P(A)P(B)

其组合意义为:一个事件是否发生,不会干涉另一个事件的发生。

19.1 条件概率

对于两个随机事件 A,B,记在事件 A 发生的条件下,事件 B 仍然发生的概率为 P(B \mid A)。根据定义

P(B \mid A)=\dfrac{|AB|}{|A|}=\dfrac{P(AB)}{P(B)}

称 P(B \mid A) 为条件概率。上式移项有

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

称为概率的乘法公式。

设事件 A_1,A_2,\cdots,A_n 两两互斥且和事件为 \Omega,并且满足 \forall 1 \le i \le n, P(A_i)>0,则有全概率公式

P(B)=\sum_{i=1}^n P(A_i) P(B \mid A_i)

19.2 随机变量的数字特征

19.2.1 概念

对于任意 \omega \in \Omega,如果存在唯一的实数 X(\omega) 与之对应,则称 X 为随机变量。按照这个定义,随机变量是一个 \Omega \to \mathbb{R} 的函数。

对于随机变量 X,其所有可能的取值为 x_1,x_2,\cdots,且取值集合有限,或者可以一一列举,则称 X 为离散型随机变量。

如无特殊说明,下文讨论的随机变量均为离散型随机变量。对于连续性随机变量,需要使用微积分的知识来定义一些特征。

我们记 p_i 为 X=x_i 的概率,即 p_i=P(X=x_i)。将数列 p_i 称为 X 的分布列。则 p_i 满足性质 \sum \limits_{i \ge 1} p_i=1。用分布列可以描述一个随机变量 X。

19.2.2 期望

对于随机变量 X,称它的均值 / 期望为

E(X)=\sum_{i=1}^n x_ip_i

需要注意的是,只有上述求和收敛时 E(X) 才存在。在 OI 中,求期望的题目期望一般都是存在的,因此下文不会讨论期望的存在性。

期望满足如下性质:

19.2.3 方差

期望并不能反映随机变量的波动,因此我们定义了 X 的方差为

\begin{aligned} D(X)&=\sum_{i=1}^n (x_i-E(X))^2 p_i\\ &=\sum_{i=1}^n (x_i^2 p_i-E^2(X))\\ &= E\left((X-E(X))^2\right)\\ &= E(X^2)-E^2(X) \end{aligned}

上述四个形式都是等价的,请读者注意。方差满足如下性质:

19.3 概率分布

19.3.1 两点分布

若随机试验 E 满足 |\Omega|=2,则称 E 为伯努利试验。记 \Omega=\{0,1\},并用随机变量 X 刻画取出的数字,设 P(X=1)=p。

根据概率的性质,必有 E(X=0)=1-p。称随机变量 X 服从两点分布或 0—1 分布。

对于服从两点分布的随机变量 X,显然有:

19.3.2 几何分布

在伯努利试验中,若 X=0 称为试验失败,X=1 称为试验成功,仍记单次试验成功的概率为 p。

进行若干次独立重复实验,直到实验成功则停止,将实验次数记为 X,则称随机变量 X 服从几何分布。记作 X \sim G(p)。

考虑求 X 的分布列。对于 X=k 的情形,进行分步计数:

从而 P(X=k)=(1-p)^{k-1}p。进一步:

:::::success[组合证法]

直接对级数求和有

\begin{aligned} E(X) &= \sum_{k \ge 1} kp_k\\ &= \sum_{k \ge 1} kp (1-p)^{k-1}\\ &= p \sum_{k \ge 1} k(1-p)^{k-1}\\ &= p \dfrac{1}{(1-(1-p))^2}\\ &= \dfrac{1}{p} \end{aligned}

对于方差,考虑计算 E(X^2) 有

\begin{aligned} E(X^2) &= \sum_{k \ge 1} k^2p_k\\ &= \sum_{k \ge 1} k^2p (1-p)^{k-1}\\ &= p \sum_{k \ge 1} k^2(1-p)^{k-1}\\ &= p \dfrac{1+1-p}{(1-(1-p))^2}\\ &= \dfrac{2-p}{p^2} \end{aligned}

从而 D(X)=E(X^2)-E^2(X)=\dfrac{2-p}{p^2}-\dfrac{1}{p^2}=\dfrac{1-p}{p^2}。

:::::

19.3.3 二项分布

将伯努利试验独立重复 n 次,称为 n 重伯努利试验。在这一随机试验中,记试验成功的次数为 X,则称随机变量 X 服从二项分布。记作 X \sim B(n,p)。

二项分布的另一个组合意义是:箱子中装有若干黑球和白球,独立放回地摸出 n 次球,将摸出黑球的次数记为随机变量 X。

可以用排列组合配合概率论的方法求 X 的分布列。对于 X=k 的情形,考虑分步计数:

于是随机变量 X 的分布列 P(X=k)=\dbinom{n}{k} p^k (1-p)^{n-k}。进一步:

:::::success[组合证法]

我们有

\begin{aligned} E(X)&=\sum_{k=0}^n k \times p_k\\ &=\sum_{k=0}^n k \dbinom{n}{k} p^k (1-p)^{n-k}\\ &= \sum_{k=1}^n n \binom{n-1}{k-1} p^k (1-p)^{n-k}\\ &= np \sum_{k=1}^n \binom{n-1}{k-1} p^{k-1}(1-p)^{n-k}\\ &= np (p+1-p)^{n-1}\\ &=np \end{aligned}

对于方差,考虑先计算 E\left(X(X-1)\right):

\begin{aligned} E(X(X-1))&=\sum_{k=0}^n k(k-1) \dbinom{n}{k} p^k (1-p)^{n-k}\\ &=\sum_{k=2}^n n(n-1) \binom{n-2}{k-2} p^k (1-p)^{n-k}\\ &=n(n-1)p^2 \sum_{k=2}^n \binom{n-2}{k-2} p^{k-2} (1-p)^{(n-2)-(k-2)}\\ &= n(n-1)p^2 (p+1-p)^{n-2}\\ &= n(n-1)p^2 \end{aligned}

第二个等号利用了二维吸收恒等式 k(k-1) \dbinom{n}{k}=n(n-1) \dbinom{n-2}{k-2}。

由方差线性性 E(X^2)=E(X(x-1)+X)=n(n-1)p^2+np。代入方差公式得

\begin{aligned} D(X)&=E(X^2)-E^2(X)\\ &= n(n-1)p^2+np-n^2p^2\\ &= n^2p-np+np-n^2p^2\\ &= np(1-p) \end{aligned}

证毕。

:::::

:::::success[PGF 证法]

写出随机变量 X 的 PGF

\begin{aligned} F(x)&=\sum_{k=0}^n p_k x^k\\ &= \sum_{k=0}^n \dbinom{n}{k} p^k (1-p)^{n-k} x^k\\ &= (px+1-p)^n \end{aligned}

对 F 求一阶导和二阶导:

\begin{aligned} F'(x)&= np(px+1-p)^{n-1}\\ F''(x) &= n(n-1)p^2 (px+1-p)^{n-2} \end{aligned}

根据 EGF 性质即可得到

\begin{aligned} E(X)&=F'(1)\\ &=np(p+1-p)^{n-1}\\ &=np\\ D(X)&= F''(1)+F'(1)-F'^2(1)\\ &=n(n-1)p^2+np-n^2p^2\\ &=np(1-p) \end{aligned}

证毕。

:::::

19.3.4 超几何分布

箱子中装有 N 个球,其中 M 个是黑球,独立不放回地摸出 n 次球,将摸出黑球的次数记为随机变量 X,则称 X 服从超几何分布。

可以发现,在这种组合意义下,二项分布和超几何分布的区别仅在于放回和不放回的抽取方法。

可以用排列组合的方法求出 X 的分布列:

因此,X 的分布列为:

P(X=k)=\dfrac{\binom{M}{k} \binom{N-M}{n-k}}{\binom{N}{n}}

进一步可得 E(X)=n\dfrac{M}{N}。

:::::success[组合证法]

我们有

\begin{aligned} E(X)&=\sum_{k=0}^n k \times p_k\\ &=\sum_{k=0}^n k \dfrac{\binom{M}{k} \binom{N-M}{n-k}}{\binom{N}{n}}\\ &=\sum_{k=1}^n \dfrac{M\binom{M-1}{k-1}\binom{N-M}{n-k}}{\binom{N}{n}}\\ &= \dfrac{M}{\binom{N}{n}} \sum_{k=1}^n \binom{M-1}{k-1}\binom{N-M}{n-k}\\ &= \dfrac{M}{\binom{N}{n}} \sum_{i=0}^{n-1} \binom{M-1}{i} \binom{N-M}{n-1-i}\\ &= \dfrac{M}{\binom{N}{n}} \binom{N-1}{n-1}\\ &= \dfrac{Mn!(N-n)!}{N!}\times \dfrac{(N-1)!}{(n-1)!(N-n)!}\\ &= \dfrac{nM}{N} \end{aligned}

证毕。倒数第三个等号使用了范德蒙德卷积。

:::::

:::::success[PGF 证法]

写出随机变量 X 的 PGF

\begin{aligned} F(x)&=\sum_{k=0}^n p_k x^k\\ &= \sum_{k=1}^n \dfrac{\binom{M}{k} \binom{N-M}{n-k}}{\binom{N}{n}} x^k \end{aligned}

注意到 F 的分子为 (1+xy)^M (1+y)^{N-M} 的展开式中 y^n 项的系数。因此:

\begin{aligned} \binom{N}{n} F(x) &= [y^n] \left((1+xy)^M (1+y)^{N-M}\right) \end{aligned}

将等式两边同时关于 x 求偏导:

\begin{aligned} \binom{N}{n} F'(x) &= [y^n]\dfrac{\partial}{\partial x} \left((1+xy)^M (1+y)^{N-M}\right)\\ \binom{N}{n} F'(x) &= [y^n] \left(My(1+xy)^{M-1}(1+y)^{N-M}\right) \end{aligned}

所求期望为 F'(1),将 x=1 代入得

\begin{aligned} \binom{N}{n} F'(1) &= [y^n] \left(My(1+y)^{M-1}(1+y)^{N-M}\right)\\ &= [y^n] My(1+y)^{N-1}\\ &= M\binom{N-1}{n-1}\\ F'(1)&= \dfrac{M\binom{N-1}{n-1}}{\binom{N}{n}}=\dfrac{nM}{N} \end{aligned}

证毕。

:::::