离散数学---概率, 期望

本文根据 MIT 计算机科学离散数学课程整理（Lecture 22 ~ Lecture 24）。

1 非负整数期望性质

用 N 表示非负整数集合，R 是 N 上的随机变量，则 R 的期望可以表示成： $E(R)=\sum_{i=0}^{\infty} P(R>i)=\sum_{i=1}^{\infty} P(R \ge i)$

证明：

$E(R)=\sum_{i=0}^{n\to \infty} i \cdot P(R=i) =\\ P(R=1) + \\ P(R=2) + P(R=2) + \\ P(R=3) + P(R=3) + P(R=3) + \\ \\ ...\\ \\ P(R=n) + ... + P(R=n)\\$

换一个形式，把每一列写到一起，既 $E(R)=\sum_{i=1}^{\infty} \sum_{j=i}^{\infty} P(R=j)=\sum_{i=1}^{\infty} P(R \ge i)$

同时期望也可以写成 $E(R)=\sum_{i=0}^{\infty} \sum_{j=i+1}^{\infty} P(R=j)=\sum_{i=0}^{\infty} P(R > i)$

应用：

对于一个系统，每一个单位时间都有 p 的概率损坏，求系统发生损坏的期望时间。

随机变量为单位时间，满足非负整数，故 $E(T)=\sum_{i=0}^{\infty} i \cdot P(T=i) = \sum_{i=1}^{\infty} P(T \ge i)=\sum_{i=1}^{\infty} (1-p)^i=\frac{1}{p}-1$

2 期望的线性性质

对于随机变量 $x_1,x_2,...,x_n$ 满足 $E(x_1+x_2+...+x_n)=E(x_1)+E(x_2)+...+E(x_n)$

对于常数 a, b 有 $E(a\cdot R+b)=a\cdot E(R)+b$

证明：

只需证明对于随机变量 X 和 Y，满足 $E(X+Y)=E(X)+E(Y)$

$E(X+Y)=\sum_{x\in X} \sum_{y\in Y} (x+y)\cdot P(X=x,Y=y) \\ = \sum_{x\in X} \sum_{y\in Y} x\cdot P(X=x,Y=y) + \sum_{y\in Y} \sum_{x\in X} y\cdot P(X=x,Y=y) \\ = \sum_{x\in X} x \sum_{y\in Y} P(X=x,Y=y) + \sum_{y\in Y} y \sum_{x\in X} P(X=x,Y=y) \\ = \sum_{x\in X} x \cdot P(X=x) + \sum_{y\in Y} y \cdot P(Y=y) =E(X)+E(Y)$

应用：

帽子检查问题(Hat-Check Problem)：标号为 1~n 的球放置在对应标号为 1~n 的位置，把所有的球重新排列，R 表示球在原来正确对应编号位置的个数，求 R 的期望。

用 $T_i$ 表示第 i 个球是否在正确的位置，可以求得分布为：

$T_i = \left\{\begin{matrix} 1,p=\frac{1}{n} \\ 0,p=1-\frac{1}{n} \end{matrix}\right.$

则有： $E(T_i)=\frac{1}{n}$ ，根据期望线性性质有： $E(R)=E(T_1+T_2+...+T_n)= \sum_{i=1}^{n}E(T_i)=1$

实际上可以求得R 的概率分布为：

$P(R=k)=\left\{\begin{matrix} \frac{1}{k!(n-k)} \quad k \le n-2 \\ \frac{1}{n!} \quad k=n-1,n \end{matrix}\right.$

对于 $k\le n-2$ ，

$P(R=k)= \binom{n}{k} \cdot \frac{1}{n} \cdot \frac{1}{n-1} \cdot ... \cdot \frac{1}{n-k+1} \cdot \frac{n-k-1}{n-k} \cdot ... \cdot \frac{1}{2} \cdot 1 \\ =\frac{n!}{k! \cdot (n-k)!} \cdot \frac{(n-k-1)!}{n!} \\ =\frac{1}{k!(n-k)}$

3 事件发生的期望次数

给定概率空间为 S，事件 $A_1,A_2,...,A_n \subseteq S$ ，用随机变量 T 表示事件发生的个数，则有：

1. 这些事件发生个数的期望值为事件发生概率相加，即： $E(T)=\sum_{i=1}^{n} P(A_i)$

2. $P(T=0) \le e^{-E(T)}$

证明：

定义： $T_i(w)=\left\{\begin{matrix} 1 \quad w \in A_i \\ 0 \quad w \notin A_i \end{matrix}\right.$

则有： $E(T)=\sum_{i=1}^{n} E(T_i)=\sum_{i=1}^{n} P(T_i=1)=\sum_{i=1}^{n} P(A_i)$

$P(T=0) =\prod_{i=1}^{n}(1-P(A_i)) \\ \le \prod_{i=1}^{n} e^{-P(A_i)} \\ = e^{-\sum_{i=1}^{n}P(A_i) }\\ =e^{-E(T)}$

应用：

抛 n 个硬币，求硬币朝上的个数期望。

用 $A_i$ 表示事件为第 i 个硬币朝上，期望可以表示成事件概率之和： $E=\sum_{i=1}^{n} P(A_i)=\frac{n}{2}$

实际上不使用该性质，期望可以直接表示成： $E=\sum_{i=1}^{n} i \cdot \binom{n}{i} \cdot 2^{-n}$ ，经过化简得到结果也是 $\frac{n}{2}$

$E=\sum_{i=1}^{n} i \cdot \binom{n}{i} \cdot 2^{-n}=\sum_{i=1}^{n} i \cdot \binom{n}{n-i} \cdot 2^{-n}=\sum_{i=1}^{n} (n-i) \cdot \binom{n}{i} \cdot 2^{-n}=n \cdot 2^{-n}\sum_{i=1}^{n} \binom{n}{i}-\sum_{i=1}^{n} i \cdot \binom{n}{i} \cdot 2^{-n}=n\cdot 2^{-n}\cdot 2^{n}-E=n-E$

所以： $2E=n \to E=\frac{n}{2}$

4 期望乘法规则

如果随机变量 $R_1,R_2,...,R_n$ 相互独立，则有 $E(R_1 \cdot R_2\cdot ...\cdot R_n)=E(R_1)\cdot E(R_2)\cdot ...\cdot E(R_n)$

证明：

只需证明对于两个相互独立的随机变量 X 和 Y，有 $E(X\cdot Y) = E(X) \cdot E(Y)$ 成立。

由独立的概率性质可知： $P(X = x, Y = y) = P(X = x) \cdot P(Y = y)$

则有：

$E(X\cdot Y) = \sum_{x} \sum_{y} x\cdot y \cdot P(X = x, Y = y) \\ = \sum_{x} \sum_{y} xy \cdot P(X = x) \cdot P(Y = y) \\ =\left( \sum_{x} x \cdot P(X = x) \right) \cdot \left( \sum_{y} y \cdot P(Y = y) \right)\\ =E(X)\cdot E(Y)$

5 马尔可夫不等式 (Markov's Thm.)

对于非负随机变量 R， $\forall x > 0, P(R \ge x) \le \frac{E(R)}{x}$

证明

$E(R)=E(R|R\ge x)\cdot P(R\ge x)+E(R|R<x)\cdot P(R<x)$

大于等于 x 的部分，显然期望也大于等于 x，即 $E(R|R\ge x) \ge x$

由非负的前提， $E(R|R<x) \ge 0$ ， $E(R|R<x)\cdot P(R<x) \ge 0$

$E(R)\ge x\cdot P(R\ge x)$ ，即 $P(R \ge x) \le \frac{E(R)}{x}$

推论

令 $x=c\cdot E(R), c >0$ ，得到推论： $P(R\ge c\cdot E(R))\le \frac{1}{c}$

6 切比雪夫不等式 (Chebyshev's Thm.)

对任意随机变量 R， $\forall x>0 ,P(\left | R-E(R) \right | \ge x ) \le \frac{Var(R)}{x^2}$ ，其中 $Var(R)$ 表示 R 的方差。

证明

$P(\left | R-E(R) \right | \ge x ) = P( (R-E(R))^2 \ge x^2)$ ，令 $T=(R-E(R))^2 \ge0$ ，满足马尔可夫使用条件，则有 $P(T \ge x^2) \ge \frac{E(T)}{x^2}=\frac{Var(R)}{x^2}$

推论

记 $\sigma (R)$ 为 R 的标准差，且满足 $\sigma(R) > 0$ ，令 $x=c\cdot \sigma(R),c>0$ ，得到推论 $P(|R-E(R)|\ge c\cdot \sigma(R)) \le \frac{1}{c^2}$

对于 $\sigma(R) =0$ 的特殊情况， $P(|R-E(R)|\ge 0) =1$ ，推论表达式并不成立。然而原表达式为 $P(0\ge x) =0 \le 0$ ，是成立的。

7 一侧切比雪夫不等式 (Cantelli's inequality)

对任意随机变量 R， $\forall x>0$ ，有

$P( R-E(R) \ge x ) \le \frac{Var(R)}{x^2+Var(R)} \\ P( R-E(R) \le -x ) \le \frac{Var(R)}{x^2+Var(R)}$

证明

下面证明 $P( R-E(R) \ge x ) \le \frac{Var(R)}{x^2+Var(R)}$ ，反向同理。

令 $T=R-E(R)$ ，即证明： $P(T \ge x ) \le \frac{Var(R)}{x^2+Var(R)}$

若 $T<0$ ，则 $P( R-E(R) \ge x )=0$ ，显然成立。下面考虑 $T \ge0$ 的情况。

下面证明： $\forall x>0,y>0,P(T+y\ge x+y)\le\frac{Var(R)+y^2}{(x+y)^2}$

令 $Z=T+y$ ，

$P(T+y\ge x+y)=\sum_{z\ge x+y}P(Z=z)\le \sum_{z\ge x+y}\frac{z^2}{(x+y)^2}\cdot P(Z=z)\le \frac{1}{(x+y)^2}\cdot \sum_{z\in Z}z^2\cdot P(Z=z)\\ =\frac{E(Z^2)}{(x+y)^2}= \frac{E(T^2)+y^2+2\cdot y\cdot E(T)}{(x+y)^2}=\frac{Var(R)+y^2}{(x+y)^2}$

令 $f(y)=\frac{Var(R)+y^2}{(x+y)^2},y>0$

问题转化为证明： $f(y)\le \frac{Var(R)}{x^2+Var(R)}$

$f^{'}(y)=\frac{2\cdot x\cdot y-2\cdot Var(R)}{(x+y)^3}$ ，求得极小值点为： $y_{min}=\frac{Var(R)}{x}$ ，代入得到 $f(y_{min})=\frac{x^2\cdot Var(R)+Var^2(R)}{x^4+Var^2(R)+2\cdot x^2\cdot Var(R)} = \frac{Var(R)\cdot (x^2+Var(R))}{(x^2+Var(R))^2} = \frac{Var(R)}{x^2+Var(R)}$

$f(y)\le f(y_{min})=\frac{Var(R)}{x^2+Var(R)}$

8 切诺夫界 (Chernoff bound)

$T_1,T_2,...,T_n$ 之间相互独立， $T_i$ 服从伯努利分布 $(T_i \in \{0,1\})$ ，记 $T=\sum_i^nT_i$ ， $\forall c >1$ ，记 $z=c\cdot ln(c)+1-c$ ，则有 $P(T\ge c\cdot E(T)) \le e^{-z\cdot E(T)}$

证明

$P(T\ge c\cdot E(T))=P(c^T\ge c^{c\cdot E(T)})$

其中 $c^T \ge 0$ ，满足马可夫不等式条件，则有： $P(c^T\ge c^{c\cdot E(T)})\le \frac{E(c^T)}{c^{c\cdot E(T)}}$

$E(c^T)=E(\prod_{i=1}^{n}c^{T_i} )=\prod_{i=1}^{n}E(c^{T_i})$

$E(c^{T_i})=c^1\cdot P(T_i=1)+c^0\cdot P(T_i=0)$

注意到 $P(T_i=0)=1-P(T_i=1)$ ， $E(T_i)=P(T_i=1)$

得到： $E(c^{T_i})=1+(c-1)\cdot E(T_i)$

由不等式： $x+1\le e^x$ ，得到： $E(c^{T_i}) \le e^{(c-1)\cdot E(T_i)}$

$E(c^T)=\prod_{i=1}^{n}E(c^{T_i})\le e^{(c-1)\cdot \sum_{i=1}^n E(T_i)}=e^{(c-1)\cdot E(T)}$

$\frac{E(c^T)}{c^{c\cdot E(T)}}\le \frac{e^{(c-1)\cdot E(T)}}{c^{c\cdot E(T)}} = e^{-(c\cdot ln(c)+1-c)\cdot E(T)}=e^{-z\cdot E(T)}$

拓展

$T_1,T_2,...,T_n$ 之间相互独立， $T_i$ 满足 $0 \le T_i \le 1$ ，上式仍然成立。

9 案例应用一

加州大学伯克利分校某计科教授论文中，对于 RISC 和 Z8002 两种指令集架构做出了如下统计：

对最后一项比值求和取均值得到 1.2 ，于是给出结论为： Z8002 的平均代码量比 RISC 长 20%。

然而如果把统计量改为 $\frac{RISC}{Z8002}$ ，区平均值求得 1.105，按照该逻辑结论应为： RISC 的平均代码量比 Z8002 长 10.5%。

问题在于，对于统计量 Z 和 R，如果 $E(\frac{Z}{R})=k$ ，并不能推出 $\frac{E(Z)}{E(R)} = k$ ，即 $E(\frac{Z}{R})=k \nvdash \frac{E(Z)}{E(R)} = k$

论文中求得 $E(\frac{\text{Z8002}}{\text{RISC}})=1.2$ ，并不能说明 $\frac{E(\text{Z8002})}{E(\text{RISC})}=1.2$

10 案例应用二

如果有 n 个作业，表示为 $b_1,b_2,..,b_n$ ，m 个网络服务器，表示为 $s_1,s_2,..,s_m$ 。服务器需要处理作业请求， $b_i$ 需要服务器处理时间为 $l_i(0\le l_i \le1)$ ，记 $l=\sum_{i=1}^n l_i$ 。采用什么方法把任务分配给服务器，使得每个服务器处理的期望时间为 $\frac{l}{m}$ 。