基本概念 · 概率论、数理统计与信息论 01

关键字概率论数理统计信息论随机变量期望概率分布概率密度函数累积分布函数算法基础

摘要 —— 自本文开始,笔者将列举概率论、数学分析与线性代数等数学课程中的重要知识点。这些知识点作为理论基础,对它们的熟练掌握是开展算法方向研究的重要前提。

放寒假了。笔者有一个长期保留的习惯,即在寒暑假全面回顾 / 重读一些基础的知识点(包含数学、计算机核心知识点)和这一学期收藏的精品文章(例如阿里技术、分布式实验室等公众号发布的文章)。在这个假期内,我会将计算机专业需要熟练掌握的算法理论基础按照概率论、数学分析和线性代数这三个专题依次发布出来。

子曰:“温故而知新,可以为师矣。”

1 基本概念

1.1 概率空间

离散概率空间 $(\Omega, \Pr)$ 由一个 非空可数集合 $\Omega$ 和定义在其上的 概率质量函数 (pmf)$\Pr: \Omega \to \mathbb{R}$ 组成。要求 $\forall \omega \in \Omega, \Pr[\omega] \geq 0$ 且 $\sum_{\omega \in \Omega} \Pr [\omega] = 1$。每一个 $\omega \in \Omega$ 被称为一个 样本点

1.2 事件

事件是非空可数集合 $\Omega$ 的一个子集(因此也必然是可数的)。事件 $A$ 发生的概率被定义为: $$ \Pr[A] := \sum_{\omega \in A} \Pr[\omega] $$ 事件的组合通常用逻辑运算符号来描述,如 $A \wedge B$,$A \vee B$,$\lnot A$ 等。下面给出了事件组合的一些性质:

1.3 组合事件的一些恒等式

1.4 随机变量

随机变量 $X$ 是一个从 $\Omega$ 到某个数值集合 $V$ 的一个映射:$X(\omega \in \Omega) = x \in V$。 随机变量既不随机,也不是一个变量,而是一个函数。 显然,有 $$ \Pr [X = x] = \Pr [A := \{ \omega \in \Omega \mid X(\omega) = x \}] $$ 定义在随机变量上的任意概念总应当回归到事件这一底层概念上去理解。

随机变量 $X$ 的(累积)分布函数 CDF 如下: $$ \textrm{CDF}_X (X \leq x) = \Pr[X \leq x] = \Pr [A := \{ \omega \in \Omega \mid X(\omega) \leq x \}] $$

1.5 期望

定义在随机变量 $X$ 上的期望为: \begin{aligned} (\textrm{离散}) \qquad &\mathbb{E} [X] := \sum_{x} x \cdot \Pr [X = x] \\ (\textrm{连续}) \qquad &\mathbb{E} [X] := \int_{-\infty}^{\infty} x f_X (x) dx \end{aligned} 其中 $f_X (\cdot)$ 是随机变量 $X$ 的概率密度函数。

若 $X$ 为任意整数随机变量,则 $$ \mathbb{E} [X] = \sum_{x \geq 1} \bigg( \Pr[X \geq x] - \Pr[X \leq -x] \bigg) $$ 这个结论可以通过 $\Pr[X = x] = \Pr[X \geq x] - \Pr [X \geq x + 1]$ 这个等价代换来证明。

1.6 条件期望

事件 $A$ 发生的情况下随机变量 $X$ 的条件期望为: \begin{aligned} \mathbb{E} [X \mid A] &:= \sum_{x} x \cdot \Pr [X = x \mid A] = \sum_{x} \frac{x \cdot \Pr [X = x \wedge A]}{\Pr [A]} \\ &= \sum_{x} \frac{x \cdot \Pr [{ \omega \in A \mid X(\omega) = x }]}{\Pr [A]} \end{aligned}

1.7(离散变量的)全期望展开

对于任意事件 $A$(或随机变量 $A$),下面两个式子成立: \begin{aligned} &\mathbb{E} [X] = \mathbb{E} [X \mid A] \cdot \Pr [A] + \mathbb{E} [X \mid \lnot A] \cdot \Pr [\lnot A] \\ &\mathbb{E} [X] = \sum_{a} \mathbb{E} [ X\mid A = a ] \cdot \Pr [A = a] \end{aligned}

1.8 联合概率(以连续变量为例)

1.9 随机变量的独立性及其特征

2 泊松分布与指数分布

3 使用概率论解决实际问题

3.1 问题 1

对应任意硬币(可能被做假,不妨假设正面落下的概率为 $p$,反面落下的概率为 $q$,$p+q=1$),试证明:通过如下方法总能产生公平的抛硬币效果,并求解 BiasedCoin() 的期望调用次数。


图 1 VonNeumannCoin 方法。

求解 :若停机,则必然有 $x \neq y$,所以 $$ \Pr [x = 0 \wedge y = 1 \mid x \neq y] = \Pr [x = 1 \wedge y = 0 \mid x \neq y] = \frac{pq}{2 pq} = \frac{1}{2} $$ 这里运用了 $x$ 和 $y$ 相互独立。

令随机变量 $T$ 为 BiasedCoin() 的调用次数,则 $$ \mathbb{E} [T] = \mathbb{E} [T \mid x \neq y] \cdot \Pr [x \neq y] + \mathbb{E} [T \mid x = y] \cdot \Pr [x = y] $$ 其中,$\Pr [x \neq y] = 2 pq$,$\mathbb{E} [x \neq y] = 2$(因为一轮就结束了,只运行了两次)。此外有 $\Pr [x = y] = 1 - 2pq$,$\mathbb{E} [T \mid x = y] = 2 + \mathbb{E} [T]$(递归调用),联立可解得 $\mathbb{E} [T] = \frac{1}{pq}$。

3.2 问题 2

假设有 $n$ 种不同的卡,每次买一包干脆面可以抽出一种卡。假设买了 $n$ 包干脆面,可以抽出多少张不同的卡?为了收集到全部种类的卡,至少要买几包干脆面?

求解 :对应第 $i$ 种卡,定义随机变量 $X_i \in \{0,1\}$ 表示我们是否拥有它。定义随机变量 $X$ 表示我们拥有的、不同种类的卡的个数。显然有 $X = \sum_{i} X_i$。 所以 $\mathbb{E} [X] = \sum_{i} \mathbb{E} [X_i] = \sum_{i} \mathbb{E} \Pr [X_i = 1]$。

在 $n$ 次购买中,$\forall i$,我们没有抽到第 $i$ 种卡的概率为 $\Pr [X_i = 0] = \big( 1 - \frac{1}{n} \big)^n \approx \frac{1}{e}$(这是因为每次购买抽出第 $i$ 种卡的概率服从独立同分布),所以 $\mathbb{E} [X] \approx \frac{n}{e} \approx 0.632 n$。

设 $T(n)$ 为收集了 $n$ 种卡所购买的干脆面的包数。将购买行为划分为 $n$ 个阶段,第 $i$ 个阶段在抽到第 $i$ 种卡之后停止。用 $T_i (n)$ 表示第 $i$ 个阶段购买的干脆面的包数。 则 $T(n)=\sum_{i=1}^n T_i (n)$。在第 $i$ 个阶段,抽到一张新卡的概率为 $\frac{n - (i-1)}{n}$,此时 $T_i (n)$ 实际上是一个几何分布的随机变量,根据几何分布的期望可知 $\mathbb{E} [T_i (n)] = \frac{n}{n-i+1}$,所以 $$ \mathbb{E} [T(n)] = \sum_{j=1}^n \frac{n}{j} = n (1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n}) $$ 后面这个几何级数满足 $\ln (n + 1) \leq \sum_{j=1}^n \frac{1}{j} \leq \ln n + 1$(借助每段函数 $\frac{1}{j}$ 的上下界函数的积分来计算),所以可得结论:至少要买 $\Theta (n \ln n)$ 包。

转载申请

本作品采用 知识共享署名 4.0 国际许可协议 进行许可, 转载时请注明原文链接。您必须给出适当的署名,并标明是否对本文作了修改。

您也可以通过下方按钮直接分享本页面:


发表评论

登录以发表评论

最新评论


Designed & written by Hailiang Zhao.
hliangzhao.cn. Copyright © 2021 - 2022 | 浙ICP备2021026965号-1
Manage