铃悬的数学小讲堂——随机事件与随机变量

# 铃悬的数学小讲堂——随机事件与随机变量 在省选及以上的比赛中，我们逐渐会遇到越来越多的数学相关的题目（不是 $ab-a-b$ 那种小学奥数题）。 由此，便有了这篇 Blog。 ## 符号及规定 1. 我们用大写字母 $A, B, \dots$ （可能有下标，下同）来表示随机事件， 大写字母 $X, Y, Z$ 表示随机变量（反正我们也用不到很多随机变量，确实很多可以用下标区分）， 而用小写字母 $a, b, c, x, y, \dots$ 表示常量。 2. 假设读者们都知道什么是 $\sum$，最好知道什么是集合。 ## 随机事件 如果一个事件有一定概率会发生，我们就把它称作*随机事件*，用 $P(A)$ 表示随机事件 $A$ 发生的*概率*。 比如，如果我掷一个普通的六面的骰子，“朝上的数是 2” 就是一个随机事件，它的概率是 $\frac{1}{6}$。 随机事件也可以有一些“运算”： - $\bar{A}$，表示 “$A$ **不**发生” 这个事件，（称为 $A$ 的 *否定*）。 - $AB$，或者写作 $A \cap B$（可能 OIer 没人会这样写），表示 “$A$ 和 $B$ **两者都**发生” 这个事件。 - $A \cup B$，表示 “$A$ 和 $B$ 中**至少有一个**发生” 这个事件。 特别的，我们还有： - $P(A|B)$ 表示：如果我已经知道 $B$ 发生了，那么 $A$ 发生的概率。 注意到 $A|B$ 本身跟前面的几个事件不太一样：我们获知了**新的信息**。 > 举一个例子：如果我骰了一个骰子。记 $A$ 为 “骰出来的数不超过 $3$”，而 $B$ 为 “骰出来的数是偶数”。 > 那么现在我骰出骰子但是不让你看结果，但是告诉你骰出来的是偶数，问它不超过 $3$ 的概率。 > 直觉上来看概率是 $\frac{1}{3}$。 我们有一些直觉的，以及不太直觉的公式： - $P(\bar{A}) = 1 - P(A)$，也就是说我一件事情有 $p$ 的概率发生，就一定有 $1-p$ 的概率不发生。 - $P(AB) + P(A \cup B) = P(A) + P(B)$。可以想象：两边都是 “平均意义下”（我们之后会定义） $A$ 和 $B$ 发生了一共多少件。若读者知道集合的话，可能更可以想象这一点。 - 特别地，若 $A$ 和 $B$ 不可能同时发生（即 $P(AB) = 0$），则 $P(A \cup B) = P(A) + P(B)$。 - 条件概率公式：$P(AB) = P(A|B)P(B)$。 > 还是上面那个例子：$AB$ 表示“骰出来的数不超过 $3$ 而且是偶数”，那么 $P(AB) = \frac{1}{6}$。 > 我们知道 $P(B) = \frac{1}{2}$，而 $P(A|B) = \frac{1}{3}$。所以这个正好是成立的。 > 直觉上可以解释为：你向我询问骰出来的数是不是偶数，这一步你 “抱着 $\frac{1}{2}$ 的信心”； > 而当你知道骰出来的数是偶数时，再问我其是否不超过 $3$。这一步你 “抱着 $\frac{1}{3}$ 的信心”。 - *全概率公式*：如果我们有一组事件：$C_1, C_2, \dots, C_n$，满足： 无论是什么情况下，这些事件都**恰好有一个**会发生。 那么： $$ P(A) = \sum_{i=1}^n P(A C_i) = \sum_{i=1}^n P(A|C_i) P(C_i) $$ > 继续这个例子：令 $C_1$ 表示 “骰出来的是奇数”，$C_2$ 表示 “骰出来的是偶数”。 > $A$ 还是表示 “骰出来的数不超过 $3$”。上式在数值上肯定是对的，而其的实际含义也不难理解。 - 特别地，如果 $C_1 = B$ 而 $C_2 = \bar{B}$，那么满足全概率公式的条件。因此，作为特例，有： $$ P(A) = P(AB) + P(A\bar{B}) = P(A|B) P(B) + P(A|\bar{B}) P(\bar{B}) $$ - *贝叶斯公式*，或称*贝叶斯定理*：我们知道 $AB$ 和 $BA$ 是同一个东西（都表示 $A$ 和 $B$ 两者都发生）。 因此根据条件概率公式，就有 $ P(B|A) P(A) = P(AB) = P(A|B) P(B) $ 改一下形式，就变成了 $$ P(A|B) = \frac{P(AB)}{P(B)} = \frac{P(B|A) P(A)}{P(B)} $$ 读者可以自己试着举一些简单的例子来理解上述命题（公式）。骰子可能是很好的工具。 ## 基本的概率论解释：事件空间 为了满足一些读者的要求，也为了更方便地引入后面的东西，这里来简单介绍一下对一些基本的概率论的诠释。 如果要研究一些随机事件，那么我们把所有可能的结果划分成很多 “小块” $e_1, e_2, \dots$，称之为*基本事件*。 我们把所有基本事件都拿过来，组成一个集合 $S$，称之为*样本空间*。比方说我只想研究骰一次骰子得到的点数， 那么就可以以点数给基本事件标号，此时 $S = \{ 1, 2, 3, 4, 5, 6 \}$。 当然，基本事件也可能有无穷多个。比方说我们有一枚硬币，一直抛硬币，直到抛出正面为止。那么可以记 $S = \{$ 正, 反正, 反反正, 反反反正, $\dots \}$。 我们为每个基本事件 $e_i$ 指定一个概率 $P(e_i)$。既然它们是整个空间的划分，那么有理由要求 $$ \sum_{e_i \in S} P(e_i) = 1 $$ > 此处不要纠结：无穷的情况下应该怎么加。你可以认为，这个无穷求和满足你想要的所有好看的性质。 这样，每个随机变量可以看作 $S$ 的一个子集，即 $A \subseteq S$。我们定义 $$ P(A) \overset{\mathrm{def}}= \sum_{e_i \in A} P(e_i) $$ 此时，不难验证 $AB$ 就是集合的交， 而 $A \cup B$ 就是集合的并。 在此基础上，上述（除条件概率外）所有公式都可以 “严格证明”。 条件概率的定义则是说：如果 $B \subseteq S$，满足 $P(B) \neq 0$，那么我们可以再定义一个样本空间， 就是直接把 $B$ 这个集合当作样本空间。然而这个时候所有基本事件的概率之和不是 $1$ 了， 于是应当将其乘上一个系数 “单位化”。事实上，每个基本事件 $E_i$ 在新的样本空间里的概率就定义为 $P_B(e_i) = \frac{P_S(e_i)}{P_S(B)}$。在此意义下也不难验证条件概率公式（就是定义）和贝叶斯公式。 ### 硬币的例子 如果一枚硬币，一直抛，抛出正面为止，那么一共抛了奇数次的概率是多少？ 记 $E_n(n = 0, 1, 2, \dots)$ 表示：抛出正面之前出现了 $n$ 次反面， 则这里 $S = \{ e_n \mid n = 0, 1, 2, \dots \}$，且（根据我们默认的常识）$P(E_n) = \frac{1}{2^{n+1}}$。 我们的随机事件（抛了奇数次）即为 $A = \{ e_{2n} \mid n = 0, 1, 2, \dots \}$。暴力算等比数列求和 $$ P(A) = \frac{1}{2} + \frac{1}{8} + \frac{1}{32} + \dots = \frac{\frac{1}{2}}{1 - \frac{1}{4}} = \frac{2}{3} $$ 所以概率是 $\frac{2}{3}$。 然而可能大部分人都觉得这样很笨。大家大概都是这样算的：如果第一次抛出了反面（$\frac{1}{2}$ 的概率）， 那么接下来就还要抛出偶数次，从而概率是 $1 - P(A)$。如果第一次抛出了正面，那么 $A$ 就直接满足了。所以 $$ P(A) = \frac{1}{2}(1 - P(A)) + \frac{1}{2} $$ 解之得 $P(A) = \frac{2}{3}$。事实上，这里面隐含地已经用到了全概率公式以及条件概率公式。 （并且我们默认了从第一次开始抛和从第二次开始抛的结果应该是等价的）。 这说明我们其实都多多少少懂一点概率论了。（bushi） ## 随机变量 继续我们的 “样本空间” 诠释。现在我们不仅要在样本空间 $S$ 上给一个子集，还要在样本空间上给一个函数 $X$。 也就是说，对每个基本事件 $e_i \in S$，我们都规定了一个值 $X(e_i)$。这样就称之为一个*随机变量*。 比方说，还是骰子。我们令 $X$ 表示 “骰子的点数”，那么 $S = \{ 1, 2, 3, 4, 5, 6 \}$，而 $X(i) = i$。 再比方说，令 $X$ 表示 “硬币抛出第一个正面前会抛出多少反面”，那么 $S = \{ e_n \mid n = 0, 1, \dots \}$， 而 $X(e_k) = k$。 对于随机变量 $X, Y$，我们有时候将其当作数来运算，比方说 $1 + X, 3X + Y, X \cdot Y$。 可以通俗地解释为：当 $X$ 和 $Y$ 分别取到 $u$ 和 $v$ 的时候，$1 + X, 3X + Y, X \cdot Y$ 即取到 $1 + u, 3u + v, u \cdot v$。（其实就是说 $(3X + Y)(E_i) = 3 X(E_i) + Y(E_i)$，等等）。 很多时候我们希望知道 “一个变量的平均结果”，即其*数学期望*。比方说骰子骰到每个点数的概率都相等， 那么 “点数的平方” 的 “平均值” 自然是 $\frac{1^2 + 2^2 + \dots + 6^2}{6}$。 然而很多时候基本事件发生的概率不相等。此时我们定义随机变量 $X$ 的期望为 $$ E(X) \overset{\mathrm{def}}= \sum_{e_i \in S} X(e_i) P(e_i) $$ 即 $X$ 的取值按概率的加权平均。类比随机事件概率，我们可以定义*条件期望* $E(X | B)$ 为 “已知 $B$ 发生的前提下，$X$ 的期望值”。其严格定义与上一节中的条件概率类似，这里不在赘述。 对任意随机事件 $A$，记 $Z_A$ 为一个随机变量，即 “$A$ 是否发生”。当 $A$ 发生时 $Z_A=1$，否则 $Z_A=-1$。 类比随机事件的概率可以找到很多公式： - $E(X Z_A) = E(X|A) P(A)$。即我们 “将 $X$ 截断到 $A$ 上，使其在 $A$ 不发生时都取 $0$”。那么此时 $X$ 的期望即为 $E(X|A) P(A)$。反过来，我们也有 $E(X|A) = \frac{E(X Z_A)}{P(A)}$。 - *全期望公式*：如果 $C_1, \dots, C_n$ 在任意情况下都恰好有一个发生（样本空间的意义下，即 $C_1 \cup \dots \cup C_n = S$，且这些集合两两不交），则 $$ E(X) = \sum_{i = 1}^n E(X|C_i) P(C_i) $$ - 特例，即 $E(X) = E(X|A) P(A) + E(X|\bar{A}) P(\bar{A})$。 ### 期望可加性 此外，还有极为重要的定理，即 *期望可加性*，或称线性性，即 - 对任意随机变量 $X, Y$，都有 $E(aX + bY) = aE(X) + bE(Y)$。 证明： $$ E(aX + bY) = \sum_{e_i \in S} (aX(e_i) + bY(e_i)) P(e_i) = a\sum_{e_i \in S} X(e_i) P(e_i) + b\sum_{e_i \in S} Y(e_i) P(e_i) = aE(X) + bE(Y) $$ 虽然它证明很容易（乘法分配律.jpg），但是其非常重要。 特别的，它在 $Y$ 取常数 $c$ 时即说明 $E(X + c) = E(X) + c$。 此外要注意的一点是，这对乘法并不成立。 比方说 $X$ 有 $\frac{1}{2}$ 概率取 $0$，$\frac{1}{2}$ 概率取 $1$，而 $Y = 1 - X$。 则 $X \cdot Y$ 恒为 $0$，从而 $E(X \cdot Y) = 0$，然而 $E(X) = E(Y) = \frac{1}{2}$。 特殊的情况下期望是可以相乘的，下文会说。 ### 例子 #### 一 硬币抛出正面之前期望要抛出多少次反面？ 令 $X$ 为 “抛出正面前的反面次数” 这个随机变量。令 $A$ 表示 “第一次抛出了正面” 这个事件， 则根据全期望公式， $$ E(X) = \frac{1}{2} E(X | A) + \frac{1}{2} E(X | \bar{A}) $$ $E(X | A)$ 自然是 $0$。我们发现 $X | \bar{A}$ 它相当于是 $1 + X$， 因为从第二次开始抛和从第一次开始抛没什么区别。根据线性性我们又有 $E(1 + X) = 1 + E(X)$，从而 $$ E(X) = \frac{1}{2} (1 + E(X)) $$ 解得 $E(X) = 1$。或者说期望要抛 $2$ 次才能抛出正面。 推而广之，如果我们不停地做一件事情，每次有 $p$ 的成功率（这里 $p = \frac{1}{2}$）， 那么期望做到第 $\frac{1}{p}$ 次的时候成功。 #### 二 有一条 $n$ 个点的链。你从一端的 $1$ 号点出发，每次会从可以到达的点里等概率随机一个。 求第一次走到另一端的 $n$ 号点的期望步数。 我们令 $X$ 为第一次走到 $n$ 时的步数；令 $X_j$ 表示从第一次走到 $j$ 到第一次走到 $j+1$ 之间用了多少步。 那么有 $X = X_1 + X_2 + \dots + X_{n-1}$，因此 $E(X) = E(X_1) + \dots + E(X_{n-1})$。 自然可以发现 $X_1 = 1$，而 $X_k$（若 $k > 1$）按第一次向哪边走分类，有 $\frac{1}{2}$ 概率为 $1$， 另外 $\frac{1}{2}$ 的概率即为从 $k - 1$ 走到 $k + 1$ 的概率。跟上一段的想法相同，这自然就是 $$ E(X_k) = \frac{1}{2} + \frac{1}{2} (1 + E(X_{k-1}) + E(X_k)) $$ 求之得 $E(X_k) = E(X_{k-1}) + 2$。从而 $E(X_k) = 2k - 1$，而 $$ E(X) = 1 + 3 + \dots + (2n - 3) = (n - 1)^2 $$ ## 独立性 有的时候两个变量是毫无关系的。比方说抛两次硬币，这两次硬币正反面的结果之间互不影响。 形式化的定义：对任意 $t$，考虑事件 $X = t$（即 “$X$ 的取值恰好为 $t$” 这个事件）。 如果对任意 $t_1, t_2$，都有 $$ P((X = t_1)(Y = t_2)) = P(X = t_1) P(Y = t_2) $$ 就称 $X, Y$ 是*独立*的。独立变量有很多性质：最常用的一条是独立随机变量的乘积之期望等于其期望之乘积。 即若 $X, Y$ 独立，则 $E(XY) = E(X) E(Y)$。 证明：套定义。 $$ \begin{aligned} E(XY) &= \sum_{a, b} ab P((X = a)(Y = b)) \\ &= \sum_{a, b} aP(X = a) bP(X = b) \\ &= \left(\sum_a aP(X = a)\right) \left(\sum_b bP(X = b)\right) \\ &= E(X) E(Y) \end{aligned} $$ 关于独立性，需要注意的几点是：$X$ 不和自己独立，除非它是常数；独立性并不传递，也就是说 $X, Y$ 独立，$Y, Z$ 独立，不能推出 $X, Z$ 独立。 ### 例题 #### 一（P1654 OSU） 有一串随机变量 $X_1, \dots, X_n$。$X_i$ 有 $p_i$ 的概率取 $1$，$1-p_i$ 的概率取 $0$； 并且这些随机变量全部独立（即，固定其中任意多个变量的取值，都不影响别的变量的取值）。 随机的序列中每有一串长为 $k$ 的连续的 $1$，就会产生 $k^3$ 的贡献。求贡献之和的期望。 解法：设 $Y_i$ 表示以 $i$ 结尾的连续的 $1$ 的长度（一个随机变量）。 则 $Y_i$ 有 $1 - p_i$ 的概率取 $0$，$p_i$ 的概率取 $Y_{i-1} + 1$。 一串长为 $k$ 的连续的 $1$ 会产生 $k^3$ 的贡献，相当于在其中第 $t$ 个位置会产生 $t^3 - (t-1)^3$ 的贡献。 因此相当于：第 $i$ 个位置会产生 $Y_i^3 - (Y_i-1)^3 = 3Y_i^2 - 3Y_i + 1$ 的贡献。 我们知道期望不能乘，但是可以加。因此 $$ \begin{aligned} E(Y_i) &= p_i (E(Y_{i-1}) + 1) \\ E(Y_i^2) &= p_i E((Y_{i-1} + 1)^2) \\ &= p_i E(Y_{i-1}^2 + 2Y_{i-1} + 1) \\ &= p_i(E(Y_{i-1}^2) + 2E(Y_{i-1}) + 1) \end{aligned} $$ 只需要从前往后对每个 $i$ 计算 $E(Y_i)$ 及 $E(Y_i^2)$ 即可；而贡献和期望就是每个位置的期望的和（可加性）， 而 $i$ 位置的期望就是 $3E(Y_i^2) - 3E(Y_i) + p_i$ （之所以最后加 $p_i$ 而不是 $1$，是因为上面没有考虑 $0^3 - (-1)^3 = 1$ 的情况，然而取 $0$ 的时候没有贡献）。