期望的性质

本章主要是进一步讨论期望值的性质。首先回顾一下，期望的定义。在离散下有：

$$ E[X]=\sum_x xp(x) $$

连续情况下有

$$ E[X]=\int_{-\infty}^{\infty} xf(x)dx $$

并且可以说明对于随机变量函数的期望各自为

$$ E[g(X)]=\sum_x g(x)p(x)\quad E[g(X)]=\int_{-\infty}^{\infty} g(x)f(x)dx $$

随机变量和的期望

在上一章中引入了随机变量的联合分布。现在将随机变量函数的期望扩展上去。即如下定理

证明思路跟连续型随机变量证明有一定类似性。这里略。

这个定理有个最直接的应用就是，两个连续型随机变量的和。设$E[X],E[Y]$均是有限的，则令$g(X,Y)=X+Y$。另有命题可得

$$ \begin{aligned} E[X+Y]&=\int_{-\infty}^\infty\int_{-\infty}^{\infty}(x+y)f(x,y)dxdy\\ &=\int_{-\infty}^\infty xf_X(x)dx+\int_{-\infty}^\infty yf_Y(y)dy=E[X]+E[Y] \end{aligned} $$

一般情形下，结论任然成立。因此，当$E[X],E[Y]$均是有限时，有

$$ E[X+Y]=E[X]+E[Y] $$

进一步用归纳法可知对于一组随机变量$X_i,i=1,2\cdots,n$。只要它们期望均有限就会有

$$ E[X_1+X_2+\cdots+X_n]=E[X_1]+E[X_2]+\cdots+E[X_n] $$

这个结论跟离散随机变量和的期望相对应。都指明，随机变量和的期望，与各自期望的和相等。

针对该特性最多应用的方式就是示性变量的应用。示性变量在前面部分也有出现，其是一个随机变量，主要用来指示某个事件是否发生。对于某个事件$A$，其一般定义为：

$$ X= \begin{cases} 1\quad & 若A发生 \\ 0\quad & 其他 \end{cases} $$

其有一些直接引用跟前面结论相对应。

二项随机变量的期望

设$X$为二项随机变量参数为$(n,p)$。根据定义，可以认为这是$n$次独立重复实验，每次成功概率为$p$。设每次独立试验的示性变量为$X_i$，则

$$ X=\sum_i X_i $$

而每次试验的示性变量有

$$ X_i= \begin{cases} 1\quad & 第i次试验成功 \\ 0\quad & 第i次试验失败 \end{cases} $$

进而有

$$ E[X]=\sum E[X_i]=np $$

负二项随机变量的期望

负二项随机变量为一系列重复独立试验知道有$r$次成功所需的试验次数。现在构造其和表达式。从每次成功试验所需次数来出发。即$X_i$表示在第$i_1$次成功之后，到第$i$次成功时所需试验次数。则

$$X=X_1+X_2+\cdots+X_r$$

现在看$X_i$的表示。可以发现其就是几何分布。即

$$ P\{X_i=n\}=p(n)=(1-p)^{n-1}p $$

进而有

$$E[X_i]=\sum_i ip(i)=\frac{1}{p}$$

所以有$E[X]=\sum E[X_i]=r/p$

超几何变量的期望

超几何变量为，从有$N$个球，$m$个白球中随机取出$n$个球，其中白球个数的值。这里考虑每个指定白球被取出事件的示性变量。即$X_i$表示第$i$个白球的被取出事件的示性变量，即其被取出时$X_i=1$。则

$$ X=X_1+X_2+\cdots+X_m $$

其中$X_i$为$1$即被取出概率有

$$p\{X_i=1\}=\frac{\binom{1}{1}\binom{N-1}{n-1}}{\binom{N}{n}}=\frac{n}{N}$$

所以有$E[X]=\sum E[X_i]=nm/N$

这一章有一个例子跟计算机算法关联。就是快速排序的对比次数期望，也即快速排序的算法复杂度。部分算法分析中也会将这个期望获得方式。与这里基本一致。这里只是系统的从概率论角度上去出发。

记$X$为对$n$个不同数排序所需的比较次数，则$E[X]$时对这个排序算法时间复杂度的一个度量。现在寻找和式表达式。首先将数组从小到大排序好的元素一次比较为$1,2\cdots,n$。现在考虑数组中任意两个元素例如$i,j$位置元素比较次数。通过算法可以知道，两个元素发生比较之后就切分了，不会再进行比较。即比较次数要么为$1$要么为$0$，即可以定义

$$ I_{i,j}= \begin{cases} 1\quad & 在排序中i,j比较过\\ 0\quad & 其他 \end{cases} $$

显然

$$ X=\sum_{i=1}^{n-1}\sum_{j=i+1}^n I_{i,j} $$

现在看$I_{i,j}$比较的概率。在排序过程中，随机选择一个比较点，然后进行比较。针对两个给定位置$i,j$，如果选择的比较点比$i$小或者比$j$大，则$i,j$会进入下一轮。如果比较点在$i$到$j$之间。即$i,i+1,\cdots,j$中一个。则细分两类，如果选择恰好为$i,j$则两者直接比较，否则，两者再也不会比较。注意要算法终结，必须要在$i$到$j$之间选择一次比较点。

也就是说，其最后必须在$i$到$j$之间选择一个点。这时选中$i,j$的概率就是$2/(j-i+1)$。

所以

$$ E[X]=\sum_{i=1}^{n-1}\sum_{j=i+1}^n \frac{2}{j-i+1} $$

计算这个可以通过转换积分方式来估计。考虑$\sum_i^n1/x$，由图像面积关系可以得

$$ \ln \frac{n+1}{i}=\int_{i}^{n+1}\frac{1}{x} dx \lt \sum_i^n1/x\lt \int_{i-1}^{n}\frac{1}{x}dx =\ln \frac{n}{i-1} $$

所以有

$$ \begin{aligned} \sum_{i=1}^{n-1}\sum_{j=i+1}^n \frac{2}{j-i+1} &\lt \sum_{i=1}^{n-1}2(\ln (x-i+1)|_i^n)\\ &=\sum_{i=1}^{n-1} 2\ln(n-i+1)\\ &=\sum_{i=1}^{n-1} 2\ln(i+1)\\ &\lt 2(n-1)\ln(n) \end{aligned} $$

书上是用积分直接近似得到的，离散求和和积分之间确实由直接的近似关系：

$$ \sum_{j=i+1}^n \frac{2}{j-i+1}\approx \int_{i+1}^n\frac{2}{x-i+1}dx==2\ln(n-i+1)\\ \sum_{i=1}^{n-1}2\ln(n-i+1)\approx \int_{i}^{n-1}\ln(n-x+1) dx=2\int_2^n\ln(x)dx=2(x\ln x-x)|_2^n\approx2n\ln n $$

实验序列中事件发生次数的矩

在随机变量章节中介绍过，随机变量的k阶矩即$E[X^k]$。本节通过随机变量和的组合关系的特性给出一个求出矩的方式。

在前面，许多例子都具有下列形式： 给定事件序列$A_1,\cdots,A_n$，求出$E[X]$，其中$X$是这些事件在实验中发生的次数。解法是给每个事件示性变量$I_i$有

$$ I_i= \begin{cases} 1\quad & 若A_i发生\\ 0\quad & 其他 \end{cases} $$

而

$$X=\sum_i I_i$$

进而有

$$E[X]=\sum_iE[I_i]=\sum_iP(A_i)$$

现在考虑对成对事件出现次数感兴趣。即如果事件$A_i$与$A_j$在实验中发生，则$I_iI_j=1$，反之则$I_iI_j=0$。所以成对发生次数即和式$\sum I_iI_j$的值。另一方面因为$X$表示整个事件发生的次数，有组合可知，其中成对发生的次数恰为$\binom{X}{2}$。由此可得

$$ \binom{X}{2}=\sum_{i\lt j}I_iI_j $$

把左边视为随机变量的函数，两边同时求期望即有

$$ E[\binom{X}{2}]=E[\frac{X(X-1)}{2}]=E[\sum_{i\lt j}I_iI_j]=\sum_{i\lt j}E[I_iI_j]=\sum_{i\lt j}P(A_iA_j) $$

由此可以解得$E[X^2]$的值，进而求出$Var(X)=E[X^2]-E^2[X]$的值等。

针对上述过程可以扩展。考虑$k$个不同事件组的出现次数，即可得

$$ E[\binom{X}{k}]=\sum_{i_1\lt i_2\lt \cdots\lt i_k}E[I_1I_2\cdots I_k]=\sum_{i_1\lt i_2\lt \cdots\lt i_k}P(A_{i_1}A_{i_2}\cdots A_{i_k}) $$

随机变量和的协方差、方差及相关系数

本节主要独立随机变量得乘积期望，以及协方差定义。

把协方差定义展开可得

$$ \begin{aligned} Cov(X,Y)&=E[XY-E[X]Y-XE[Y]+E[X]E[Y]]\\ &=E[XY]-E[X]E[Y]-E[X]E[Y]+E[X]E[Y]\\ &=E[XY]-E[X]E[Y] \end{aligned} $$

所以如果两个随机变量$X,Y$独立。有前面定理可知$E[XY]=E[X]E[Y]$。进而有$Cov(X,Y)=0$。但注意$Cov(X,Y)=0$并不能说明$X,Y$独立。$Cov(X,Y)=0$只要期望刚好满足，或者两者都为0即可。所以独立性是更强的条件。

关于协方差有以下特点。

证明方式从协方差定义入手即可。

结合上述定理，可以得到关于随机变量和的方差的一些有用信息。令上述定理中第四条中$Y_j=X_j,j=1,\cdots,n$。即相同变量和的协方差。有如下公式：

$$ \begin{aligned} Var(\sum_{i=1}^nX_i)&=Cov(\sum_{i=1}^nX_i,\sum_{j=1}^nX_j)=\sum_{i=1}^n\sum_{j=1}^nCov(X_i,X_j)\\ &=\sum_{i=1}^nVar(X_i)+\sum\sum_{i\ne j}Cov(X_i,X_j) \end{aligned} $$

可以注意到当$i=j$时$X_i=X_j$即方差值。这个公式表面，随机变量和的方差，等于各自方差的和，加上所以不同变量之间协方差的和。如果$X_1,\cdots,X_n$两两独立，即对于$i\ne j$,$X_i$和$X_j$相互独立。则$Cov(X_i,X_j)=0$所以有：

$$ Var(\sum_{i=1}^nX_i)=\sum_{i=1}^nVar(X_i) $$

条件期望

在前面章节中定义过随机变量的条件分布。当$X,Y$联合分布离散时，当$P\{Y=y\}>0$时，$X$的条件分布列为：

$$ p_{X|Y}(x|y)=P\{X=x|Y=y\}=\frac{p(x,y)}{p_Y(y)} $$

其也是一个概率分布，可以自然的定义$X$在给定$Y=y$之下的条件期望为：

类似地，当$X,Y$联合分布连续时，其联合概率密度函数为$f(x,y)$，对于个给定地$Y=y$，当$f_Y(y)>0$时，条件概率密度函数为定义为

$$ f_{X|Y}(x|y)=\frac{f(x,y)}{f_Y(y)} $$

正如条件概率满足概率的所有性质，条件期望也满足通常期望的性质。例如如下公式：

$$ E[g(X)|Y=y]= \left\{ \begin{aligned} &\sum_x g(x)p_{X|Y}(x|y)\quad 离散情形\\ &\int_{-\infty}^\infty g(x)f_{X|Y}(x|y)dx \quad 连续情形 \end{aligned} \right. $$

即条件概率下，随机变量的函数依然可以直接带入函数来计算期望。同理，期望的加和性质也成立即:

$$ E[\sum_{i=1}^nX_i|Y=y]=\sum_{i=1}^nE[X_i|Y=y] $$

事实上，给定$Y=y$的条件下条件期望，可以看成是减小了样本空间中的普通期望，这个减小的样本空间由满足$Y=y$条件的那些样本点组成。

通过取条件计算期望

根据前面定义。$E[X|Y=y]$表示在随机变量$Y$取值$y$的情况下对$X$的期望。即针对每一个给定的$Y=y$值，$E[X|Y]$给出一个数值。可当作$g(y)=E[X|Y=y]$。所以实际上可以把$E[X|Y]$视为随机变量$Y$的函数。由此可证明如下定理：

在这个公式中，实际上$E[X|Y]$视为随机变量$Y$的函数。所以$E[E[X|Y]]$实际相当于对随机变量$Y$的函数的一个期望。

换句话说，如果$Y$是离散随机变量则

$$ E[X]=E[E[X|Y]]=\sum_y E[X|Y=y]P\{Y=y\} $$

$Y$是连续型随机变量则

$$ E[X]=\int_{-\infty}^\infty E[X|Y=y]f_Y(y)dy $$

证明思路就是讲公式中的各个表达展开。例如对于离散情况下来说有：

$$ \begin{aligned} \sum_y E[X|Y=y]P\{Y=y\}&=\sum_y(\sum_x xP\{X=x|Y=y\})P\{Y=y\}\\ &=\sum_y(\sum_x x\frac{P\{X=x,Y=y\}}{P\{Y=y\}}P\{Y=y\})\\ &=\sum_y\sum_x xP\{X=x,Y=y\}=E[X] \end{aligned} $$

对于连续情况下来说有：

$$ \begin{aligned} \int_{-\infty}^\infty E[X|Y=y]f_Y(y)dy&=\int_{-\infty}^\infty (\int_{-\infty}^\infty xf_{X|Y}(x|y) dx)f_Y(y)dy \\ &=\int_{-\infty}^\infty\int_{-\infty}^\infty xf(x,y) dxdy=E[X] \end{aligned} $$

这个定理可以这样来解释，期望值$E[X]$可以看成是条件期望$E[X|Y=y]$的加权平均，其权重刚好是$Y=y$的概率。这个定义跟随机变量的期望是一样的。回顾期望的定义，期望是随机变量每个可能值根据发生概率的加权平均值。这里的可能指就是$E[X|Y=y]$。

通过条件计算概率

取条件期望的方法还可以计算概率。方式通过示性变量来关联期望和概率。设$A$为一个随机事件，令$X$为$A$的示性变量，即

$$ X= \begin{cases} 1 & A发生 \\ 0 & A不发生 \\ \end{cases} $$

则显然有

$$ E[X]=P(A)\\ E[X|Y=y]=P(A|Y=y) $$

重新引用期望公式即有

$$ E[X]=P(A)= \left\{ \begin{aligned} &\sum_y P(A|Y=y)P(Y=y)\quad 离散情形\\ &\int_{-\infty}^\infty P(A|Y=y)f_Y(y)dy \quad 连续情形 \end{aligned} \right. $$

注意到如果$Y$为离散型随机变量，那么针对每个值定义事件$B_i=\{Y=y_i\}$，即哪些所有使的随机变量为$y_i$的结果包成一个事件。则上述公式会变成全概率公式。即

$$ P(A)=\sum_i P(A|B_i)P(B_i) $$

从这里可以看到随机变量条件概率跟事件条件概率之间的关联性。

条件期望及预测

这里讨论的主要问题是，观测到随机变量$X$的值，然后基于$X$的值，对第二个随机变量$Y$进行预测。即用$g(X)$来预测表示$Y$这个随机变量。现在显然希望能选择$g$使得$g(X)$最接近$Y$。选择$g$的一个标准是极小化$E[(Y-g(X))^2]$。

下面证明，$Y$的最优预测值为$g(X)=E[Y|X]$。即用$X=x$情况下$Y$发生的期望值来预测$Y$。

定理是说对于$X$的任何函数预测偏差都比$E[Y|X]$要大。从$X$条件期望入手：

$$ \begin{aligned} E[(Y-g(X))^2|X]&=E[(Y-E[Y|X]+E[Y|X]-g(X))^2|X]\\ &=E[(Y-E[Y|X])^2|X]+E[(E[Y|X]-g(X))^2|X]\\ &\quad+2E[(Y-E[Y|X])(E[Y|X]-g(X))|X] \end{aligned} $$

在公式添加$E[Y|X]$项之后平方展开。这里最需要关注的是最后一项。对于给定的$X$值，注意$E[Y|X]-g(X)$是关于$X$的函数，给定值之后其相当于常数所以有

$$ E[(Y-E[Y|X])(E[Y|X]-g(X))|X]=(E[Y|X]-g(X))E[Y-E[Y|X]|X] $$

注意$E[E[Y|X]|X]$可视为一个随机变量关于$X$的期望，由定理7可得$E[E[Y|X]|X]=E[Y|X]$。所以有

$$ E[Y-E[Y|X]|X]=E[Y|X]-E[Y|X]=0 $$

由此可得

$$ E[(Y-g(X))^2|X] \ge E[(Y-E[Y|X])^2|X] $$

矩母函数

随机变量$X$的矩母函数$M(t)$由下式定义：

$$ M(t)=E[e^{tX}]= \left\{ \begin{aligned} &\sum_xe^txp(x)\quad 离散情形\\ &\int_{-\infty}^\infty e^{tx}f(x)dx \quad 连续情形 \end{aligned} \right. $$

只所以称之为矩母函数，因为$X$的所有各阶矩都可以从$M(t)$的各阶微分中得到。例如

$$ M'(t)=\frac{d}{dt}E[e^{tX}]=E[\frac{d}{dt}e^{tX}]=E[Xe^{tX}] $$

上市有个假定，即微分和期望两个运算可以交换次序。在通常情况下，这个是可以交换的。特别是本书中提到的分布都能满足上述要求。

现在令$t=0$则有$M'(0)=E[X]$。一般地，对$M(t)$求$n$次导数可得

$$ M^n(t)=E[X^ne^{tX}] $$

从而有

$$ M^n(0)=E[X^n] $$

本书中经典的概率分布有如下表：

离散型概率分布

	分布列	矩母函数	均值	方差
二项分布 参数$(n,p),0\lt p\lt 1$	$\binom{n}{x}p^x(1-p)^{n-x}$	$(pe^t+1-p)^n$	$np$	$np(1-p)$
泊松分布 参数$\lambda>0$	$\frac{\lambda^x}{x!}e^{-\lambda}$	$exp\{\lambda(e^t-1)\}$	$\lambda$	$\lambda$
几何分布 参数$0\le p\le 1$	$p(1-p)^{x-1}$	$\frac{pe^t}{1-(1-p)e^t}$	$\frac{1}{p}$	$\frac{1-p}{p^2}$
负二项分布 参数$r,p,0\le p\le 1$	$\binom{n-1}{r-1}p^r(1-p)^{n-r}$	$[\frac{pe^t}{1-(1-p)e^t}]^r$	$\frac{r}{p}$	$\frac{r(1-p)}{p^2}$

连续型概率分布

	分布列	矩母函数	均值	方差
$(a,b)$上均匀分布	$f(x)=\begin{cases}\frac{1}{b-a} \quad a\lt x\lt b\\0\quad other\end{cases}$	$\frac{e^{tb}-e^{ta}}{t(b-a)}$	$\frac{a+b}{2}$	$\frac{(b-a)^2}{12}$
指数分布	$f(x)=\begin{cases}\lambda e^{-\lambda x} \quad x\ge 0\\0\quad x\lt 0\end{cases}$	$\frac{\lambda}{\lambda-t}$	$\frac{1}{\lambda}$	$\frac{1}{\lambda^2}$
$\Gamma$分布 参数$(s,\lambda),\lambda>0$	$f(x)=\begin{cases}\frac{\lambda e^{-\lambda x}(\lambda x)^{s-1}}{\Gamma(s)} \quad x\ge 0\\0\quad x\lt 0\end{cases}$	$(\frac{\lambda}{\lambda-t})^s$	$\frac{s}{\lambda}$	$\frac{s}{\lambda^2}$
正态分布 参数$(\mu,\sigma^2)$	$f(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-(x-\mu)^2/2\sigma^2}$	$exp\{\mu t+ \sigma^2t^2/2\}$	$\mu$	$\sigma^2$

矩母函数有个重要性质是，独立随机变量和的矩母函数等于各随机变量各自矩母函数的乘积。换句话说，设$X$和$Y$为相互独立的随机变量，其矩母函数分别为$M_X(t)$和$M_Y(t)$。记$M_{X+Y}(t)$为$X+Y$的矩母函数则：

$$ M_{X+Y}(t)=E[e^{t(X+Y)}]=E[e^{tX}]E[e^{tY}]=M_X(t)M_Y(t) $$