概率论
stripe_python
·
·
学习·文化课
对于一个随机试验 E,我们将其所有可能的基本结果称为样本点,记为 \omega。所有样本点组成的集合称作样本空间 \Omega。
定义事件 A 是 \Omega 的子集。当且仅当 \exists \omega \in A, \omega 出现,称为事件 A 发生。此时有:
- 若 A=\Omega,称 A 为必然事件。
- 若 A=\varnothing,称 A 为不可能事件。
事件是一个集合,因此集合的交 & 并 & 补 & 对称差操作都可以推广到事件上。具体地:
- 称 A \cup B 为事件 A,B 的和事件,记作 A+B。组合意义为事件 A 发生或事件 B 发生。
- 称 A \cap B 为事件 A,B 的积事件,记作 AB。组合意义为事件 A 发生且事件 B 发生。
- 称 A \cap B=\varnothing 的事件 A,B 互斥。组合意义为事件 A,B 不可能同时发生。
- 称 \Omega \setminus A 为 A 的对立事件,记作 \overline A。组合意义为事件 A,\overline {A} 中必然有且仅有一个发生。
如果满足 \Omega 是有限集,且每个样本点出现的可能性相等,则可以用古典概型定义事件 A 发生的概率
P(A)=\dfrac{|A|}{|\Omega|}
概率函数满足如下性质:
-
- 若事件 A,B 互斥,则 P(A+B)=P(A)+P(B)。称为概率的加法公式。
- 若 A,B 互为独立,则 P(A)+P(B)=1。
- 若 A \subseteq B,则 P(A) \le P(B)。
- 概率的容斥原理:P(A+B)=P(A)+P(B)-P(AB)。
定义事件 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 中,求期望的题目期望一般都是存在的,因此下文不会讨论期望的存在性。
期望满足如下性质:
- 线性性:对于随机变量 X,有 E(aX+b)=aE(X)+b。
- 乘法公式:对于独立随机变量 X,Y,有 E(XY)=E(X)E(Y)。注意,X,Y 独立不是等式成立的必要条件。
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}
上述四个形式都是等价的,请读者注意。方差满足如下性质:
- 对于随机变量 X,有 D(aX+b)=a^2D(X)。
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 的情形,进行分步计数:
- 前 k-1 次实验失败,概率 (1-p)^{k-1}。
- 第 k 次实验成功,概率 p。
从而 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 的情形,考虑分步计数:
- 钦定 k 次试验成功,方案数 \dbinom{n}{k}。
- 对于成功的 k 次试验,概率 p^k。
- 对于失败的 n-k 次试验,概率 (1-p)^{n-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 的分布列:
- 总方案数 \dbinom{N}{n}。
- 从 M 个黑球里取出 k 个,再从 N-M 个白球里取出 n-k 个,由乘法原理得到合法方案数 \dbinom{M}{k} \dbinom{N-M}{n-k}。
因此,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}
证毕。
:::::