第三章 离散型随机变量

---

1、Probability mass function(概率质量函数)

我们回顾一下，离散型随机变量 $X$ 仅在可数点集 $\left\{x_{1}, x_{2}, \ldots\right\}$ 上取值，其分布函数 $F(x)=\mathbb{P}(X \leq x)$ 为阶跃函数，除此之外，它的概率质量函数同样值得研究。

Definition 1. 离散型随机变量 $X$ 有 probability mass function(概率质量函数) $f: \mathbb{R} \rightarrow[0,1]$，定义为
$f(x)=\mathbb{P}(X=x)$

分布函数与质量函数间的关系为

$F(x)=\sum_{x_{i} \leq x} f\left(x_{i}\right), \quad f(x)=F(x)-\lim _{y \rightarrow x^{-}} F(y)$

Lemma 2. 概率质量函数 $f: \mathbb{R} \rightarrow[0,1]$ 满足
$\sum_{x\in \mathbb{R}} f(x)=1$

Example 3. Binomial distribution(二项分布). 投掷一枚硬币 $n$ 次，每次结果为正面朝上的概率为 $p$，反面朝上的概率为 $q=1-p$，则 $\Omega=\{\mathrm{H}, \mathrm{T}\}^{n}$，设结果为正面朝上的次数为随机变量 $X\in \{0,1,2,\ldots,n\}$，显然 $X$ 为离散型随机变量，其概率质量函数 $f(x)$ 满足
$f(x)=0 \quad \text { if } \quad x \notin\{0,1,2, \ldots, n\}$ 设整数 $k\in [0,n]$，则
$f(k)=\binom{n}{k} p^{k} q^{n-k}$ 我们称随机变量 $X$ 服从参数为 $n,p$ 的二项分布，记作 $X \sim \text{bin}(n,p)$.

Example 4. Poisson distribution(泊松分布). 若随机变量 $X\in \{0,1,2,\ldots\}$ 有质量函数
$f(k)=\frac{\lambda^{k}}{k !} e^{-\lambda}, \quad k=0,1,2, \ldots$ 其中 $\lambda>0$，则称 $X$ 服从参数为 $\lambda$ 的泊松分布.

Exercise 5. Log-convexity(对数凸性). 
（1）证明二项分布和泊松分布的质量函数满足
$f(k-1) f(k+1) \leq f(k)^{2},\quad k\geq 1$（2）证明质量函数 $f(k)=90 /(\pi k)^{4}$ 满足
$f(k-1) f(k+1) \geq f(k)^{2},\quad k\geq 1$（3）找出一个质量函数满足
$f(k-1) f(k+1) = f(k)^{2},\quad k\geq 1$

难度：★★★☆☆（点击查看答案）

（1）对于二项分布，有

$\begin{aligned}\frac{f(k-1)f(k+1)}{f(k)^{2}} &=\frac{\binom{n}{k-1}\binom{n}{k+1}}{\binom{n}{k}^{2}}=\frac{k(n-k)}{(k+1)(n-k+1)}\\ &=\frac{nk-k^{2}}{nk-k^{2}+n+1}<1 \end{aligned}$

对于泊松分布，有

$\frac{f(k-1)f(k+1)}{f(k)^{2}}=\frac{k}{k+1}<1$

（2）对于给定的质量函数，有

$\frac{f(k-1)f(k+1)}{f(k)^{2}}=\frac{k^{4}}{(k-1)^{4}(k+1)^{4}}=\left(\frac{k^{2}}{k^{2}-1}\right)^{4}>1$

（3）我们发现需要满足的条件等价于

$\frac{\log{f(k-1)}+\log{f(k+1)}}{2}=\log{f(k)}$

即我们的函数需要满足取对数之后，二阶导恒为零，显然取 $f(x)=pe^{x}$ 满足条件。

---

2、Independence(独立性)

我们之前探讨了事件间的独立性，事件 $A,B$ 独立，当且仅当 $A$ 发生的概率不受 $B$ 发生概率的影响，即

$\mathbb{P}(A \cap B)=\mathbb{P}(A) \mathbb{P}(B)$

类似的，我们考虑离散型随机变量 $X,Y$ 的独立性，即 $X$ 的取值不影响 $Y$ 的分布。

Definition 1. 离散型随机变量 $X,Y$ 独立，当且仅当对于所有的 $x,y$，事件 $\{X=x\},\{Y=y\}$ 独立。

设 $X$ 的取值集合为 $\left\{x_{1}, x_{2}, \dots\right\}$，$Y$ 的取值集合为 $\left\{y_{1}, y_{2}, \ldots\right\}$，设事件

$A_{i}=\left\{X=x_{i}\right\}, \quad B_{j}=\left\{Y=y_{j}\right\}$

注意到 $X,Y$ 可以表示为指示函数 $I_{A_{i}},I_{B_{j}}$ 的线性组合

$X=\sum_{i} x_{i} I_{A_{i}},\quad Y=\sum_{j} y_{j} I_{B_{j}}$

因此要使 $X,Y$ 的取值互不影响，要求 $A_{i},B_{j}$ 的概率互不影响。

Example 2. Poisson flips(泊松投掷). 投掷一枚硬币，正面朝上的概率为 $p=1-q$，设随机变量 $X,Y$ 分别表示正面和反面朝上的次数，若投掷硬币 $N$ 次，其中 $N$ 服从参数为 $\lambda$ 的泊松分布，则 $X,Y$ 独立。

根据全概率公式，

$\begin{aligned} \mathbb{P}(X=x) &=\sum_{n \geq x} \mathbb{P}(X=x | N=n) \mathbb{P}(N=n) \\ &=\sum_{n \geq x}\binom{n}{x} p^{x} q^{n-x} \frac{\lambda^{n}}{n !} e^{-\lambda}=\sum_{n\geq x}\frac{\lambda^{n}}{x!(n-x)!}p^{x}q^{n-x}e^{-\lambda}\\ &=\sum_{n\geq 0}\frac{\lambda^{n+x}}{x!n!}p^{x}q^{n}e^{-\lambda}=\frac{(\lambda p)^{x}}{x!}e^{-\lambda}\sum_{n\geq 0}\frac{(\lambda q)^{n}}{n!}\\ &=\frac{(\lambda p)^{x}}{x!}e^{-\lambda}e^{\lambda q}=\frac{(\lambda p)^{x}}{x !} e^{-\lambda p} \end{aligned}$

$\begin{aligned} \mathbb{P}(X=x, Y=y) &=\mathbb{P}(X=x, Y=y | N=x+y) \mathbb{P}(N=x+y) \\ &=\binom{x+y}{x} p^{x} q^{y} \frac{\lambda^{x+y}}{(x+y) !} e^{-\lambda}=\frac{(\lambda p)^{x}(\lambda q)^{y}}{x ! y !} e^{-\lambda} \end{aligned}$

因此 $X,Y$ 独立。

Theorem 3. 若随机变量 $X,Y$ 独立，且函数 $g, h: \mathbb{R} \rightarrow \mathbb{R}$，则随机变量 $g(X),h(Y)$ 也是独立的。

证明：对于 $a,b\in\mathbb{R}$

$\begin{aligned}\mathbb{P}(g(X)=a, h(Y)=b) &= \sum_{g(x)=a,h(y)=b} \mathbb{P}(X=x, Y=y)\\ &= \sum_{g(x)=a,h(y)=b} \mathbb{P}(X=x) \mathbb{P}(Y=y)\\ &= \sum_{g(x)=a} \mathbb{P}(X=x) \sum_{h(y)=b} \mathbb{P}(Y=y)\\ &= \mathbb{P}(g(X)=a) \mathbb{P}(h(Y)=b) \end{aligned}$

更一般的，我们可以把独立性推广到多个随机变量，即一组离散型随机变量 $\left\{X_{i}\mid i \in I\right\}$ 独立，当且仅当事件 $\left\{X_{i}=x_{i}\right\}$ 对于 $X_{i}$ 的所有取值 $x_{i}$ 都独立。

Exercise 4. 设随机变量 $X,Y\in \mathbb{Z}^{+}$ 相互独立，且拥有相同的质量函数 $f(x)=2^{-x}$，求：
（1）$\mathbb{P}(\min \{X, Y\} \leq x)$，其中 $x\geq 1$
（2）$\mathbb{P}(X<Y)$
（3）$\mathbb{P}(X \text { divides } Y)$
（4）$\mathbb{P}(X \geq k Y)$，其中 $k$ 为给定正整数
（5）$\mathbb{P}(X=r Y)$，其中 $r$ 为给定正实数

难度：★★☆☆☆（点击查看答案）

$\begin{aligned} \mathbb{P}(\min \{X, Y\} \leq x) &=1-\mathbb{P}(X>x, Y>x)=1-\mathbb{P}(X>x) \mathbb{P}(Y>x) \\ &=1-2^{-x} \cdot 2^{-x}=1-4^{-x}\\ \mathbb{P}(X<Y)&=\sum_{x=1}^{\infty}\sum_{y=x+1}^{\infty}\mathbb{P}(X=x,Y=y)\\ &=\sum_{x=1}^{\infty}\sum_{y=x+1}^{\infty}2^{-x}\cdot 2^{-y}=\frac{1}{3}\\ \mathbb{P}(X \text { divides } Y) &=\sum_{k=1}^{\infty} \mathbb{P}(Y=k X)=\sum_{k=1}^{\infty} \sum_{x=1}^{\infty} \mathbb{P}(Y=k x, X=x) \\ &=\sum_{k=1}^{\infty} \sum_{x=1}^{\infty} 2^{-k x} 2^{-x}=\sum_{k=1}^{\infty} \frac{1}{2^{k+1}-1}\\ \mathbb{P}(X \geq k Y) &=\sum_{y=1}^{\infty} \mathbb{P}(X \geq k y, Y=y)=\sum_{y=1}^{\infty} \mathbb{P}(X \geq k y) \mathbb{P}(Y=y) \\ &=\sum_{y=1}^{\infty} \sum_{x=0}^{\infty} 2^{-k y-x} 2^{-y}=\frac{2}{2^{k+1}-1}\\ \mathbb{P}(X=r Y)&=\sum_{k=1}^{\infty} \mathbb{P}(X=k m, Y=k n)（r \text{ 的最简分数形式为 } \frac{m}{n}）\\ &=\sum_{k=1}^{\infty} 2^{-k m} 2^{-k n}=\frac{1}{2^{m+n}-1} \end{aligned}$

Exercise 5. 三个玩家 $A,B,C$ 按照 $ABCABC\ldots$ 的顺序轮流扔骰子。
（1）证明：最先扔出 $6$ 的玩家是 $A$，其次是 $B$，最后是 $C$ 的概率为 $\frac{216}{1001}$.
（2）证明：最先扔出的 $6$ 来自玩家 $A$，第二次来自 $B$，第三次来自 $C$ 的概率为 $\frac{46656}{753571}$.

难度：★★★★☆（点击查看答案）

（1）设事件 $\{A<B<C\}$ 表示 $A$ 比 $B$ 先扔出 $6$，且 $B$ 比 $C$ 先扔出 $6$，那么该事件发生的情况如下：

• 本轮中 $A,B$ 都扔出了 $6$.
• 本轮中 $A$ 扔出了 $6$，$B,C$ 没有扔出，且接下来的游戏中事件 $\{B<C\}$ 发生。
• 本轮中没有人扔出 $6$，且接下来的游戏中事件 $\{A<B<C\}$ 发生。

事件 $\{B<C\}$ 的定义是类似的，因此

$\mathbb{P}(A<B<C)=\left(\frac{1}{6}\right)^{2}+\frac{1}{6}\left(\frac{5}{6}\right)^{2} \mathbb{P}(B<C)+\left(\frac{5}{6}\right)^{3} \mathbb{P}(A<B<C)$

$\mathbb{P}(B<C)=\left(\frac{5}{6}\right)^{2} \mathbb{P}(B<C)+\frac{1}{6}$

据此我们得到 $\mathbb{P}(B<C)=\frac{6}{11}$，$\mathbb{P}(A<B<C)=\frac{216}{1001}$

（2）设 $N$ 表示第一个 $6$ 出现时三人的投掷总次数，那么最先扔出的 $6$ 来自 $A$ 等价于 $N\in \{1,4,7,\ldots\}$ 且

$\mathbb{P}(N \in\{1,4,7, \ldots\})=\sum_{k=1,4,7, \ldots}\left(\frac{5}{6}\right)^{k-1} \frac{1}{6}=\frac{36}{91}$

当 $A$ 扔出第一个 $6$ 时，游戏次序变成了 $BCABCA\ldots$，因此第二个 $6$ 来自 $B$ 的概率是相同的，第三个同理，故

$Ans=\left(\frac{36}{91}\right)^{3}=\frac{46656}{753571}$

---

3、Expectation(数学期望)

设 $x_{1}, x_{2}, \ldots, x_{N}$ 为用数字表示的 $N$ 次试验的结果，则它们的均值

$m=\frac{1}{N} \sum_{i} x_{i}$

现在，我们设随机变量 $X_{1}, X_{2}, \ldots, X_{N}$ 分别表示这 $N$ 次试验的结果，则这些随机变量是离散型的，且拥有相同的分布函数 $f$，那么对于某个取值 $x$，约有 $Nf(x)$ 个 $X_{i}$ 取到 $x$ 这个值，因此这些随机变量的均值为

$m \approx \frac{1}{N} \sum_{x} x N f(x)=\sum_{x} x f(x)$

这个均值 $m$ 被称为分布函数 $f$ 的 expectation(期望) 或 mean value(均值).

Definition 1. 随机变量 $X$ 的期望或均值定义为
$\mathbb{E}(X)=\sum_{x} x f(x)$ 其中 $f$ 为分布函数，且和式绝对收敛。

我们要求右边的和式绝对收敛，这是为了保证交换 $x_{i}$ 的求和次序不会对和式的值产生影响。

想象一下，我们把 $X$ 的取值 $x$ 看成数轴上的点，这个点的重量为 $f(x)$，那么 $X$ 的期望实际上就是这些点的重心位置。

Example 2. 我们回到 Example 2.1.1 中的例子，随机变量 $X,W$ 的期望值为
$\begin{aligned} \mathbb{E}(X)&=\sum_{x} x \mathbb{P}(X=x)=0 \cdot \frac{1}{4}+1 \cdot \frac{1}{2}+2 \cdot \frac{1}{4}=1 \\ \mathbb{E}(W)&=\sum_{x} x \mathbb{P}(W=x)=0 \cdot \frac{3}{4}+4 \cdot \frac{1}{4}=1 \end{aligned}$

若 $X$ 为随机变量且函数 $g: \mathbb{R} \rightarrow \mathbb{R}$，设 $Y=g(X)$，严谨一点的话应该是 $Y(\omega)=g(X(\omega))$，显然 $Y$ 也是一个随机变量，现在我们想知道 $Y$ 的期望值。

按照定义，我们必须先求出 $Y$ 的分布函数 $f_{Y}$，但这个过程可能非常复杂，而使用下面的引理可以避免这些复杂的计算。

Lemma 3. 若随机变量 $X$ 有分布函数 $f$，且函数 $g: \mathbb{R} \rightarrow \mathbb{R}$，则
$\mathbb{E}(g(X))=\sum_{x} g(x) f(x)$ 其中，右边的和式绝对收敛。

证明如下：（亮点在于最后一步中的交换求和号）

$\begin{aligned}\mathbb{E}(g(X)) &=\sum_{y} y \mathbb{P}(g(X)=y)=\sum_{y} \sum_{x: g(x)=y} y \mathbb{P}(X=x)\\ &=\sum_{x} g(x) \mathbb{P}(X=x) \end{aligned}$

这个引理被称为 law of the unconscious statisitician(无意识统计学家法则).

Example 4. 设随机变量 $X$ 的取值为 $-2,-1,1,3$，对应的概率分别为 $\frac{1}{4}, \frac{1}{8}, \frac{1}{4}, \frac{3}{8}$，现在要求 $Y=X^{2}$ 的期望。

我们用这个例子直观的检验一下上面的引理，按照常规流程来做，$Y$ 的取值为 $1,4,9$，对应的概率分别为 $\frac{3}{8}, \frac{1}{4}, \frac{3}{8}$，因此

$\mathbb{E}(Y)=\sum_{x} x \mathbb{P}(Y=x)=1 \cdot \frac{3}{8}+4 \cdot \frac{1}{4}+9 \cdot \frac{3}{8}=\frac{19}{4}$

而如果直接使用引理

$\mathbb{E}(Y)=\sum_{x} x^{2} \mathbb{P}(X=x)=4 \cdot \frac{1}{4}+1 \cdot \frac{1}{8}+1 \cdot \frac{1}{4}+9 \cdot \frac{3}{8}=\frac{19}{4}$

Definition 5. 若 $k$ 为正整数，则随机变量 $X$ 的 k-th moment(k阶矩) $m_{k}$ 定义为
$m_{k}=\mathbb{E}\left(X^{k}\right)$ 且 $X$ 的 k-th central moment(k阶中心矩) $\sigma_{k}$ 定义为
$\sigma_{k}=\mathbb{E}\left(\left(X-m_{1}\right)^{k}\right)$

我们最常使用的两个矩是

$m_{1}=\mathbb{E}(X),\quad \sigma_{2}=\mathbb{E}\left((X-\mathbb{E} X)^{2}\right)$

分别叫做 $X$ 的 expectation(期望) 和 variance(方差)，这两个量分别描述了 $X$ 的平均值和分散程度。

我们常把 $m_{1}$ 记为 $\mu$，把方差记为 $\operatorname{var}(X)$，其非负平方根 $\sigma=\sqrt{\operatorname{var}(X)}$ 称为 standard deviation(标准偏差).

注：根据定义，显然 $\operatorname{var}(X)$ 非负，因此开方是没有问题的。

事实上中心矩 $\{\sigma_{i}\}$ 总能用 $\{m_{i}\}$ 表示，如

$\begin{aligned} \sigma_{2} &=\sum_{x}\left(x-m_{1}\right)^{2} f(x) \\ &=\sum_{x} x^{2} f(x)-2 m_{1} \sum_{x} x f(x)+m_{1}^{2} \sum_{x} f(x) \\ &=m_{2}-m_{1}^{2} \end{aligned}$

该式即是普遍使用的方差计算式

$\operatorname{var}(X)=\mathbb{E}\left((X-\mathbb{E} X)^{2}\right)=\mathbb{E}\left(X^{2}\right)-(\mathbb{E} X)^{2}$

Example 6. Bernoulli distribution(伯努利分布). 设 $X$ 为伯努利变量，取值为 $1$ 的概率为 $p=1-q$，则
$\begin{aligned} \mathbb{E}(X) &=\sum_{x} x f(x)=0 \cdot q+1 \cdot p=p \\ \mathbb{E}\left(X^{2}\right) &=\sum_{x} x^{2} f(x)=0 \cdot q+1 \cdot p=p \\ \operatorname{var}(X) &=\mathbb{E}\left(X^{2}\right)-\mathbb{E}(X)^{2}=p q \end{aligned}$

Example 7. Binomial distribution(二项分布). 设 $X\sim \text{bin}(n,p)$，则
$\mathbb{E}(X)=\sum_{k=0}^{n} k f(k)=\sum_{k=0}^{n} k\binom{n}{k} p^{k} q^{n-k}$ 为了计算这个和式，我们把恒等式
$\sum_{k=0}^{n}\binom{n}{k} x^{k}=(1+x)^{n}$ 两边求导并乘上一个 $x$ 得到
$\sum_{k=0}^{n} k\binom{n}{k} x^{k}=n x(1+x)^{n-1}$ 将 $x=p/q$ 带入得
$\mathbb{E}(X)=nq^{n}\frac{p}{q}(1+\frac{p}{q})^{n-1}=np$类似的，我们可以算出 $\operatorname{var}(X)=n p q$

Theorem 8. 期望算子 $\mathbb{E}$ 具有线性性质，即对于 $a, b \in \mathbb{R}$，有
$\mathbb{E}(a X+b Y)=a \mathbb{E}(X)+b \mathbb{E}(Y)$

证明：设事件 $A_{x}=\{X=x\}, B_{y}=\{Y=y\}$，则

$\begin{aligned}\mathbb{E}(a X+b Y) &=\sum_{x, y}(a x+b y) \mathbb{P}\left(A_{x} \cap B_{y}\right)\\ &=\sum_{x}a x \sum_{y}\mathbb{P}\left(A_{x} \cap B_{y}\right)+\sum_{y}b y\sum_{x}\mathbb{P}\left(A_{x} \cap B_{y}\right) \end{aligned}$

我们发现需要解决两个部分：

$\sum_{y} \mathbb{P}\left(A_{x} \cap B_{y}\right)=\mathbb{P}\left(A_{x} \cap\left(\bigcup_{y} B_{y}\right)\right)=\mathbb{P}\left(A_{x} \cap \Omega\right)=\mathbb{P}\left(A_{x}\right)$

$\sum_{x} \mathbb{P}\left(A_{x} \cap B_{y}\right)=\mathbb{P}\left(\left(\bigcup_{x} A_{x} \right)\cap B_{y}\right)=\mathbb{P}\left(\Omega \cap B_{y}\right)=\mathbb{P}\left(B_{y}\right)$

带入得到

$\begin{aligned}\mathbb{E}(a X+b Y) &=a \sum_{x} x \mathbb{P}\left(A_{x}\right)+b \sum_{y} y \mathbb{P}\left(B_{y}\right) \\ &=a \mathbb{E}(X)+b \mathbb{E}(Y) \end{aligned}$

我们证明了期望的线性性质，但遗憾的是 $\mathbb{E}(X Y)=\mathbb{E}(X) \mathbb{E}(Y)$ 并不是普遍成立的。

Theorem 9. 若随机变量 $X,Y$ 独立，则
$\mathbb{E}(X Y)=\mathbb{E}(X) \mathbb{E}(Y)$

证明：设事件 $A_{x}=\{X=x\}, B_{y}=\{Y=y\}$，则

$\begin{aligned} \mathbb{E}(X Y) &=\sum_{x, y} x y \mathbb{P}\left(A_{x}\right) \mathbb{P}\left(B_{y}\right) \quad \text { by independence } \\ &=\sum x \mathbb{P}\left(A_{x}\right) \sum y \mathbb{P}\left(B_{y}\right)=\mathbb{E}(X) \mathbb{E}(Y) \end{aligned}$

若随机变量 $X,Y$ 满足 $\mathbb{E}(X Y)=\mathbb{E}(X) \mathbb{E}(Y)$，我们称 $X,Y$ uncorrelated(不相关).

上面的定理告诉我们独立的随机变量一定不相关，但是反过来却不一定成立。

Example 10. 设 $X,Y$ 服从参数为 $\frac{1}{2}$ 的伯努利分布，证明：
$X+Y, \quad |X-Y|$ 不相关却不独立。

$\begin{aligned} \mathbb{E}\{(X+Y)|X-Y|\}&=\frac{1}{4}(0+1+1+0)=\frac{1}{2}\\ \mathbb{E}(X+Y) \mathbb{E}(|X-Y|)&=\frac{1}{4}(0+1+1+2)\times \frac{1}{4}(0+1+1+0)=\frac{1}{2}\\ \mathbb{P}(X+Y=0,|X-Y|=0)&=\mathbb{P}(X=0,Y=0)=\frac{1}{4}\\ \mathbb{P}(X+Y=0) \mathbb{P}(|X-Y|=0)&=\mathbb{P}^{2}(X=0,Y=0)\mathbb{P}(X=1,Y=1)=\frac{1}{8} \end{aligned}$

Theorem 11. 随机变量 $X,Y$ 的方差满足
（1）$\operatorname{var}(a X)=a^{2} \operatorname{var}(X)$，其中 $a\in \mathbb{R}$.
（2）$\operatorname{var}(X+Y)=\operatorname{var}(X)+\operatorname{var}(Y)$，当且仅当 $X,Y$ 不相关。

证明：（1）根据期望的线性性质

$\begin{aligned} \operatorname{var}(a X) &=\mathbb{E}\left\{(a X-\mathbb{E}(a X))^{2}\right\}=\mathbb{E}\left\{a^{2}(X-\mathbb{E} X)^{2}\right\} \\ &=a^{2} \mathbb{E}\left\{(X-\mathbb{E} X)^{2}\right\}=a^{2} \operatorname{var}(X) \end{aligned}$

（2）根据 $X,Y$ 的不相关性

$\begin{aligned} \operatorname{var}(X+Y) &=\mathbb{E}\left\{(X+Y-\mathbb{E}(X+Y))^{2}\right\} \\ &=\mathbb{E}\left[(X-\mathbb{E} X)^{2}+2(X Y-\mathbb{E}(X) \mathbb{E}(Y))+(Y-\mathbb{E} Y)^{2}\right] \\ &=\operatorname{var}(X)+2[\mathbb{E}(X Y)-\mathbb{E}(X) \mathbb{E}(Y)]+\operatorname{var}(Y) \\ &=\operatorname{var}(X)+\operatorname{var}(Y) \end{aligned}$

在某些情况下，级数 $S=\sum x f(x)$ 不是绝对收敛的，此时，分布函数 $f(x)$ 的期望不存在，我们来看下面的例子。

Example 12. A distribution without a mean(不存在期望的分布). 设随机变量 $X$ 有分布函数
$f(k)=A k^{-2} \quad \text { for } \quad k=\pm 1,\pm 2, \ldots$ 选定 $A$ 的值使得分布函数满足 $\sum f(k)=1$，我们发现
$\sum_{k} k f(k)=A \sum_{k \neq 0} k^{-1}$ 正负两部分都不收敛，因此级数不满足绝对收敛，期望不存在。

值得一提的是，现在我们可以将概率论的根基建立在期望算子 $\mathbb{E}$ 上，而不是概率测度 $\mathbb{P}$，毕竟我们关于 average 的直觉已经和量化的概率一样好了。

严谨来说，我们以 Theorem 8 为公理定义了名为 expectation operator(期望算子) 的东西，作用于随机变量所在的空间，而事件发生的概率可以重新定义为

$\mathbb{P}(A)=\mathbb{E}\left(I_{A}\right)$

Whittle 曾是该理论的有力支持者，著有《Probability via Expectation》.

这样的理论可用于解决 quantum theory(量子理论) 中的概率学问题，量子理论是理论物理学的一个重要分支，其中的某些问题不能在概率学框架下完整解决。这类问题中不存在样本空间 $\Omega$，不存在指示函数，不存在概率空间下的那一套东西，但是存在期望算子 $\mathbb{E}$，可作用于一种叫做 observables(可观测量) 的线性算子。

Example 13. Wagers(打赌). 概率学家们曾思考一个问题，支付一定的费用开启游戏，然后根据你在游戏中的表现给予奖励，例如我将一枚硬币掩藏在掌下，然后邀请一位朋友支付 $1$ 英镑的价格来猜测硬币正面或反面朝上，猜对获得 $2$ 英镑的报酬，猜错则血本无归。

这样的游戏看起来很公平，因为庄家和玩家最终收益的期望值均为 $0$，朋友们乐意借此消遣无趣的生活。

但是，如果我将游戏的奖励换成 $2^{10}$ 英镑，你是否愿意支付 $2^{9}$ 英镑来玩这个游戏呢？

虽然收益的期望值还是 $0$，游戏仍旧公平，但诸位必定会慎重考虑三思而行，因为这是一场真金白银的豪赌。

由此可见，游戏的公平性与合理性并不等价，玩家对待小赌和大赌的态度是不同的，尽管获胜的概率都是 $50\%$.

我们引入 utility function(效用函数) $u(x)$ 表示某人获取 $x$ 英镑的满意程度，则游戏的合理费用应该是

$\frac{1}{2}(u(0)+u(2^{10}))$

当然，每个人的效用函数都是不同的，但是都满足 $u(0)=0$，且 $u$ 单调不减，对于较小的 $x$，$u(x)$ 的值非常接近 $x$，且 $u$ 为凹函数，因此

$u(x)\leq xu(1) \quad \text{for } x\geq 1$

效用函数是微观经济学中的常用概念，它衡量了消费者对于某次消费的满意程度，其中包含了三条重要原理：

• 人对于财富的占有多多益善，即 $u^{\prime}(x)>0$.
• 随着财富的增加，满足程度的增加速度不断下降，即 $u^{\prime\prime}(x)<0$.
• 在随机条件下，人的决策行为准则是获得最大期望效用值而非最大期望金额。

这也验证了经济市场中的一个准则：

$\text{no free lunch with vanishing risk}$

Example 14.  Joy 现有 $100$ 大洋，他的行为准则是最大化期望效用且效用函数为
$u(x)=\sqrt{x}$ 已知 Joy 有 $0.1$ 的概率睡过他的经济学考试，错过考试需要向学校缴纳 $100$ 块的补考费，然而 Joy 的室友 Mary 从未睡过头，Joy 可以向她支付一定的费用请她帮忙在考试当天叫醒自己，求 Joy 愿意支付的最大费用。

如果采用决策一，即顺天应命不接受叫醒服务，则期望效用为

$u_{1}=\frac{9}{10}\sqrt{100}=9$

如果采用决策二，花费 $x$ 元接受叫醒服务，则期望效用为

$u_{2}=\sqrt{100-x}$

我们发现当 $x\leq 19$ 时，$u_{2}\leq u_{1}$，即愿意支付的最大费用为 $19$ 元。

Example 15. St Peterburg paradox(圣彼得堡悖论) 重复投掷一枚均匀的硬币，直到出现正面朝上为止，记投掷次数为 $k$，玩家将获得 $2^{k}$ 英镑的奖励，你愿意花费多少钱参加这个游戏？

我们发现一次游戏的期望收益为

$\sum_{k=1}^{\infty} 2^{-k} \cdot 2^{k}=\infty$

即如果玩家希望实现自己的收益最大化，只要能够参加游戏，付出多少钱都是可以接受的，然而事实并非如此。

我们知道随着试验次数的增加，试验的结果将会接近其数学期望，设玩家进行了 $N$ 次试验，根据计算机模拟的结果，每次试验的平均收益

$W\approx \frac{\log{N}}{\log{2}}$

虽然随着 $N$ 的增大，$W$ 的值也在不断增大，但是增长速度太慢了，如果游戏的参与称为为 $1$ 亿元，解出对应的 $N\approx 10^{301000000}$，也就是说，重复进行这么多次游戏，你的收益才能和成本抵消。

这个例子告诉我们不能完全按照期望来做决策，我们还需要考虑期望和实验次数的关系。

Exercise 16. Coupons(礼券). 某商场发行了 $c$ 种礼券，每包不透明的商品内等概率的含有一种礼券，集齐所有种类的礼券可获得神秘奖品，假设你每天买一包商品。
（1）求收集 $j$ 种到 $j+1$ 种不同礼券需要花费的天数的期望值。
（2）求获得神秘奖品需要花费的天数的期望值。

难度：★★☆☆☆（点击查看答案）

（1）已经拥有 $j$ 种不同礼券时，设随机变量 $X$ 表示获得新礼券的数量，则每购买一包商品时

$\mathbb{P}(X=1)=\frac{c-j}{c},\quad \mathbb{P}(X=0)=\frac{j}{c}$

设用时为 $n$ 天，则

$\mathbb{E}(nX)=n\mathbb{E}(X)=\frac{n(c-j)}{c}=1\Rightarrow n=\frac{c}{c-j}$

（2）有了上一问的经验就很简单了

$Ans=\sum_{j=0}^{c-1} \frac{c}{c-j}=c \sum_{k=1}^{c} \frac{1}{k}$

Exercise 17. $n$ 个玩家轮流投掷一枚均匀的骰子，则一轮游戏中
（1）若每有一对玩家掷出相同的点数，集体获得一分，求集体总分的期望与方差。
（2）若每有一对玩家掷出相同的点数，集体获得与该点数相同的分数，求集体总分的期望与方差。

难度：★★★★☆（点击查看答案）

（1）设 $I_{ij}$ 表示事件玩家 $i,j$ 掷出相同点数的指示函数，则

$\mathbb{E}\left(I_{i j}\right)=\mathbb{P}\left(I_{i j}=1\right)=\sum_{i=1}^{6}\left(\frac{1}{6}\right)^{2}=\frac{1}{6}, \quad i \neq j$

$\operatorname{var}(I_{ij})=\mathbb{E}(I^{2}_{ij})-\mathbb{E}^{2}(I_{ij})=\frac{1}{6}-\frac{1}{36}=\frac{5}{36},\quad i\neq j$

设集体总分为 $S$，根据期望的线性性质

$\mathbb{E}(S)=\sum_{i<j} \mathbb{E}\left(I_{i j}\right)=\frac{1}{6}\binom{n}{2}$

事实上，随机变量组 $\left\{I_{i j}\mid i<j\right\}$ 两两独立，这是因为

$\begin{aligned} \mathbb{E}\left(I_{i j} I_{j k}\right)&=\mathbb{P}(i, j, k \text { throw same number})\\ &=\sum_{r=1}^{6}\left(\frac{1}{6}\right)^{3}=\frac{1}{36}=\mathbb{E}\left(I_{i j}\right) \mathbb{E}\left(I_{j k}\right) \end{aligned}$

因此，根据方差的性质

$\operatorname{var}(S)=\operatorname{var}\left(\sum_{i<j} I_{i j}\right)=\sum_{i<j} \operatorname{var}\left(I_{i j}\right)=\frac{5}{36}\binom{n}{2}$

（2）设 $X_{ij}$ 表示玩家 $i,j$ 的得分，则

$\mathbb{E}\left(X_{i j}\right)=\sum_{i=1}^{6}i\left(\frac{1}{6}\right)^{2}=\frac{7}{12}, \quad i \neq j$

$\mathbb{E}(S)=\sum_{i<j} \mathbb{E}\left(X_{i j}\right)=\frac{7}{12}\binom{n}{2}$

现在 $X_{ij}$ 之间并不是两两独立的，我们只能埋头苦算

$\begin{aligned} \operatorname{var}(S) &=\mathbb{E}\left\{\left(\sum_{i<j} X_{i j}\right)^{2}\right\}-\mathbb{E}^{2}(S) \\ &=\binom{n}{2} \mathbb{E}\left(X_{12}^{2}\right)+\binom{n}{3} \mathbb{E}\left(X_{12} X_{23}\right)+\left\{\binom{n}{2}^{2}-\binom{n}{2}-\binom{n}{3}\right\} \mathbb{E}\left(X_{12}\right)^{2}-\left(\frac{7}{12}\right)^{2}\binom{n}{2}^{2} \\ &=\frac{315}{144}\binom{n}{2}+\frac{35}{432}\binom{n}{3} \end{aligned}$

注：以上是官方所给答案，但是博主认为上述过程中没有考虑到 $X_{ij},X_{ik}$ 不独立的情形，因此博主的答案是

$\begin{aligned}\operatorname{var}(S) &=\binom{n}{2}\mathbb{E}(X^{2}_{12})+6\binom{n}{3}\mathbb{E}(X_{12}X_{23})+6\binom{n}{4}\mathbb{E}^{2}(X_{12})-\left(\frac{7}{12}\right)^{2}\binom{n}{2}^{2}\\ &=\frac{91}{36}\binom{n}{2}+\frac{91}{36}\binom{n}{3}+\frac{24}{49}\binom{n}{4}-\frac{49}{144}\binom{n}{2}^{2} \end{aligned}$

注意到 $\binom{n}{2}+6\binom{n}{3}+6\binom{n}{4}=\binom{n}{2}^{2}$，因此

$\operatorname{var}(S)=\frac{315}{144}\binom{n}{2}+\frac{35}{72}\binom{n}{3}$

Exercise 18. Arbitrage(套利). 在一场赌马游戏中，共 $n$ 匹赛马，第 $k$ 匹马的下注回报率为 $\pi(k)$，且满足
$\sum_{k=1}^{n}\frac{1}{\pi(k)+1}<1$ 证明：存在一种下注方法可以保证盈利。

难度：★★☆☆☆（点击查看答案）

我们在所有的赛马上下注，第 $k$ 匹马上下注 $\frac{1}{\pi(k)+1}$，那么总的花费小于 $1$，且不管哪匹马获胜我们的回报都是 $1$.

---

4、Indicators and matching(指示函数和匹配问题)

本节我们介绍一些指示函数的应用，在 Example 2.1.8 中我们定义了指示函数

$I_{A}(\omega)=\left\{\begin{array}{ll} 1 & \text { if } \omega \in A \\ 0 & \text { if } \omega \in A^{c} \end{array}\right.$

并且我们知道 $\mathbb{E} I_{A}=\mathbb{P}(A)$.

Example 1. 我们尝试用指示函数证明 Lemma 1.3.6，即
$\mathbb{P}(A \cup B)=\mathbb{P}(A)+\mathbb{P}(B)-\mathbb{P}(A \cap B)$

显然，对于指示函数，有

$I_{A \cup A^{c}}=1,\quad I_{A \cap B}=I_{A} I_{B}$

因此

$\begin{aligned} I_{A \cup B} &=1-I_{(A \cup B)^{c}}=1-I_{A^{c} \cap B^{c}} \\ &=1-I_{A^{c}} I_{B^{c}}=1-\left(1-I_{A}\right)\left(1-I_{B}\right) \\ &=I_{A}+I_{B}-I_{A} I_{B} \end{aligned}$

两边取期望得到

$\mathbb{P}(A \cup B)=\mathbb{P}(A)+\mathbb{P}(B)-\mathbb{P}(A \cap B)$

更一般的，设 $B=\bigcup_{i=1}^{n} A_{i}$，则

$I_{B}=1-\prod_{i=1}^{n}\left(1-I_{A_{i}}\right)$

把乘积展开后两边取期望得到

$\mathbb{P}\left(\bigcup_{i=1}^{n} A_{i}\right)=\sum_{i} \mathbb{P}\left(A_{i}\right)-\sum_{i<j} \mathbb{P}\left(A_{i} \cap A_{j}\right)+\cdots+(-1)^{n+1} \mathbb{P}\left(A_{1} \cap \cdots \cap A_{n}\right)$

这个恒等式称为 inclusion-exclusion formula(容斥公式).

Example 2. Matching problem(匹配问题). 一位秘书打印了 $n$ 封不同的信，每封信都有与之匹配的信封，秘书失误把沓信件摔下来楼梯，于是只好把它们随机地重新放入信封中，假设每种匹配方案都是等概率的，我们想知道恰好有 $r$ 封信放入正确信封的概率。

设 $L_{1},L_{2},\ldots,L_{n}$ 表示这些信件，事件 $A_{i}$ 表示 $L_{i}$ 放入了正确的信封，且 $I_{i}$ 为 $A_{i}$ 的指示函数，定义

$S=\sum_{\pi} I_{j_{1}} \cdots I_{j_{r}}\left(1-I_{k_{r+1}}\right) \cdots\left(1-I_{k_{n}}\right)$

其中 $j_{1},\ldots,j_{r},k_{r+1},\ldots,k_{n}$ 枚举了所有 $1,2,\ldots,n$ 的排列，记随机变量 $X$ 表示放入正确信封的信件数量，则

$S=\left\{\begin{array}{ll} 0 & \text { if } X \neq r \\ r !(n-r) ! & \text { if } X=r \end{array}\right.$

我们要求的事件是 $\{X=r\}$，其指示函数

$I=\frac{1}{r !(n-r) !} S$

也就是说，我们只要求出 $\mathbb{E}(S)$，问题就解决了，将 $S$ 的定义式两边取期望，根据对称性得到

$\mathbb{E}(S)=\sum_{\pi} \sum_{s=0}^{n-r}(-1)^{s}\binom{n-r}{s} \mathbb{E}\left(I_{j_{1}} \cdots I_{j_{r}} I_{k_{r+1}} \cdots I_{k_{r+s}}\right)$

而 $\mathbb{E}\left(I_{j_{1}} \cdots I_{j_{r}} I_{k_{r+1}} \cdots I_{k_{r+s}}\right)$ 即 $L_{j_{1}},\ldots,L_{j_{r}},L_{k_{r+1}},L_{k_{r+s}}$ 都放入正确信封的概率，因此

$\mathbb{E}\left(I_{j_{1}} \cdots I_{j_{r}} I_{k_{r+1}} \cdots I_{k_{r+s}}\right)=\frac{(n-r-s) !}{n !}$

将这些公式代入得到

$\begin{aligned} \mathbb{P}(X=r) &=\mathbb{E}(I)=\frac{1}{r !(n-r) !} \mathbb{E}(S) \\ &=\frac{1}{r !(n-r) !} \sum_{s=0}^{n-r}(-1)^{s}\binom{n-r}{s} n ! \frac{(n-r-s) !}{n !} \\ &=\frac{1}{r !} \sum_{s=0}^{n-r}(-1)^{s} \frac{1}{s !} \end{aligned}$

特别的，当 $n\rightarrow \infty$ 时，没有信装入正确信封的概率为

$\lim_{n\rightarrow \infty} \sum_{s=0}^{n}\frac{(-1)^s}{s!}=e^{-1}$

事实上，我们可以使用容斥公式更简单的解决匹配问题，留作练习。

Example 3. The probabilistic method(概率学方法). 一块土地的外围有 $17$ 根护栏，其中有 $5$ 根损坏，证明：存在连续的 $7$ 根护栏，其中至少有 $3$ 根损坏。

我们给护栏编号为 $1,2,\ldots,17$，设 $I_{k}$ 表示第 $k$ 根护栏损坏的指示函数，随机变量 $R_{k}$ 编号为 $k+1,k+2,\ldots,k+7\pmod{17}$ 的护栏中损坏的数量。

现在，我们等概率的随机选取一根护栏 $K$，有

$\mathbb{E}\left(R_{K}\right)=\frac{1}{17}\sum_{k=1}^{17} \left(I_{k+1}+I_{k+2}+\cdots+I_{k+7}\right)=\sum_{j=1}^{17} \frac{7}{17} I_{j}=\frac{7}{17} \cdot 5>2$

由于 $R_{k}$ 的取值为整数，因此 $\mathbb{P}\left(R_{K} \geq 3\right)>0$，得证。

Exercise 4. The probabilistic method(概率学方法). 设 $G=(V,E)$ 为有限图，对于任意的点集 $W$ 和边 $e\in E$，定义指示函数 $I_{W}(e)=\left\{\begin{array}{ll}1 & \text { if } e \text { connects } W \text { and } W^{\mathrm{c}} \\ 0 & \text { otherwise }\end{array}\right.$ 设 $N_{W}=\sum_{e \in E} I_{W}(e)$，证明：存在 $W\subseteq$ 使得 $N_{W} \geq \frac{1}{2}|E|$.

难度：★★★☆☆（点击查看答案）

我们对图 $G$ 的所有顶点以 $\frac{1}{2}$ 的概率黑白染色，令 $W$ 表示白色点集，则 $N_{W}$ 表示端点为一黑一白的边的数量，故

$\mathbb{E} N_{W}=\frac{1}{2}|E|, \quad \mathbb{P}(N_{W}>\frac{1}{2}|E|)>0$

---

5、Examples of discrete variables

Example 1. Bernoulli trials(伯努利试验). 随机变量 $X$ 的取值为 $0,1$，对应的概率分别为 $p,q=1-p$，有时我们可以用 $X$ 描述一次试验的结果，$0,1$ 分别表示失败和成功，其概率质量函数
$f(0)=1-p, \quad f(1)=p$ 且期望 $\mathbb{E} X=p$，方差 $\operatorname{var}(X)=p(1-p)$.

Example 2. Binomial distribution(二项分布). 我们进行 $n$ 次伯努利试验 $X_{1}, X_{2}, \ldots, X_{n}$，试验成功的次数 $Y=X_{1}+X_{2}+\cdots+X_{n}$，根据 Example 3.1.3 的讨论，$Y$ 的质量函数
$f(k)=\binom{n}{k} p^{k}(1-p)^{n-k}, \quad k=0,1, \ldots, n$ 根据 Theorem 3.3.9 和 Theorem 3.3.11 可得
$\mathbb{E} Y=n p, \quad \operatorname{var}(Y)=n p(1-p)$

Example 3. Trinomial distribution(三项分布). 我们进行 $n$ 次试验，每次试验有 $3$ 种可能的结果，不妨用红白蓝表示，对应的概率分别为 $p,q,1-p-q$，那么红白蓝的次数分别为 $r,w,n-r-w$ 的概率为
$\frac{n !}{r ! w !(n-r-w) !} p^{r} q^{w}(1-p-q)^{n-r-w}$ 这就是参数为 $n,p,q$ 的三项分布，更一般的，若试验的结果有 $t$ 种，称为 multinomial distribution(多项分布).

Example 4. Poisson distribution(泊松分布). 泊松随机变量是指服从质量函数
$f(k)=\frac{\lambda^{k}}{k !} e^{-\lambda}, \quad k=0,1,2, \ldots$ 的随机变量，其中参数 $\lambda>0$，不难验证泊松分布的期望与方差都是 $\lambda$.

泊松分布的由来如下，设随机变量 $Y\sim \text{bin}(n,p)$，设 $\lambda=\mathbb{E}(Y)=n p$，当 $n \rightarrow \infty, p \rightarrow 0$ 时

$\mathbb{P}(Y=k)=\binom{n}{k} p^{k}(1-p)^{n-k} \sim \frac{1}{k !}\left(\frac{n p}{1-p}\right)^{k}(1-p)^{n} \rightarrow \frac{\lambda^{k}}{k !} e^{-\lambda}$

Example 5. Geometric distribution(几何分布). 几何随机变量是指服从质量函数
$f(k)=p(1-p)^{k-1}, \quad k=1,2, \ldots$ 的随机变量，其中参数 $p\in (0,1)$，不难验证几何分布的期望为 $p^{-1}$，方差为 $(1-p)p^{-2}$.

几何分布的由来如下，不断进行参数为 $p$ 的伯努利试验，记 $W$ 为第一次试验成功时已经进行的试验次数，我们把 $W$ 称为 waiting time(等待时长)，那么显然 $\mathbb{P}(W>k)=(1-p)^{k}$，因此

$\mathbb{P}(W=k)=\mathbb{P}(W>k-1)-\mathbb{P}(W>k)=p(1-p)^{k-1}$

Example 6. Negative binomal distribution(负二项分布). 负二项分布是几何分布的扩展，设 $W_{r}$ 表示伯努利试验成功 $r$ 次时的等待时长，不难验证 $W_{r}$ 有质量函数
$\mathbb{P}\left(W_{r}=k\right)=\binom{k-1}{r-1} p^{r}(1-p)^{k-r}, \quad k=r, r+1, \ldots$ 事实上，$W_{r}$ 是 $r$ 个几何随机变量的和，设 $X_{i}$ 表示第 $i-1$ 次成功至第 $i$ 次成功之间的等待时长，不难看出 $X_{1},X_{2},\ldots,X_{r}$ 为相互独立的几何随机变量，且
$W_{r}=X_{1}+X_{2}+\cdots+X_{r}$ 应用 Theorem 3.3.8 和 Theorem 3.3.11 不难求出 $W_{r}$ 的期望和方差。

Exercise 7. 设 $X$ 服从泊松分布
$\mathbb{P}(X=n)=p_{n}(\lambda)=\frac{\lambda^{n}}{n!}e^{-\lambda}, \quad\text { for } n \geq 0$ 证明：
$\mathbb{P}(X \leq n)=1-\int_{0}^{\lambda} p_{n}(x) d x$

难度：★★★☆☆（点击查看答案）

我们将要证的式子两边对 $\lambda$ 求导得

$\frac{d}{d\lambda}\{\mathbb{P}(X\leq n)\}=-p_n(\lambda)$

而 $\mathbb{P}(X\leq n)=\sum_{i=0}^{n}p_{i}(\lambda)$，因此

$\begin{aligned} \frac{d}{d\lambda}\{\mathbb{P}(X\leq n)\}&=\sum_{i=0}^{n}\frac{d}{d\lambda}p_{i}(\lambda)=\sum_{i=0}^{n}\frac{i\lambda^{i-1}e^{-\lambda}-\lambda^{i}e^{-\lambda}}{i!}\\ &=\sum_{i=0}^{n}\{p_{i-1}(\lambda)-p_{i}(\lambda)\}=-p_{n}(\lambda) \end{aligned}$

两边对 $\lambda$ 积分得到

$\mathbb{P}(X \leq n)=C-\int_{0}^{\lambda} p_{n}(x) d x$

令 $n=0$ 得到 $C=1$，证毕。

Exercise 8. Capture-recapture(重复捕捉) 某动物群体中共有 $b$ 个成员，现捕捉其中 $a$ 个，标记后放回，设随机变量 $X$ 表示再次捕捉时捉到 $m$ 个带标记的成员需要的捕捉次数，证明：
$\left.{\mathbb{P}(X=n)=\frac{a}{b}\binom{a-1}{m-1}\binom{b-a}{n-m}}\middle/ \binom{b-1}{n-1}\right.$ 并求 $\mathbb{E} X$，事实上，$X$ 服从 negative hypergeometric distribution(负超几何分布).

难度：★★★☆☆（点击查看答案）

为了满足条件，第 $n$ 次捕捉的动物必须有标记，前 $n-1$ 次捕捉的动物中必须有 $m-1$ 个动物有标记，对应的方案数为 $\frac{a}{b}\binom{a-1}{m-1}\binom{b-a}{n-m}$，而总的方案数为 $\binom{b-1}{n-1}$，证毕。

设 $X_{j}$ 表示捕捉第 $j-1$ 和第 $j$ 个带标记动物之间捕捉的不带标记的动物的期望个数，则

$\sum_{j=0}^{a}\mathbb{E}X_{j}=b-a$

根据对称性，有 $\mathbb{E}X_{1}=\mathbb{E}X_{2}=\cdots=\mathbb{E}X_{n}=\frac{b-a}{a+1}$，因此

$\mathbb{E}X=\sum_{j=1}^{m}(\mathbb{E}X_{j}+1)=\frac{m(b+1)}{a+1}$

---

6、Dependence(相关性)

概率论常常考虑一组随机变量，这些随机变量之间往往不完全是独立的。

我们需要一个工具来研究这些相互关联的随机变量组，下面我们以两个随机变量为例，来研究它们的相关性。

Definition 1. 离散型随机变量 $X,Y$ 的 joint distribution function(联合分布函数) $F: \mathbb{R}^{2} \rightarrow[0,1]$ 定义为
$F(x, y)=\mathbb{P}(X \leq x \text { and } Y \leq y)$ 且 joint mass function(联合质量函数) $f: \mathbb{R}^{2} \rightarrow[0,1]$ 定义为
$f(x, y)=\mathbb{P}(X=x \text { and } Y=y)$

多个随机变量的联合分布函数与联合质量函数的定义也是一样的。

当需要指明随机变量的符号时，我们用 $F_{X,Y}$ 和 $f_{X,Y}$ 来指明对应的随机变量是 $X,Y$.

Lemma 2. 离散型随机变量 $X,Y$ 独立当且仅当
$f_{X, Y}(x, y)=f_{X}(x) f_{Y}(y) \quad \text { for all } x, y \in \mathbb{R}$ 更进一步，$X,Y$ 独立当且仅当 $f_{X,Y}(x,y)$ 可以写成仅含有 $x$ 的函数 $g(x)$ 与仅含有 $y$ 的函数 $h(y)$ 的乘积
$f_{X,Y}(x,y)=g(x)h(y)$

证明：（1）设事件 $A_{x}=\{X=x\},B_{y}=\{Y=y\}$，则

$f_{X,Y}(x, y)=\mathbb{P}\left(A_{x} \cap B_{y}\right)$

根据 Definition 3.2.1，若 $X,Y$ 独立，则

$f_{X,Y}(x,y)=\mathbb{P}(A_{x})\mathbb{P}(B_{y})=f_{X}(x)f_{Y}(y)$

若 $f_{X, Y}(x, y)=f_{X}(x) f_{Y}(y)$，则对于 $x,y\in \mathbb{R}$

$\mathbb{P}\left(A_{x} \cap B_{y}\right)=\mathbb{P}(A_{x})\mathbb{P}(B_{y})\Rightarrow X,Y 独立$

（2）若 $f_{X,Y}(x,y)=g(x)h(y)$，则

$f_{X}(x)=\sum_{y} f_{X, Y}(x, y)=g(x) \sum_{y} h(y)$

$f_{Y}(y)=\sum_{x} f_{X, Y}(x, y)=h(y) \sum_{x} g(x)$

而 $\sum_{x} g(x) \sum_{y} h(y)=1$，因此

$f_{X}(x) f_{Y}(y)=g(x) h(y) \sum_{x} g(x) \sum_{y} h(y)=g(x) h(y)=f_{X, Y}(x, y)$

注：上述过程中，为了验证 $f_{X, Y}(x, y)=f_{X}(x) f_{Y}(y)$，我们计算了 marginal mass function(边际质量函数) $f_{X},f_{Y}$，原理如下：

$\begin{aligned} f_{X}(x) &=\mathbb{P}(X=x)=\mathbb{P}\left(\bigcup_{y}(\{X=x\} \cap\{Y=y\})\right) \\ &=\sum_{y} \mathbb{P}(X=x, Y=y)=\sum_{y} f_{X, Y}(x, y) \end{aligned}$

Example 3. Calculation of marginals(边际的计算) 在 Example 3.2.2 中，我们遇到了一对随机变量 $X,Y$，它们的联合质量函数为
$f(x, y)=\frac{\alpha^{x} \beta^{y}}{x ! y !} e^{-\alpha-\beta} \quad \text { for } \quad x, y=0,1,2, \ldots$ 其中 $\alpha, \beta>0$，那么 $X$ 的边际质量函数为
$f_{X}(x)=\sum_{y} f(x, y)=\frac{\alpha^{x}}{x !} e^{-\alpha} \sum_{y=0}^{\infty} \frac{\beta^{y}}{y !} e^{-\beta}=\frac{\alpha^{x}}{x !} e^{-\alpha}$ 因此 $X$ 服从参数为 $\alpha$ 的泊松分布，且容易验证 $X,Y$ 独立。

对于一对随机变量 $X,Y$，实函数 $g(X,Y)$ 是一个随机变量，我们经常要求它的期望，为了避免计算其复杂的分布函数，我们引入下面的引理。

Lemma 4. 对于随机变量 $X,Y$ 组合而成的随机变量 $g(X,Y)$，有
$\mathbb{E}(g(X, Y))=\sum_{x, y} g(x, y) f_{X, Y}(x, y)$

证明：该引理的证明与 Lemma 3.3.3 类似

$\begin{aligned} \mathbb{E}(g(X,Y))&=\sum_{w}w\mathbb{P}(g(X,Y)=w)\\ &=\sum_{w}w\sum_{x,y:g(x,y)=w}\mathbb{P}(X=x,Y=y)\\ &=\sum_{x,y}\mathbb{P}(X=x,Y=y)\sum_{w:g(x,y)=w}w\\ &=\sum_{x,y}F_{X,Y}(x,y)g(x,y) \end{aligned}$

这个公式对那些试图向门外汉解释独立性的统计学家非常重要。

假设政府希望宣布国防支出与生活费用间的相关性极小，那么不应该发表其联合质量函数的估计结果，大部分群众更喜欢用一个单独的数字来描述这种相关性的规模大小，因此我们引入下面的定义。

Definition 5. 随机变量 $X,Y$ 的 covariance(协方差) 定义为
$\operatorname{cov}(X, Y)=\mathbb{E}[(X-\mathbb{E} X)(Y-\mathbb{E} Y)]$ 它们的 correlation coefficient(相关系数) 定义为
$\rho(X, Y)=\frac{\operatorname{cov}(X, Y)}{\sqrt{\operatorname{var}(X) \cdot \operatorname{var}(Y)}}$

根据协方差的定义，我们知道 $\operatorname{cov}(X, X)=\operatorname{var}(X)$，将定义式展开得到

$\operatorname{cov}(X, Y)=\mathbb{E}(X Y)-\mathbb{E}(X) \mathbb{E}(Y)$

根据 Theorem 3.3.9，如果 $\operatorname{cov}(X, Y)=0$，那么 $X,Y$ 不相关，独立的随机变量一定不相关，反之则不一定成立。

Theorem 6. Cauchy-Schwarz inequality(柯西-施瓦茨不等式) 对于随机变量 $X,Y$
$\mathbb{E}^{2}(X Y) \leq \mathbb{E}\left(X^{2}\right) \mathbb{E}\left(Y^{2}\right)$
等号成立当且仅当 $\mathbb{P}(a X=b Y)=1$，其中 $a,b$ 是不同时为 $0$ 的实数。

证明：我们可以设 $\mathbb{E}\left(X^{2}\right),\mathbb{E}\left(Y^{2}\right)$ 严格为正，因为其中一个为零的情况下证明是显然的，设 $Z=a X-b Y$，则

$0 \leq \mathbb{E}\left(Z^{2}\right)=a^{2} \mathbb{E}\left(X^{2}\right)-2 a b \mathbb{E}(X Y)+b^{2} \mathbb{E}\left(Y^{2}\right)$

不妨设 $b\neq 0$，把右边看成以 $a$ 为元的二次方程，那么方程最多有一个实根，其判别式非正，则

$\mathbb{E}(X Y)^{2}-\mathbb{E}\left(X^{2}\right) \mathbb{E}\left(Y^{2}\right) \leq 0$

当等号成立时，

$\mathbb{E}(Z^{2})=\mathbb{E}\left((a X-b Y)^{2}\right)=0$

因此 $aX-bY=0$ 恒成立，即存在 $a,b\in \mathbb{R}$ 使得 $\mathbb{P}(aX=bY)=1$.

Lemma 7. 相关系数 $\rho$ 满足
$|\rho(X, Y)| \leq 1$ 等号成立当且仅当存在 $\mathbb{P}(a X+b Y=c)=1$，其中 $a,b,c\in\mathbb{R}$.

证明：对于随机变量 $X-\mathbb{E} X$ 和 $Y-\mathbb{E} Y$，根据柯西-施瓦茨不等式

$\begin{aligned} \operatorname{cov}^{2}(X,Y)&=\mathbb{E}^{2}((X-\mathbb{E}X)(Y-\mathbb{E}Y))\\ &\leq \mathbb{E}((X-\mathbb{E}X)^2)\mathbb{E}((Y-\mathbb{E}Y)^2)\\ &=\operatorname{var}(X)\operatorname{cov}(Y) \end{aligned}$

根据相关系数的定义即可证明不等式，当等号成立时

$a(X-\mathbb{E}X)+b(Y-\mathbb{E}Y)=0$

$aX-bY=b\mathbb{E}Y-a\mathbb{E}X$

令 $c=b\mathbb{E}Y-a\mathbb{E}X$ 即可。

Example 8. 设随机变量 $X,Y$ 分别在 $\{1,2,3\},\{-1,0,2\}$ 取值，其联合质量函数 $f(x,y)$ 如下：

经过计算，我们可以得到如下结果：

$\begin{aligned} \mathbb{E}(X Y) &=\sum_{x, y} x y f(x, y)=\frac{29}{18} \\ \mathbb{E}(X) &=\sum_{x} x f_{X}(x)=\frac{37}{18}, \quad \mathbb{E}(Y)=\frac{13}{18} \\ \operatorname{var}(X) &=\mathbb{E}\left(X^{2}\right)-\mathbb{E}(X)^{2}=\frac{233}{324}, \quad \operatorname{var}(Y)=\frac{461}{324} \\ \operatorname{cov}(X, Y) &=\frac{41}{324}, \quad \rho(X, Y)=\frac{41}{\sqrt{107413}} \end{aligned}$

Exercise 9. 设离散型随机变量 $X,Y$ 的联合质量函数为
$f(x, y)=\frac{C}{(x+y-1)(x+y)(x+y+1)}, \quad x, y=1,2,3, \ldots$ 求 $X,Y$ 的边际质量函数，计算常数 $C$ 的值以及 $X,Y$ 的协方差。

难度：★★☆☆☆（点击查看答案）

随机变量 $X$ 的边际质量函数 $f_{X}(x)$ 为

$\begin{aligned} \mathbb{P}(X=x) &=\sum_{y=1}^{\infty} \mathbb{P}(X=x, Y=y) \\ &=\sum_{y=1}^{\infty} \frac{C}{2}\left\{\frac{1}{(x+y-1)(x+y)}-\frac{1}{(x+y)(x+y+1)}\right\} \\ &=\frac{C}{2 x(x+1)}=\frac{C}{2}\left(\frac{1}{x}-\frac{1}{x+1}\right) \end{aligned}$

根据 $\sum_{x=1}^{\infty}f_{X}(x)=1$ 可得 $C=2$.

注意到 $f(x,y)$ 中 $x,y$ 的地位相同，因此 $Y$ 的分布和 $X$ 相同，由于

$\mathbb{E}(X)=\sum_{x=1}^{\infty}(x+1)^{-1}=\infty$

$X,Y$ 的协方差不存在。

Exercise 10. 设离散型随机变量 $X,Y$ 的期望值为 $0$，方差为 $1$，且协方差为 $\rho$，证明：
$\mathbb{E}\left(\max \left\{X^{2}, Y^{2}\right\}\right) \leq 1+\sqrt{1-\rho^{2}}$

难度：★★★☆☆（点击查看答案）

我们知道 $\operatorname{max}\{u, v\}=\frac{1}{2}(u+v)+\frac{1}{2} |u-v|$，因此

$\begin{aligned} \mathbb{E}\left(\max \left\{X^{2}, Y^{2}\right\}\right) &=\frac{1}{2} \mathbb{E}\left(X^{2}+Y^{2}\right)+\frac{1}{2} \mathbb{E}|(X-Y)(X+Y)| \\ &=1+\frac{1}{2} \mathbb{E}|(X-Y)(X+Y)| \end{aligned}$

接下来我们需要处理乘积绝对值的期望，把柯西-施瓦茨不等式两边开方得到

$|\mathbb{E}(XY)|\leq \sqrt{\mathbb{E}(X^{2})\mathbb{E}(Y^{2})}$

代入得到

$\begin{aligned} \mathbb{E}\left(\max \left\{X^{2}, Y^{2}\right\}\right) &\leq 1+\frac{1}{2} \sqrt{\mathbb{E}\left((X-Y)^{2}\right) \mathbb{E}\left((X+Y)^{2}\right)} \\ &=1+\frac{1}{2} \sqrt{(2-2 \rho)(2+2 \rho)}\\ &=1+\sqrt{1-\rho^{2}} \end{aligned}$

Exercise 11. Mutual information(互信息). 设离散型随机变量 $X,Y$ 的联合质量函数为 $f$.
（1）证明：
$\mathbb{E}\left(\log f_{X}(X)\right) \geq \mathbb{E}\left(\log f_{Y}(X)\right)$ （2）证明：互信息
$I=\mathbb{E}\left(\log \left\{\frac{f(X, Y)}{f_{X}(X) f_{Y}(Y)}\right\}\right)\geq 0$ 等号成立当且仅当 $X,Y$ 独立。

难度：★★★☆☆（点击查看答案）

（1）我们知道 $\log{y}\leq y-1$ 恒成立，当且仅当 $y=1$ 时等号成立，因此

$\begin{aligned} \mathbb{E}\left(\log \frac{f_{Y}(X)}{f_{X}(X)}\right) &\leq \mathbb{E}\left[\frac{f_{Y}(X)}{f_{X}(X)}\right]-1\\ &=\sum_{x}f_{X}(x)\frac{f_{Y}(x)}{f_{X}(x)}-1\\ &=\sum_{x}f_{Y}(x)-1\leq 0 \end{aligned}$

等号成立当且仅当 $f_{X}=f_{Y}$.

（2）还是利用 $\log{y}\leq y-1$ 得到

$\begin{aligned} \mathbb{E}\left(\log \left\{\frac{f_{X}(X) f_{Y}(Y)}{f(X, Y)}\right\}\right)&\leq \mathbb{E}\left(\frac{f_{X}(X) f_{Y}(Y)}{f(X, Y)}\right)-1\\ &=\sum_{x,y}f(x,y)\frac{f_{X}(x)f_{Y}(y)}{f(x,y)}-1\\ &=\sum_{x}f_{X}(x)\sum_{y}f_{Y}(y)-1=0 \end{aligned}$

等号成立当且仅当 $f(x,y)=f_{X}(x)f_{Y}(y)$，即 $X,Y$ 独立。

---

7、Conditional distributions(条件分布)

之前我们讨论了条件概率 $\mathbb{P}(B \mid A)$，我们可以把它扩展到更一般的情境之下，讨论随机变量 $Y$ 在已知随机变量 $X$ 的值的条件下的条件分布。

Definition 1. 随机变量 $Y$ 在给定另一随机变量 $X=x$ 下的 conditional distribution function(条件分布函数) $F_{Y \mid X}(\cdot \mid x)$ 定义为
$F_{Y \mid X}(y \mid x)=\mathbb{P}(Y \leq y \mid X=x)$ 其中 $\mathbb{P}(X=x)>0$，对应的 conditional mass function(条件质量函数) $f_{Y \mid X}(\cdot \mid x)$ 定义为
$f_{Y \mid X}(y \mid x)=\mathbb{P}(Y=y \mid X=x)$

根据定义我们可以得到

$\begin{aligned} f_{Y \mid X}(y \mid x) &=\mathbb{P}(Y=y \mid X=x)\\ &=\frac{\mathbb{P}(Y=y, X=x)}{\mathbb{P}(X=x)}=\frac{f_{X,Y}(x,y)}{f_{X}(x)} \end{aligned}$

由此可知，当 $f_{Y \mid X}=f_{Y}$ 时，$X,Y$ 独立。

当给定 $X=x$ 时，$Y$ 的条件质量函数 $f_{Y \mid X}(y \mid x)$ 是一个关于 $y$ 的函数，其均值

$\sum_{y} y f_{Y \mid X}(y \mid x)$

命名为 conditional expectation(条件期望)，当 $x$ 值变化时，这个条件期望随之变化，我们把这个函数关系记作

$\psi(x)=\mathbb{E}(Y \mid X=x)=\sum_{y} y f_{Y \mid X}(y \mid x)$

Definition 2. 记 $\psi(x)=\mathbb{E}(Y \mid X=x)$，随机变量 $Y$ 在给定随机变量 $X$ 下的条件期望定义为
$\mathbb{E}(Y \mid X)=\psi(X)$

虽然条件期望听起来像是一个数值，但实际上是一个与 $X$ 相关的随机变量。

且条件期望拥有下面这一条重要性质。

Theorem 3. 条件期望 $\psi(X)=\mathbb{E}(Y \mid X)$ 满足
$\mathbb{E}(\psi(X))=\mathbb{E}(Y)$

证明：根据 Lemmma 3.3.3

$\begin{aligned} \mathbb{E}(\psi(X)) &=\sum_{x} \psi(x) f_{X}(x)=\sum_{x, y} y f_{Y \mid X}(y \mid x) f_{X}(x) \\ &=\sum_{x, y} y f_{X, Y}(x, y)=\sum_{y} y f_{Y}(y)=\mathbb{E}(Y) \end{aligned}$

这个性质非常的重要，它提供了一种计算期望 $\mathbb{E}(Y)$ 的方法，类似于全概率公式，可以将期望拆开计算

$\mathbb{E}(Y)=\sum_{x} \mathbb{E}(Y \mid X=x) \mathbb{P}(X=x)$

Example 4. 一只母鸡下了 $N$ 个蛋，$N$ 服从参数为 $\lambda$ 的泊松分布，每个鸡蛋有 $p$ 的概率孵化且与其它鸡蛋相互独立，记 $K$ 孵化出的雏鸡数量，计算 $\mathbb{E}(K \mid N), \mathbb{E}(K),\mathbb{E}(N \mid K)$.

我们知道泊松分布的质量函数

$f_{N}(n)=\frac{\lambda^{n}}{n !} e^{-\lambda}$

根据二项分布可以得到 $K$ 在 $N$ 下的条件质量函数

$f_{K \mid N}(k \mid n)=\binom{n}{k} p^{k}(1-p)^{n-k}$

由此可以计算

$\psi(n)=\mathbb{E}(K \mid N=n)=\sum_{k} k f_{K \mid N}(k \mid n)=p n$

$\mathbb{E}(K \mid N)=\psi(N)=p N$

根据 Theorem 3 可得

$\mathbb{E}(K)=\mathbb{E}(\psi(N))=p \mathbb{E}(N)=p \lambda$

接下来要求 $\mathbb{E}(N \mid K)$，我们需要知道对应的条件质量函数 $f_{N \mid K}$，而

$\begin{aligned} f_{N \mid K}(n \mid k) &=\mathbb{P}(N=n \mid K=k) \\ &=\frac{\mathbb{P}(K=k, N=n) }{\mathbb{P}(K=k)}=\frac{f_{N,K}}{f_{K}} \end{aligned}$

因此我们需要先求联合质量函数

$f_{N,K}(n,k)=f_{K \mid N}(k \mid n)f_{N}(n)=\binom{n}{k} p^{k}(1-p)^{n-k}\frac{\lambda^n}{n!} e^{-\lambda}$

以及 $K$ 的边际质量函数

$\begin{aligned}f_{K}(k) &=\sum_{n=k}^{\infty} \binom{n}{k} p^{k}(1-p)^{n-k}\frac{\lambda^n}{n!} e^{-\lambda}=\frac{p^{k}}{k!}e^{-\lambda}\sum_{n=k}^{\infty} \frac{(1-p)^{n-k}}{(n-k)!} \lambda^n\\ &=\frac{p^{k}}{k!}e^{-\lambda}\sum_{n=0}^{\infty} \frac{(1-p)^{n}}{n!} \lambda^{n+k}=\frac{p^{k}}{k!}e^{-\lambda}\lambda^{k}\sum_{n=0}^{\infty} \frac{[(1-p)\lambda]^{n}}{n!}\\ &=\frac{p^{k}}{k!}e^{-\lambda}\lambda^{k}e^{(1-p)\lambda}=\frac{(\lambda p)^{k}e^{-p\lambda}}{k!} \end{aligned}$

由此得到

$f_{N \mid K}(n \mid k)=\frac{f_{N,K}}{f_{K}}=\frac{[(1-p)\lambda]^{n-k}}{(n-k)!}e^{-(1-p)\lambda}$

因此

$\begin{aligned}\psi(k) &=\mathbb{E}(N \mid K=k)=\sum_{n=k}^{\infty}nf_{N \mid K}(n \mid k)\\ &=e^{-(1-p)\lambda}\sum_{n=0}^{\infty}(n+k)\frac{[(1-p)\lambda]^{n}}{n!}=k+(1-p)\lambda \end{aligned}$

即 $\mathbb{E}(N \mid K)=K+(1-p)\lambda$.

Theorem 5. 条件期望 $\psi(X)=\mathbb{E}(Y \mid X)$ 满足
$\mathbb{E}(\psi(X) g(X))=\mathbb{E}(Y g(X))$ 其中 $g(X)$ 的期望存在。

证明：和 Theorem 3 类似

$\begin{aligned} \mathbb{E}(\psi(X) g(X)) &=\sum_{x} \psi(x) g(x) f_{X}(x)=\sum_{x, y} y g(x) f_{Y \mid X}(y \mid x) f_{X}(x) \\ &=\sum_{x, y} y g(x) f_{X, Y}(x, y)=\mathbb{E}(Y g(X)) \end{aligned}$

事实上，令 $g(x)=1$ 即可得到 Theorem 3，该定理将其进行了扩展。

---

8、Sums of random variables(随机变量的和)

在概率论中，我们常常要考虑随机变量之和的分布，例如我们已经见过的投掷 $n$ 枚硬币的例子。

然而还有很多情形更为复杂，我们需要一个系统的理论在解决随机变量之和的问题。

Theorem 1. 我们有 $\mathbb{P}(X+Y=z)=\sum f(x, z-x)$

证明是显然的

$\mathbb{P}(X+Y=z)=\sum_{x} \mathbb{P}(X=x, Y=z-x)=\sum_{x} f(x, z-x)$

特别的，如果 $X,Y$ 独立，那么

$\mathbb{P}(X+Y=z)=f_{X+Y}(z)=\sum_{x} f_{X}(x) f_{Y}(z-x)$

其中 $X+Y$ 的质量函数是 $X,Y$ 质量函数的 convolution(卷积)，记作

$f_{X+Y}=f_{X} * f_{Y}$

Example 2. 设随机变量 $X_{1},X_{2}$ 服从几何分布，质量函数均为
$f(k)=p(1-p)^{k-1}, \quad k=1,2, \ldots$ 求 $Z=X_{1}+X_{2}$ 的质量函数。

$\begin{aligned} \mathbb{P}(Z=z) &=\sum_{k} \mathbb{P}\left(X_{1}=k\right) \mathbb{P}\left(X_{2}=z-k\right) \\ &=\sum_{k=1}^{z-1} p(1-p)^{k-1} p(1-p)^{z-k-1} \\ &=(z-1) p^{2}(1-p)^{z-2}, \quad z=2,3, \ldots \end{aligned}$

Example 3. Pepys's problem(佩皮斯问题). Sam 扔了 $6n$ 枚骰子，希望扔出至少 $n$ 个 $6$，而 Isaac 扔了 $6(n+1)$ 枚骰子，希望扔出至少 $n+1$ 个 $6$，谁更容易达成目标？

设随机变量 $X_{n}$ 表示扔 $6n$ 个骰子得到的 $6$ 的个数，那么

$X_{n+1}=X_{n}+Y$

其中 $Y$ 的分布与 $X_{1}$ 相同且与 $X_{n}$ 独立，那么

$\begin{aligned} \mathbb{P}\left(X_{n+1} \geq n+1\right) &=\sum_{r=0}^{6} \mathbb{P}\left(X_{n} \geq n+1-r\right) \mathbb{P}(Y=r) \\ &=\mathbb{P}\left(X_{n} \geq n\right)+\sum_{r=0}^{6}\left[\mathbb{P}\left(X_{n} \geq n+1-r\right)-\mathbb{P}\left(X_{n} \geq n\right)\right] \mathbb{P}(Y=r) \end{aligned}$

设 $g(k)=\mathbb{P}\left(X_{n}=k\right)$，显然 $g(k)$ 单调递减，因此

$\begin{aligned} \mathbb{P}\left(X_{n+1} \geq n+1\right) &=\mathbb{P}\left(X_{n} \geq n\right)+\mathbb{P}(Y=0)(-g(n))+\sum_{r=1}^{6}\sum_{k=n-r+1}^{n-1}g(k)\mathbb{P}(Y=r)\\ &\leq \mathbb{P}\left(X_{n} \geq n\right)+\mathbb{P}(Y=0)(-g(n))+\sum_{r=1}^{6}(r-1)g(n)\mathbb{P}(Y=r)\\ &=\mathbb{P}\left(X_{n} \geq n\right)+g(n) \sum_{r=0}^{6}(r-1) \mathbb{P}(Y=r)\\ &=\mathbb{P}\left(X_{n} \geq n\right)+g(n)(\mathbb{E}(Y)-1) \end{aligned}$

显然 $\mathbb{E}(Y)=1$，因此 Sam 更容易。