概率与期望

离散概率

基本定义

概率空间$\Omega$:在一个给定问题中可能发生的所有情况.

事件:$\Omega$的一个子集.

基本事件$\omega$:$\Omega$中的单个元素,也可以看作集合大小为$1$的事件.

概率:若$\omega \in \Omega$,我们称它发生的概率为$\Pr ( \omega )$,有$\Pr ( \omega ) \geq 0$且$\sum_{ \omega \in \Omega } \Pr ( \omega ) = 1$.

随机变量:在概率空间的基本事件上定义的函数.

联合分布:如果两个随机变量$X$和$Y$定义在同一个概率空间$\Omega$上,对于每一个在$X$取值范围内的$x$以及在$Y$取值范围内的$y$,我们称$\Pr ( X = x \land Y = y )$为它们的联合分布.

独立:如果对于每一个在$X$取值范围内的$x$以及在$Y$取值范围内的$y$,$\Pr ( X = x \land Y = y ) = \Pr ( X = x ) \times \Pr ( Y = y )$,我们称$X$和$Y$是独立的.

期望(均值)$E X$:我们设概率空间上的随机变量$X$的期望$EX = \sum_{ x \in X ( \Omega ) } x \times \Pr ( X = x ) = \sum_{ w \in \Omega } X ( \omega ) \Pr ( \omega )$.

中位数:我们设概率空间上的随机变量$X$的中位数为满足$\Pr ( X \leq x ) \geq 0 . 5 \land \Pr ( X \geq x ) \geq 0 . 5$的$x \in X ( \Omega )$所组成的集合.

众数:我们设概率空间上的随机变量$X$的众数为满足$\Pr ( X = x ) \geq \Pr ( X = x ‘ ) , \forall x ‘ \in X ( \Omega )$的$x \in X ( \Omega )$所组成的集合.

方差$VX$:我们设概率空间上的随机变量$X$的方差$VX = E ( ( X - EX )^2 )$.

标准差$\sigma$:我们设概率空间上的随机变量$X$的标准差$\sigma = \sqrt{ VX }$.

期望的简单运算

如果$X , Y$是定义在同一个概率空间上的两个随机变量,那么:

1. $E ( X + Y ) = EX + EY$.

2. $E ( \alpha X ) = \alpha EX$.

3. 如果$X$和$Y$互相独立,那么$E ( XY ) = ( EX ) ( EY )$.

上述法则都可以通过期望的定义简单证明.

此外(3)的逆命题不成立.考虑取$X$分别以$\frac{1}{2}$的概率选取$-1$和$1$,取$Y=X^2$,则$E(X)=E(XY)=0$.

方差的简单运算

我们考虑方差的定义式:

$$\begin{aligned} E ( ( X - EX )^2 ) & = E ( X^2 - 2 X ( EX ) + ( EX )^2 ) \\ & = E ( X^2 ) - 2 ( EX ) ( EX ) + ( EX )^2 \\ & = E ( X^2 ) - ( EX )^2 \end{aligned}$$

也即:方差等于随机变量平方的均值减均值的平方.

当$X$和$Y$为独立的随机变量时,我们有:

$$\begin{aligned} V ( X + Y ) & = E ( ( X + Y )^2 ) - ( EX + EY )^2 \\ & = E ( ( X + Y )^2 ) - ( EX )^2 - 2 ( EX ) ( EY ) - ( EY )^2 \end{aligned}$$

而又有:

$$\begin{aligned} E ( ( X + Y )^2 ) & = E ( X^2 + 2 XY + Y^2 ) \\ & = E ( X^2 ) + 2 ( EX ) ( EY ) + E ( Y^2 ) \end{aligned}$$

则:

$$\begin{aligned} V ( X + Y ) & = E ( X^2 ) + 2 ( EX ) ( EY ) + E ( Y^2 ) - ( EX )^2 - 2 ( EX ) ( EY ) - ( EY )^2 \\ & = VX + VY \end{aligned}$$

即:独立随机变量之和的方差等于它们的方差之和.此外显然也有$\mathrm{Var}(X-Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)$.

事实上,容易见到可以定义协方差$\mathrm{Cov}(X,Y)=E(XY)-E(X)E(Y)$.容易见到以下性质:

1. $\mathrm{Cov}(X,X)=\mathrm{Var}(X)$.
2. $\mathrm{Cov}(X,Y)=\mathrm{Cov}(Y,X)$.
3. $\mathrm{Cov}(aX,bY)=ab\mathrm{Cov}(X,Y)$.
4. $\mathrm{Cov}(X_1+X_2,Y)=\mathrm{Cov}(X_1,Y)+\mathrm{Cov}(X_2,Y)$.
5. 若$X,Y$相互独立,则$\mathrm{Cov}(X,Y)=0$.然而逆命题不成立.
6. $\mathrm{Var}(\sum_{i}X_i)=\sum_{i}\sum_j\mathrm{Cov}(X_i,X_j)$.
7. $\mathrm{Var}(X+Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)+2\mathrm{Cov}(X,Y)$.

随机抽样调查

如果我们随机取得了$n$个值$X_1 , X_2 , . . . , X_n$,那么我们可以通过这些值来估计概率空间的期望和方差.

$\hat EX = \cfrac{ \sum_{ i = 1 }^n X_i }{ n }$.

$\hat VX = \cfrac{ \sum_{ i = 1 }^n X_i^2 }{ n - 1 } - \cfrac{ ( \sum_{ i = 1 }^n X_i )^2 }{ n ( n - 1 ) }$.

这里的$\hat VX$似乎与定义不是那么相符.但是它拥有更好的性质:$E ( \hat VX ) = VX$.

证明如下:

$$\begin{aligned} E ( \hat VX ) & = \cfrac{ 1 }{ n - 1 } E ( \sum_{ i = 1 }^n X_i^2 - \cfrac{ 1 }{ n } \sum_{ j = 1 }^n \sum_{ k = 1 }^n X_j X_k ) \\ & = \cfrac{ 1 }{ n - 1 } ( \sum_{ i = 1 }^n E ( X_i^2 ) - \cfrac{ 1 }{ n } \sum_{ i = 1 }^n \sum_{ j = 1 }^n E ( X_i X_j ) ) \\ & = \cfrac{ 1 }{ n - 1 } ( \sum_{ i = 1 }^n E ( X^2 ) - \cfrac{ 1 }{ n } \sum_{ i = 1 }^n \sum_{ j = 1 }^n ( ( EX )^2 [ j \ne k ] + E ( X^2 ) [ j = k ] ) ) \\ & = \cfrac{ 1 }{ n - 1 } ( nE ( X^2 ) - \cfrac{ 1 }{ n } ( nE ( X^2 ) + n ( n - 1 ) ( EX )^2 ) ) \\ & = E ( X^2 ) - ( EX )^2 \\ & = VX \end{aligned}$$

条件概率

已知事件B发生时事件A发生的概率为$P ( A | B ) = \frac{ P ( AB ) }{ P ( B ) } \\$.

贝叶斯公式

贝叶斯公式:如果有$\{ B_i \}$是样本空间的一个划分,即$\forall i , j$,有$B_i \cap B_j = \emptyset$,并且有$\bigcup_{ i = 1 }^n B_i = \Omega$.则有$P ( B_i | A ) = \frac{ P ( AB_i ) }{ P ( A ) } = \frac{ P ( AB_i ) }{ P ( A ) \sum P ( B_j ) } = \frac{ P ( A B_i ) }{ \sum_{ j = 1 }^n P ( A B_j ) } = \frac{ P ( A | B_i ) P ( B_i ) }{ \sum_{ j = 1 }^n P ( A | B_j ) P ( B_j ) } \\$.

简化形式:$P ( B | A ) = \frac{ P ( A | B ) P ( B ) }{ P ( A ) } \\$.

另外,我们考虑设$O ( B ) = \cfrac{ P ( B ) }{ P ( \lnot B ) }$,称$\cfrac{ P ( B | E ) }{ P ( \lnot B | E ) }$为贝叶斯算子,则同理可得:

$$O ( B | E ) = O ( B ) \cfrac{ P ( B | E ) }{ P ( \lnot B | E ) }$$

这个公式更加精准地分开了先验概率和后验概率,也表现了贝叶斯算子对先验概率的改变.

概率生成函数

如果$X$是定义在概率空间$\Omega$上的随机变量,那么它的概率生成函数为$G_X ( z ) = \sum_{ k \geq 0 } \Pr ( X = k ) z^k = E ( z^X )$.

不难发现$G_X ( z )$需要满足的条件:所有系数都非负并且$G_X ( 1 ) = 1$.

我们发现,当我们定义了概率生成函数后,期望和方差都可以使用它来表示:

$$\begin{aligned} EX & = G_X ' ( 1 ) \\ E ( X^2 ) & = G ' '_X ( 1 ) + G_X ' ( 1 ) \\ VX & = G_X ' ' ( 1 ) + G_X ' ( 1 ) - ( G_X ' ( 1 ) )^2 \end{aligned}$$

通常,我们也可以将方差和均值的定义扩展到任意函数上,于是我们定义:

$$\begin{aligned} Mean ( G ) & = G ' ( 1 ) \\ Var ( G ) & = G ' ' ( 1 ) + G ' ( 1 ) - ( G ' ( 1 ) )^2 \end{aligned}$$

不过,求导的过程可能会有些麻烦,但我们可以直接使用泰勒定理:

$$G ( 1 + t ) = \sum_{ i \geq 0 } \cfrac{ G^{ ( i ) } ( 1 ) }{ i ! } t^i$$

另外,我们不难发现:$G_{ X + Y } ( z ) = G_X ( z ) G_Y ( z )$.

根据前面的推导,我们有:

$$\begin{aligned} Mean ( G_{ X + Y } ) & = Mean ( G_X ) + Mean ( G_Y ) \\ Var ( G_{ X + Y } ) & = Var ( G_X ) + Var ( G_Y ) \end{aligned}$$

换句话说,若$G_X ( 1 ) = 1 , G_Y ( 1 ) = 1$,那么这个式子与直接对$G_{ X + Y }$使用求导的那个公式是等价的.注意,这里并没有要求这些生成函数的系数是非负的.

于是我们有了另一个法则:

$$\begin{aligned} Mean ( G_X ) & = Mean ( G_{ X + Y } ) - Mean ( G_Y ) \\ Var ( G_X ) & = Var ( G_{ X + Y } ) - Var ( G_Y ) \end{aligned}$$

Example1

一枚硬币正面向上的概率为$p$,反面向上的概率为$q$,设硬币正面向上为H,反面向上为T,不断抛掷硬币直到抛掷出连续的THTTH为止,求期望次数.

考虑设$N$为所有不包含THTTH的硬币序列的生成函数,$S$为所有只有结尾为THTTH的硬币序列的生成函数,令$H = pz , T = qz$,$1$为空集,我们显然有:

$$\begin{aligned} 1 + N \times ( H + T ) & = N + S \\ N \times THTTH & = S + S \times TTH \end{aligned}$$

解方程即可.

另外不难发现,这种方法取决于字符串的所有border,显然是通用方法.

我们考虑扩展这个方法,设$A$是我们要找到的字符串,$m$是它的长度,令$A^{ ( k ) }$表示$A$字符串的前$k$个字符所组成的字符串,$A_{ ( k ) }$表示$A$字符串的后$k$个字符所组成的字符串.这样的形式与$k$阶导的形式可能会起冲突,但至少在接下来我们的式子中不会出现导数(好吧其实是因为《具体数学》上就这么写的我也懒得改了).

我们的方程将会变为:

$$\begin{aligned} 1 + N ( H + T ) & = N + S \\ N \times A & = S ( \sum_{ k = 0 }^{ m - 1 } A^{ ( k ) } [ A^{ ( m - k ) } = A_{ ( m - k ) } ] ) \end{aligned}$$

如果我们设$\tilde{ A }$为将字符串$A$中的H替换成$\cfrac{ 1 }{ p } z$,T替换成$\cfrac{ 1 }{ q } z$之后的值,那么显然有:

$$\begin{aligned} N \times A & = A \times S \times ( \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ] ) \\ N & = S \times ( \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ] ) \\ \cfrac{ S - 1 }{ H + T - 1 } & = S \times ( \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ] ) \\ S \times ( 1 + ( 1 - H - T ) \times ( \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } & = A_{ ( k ) } ] ) ) = 1 \end{aligned}$$

这显然是一个卷积的形式.

令$w = \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ]$.

令$H ( z ) = 1$,$F ( z ) = ( 1 + ( 1 - z ) \times w )$,$G ( z ) = S$.

那么我们显然可以直接求$G ( z )$的期望和方差,事实上:

$$\begin{aligned} EX & = \sum_{ k = 1 }^{ m } \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ] \\ VX & = ( EX )^2 - \sum_{ k = 1 }^m ( 2 k - 1 ) \tilde{ A }_{ ( k ) } [ A^{ ( k ) } = A_{ ( k ) } ] \end{aligned}$$

如果硬币是均匀的($p = q = \cfrac{ 1 }{ 2 }$)我们引入另一个符号:我们设$A : A = \sum_{ k = 1 }^m 2^{ k } [ A^{ ( k ) } = A_{ ( k ) } ]$.那么显然期望需要的抛硬币次数就是$( A : A )$.

Example2(Penney游戏)

一枚均匀硬币,设硬币正面向上为H,反面向上为T.不断扔硬币直到扔出连续的HHT或HTT为止,求最后以HHT结尾的概率.

我们设$S_A$为所有以HHT结尾的硬币序列的生成函数,设$S_B$为所有以HTT结尾的硬币序列的生成函数.$N$为其它的硬币序列的生成函数,令$H = T = 0 . 5 z$.

我们显然有:

$$\begin{aligned} 1 + N ( H + T ) & = N + S_A + S_B \\ N \times HHT & = S_A \\ N \times HTT & = S_A \times T + S_B \end{aligned}$$

解方程并带入$z = 1$,可以有得知以HHT结尾的概率为$\cfrac{ 2 }{ 3 }$.

事实上,我们使用类似Example1的方法,设这两个硬币序列分别为$A$和$B$,那么可以求出:

$$\cfrac{ S_A }{ S_B } = \cfrac{ B : B - B : A }{ A : A - A : B }$$

Example3([SDOI2017] 硬币游戏)

是Example2的超级加强版.

把上面的东西给形式化一下,不妨设$g_i$表示进行了$i$步还未结束的概率,$f_{ k , i }$为进行了$i$步恰好第$k$个人胜利的概率,$F , G$是它们的生成函数,我们自然有:

1. $1 + xG ( x ) = \sum_k F_k ( x ) + G ( x )$.

2. $( \frac{ 1 }{ 2 } x )^L G ( x ) = \sum_{ j = 1 }^n F_j ( x ) \sum_{ i = 0 }^{ L - 1 } ( \frac{ 1 }{ 2 } x )^i [ A_k^{ ( L - i ) } ={ A_j }_{ ( L - i ) } ]$.

第一个式子的用处在于带入$x = 1$,发现$\sum_{ k } F_k ( 1 ) = 1$.

把(2)化简一下,有:

$$\begin{aligned} x^L G ( x ) & = \sum_{ j = 1 }^n F_j ( x ) \sum_{ i = 0 }^{ L - 1 } ( \frac{ 1 }{ 2 } x )^{ i - L } [ A_k^{ ( L - i ) } ={ A_j }_{ ( L - i ) } ] \\ x^L G ( x ) & = \sum_{ j = 1 }^n F_j ( x ) \sum_{ i = 1 }^{ L } ( \frac{ 1 }{ 2 } x )^{ - i } [ A_k^{ ( i ) } ={ A_j }_{ ( i ) } ] \end{aligned}$$

带入$x = 1$,有:

$$G ( 1 ) = \sum_{ j = 1 }^n F_j ( 1 ) \sum_{ i = 1 }^{ L } 2^i [ A_k^{ ( i ) } ={ A_j }_{ ( i ) } ]$$

不难发现对于不同的$k$,(2)的右边不同,而左边一定相同,这样就给出了$n$个等式,算上(1)一共有$n + 1$个等式,可以算出$G ( 1 ) , F_{ 1 \cdots n } ( 1 )$这$n + 1$个未知数.

二项式分布

现在有一个大小为$n + 1$的概率空间,其中$\Pr ( \omega_k ) = \binom{ n }{ k } p^k q^{ n - k } \\$,我们把这样的概率序列称为二项式分布.

如果我们令$H ( z ) = q + pz$,不难发现二项式分布的生成函数为$H ( z )^n$.

不难发现,满足二项式分布的随机变量的均值是$np$,方差是$npq$.

与二项式分布相对应的还有负二项式分布,它的生成函数形如:$G ( z )^n = ( \cfrac{ p }{ 1 - qz } )^n = \sum_{ k } \binom{ n + k - 1 }{ k } p^n q^k z^k$.

我们考虑如何求$G ( z )$的方差和均值,不妨设$F ( z ) = \cfrac{ 1 - qz }{ p } = \cfrac{ 1 }{ p } - \cfrac{ q }{ p } z$,则$G ( z )^n = F ( z )^{ - n }$.

不难发现$F ( z )$满足二项式分布.也就是说,以$( n , p , q )$为参数的负二项式分布也就是以$( - n , - \cfrac{ q }{ p } , \cfrac{ 1 }{ p } )$为参数的二项式分布.

模型

树上随机游走

随机游走指每次从相邻的点中随机选一个走过去， 重复这样的过程若干次.

Example1

给一棵所有边长都为$1$的$n$个点的树,问所有点对$( i , j ) ( 1 \leq i , j \leq n )$中,从$i$走到$j$的期望距离的最大值是多少.

由于树上简单路径唯一,我们考虑设$f_u$表示$u$随机走到它父亲的期望,$g_v$表示$v$的父亲(假设是$u$)走到$v$的期望.

对于$f_u$,我们有:

$$\begin{aligned} f_u & = \cfrac{ \sum_{ u \rightarrow v } ( f_v + f_u ) }{ \deg_u } + 1 \\ f_u & = \deg_u + \sum_{ u \rightarrow v } f_v \end{aligned}$$

对于$g_v$,我们有:

$$\begin{aligned} g_v & = \cfrac{ g_u + g_v + \sum_{ u \rightarrow w , w \ne v } ( g_v + f_w ) }{ \deg_u } + 1 \\ g_v & = g_u + \sum_{ u \rightarrow w , w \ne v } f_w + \deg_u \end{aligned}$$

Example2

给出一棵$n$个节点的树,每个点有可能是黑白两种颜色的一种.

现在从$1$号点开始随机游走(即走这个点的每条出边的概率是相同的),每到一个点,如果这个点是黑点,或者这是白点并且这个点第一次经过,那么答案$+ 1$.当走到度数为$1$的节点时游走停止.

注意到黑白点对答案的贡献是互相独立的,所以分开讨论:

如果只有黑点,那么显然答案就是路径的期望长度,我们设$f_u$表示以$u$为起点的路径的期望长度,不难注意到$f_{ leaf } = 1$且$f_u = 1 + \cfrac{ 1 }{ \deg_u } \sum_{ u \rightarrow v \lor v \rightarrow u } f_v$.这个dp转移显然是有后效性的,可以使用高斯消元做,但有一个经典做法:我们求得$f_u = k_u f_{ fa } + b_u$,然后就可以采取带入化简的方法做了.

如果只有白点,考虑每个点只会贡献一次,所以我们要求出的就是每个点被走到的概率.注意到一个点被走到一定是从它父亲走来的,于是我们需要求出$g_v$表示从$v$的父亲(假设是$u$)走到$v$的概率,再令$f_u$表示从$u$走到父亲的概率,类似Example1,我们有:

$$\begin{aligned} f_u & = \cfrac{ 1 }{ \deg_u } ( 1 + \sum_{ u \rightarrow v } f_v f_u ) \\ g_v & = \cfrac{ 1 }{ \deg_u } ( 1 + g_v g_u + \sum_{ u \rightarrow w , w \ne v } f_w g_v ) \end{aligned}$$

最后把两部分答案合起来就好.

计数与期望的转换

Example(CodeChef Secplayer)

冷静一下,如果我们直接计数的话会发现巨大难做,因为项太多了,直接乘起来也太麻烦了.

这启发我们:当我们注意到一个计数题的各种情况相乘很麻烦的时候,我们不妨只考虑一种情况并计算期望,然后拿期望和总数反推计数.注意到权值最小的人最危险,他不能和其他任何一个人匹配到,不然就死了.那不难求得此时他作为次大值存活的概率为$\frac{ 1 }{ \binom{ n }{ 2 } }$.

把所有人权值从大到小排序,设$f_i$表示只考虑前$i$个人的时候的期望,不难发现:$f_{ i } = \frac{ 1 }{ \binom{ i }{ 2 } } v_i + ( 1 - \frac{ 1 }{ \binom{ i }{ 2 } } ) f_{ i - 1 }$.

一些小技巧

Example1(CF865C)

首先写出转移式子,但是存在后效性.如果我们设$f_{ i , j }$表示过了$i$关,花费为$j$的期望,不难发现所有的$f$都需要与$f_{ 0 , 0 }$取$\min$,这咋办?

我们考虑二分这个$f_{ 0 , 0 }$,做的时候直接取$\min$,这样最后还会求出一个$f_{ 0 , 0 }$,比较一下大小然后继续做二分.

等一下,为撒子这样是收敛的呢?

首先,根据这个题,期望肯定是存在的.

我们注意到我们一开始二分的$f_{ 0 , 0 }$越大,最后的答案就越大,但是增长的一定会变慢.换句话说,最后的答案关于我们二分的值的关系应该是一个上凸的函数(增长的时候会被取$\min$的另一项限制住,但原本应该是没被限制的),于是这个时候得到的答案如果比二分的答案更小,那我们就应该调小一点.

换句话说,当我们二分答案的时候,应该判断函数凸性.wqs二分也是这个道理:二分答案并判断答案是否满足条件.

Example2(猎人杀)

先做一步转化:如果做期望的时候,会有一些操作变得不能做,那我们改为:先随便选,如果选到不合法的操作就跳过,概率和期望都不会变.

offline

Example3(AGC019F)

人类智慧题…

首先注意到策略显然是每次选剩下最多的答案.

我们画一张$n \times m$的图(假设$n \geq m$),其中格点$( a , b )$表示现在还剩$a$个Yes,$b$个No.我们再把我们的策略用图上的有向边表示.我们先考虑转化为计数问题,那答案显然就是所有从$( n , m )$走到$( 0 , 0 )$的路径与我们图上有向边的交的大小总和.

然后咧?

我们注意到这张图长得太规律了,换句话说,如果我们把图的左半部分沿着直线$y = x$翻折(路径也跟着翻折),注意到对着这张图做仍然是一样的!

所以呢?由于从$( n , m )$走到$( 0 , 0 )$一定会经过$n$条有向边,所以期望贡献一定要加上一个$n$.而如果我走到了直线$y = x$上,那接下来的贡献是$\frac{ 1 }{ 2 }$.我们只需要枚举一下走到了多少次即可.

一些不等式

Union Bound

即:$\mathbb{P} [ \bigcup_i X_i ] \leq \sum \mathbb P [ X_i ]$,取等当且仅当所有$X_i$互斥.

Markov 不等式

若$X \geq 0$,则$\mathbb{P} [ X \geq t \mathbb{ E } [ X ] ] \leq \frac{ 1 }{ t }$.

显然,多的太多的话就会超过$E$.

Chebyshev 不等式

当$\sigma(X)>0$时,有

$$\mathbb{P}(|X-\mathbb{E}(X)|\geq c\sdot \sigma(X))\leq \frac{1}{c^2}$$

证明的话直接考虑设$Y=(X-\mathbb E(X))^2$,用Markov不等式得到:

$$\begin{aligned} \mathbb{P}(Y\geq c^2\mathbb E(Y))&\leq \frac{1}{c^2}\\ \mathbb{P}((X-\mathbb E(X))^2\geq c^2\sigma^2(X))&\leq \frac{1}{c^2}\\ \mathbb{P}|(X-\mathbb E(X)|\geq c\sigma(X))&\leq \frac{1}{c^2}\\ \end{aligned}$$

一些离散分布

泊松分布

取二项分布的极限情况.设此时$n=\lambda m$,每个东西有$\frac{1}{m}$的概率选入,则对于一个固定的常数$k$,当$m\to \infty$的时候,$P(X=k)=\frac{1}{k!}\lambda^k e^{-\lambda}$,记作$X\sim \pi(\lambda)$.

欸,虽然我们这里只考虑了$k$某种程度上远小于$m$的存在,但好在大的部分也不会有什么太大影响,因此:

$$\sum_k P(X=k)=1$$

原因是$e^{\lambda}=\sum_k \frac{\lambda^k}{k!}$.

此时来看$\mathbb E(X)$,留神到无非是上面那个东西转移了一下子,因此$\mathbb{E}(X)=\lambda$.

来看$\mathbb{E}(X^2)$,自然有:

$$\begin{aligned} &\sum_k \frac{1}{k!}\lambda^k e^{-\lambda}k^2\\ =&\sum_k \frac{1}{k!}\lambda^k e^{-\lambda}k(k-1)+\sum_k \frac{1}{k!}\lambda^k e^{-\lambda}k\\ =&\lambda^2+\lambda \end{aligned}$$

所以$\sigma^2(X)=\mathbb{E}(X^2)-(\mathbb E(X))^2=\lambda$.

几何分布

伯努利试验中首次发生结果$A$的次数,记作$X\sim \text{G}(p)$.

显然$P(X=k)=p(1-p)^{k-1}$,此外$P(X>n)=(1-p)^n$.

设$f(p)=\sum_{k\geq 1}(1-p)^{k-1}$,则$f(p)=\frac{1}{p}$,$E(X)=-pf’(p)=\frac{1}{p}$,$\sigma^2(X)=\frac{1-p}{p^2}$.

很重要的一个性质是无记忆性.即$P(X>m+n|X>m)=P(X>n)$.

负二项分布

伯努利实验中结果$A$发生$r$次的重复次数.则$P(X=k)=\binom{k-1}{r-1}p^r(1-p)^{k-r}$,记作$X\sim \text{NB}(r,p)$.显然$\text{NB}(1,p)\sim \text{G}(p)$.必然有$E(X)=\frac{r}{p}$.

首先要验证:

$$\begin{aligned} \sum_{k\geq r}P(X=k)&=\sum_{k\geq r}\binom{k-1}{r-1}p^r(1-p)^{k-r}\\ &=\sum_{l\geq 0}\binom{l+r-1}{r-1}p^r(1-p)^l\\ &=\sum_{l\geq 0}\binom{l+r-1}{l}p^r(1-p)^l \end{aligned}$$

而:

$$\begin{aligned} p^{-r}&=(1-(1-p))^{-r}\\ &=\sum_{l\geq 0}\binom{-r}{l}(-1)^l(1-p)^{l}\\ &=\sum_{l\geq 0}\binom{l+r-1}{l}(1-p)^l \end{aligned}$$

连续随机变量

给定随机变量$X$和实数$x$,定义$F(x)=P(X\leq x)$为随机变量$X$的分布函数.

分布函数有如下性质:

1. 有界性:$0\leq F(x)\leq 1$,而且$\lim_{x\to -\infty}F(x)=0,\lim_{x\to +\infty}F(x)=1$.
2. 单调性:$F(x)$单调不减.
3. 右连续:$F(x_0+0)=F(x_0)$.

如果存在一个$f(x)$,使得$F(x)=\int_{-\infty}^x f(x)\mathrm{d}x$,则称$X$是连续随机变量,而$f(x)$是其概率密度函数.它还应当满足以下性质:

1. 非负性:$f(x)\geq 0$.
2. 正则性:$\int_{-\infty}^{+\infty}f(t)\mathrm{d}t=1$.

对于连续随机变量.此时$F$还满足左连续$F(x_0-0)=F(x_0)$.

由此还可以得出连续随机变量在任何一点处取值必然为零,因为$P(a\leq X\leq a)=P(a<X<a)=0$.

由此可以定义期望:当$\int_{-\infty}^{+\infty}f(x)|x|\mathrm{d}x<\infty$,则定义$E(X)=\int_{-\infty}^{+\infty}xf(x)\mathrm{d}x$.注意这里要求的是绝对可积而不是可积.

现在我们来搞定:$P(X\leq E(X))>0$.

策略是反证:如果$P(X\leq E(X))=0$.此时任取一个$\epsilon>0$使得$P(X\leq E(X)+\epsilon)\leq \frac{1}{2}$.

此时$E(X)\geq P(X\geq E(X)+\epsilon)(E(X)+\epsilon)+P(X< E(X)+\epsilon)E(X)>E(X)$,这就矛盾了.

接下来来做Markov不等式,对于非负随机变量$X$,若$E(X)> 0,a>0$,则$P(X\geq aE(X))\leq \frac{1}{a}$.原因是:

$$\begin{aligned} E(X)&=\int_{-\infty}^{+\infty}f(x)x\mathrm{d}x\\ &\geq \int_{aE(X)}^{+\infty}f(x)x\mathrm{d}x\\ &\geq \int_{aE(X)}^{+\infty}f(x)aE(X)\mathrm{d}x\\ &=aE(X)\int_{aE(X)}^{+\infty}f(x)\mathrm{d}x\\ &=aE(X)P(X\geq aE(X)) \end{aligned}$$

此时还可以定义$\mathrm{Var}(X)=E((X-E(X))^2)=E(X^2)-E^2(X)$.

Chebyshev不等式的证明只依赖于Markov不等式,因此在这里也能用.

高斯分布

概率密度函数$f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}$.

除了上述已经提到的性质,它还满足:

1. 对称性:$f(x)=f(-x)$.
2. $f(x)_{\max}=f(0)$.
3. $\lim_{x\to -\infty}f(x)=\lim_{x\to +\infty}f(x)=0$.
4. $E(X)=\int_{-\infty}^{+\infty}f(x)x\mathrm{d}x=0$.
5. $E(X^2)=\int_{-\infty}^{+\infty}f(x)x^2\mathrm{d}x=1$.
6. $\mathrm{Var}(X)=1$.

其中(5)的证明见:

$$\begin{aligned} \int_{-\infty}^{+\infty}f(x)x^2\mathrm{d}x&=\int_{-\infty}^{+\infty}\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}x^2\mathrm{d}x\\ &=\int_{-\infty}^{+\infty}\frac{1}{\sqrt{2\pi}}(-x)\mathrm{d}e^{-\frac{x^2}{2}}\\ &=\frac{1}{\sqrt{2\pi}}(-x)e^{-\frac{x^2}{2}}|_{-\infty}^{+\infty}+\int_{-\infty}^{+\infty}\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}\mathrm{d}x\\ &=1 \end{aligned}$$

还可以对此进行推广,考虑$f(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$,记$X\sim N(\mu,\sigma^2)$.只需取$y=\frac{x-\mu}{\sigma}$,就可以转换回标准正态分布,并且此时$F_Y(y)=F_X(\sigma y+\mu)$.

指数分布

对于$\lambda>0$,定义概率密度函数$f(x)=\begin{cases}\lambda e^{-\lambda x}&x\geq 0\\0&x<0\end{cases}$,记作$x\sim \mathrm{exp}(\lambda)$.其分布函数$f(x)="\begin{cases}1-e^{-\lambda" x}&x>0\\0&X\leq 0\end{cases}$.

它同样也有无记忆性.考虑$P(X>t)=e^{-\lambda t}$,从而$P(X>s+t|X>s)=P(X>t)$.

伽马分布

对于$\alpha>0$,定义伽马函数$\Gamma(\alpha)=\int_0^{+\infty}x^{\alpha-1}e^{-x}\mathrm{d}x$.我们见过很多次这个东西了,请看:

1. $\Gamma(1)=1$.
2. $\Gamma(\frac{1}{2})=\sqrt{\pi}$.
3. $\Gamma(\alpha+1)=\alpha\Gamma(\alpha)$.
4. $\Gamma(n+1)=n!$.
5. $\Gamma(n+\frac{1}{2})=\frac{(2n)!}{4^nn!}\sqrt \pi$.

对于$\lambda,\alpha>0$,定义概率密度函数$f(x)=\begin{cases}\frac{\lambda^\alpha}{\Gamma(\alpha)}x^{\alpha-1}e^{-\lambda x}&x\geq 0\\0&x<0\end{cases}$,称此时$x$符合伽马分布,记作$X\sim \Gamma(\alpha,\lambda)$.

先把正则性验证了吧,令$y=\lambda x$,则$f(x)=\frac{\lambda}{\Gamma(\alpha)}y^{\alpha-1}e^{-y}$,则$f(x)\mathrm{d}x=\frac{1}{\Gamma(\alpha)}y^{\alpha-1}e^{-y}\mathrm{d}y$,于是搞定了.

然后是其期望:

$$\begin{aligned} E(X)&=\int_{0}^{+\infty}xf(x)\mathrm{d}x\\&=\int_0^{+\infty}\frac{1}{\Gamma(\alpha)}y^{\alpha}e^{-y}\frac{\mathrm{d}y}{\lambda}\\ &=\frac{\Gamma(\alpha+1)}{\Gamma(\alpha)\lambda}\\ &=\frac{\alpha}{\lambda} \end{aligned}$$

类似地,$\int_0^{+\infty}x^2f(x)\mathrm{d}x=\frac{\Gamma(\alpha+2)}{\Gamma(\alpha)\lambda^2}$,从而算出$\mathrm{Var}(X)=\frac{\alpha}{\lambda^2}$.显然当$X\sim \Gamma(\alpha,\lambda)$时，$Y=kX\sim \Gamma(\alpha,\frac{\lambda}{k})$.

当$\alpha=1$的时候,我们得到了指数分布$\Gamma(1,\lambda)\sim \mathrm{Exp}(\lambda)$.

另一个特例是,$\alpha=\frac{n}{2},\lambda=\frac{1}{2}$.此时我们称其为自由度为$n$的卡方$\chi^2$分布.记作$\chi^2(n)$,其数学期望为$n$,方差为$2n$.当$n=1$的时候,$f(x)=\sqrt \frac{1}{2\pi x}e^{-\frac{x}{2}}$.

多维离散随机变量

重期望公式

考虑把$E(X|Y)$视作一个$g(Y)$,则$E(E(X|Y))=E(X)$.原因是$E(E(X|Y))=\sum_j P(Y=y_j)E(X|Y=y_j)$.

多维连续随机变量

设$F(x,y)=P(X\leq x\land Y\leq y)$.应该有:

联合分布函数有如下性质:

1. 有界性:$0\leq F(x,y)\leq 1$,而且$\lim_{x\to -\infty}F(x,y)=\lim_{y\to -\infty}F(x,y)=0,\lim_{x,y\to +\infty}F(x,y)=1$.
2. 单调性:当$x_1\leq x_2$时,$F(x_1,y)\leq F(x_2,y)$;当$y_1\leq y_2$时,$F(x,y_1)\leq F(x,y_2)$.
3. 右连续:$F(x_0+0,y)=F(x_0,y)$,$F(x,y_0+0)=F(x,y_0)$.
4. 非负性:$P(a<X\leq b,c<Y\leq d)=F(b,d)-F(a,d)-F(b,c)+F(a,c)\geq 0$.

当$F$连续时,如果能找到函数$f\geq 0$满足$F(x,y)=\int_{-\infty}^x\int_{-\infty}^y f(u,v)\mathrm{d}v\mathrm{d}u$,称$f$为联合密度函数.

接下来来看条件分布函数和条件密度函数,当概率密度函数的确连续时,定义:

$$\begin{aligned} P(X\leq x|Y=y)&=\lim_{\Delta\to +0}P(X\leq x|y\leq Y\leq y+\Delta)\\ &=\lim_{\Delta\to +0}\cfrac{\int_{-\infty}^x\int_{y}^{y+\Delta}f(u,v)\mathrm{d}v\mathrm{d}u}{\int_{y}^{y+\Delta}f_Y(v)\mathrm{d}v}\\ &=\lim_{\Delta\to +0}\cfrac{\int_{-\infty}^x(\frac{1}{\Delta}\int_{y}^{y+\Delta}f(u,v)\mathrm{d}v)\mathrm{d}u}{\frac{1}{\Delta}\int_{y}^{y+\Delta}f_Y(v)\mathrm{d}v}\\ &=\cfrac{\int_{-\infty}^xf(u,y)\mathrm{d}u}{f_Y(y)}\\ &=\int_{-\infty}^x\cfrac{f(u,y)}{f_Y(y)}\mathrm{d}u\\ \end{aligned}$$

其中$f_Y(y)=\int_{-\infty}^{+\infty}f(u,y)\mathrm{d}u$.

当$\forall x,y$都有$f(x,y)=f_X(x)f_Y(y)$,则称$X,Y$相互独立.

容易检验$E(X+Y)=E(X)+E(Y)$,而且当$X,Y$相互独立的时候,$E(XY)=E(X)E(Y)$,于是自然也有$\mathrm{Var}(X\pm Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)$.

二维正态分布

即:

$$f(x,y)=\frac{\exp(-\frac{1}{2(1-\rho^2)}\left(\frac{(x-\mu_1)^2}{\sigma_1^2}+\frac{(y-\mu_2)^2}{\sigma_2^2}-\frac{2\rho(x-\mu_1)(y-\mu_2)}{\sigma_1\sigma_2}\right))}{2\pi \sigma_1\sigma_2\sqrt{1-\rho^2}}$$

现在来验证正则性,取$u=\frac{\frac{x-\mu_1}{\sigma_1}-\rho \frac{y-\mu_2}{\sigma_2}}{\sqrt{1-\rho^2}},v=\frac{y-\mu_2}{\sigma_2}$.而$\left|\frac{\partial(u,v)}{\partial(x,y)}\right|=\sigma_1\sigma_2\sqrt{1-\rho^2}$​.于是:

$$\begin{aligned} &\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}f(x,y)\mathrm{d}x\mathrm{d}y\\ =&\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}\frac{1}{2\pi}\exp\left(-\frac{1}{2}(u^2+v^2)\right)\mathrm{d}u\mathrm{d}v\\ =&1 \end{aligned}$$

此外请看:

$$\begin{aligned} f_X(x)&=\int_{-\infty}^{+\infty}f(x,y)\mathrm{d}y\\ &=\sigma_2\sqrt{1-\rho^2}\int_{-\infty}^{+\infty}f(x,y)\mathrm{d}u\\ &=\frac{1}{\sigma_1\sqrt{2\pi}}\exp\left(-\frac{(x-\mu_1)^2}{2\sigma_1^2}\right) \end{aligned}$$

于是当$X,Y\sim N(\mu_1,\mu_2,\sigma_1^2,\sigma_2^2,\rho)$,则$X\sim N(\mu_1,\sigma_1^2),Y\sim N(\mu_2,\sigma_2^2)$.

此外:

$$\begin{aligned} f(x|y)&=\frac{f(x,y)}{f_Y(y)}\\ &=\frac{1}{\sigma_1\sqrt{2\pi}\sqrt{1-\rho^2}}\exp\left(-\frac{1}{2(1-\rho^2)}\left(\frac{x-\mu_1}{\sigma_1}-\rho\frac{y-\mu_2}{\sigma_2}\right)^2\right) \end{aligned}$$

也就是说,当$Y=y$时,$X\sim N(\mu_1+\rho\frac{\sigma_1}{\sigma_2}(y-\mu_2),\sigma_1^2(1-\rho^2))$,容易见到相互独立当且仅当$\rho=0$.

Example1

设$n\times n$的矩阵$A$中每个元素独立服从$N(0,1)$.求$E(\det A),E(\mathrm{trace}(A)),E(\mathrm{trace}(A^2))$.

考虑$\det A=\sum_{\sigma}\mathrm{sgn}(\sigma)\prod A_{i,\sigma(i)}$.直接套期望就知道$E(\det A)=0$.

显然$E(\mathrm{trace}(A))=0$.

而$E(\mathrm{trace}(A^2))$中,每一个$(A^2)_{i,i}=\sum_{j}E(a_{i,j}a_{j,i})=1$,于是$E(\mathrm{trace}(A^2))=n$.

重期望公式

定义$E(X|Y=y)=\int_{-\infty}^{+\infty}f(x|y)x\mathrm{d}x$.则$E(E(X|Y))=E(X)$.

协方差

和离散时的基本全部一样.其实早该看出来协方差就是一种双线性形式.

Example1

证明二维正态分布的$\mathrm{Cov}(X,Y)=\sigma_1\sigma_2\rho$.

容易见到:

$$\begin{aligned} \mathrm{Cov}(X,Y)&=\int\int f(x,y)(x-\mu_1)(y-\mu_2)\mathrm{d}x\mathrm{d}y\\ &=\int\int\frac{1}{2\pi}\exp\left(-\frac{1}{2}(u^2+v^2)\right)\sigma_1\sigma_2v(u\sqrt{1-\rho^2}+\rho v)\mathrm{d}u\mathrm{d}v \end{aligned}$$

然而:

$$\begin{aligned} \int\int\frac{1}{2\pi}\exp\left(-\frac{1}{2}(u^2+v^2)\right)uv\mathrm{d}u\mathrm{d}v&=0\\ \int\int\frac{1}{2\pi}\exp\left(-\frac{1}{2}(u^2+v^2)\right)v^2\mathrm{d}u\mathrm{d}v&=1\\ \end{aligned}$$

带入得到结果.

相关系数

可以定义相关系数$\mathrm{Corr}(X,Y)=\frac{\mathrm{Cov}(X,Y)}{\sigma(X)\sigma(Y)}$.一个很好玩的事是两个变量的任意线性变换$X’=aX+b$后,仍有:

$$\begin{aligned} \mathrm{Corr}(X',Y)=\frac{a\mathrm{Cov}(X,Y)}{|a|\sigma(X)\sigma(Y)}=\mathrm{sgn}(a)\frac{\mathrm{Cov}(X,Y)}{\sigma(X)\sigma(Y)} \end{aligned}$$

一个显然结论是当标准化后即$\tilde X=\frac{X-E(X)}{\sigma(X)}$后相关系数不变.

此外,我们可以证明以下性质:

1. $|\mathrm{Corr}(X,Y)|\leq 1$.
2. 如果$|\mathrm{Corr}(X,Y)|=1$等价于$Y,X$存在关系$a\ne 0$使得$P(Y=aX+b)=1$.

(1)(2)其实就是柯西不等式对吧,因为$\mathrm{Cov}$其实是某种内积,所以当然有$\frac{\mathrm{Cov}(X,Y)}{\sqrt{\mathrm{Cov}(X,X)\mathrm{Cov}(Y,Y)}}\in [-1,1]$.

协方差矩阵

设随机变量$X=(X_1,\cdots,X_n)$,定义$E(X)=(E(X_1),\cdots,E(X_n))$为其数学期望向量,而$\mathrm{Cov}(X)=E((X-E(X))(X-E(X))^t)$为$X$的协方差矩阵.也就是$\mathrm{Cov}(X)_{i,j}=\mathrm{Cov}(X_i,X_j)$.容易见到其半正定,原因是$\alpha^t\mathrm{Cov}(X)\alpha=E((\alpha^t(X-E(X)))^2)$.

事实上应该总有$\mathrm{Cov}(AX)=A\mathrm{Cov}(X)A^t$,原因是:

$$\mathrm{Cov}(AX)=E((AX-E[AX])(AX-E[AX])^t)$$

Example1

求二维正态分布的协方差矩阵.

显然为:

$$B=\begin{bmatrix} \sigma_1^2&\rho\sigma_1\sigma_2\\ \rho\sigma_1\sigma_2&\sigma_2^2 \end{bmatrix}$$

此外$\det(B)=(1-\rho^2)\sigma_1^2\sigma_2^2$.其逆矩阵$B^{-1}=\frac{1}{1-\rho^2}\begin{bmatrix}\frac{1}{\sigma_1^2}&-\frac{\rho}{\sigma_1\sigma_2}\-\frac{\rho}{\sigma_1\sigma_2}&\frac{1}{\sigma_2^2}\end{bmatrix}$.

此时见到:

$$\begin{aligned} f(x_1,x_2)&=\frac{\exp(-\frac{1}{2(1-\rho^2)}\left(\frac{(x_1-\mu_1)^2}{\sigma_1^2}+\frac{(x_2-\mu_2)^2}{\sigma_2^2}-\frac{2\rho(x_1-\mu_1)(x_2-\mu_2)}{\sigma_1\sigma_2}\right))}{2\pi \sigma_1\sigma_2\sqrt{1-\rho^2}}\\ &=\frac{1}{2\pi\sqrt {\det B}}\exp\left(-\frac{1}{2}(\vec x-\vec \mu)^TB^{-1}(\vec x-\vec \mu)\right) \end{aligned}$$

从而容易推广到任意多维,只需定义:

$$\begin{aligned} f(\vec x) &=\frac{1}{(2\pi)^{\frac{n}{2}}\sqrt {\det B}}\exp\left(-\frac{1}{2}(\vec x-\vec \mu)^TB^{-1}(\vec x-\vec \mu)\right) \end{aligned}$$

Example2

求证:当$\vec X\sim N(\vec \mu,B)$,则$\vec Y=A\vec X+\vec b\sim N(A\vec \mu+\vec b,ABA^t)$,其中$A$必须行满秩.

当$A$是方阵的时候,直接可逆,于是:

$$\begin{aligned} f_Y(y)&=f_X(A^{-1}(y-b))|\frac{\partial x}{\partial y}|\\ &=f_X(A^{-1}(y-b))|\frac{\partial y}{\partial x}|^{-1}\\ &=f_X(A^{-1}(y-b))|\frac{1}{\det A}|\\ &=\frac{1}{(2\pi)^{\frac{n}{2}}\sqrt {\det ABA^{t}}}\exp\left(-\frac{1}{2}(A^{-1}(\vec y-\vec b)-\vec \mu)^TB^{-1}(A^{-1}(\vec y-\vec b)-\vec \mu)\right)\\ &=\frac{1}{(2\pi)^{\frac{n}{2}}\sqrt {\det ABA^{t}}}\exp\left(-\frac{1}{2}(\vec y-A\vec \mu-\vec b)^T(ABA^{T})^{-1}(A^{-1}(\vec y-A\vec \mu-\vec b)\right) \end{aligned}$$

此外,一般的多为高斯分布可以看作独立同分布标准正态分布线性变换后的结果,原因是当$X\sim N(0,I),Y\sim N(\vec \mu,B)$,当然有$Y=B^{\frac{1}{2}}X+\vec \mu$.

特别地,把一个有一定信息关系的东西$Y$变成$X$也只需要$X=B^{-\frac{1}{2}}(X-\vec \mu )$,这个过程一般叫白化.因为信息被缩简单了.

然而,考虑如果$X\sim N(0,I)$,如果$Y=AX$,此时$Y$的结果似乎只和$AA^t$有关,而与$A$竟然无关.特别地,如果$A$是一个正交矩阵,则$Y$干脆和$X$服从同样的分布.

这揭示了正态分布其实更关注于模长,换言之,当$\vec \mu=0,B=I$的时候,$f(\vec y)$其实是只和$\vec y$的模长相关的.此时如果看它的等密度轮廓线其实是一圈又一圈的圆.而拉伸之后就成了某种一圈又一圈的椭圆(因为要拉伸呀).

卷积

若$X,Y$相互独立,考虑$Z=X+Y$,则$f_Z(z)=\int_{-\infty}^{+\infty}f_X(z-y)f_Y(y)\mathrm{d}y$.

熵

离散情况下将熵定义为$H[X]=E(\log \frac{1}{P(X)})=\sum_{i}P_i\log \frac{1}{P_i}$.如果设$|X|=|\{x|P(x)>0\}|$,则容易见到$0\leq H[X]\leq \log|X|$.

接下来我们想定义条件熵,直观的理解是”去掉$X$的信息后$Y$还剩多少信息”:

$$\begin{aligned} H[Y|X]&=\sum_xH[Y|X=x]P[X=x]\\ &=\sum_x\sum_yP(Y=y|X=x)P[X=x]\lg\frac{1}{P(Y=y|X=x)}\\ &=\sum_{x,y}P(Y=y,X=x)\lg\frac{1}{P(Y=y|X=x)}\\ &=E(\lg\frac{1}{P(Y|X)}) \end{aligned}$$

首先检验$f(x)=x\ln x$是下凸函数,原因是$f’(x)=1+\ln x$而$f’’(x)=\frac{1}{x}>0$.于是琴生不等式给出$f(\frac{a+b}{2})\leq \frac{f(a)+f(b)}{2}$,或说$E(f(X))\geq f(E(X))$.

另外一个很重要的工具是对数求和不等式,对于任何非负实数$a_1,\cdots,a_n$和正数$b_1,\cdots,b_n$,记$a=\sum_i a_i,b=\sum_i b_i$,则:

$$\sum_i a_i\log\frac{a_i}{b_i}\geq a\log \frac{a}{b}$$

一个重要的性质是证明其是上凸函数,对于任意分布$P,Q$和$\lambda\in (0,1)$,都有:

$$H[\lambda P+(1-\lambda)Q]\geq \lambda H[P]+(1-\lambda)H[Q]$$

原因是考虑:

$$f(\lambda p_i+(1-\lambda)q_i)\leq \lambda f(p_i)+(1-\lambda)f(q_i)$$

可以见到以下性质:

1. $H[X,Y]=H[X]+H[Y|X]$.
2. $H[X|Y]\leq H[X]$.
3. 作为(2)的推论,互信息$I(X,Y)=H[X]+H[Y]-H[X,Y]=H[X]-H[X|Y]\geq 0$.
4. 对于一个确定性函数$g$,$H[X]\geq H[g(X)]$.
5. $I(X;YZ)=I(X;Z)+I(X;Y|Z)$.
6. $I(X;Y\mid Z)\leq I(X;Y)+H(Z)$.
7. 当$X,Y,Z$满足Markov规则,或者说$P_{X,Y,Z}=P_XP_{Y|X}P_{Z|Y}$,或说$P_{Z|Y}=P_{Z|XY}$,则$I(X;Y)=I(X;Z)+I(X;Y|Z)$.这自然推出$I(X;Y)\geq I(X;Z)$,也即这个过程中信息不会增多.

(1)是上述的一个显然推论.

(2)的话考虑:

$$\begin{aligned} &H[X]-H[X|Y]\\ =&\sum_x\left(P(X=x)\lg \frac{1}{P(X=x)}-\sum_y P(X=x,Y=y)\lg \frac{1}{P(X=x|Y=y)}\right)\\ =&\sum_x\left(\sum_y P(X=x,Y=y)\lg \frac{P(X=x|Y=y)}{P(X=x)}\right)\\ =&\sum_x\sum_y P(X=x,Y=y)\lg \frac{P(X=x,Y=y)}{P(X=x)P(Y=y)}\\ \end{aligned}$$

不妨令$a_i=P(X=x,Y=y),b_i=P(X=x)P(Y=y)$.容易见到$a=\sum_i a_i=1,b=\sum_i b_i=1$.于是上式变为:

$$\begin{aligned} &H[X]-H[X|Y]\\ =&\sum_i a_i\lg \frac{a_i}{b_i}\\ =&-\sum_i a_i\lg \frac{b_i}{a_i}\\ \geq &-\sum_i a_i (\frac{b_i}{a_i}-1)\\ =&-\sum_i (b_i-a_i)\\ =&0 \end{aligned}$$

对于(4),轻易地:

$$\begin{aligned} H[X,g(X)]&=H[g(X)]+H[X|g(X)]\\ H[X]&=H[g(X)]+H[X|g(X)] \end{aligned}$$

然而后者非负,于是显然.特别地,当$g$是一个单射的时候,$H[X]=H[g(X)]$.

对于(5),留神到$H[X]=I(X;Z)+H[X|Z]$,考虑:

$$\begin{aligned} I(X;YZ)&=H[X]-H[X|YZ]\\ &=I(X;Z)+H[X|Z]-H[X|YZ] \end{aligned}$$

然而$I(X;Y\mid Z)=H[X| Z]-H[(X|Y)|Z]=H[X|Z]-H[X|YZ]$.

对于(6),考虑:

$$\begin{aligned} I(X;YZ)&=I(X;Z)+I(X;Y\mid Z)\\ &=I(X;Y)+I(X;Z\mid Y)\\ I(X;Y\mid Z)&=I(X;Y)+I(X;Z\mid Y)-I(X;Z)\\ \end{aligned}$$

然而$I(X;Z\mid Y)=H[Z|Y]-H[X|YZ]\leq H[Z]$,而$I(X;Z)\geq 0$,于是显然.

对于(7),考虑:

$$\begin{aligned} I(X;YZ)&=I(X;Y)+I(X;Z\mid Y)\\ I(X;YZ)&=I(X;Z)+I(X;Y\mid Z)\\ \end{aligned}$$

此外:

$$\begin{aligned} I(X;Y)+I(X;Z\mid Y)&=H[X]-H[X|Y]+H[Z|Y]-H[Z|YX]\\ &=H[X]-H[X|Y]+H[Z|Y]-H[Z|Y]\\ &=I(X;Y) \end{aligned}$$

于是$I(X;Z\mid Y)=0$,这就证毕.

KL散度

定义$D(P||Q)=\sum_x P(x)\lg \frac{P(x)}{Q(x)}$.其中如果$P(x)\ne 0$而$Q(x)=0$的情况出现,我们就说此时其为$+\infty$.我们想要证明:$D(P||Q)\geq 0$.考虑:

$$\begin{aligned} D(P||Q)&=E_{x\sim Q}(\frac{P(X)}{Q(X)}\lg \frac{P(X)}{Q(X)})\\ &\geq f\left(E_{x\sim Q}(\frac{P(X)}{Q(X)})\right)\\ &=f(1)\\ &=0 \end{aligned}$$

从而这的确是某种衡量偏离程度的算子.

此外还应当定义条件KL散度.考察:

$$\begin{aligned} D(P_{X,Z}||Q_{X,Z})&=\sum_{(x,z)} P_{X,Z}(x,z)\log \frac{P_{X,Z}(x,z)}{Q_{X,Z}(x,z)}\\ &=\sum_{(x,z)} P_{Z|X}(z|x)P_{X}(x)\log \frac{P_{Z|X}(z|x)P_{X}(x)}{Q_{Z|X}(z|x)Q_{X}(x)}\\ &=D(P_X||Q_X)+\sum_{(x,z)} P_{Z|X}(z|x)P_{X}(x)\log \frac{P_{Z|X}(z|x)}{Q_{Z|X}(z|x)}\\ \end{aligned}$$

将后面的部分定义为$D(P_{Y|X}||Q_{Y|X}\mid P_X)$.顺便应该有$D(P_{X,Z}||Q_{X,Z})\geq D(P_X||Q_X)$.

此外还应当证明KL散度凸性.对于概率分布对$(P_1,Q_1),(P_2,Q_2)$,以及任意$\theta\in [0,1]$,令$P=\theta P_1+(1-\theta)P_2,Q=\theta Q_1+(1-\theta)Q_2$.下面我们证明下凸:

$$D(P||Q)\leq \theta D(P_1||Q_1)+(1-\theta)D(P_2||Q_2)$$

此外,有趣的性质是证明$I(X;Y)=D(P_{XY}||P_XP_Y)$,不过这个只需简单转化即可.

另外,对任意$P_X,Q_X$和kernel$P_{Y|X}$,令$P_Y=P_X\circ P_{Y|X}$,$Q_Y=Q_X\circ P_{Y|X}$. 散度的data-processing不等式给出:$D(P_X||Q_X)\geq D(P_Y||Q_Y)$.

Example1

求证$d(p||q)=D(\mathrm{Bern}(p)||\mathrm{Bern}(q))\geq (2\log e)(p-q)^2$.

具体来说,$d(p||q)=p\log \frac{p}{q}+(1-p)\log \frac{1-p}{1-q }$.

编码

一般无损编码

考虑一个编码-解码过程,要求编码器Encode是一个到$\{0,1\}^*$的单射,从而存在其的一个左逆Decode满足$\text{Decode}(\text{Encode}(x))=x $.

对于编码,我们非常在意的是它的长度.考虑设$L(X)=\text{len}(\text{Encode}(X))$,我们下面将会估计$E(L(X))$的大小.

首先证明其下界,我们断言:

$$H(X)-H(L)\leq E[L(X)]$$

由于$H(X)-H(L)=H(X|L)$,因此其实只需要证明$H(X|L)\leq E[L]$.由于该编码无损,不妨设$n(l)$为满足$L(x)=l$的数量,容易见到$n(l)\leq 2^l$,立刻有$H(X|L=l)=\log_2 n(l)\leq l$.于是:

$$H(X|L)=\sum_l P(L=l)H(X|L=l)\leq \sum_{l}P(L=l)l=E[L]$$

此外我们还想要估计$H(L)$具体有多大,事实上:

$$H(L)\leq \log_2(e(1+E[L]))$$

下面来看一种比较优秀的编码方式.不妨假设$P(x_1)\geq P(x_2)\geq \cdots$,于是自然有$P(x_i)\geq \frac{1}{i}$.取码长$L(x_i)=\lfloor \log_2i\rfloor$.其实就是按照出现的频率用小码,则:

$$\begin{aligned} E[L(X)]&=\sum_i P(x_i)\lfloor \log_2 i\rfloor\\ &\leq \sum_i P(x_i)\log_2 i\\ &\leq \sum_i P(x_i)\log_2 \frac{1}{P(x_i)}\\ &=H(X) \end{aligned}$$

前缀码

一个更合适的例子是前缀码,对于一个$L(X)$函数,我们声称存在前缀码$f$使得$|f(x_i)|=L(x_i)$,当且仅当$\sum_{x\in A}2^{-L(x)}\leq 1$,原因是在二叉树上表示一下.

众所周知Huffman编码是最优编码,现在我们来看它为什么优秀,我们说其满足$H(X)\leq E[L(X)]\leq H(X)+1$,下面我们来证明这个结论.

先证上界,由于Huffman编码是最优编码,我们只要选取任意一个编码,使得它的界$\leq H(X)+1$即可.根据上面的引理,我们直接将$x$映射到一个长度为$\lceil \log \frac{1}{P(x)}\rceil$的前缀编码.此时:

$$\begin{aligned} E(L(X))&=\sum_{x}P(x)\lceil \log \frac{1}{P(x)}\rceil\\ &\leq \sum_{x}P(x)\left(\log \frac{1}{P(x)}+1\right)\\ &=H(X)+1 \end{aligned}$$

再来看下界.来证明任意前缀编码都会被这个下界控制住.

对于一个前缀编码,实际上是把$X$映射到了另一个$Y$处.由于这是一个单射,所以有$H(X)=H(Y)$.然而:

$$\begin{aligned} H(Y)&=\sum_{t}H(Y_t|Y_{1}\cdots Y_{t-1})\\ \end{aligned}$$

来看一个特定的$H(Y_t|Y_1\cdots Y_{t-1}=y_1\cdots y_{t-1})$,如果此时$y_1\cdots y_{t-1}$已经能解码了,那$Y_t$就一定是空白,因此此时熵为$0$;反之,则$Y_t$要么是$0$要么是$1$,伯努利分布的最大值只有$\log_2 2=1$.因此我们可以发现,对于一个特定的$x$和对应的$y_1\cdots y_k$,一定有$H(Y_t|Y_1\cdots Y_{t-1}=y_1\cdots y_{t-1})\leq Pr[L(x)\geq t]$.

所以实际上$H(Y)\leq \sum_t Pr[L(X)\geq t]=E(L)$.

几乎无损压缩

对于独立同分布$X^n$,如果满足:

$$Pr[\text{Decode}(\text{Encode}(X^n))=X^n]\geq 1-\epsilon,\epsilon\to 0$$

则称其为几乎无损压缩.不妨记录$\vec X\sim X^n$.

现在我们来看做到几乎无损压缩需要怎么办.我们将说明几乎就一定需要$nH(X)$左右的信息长度才足够.事实上:

1. $\forall \delta>0$,存在编码方案使得$L\leq n(H(X)+\delta)$,并且错误概率趋近于$0$.
2. $\forall \delta>0$,如果$L<n(H(X)-\delta)$,则无论怎么编码,错误概率趋近于$1$.

先来证明(1),考虑直接取$L=n(H(X)+\delta)$,并且编码出现概率最大的前$2^L$个元素,剩下的扔掉.不妨可以发现我们只会扔掉所有$P(\vec X)\leq 2^{-n(H(X)+\delta)}$的,原因是比这个阈值大的不可能超过$2^L$个.然而留意到$P(\vec X=(x_1,\cdots,x_n))=\prod_i P(X=x_i)$:

$$\begin{aligned} Pr[P(\vec X)\leq 2^{-n(H(X)+\delta)}]&=Pr[-\log_2P(\vec X)\geq n(H(X)+\delta)]\\ &=Pr[-\sum_i\log_2P(X_i)\geq n(H(X)+\delta)]\\ \end{aligned}$$

可是$\sum_i -\log_2 P(X_i)$的期望恰好为$H(X)$,因此根据Chernoff-Hoeffding Bound,这个错误概率$\leq e^{-O(n\delta^2)}$.

那么反过来的界怎么证明呢?此时最多可编码$2^{n(H(X)-\delta)}$个元素.仍然用Chernoff Bound就可以搞定了.

通用压缩

我们上面的所有讨论都基于已知分布的情况.如果我们不知道分布,又能做到多好的编码呢?

当编码的时候不知道分布,但解码的时候知道分布的时候,事实上可以做到:$\varlimsup_{n\to \infty}\frac{1}{n}E[L_n(X^n)]\leq H(X)+\epsilon$,其中$\epsilon$可以任意小.

这个怎么做呢?考虑一个暴力方法,我先随便将信息映射到$\{0,1\}^L$.此时的Encode并非单射.解码的时候直接最大似然估计找最好的那个解码.

假设$x_i\to c_i$,并且$P(x_1)\geq P(x_2)\geq \cdots$,取一个阈值$M=2^{n(H(X)+\delta)}$,以及$L=n(H(X)+2\delta)$现在来看失败概率也就是:

$$\begin{aligned} &\sum_{i} P(x_i)Pr[c_i\in \{c_1,\cdots,c_{i-1}\}]\\ =&\sum_{i=1}^M P(x_i)Pr[c_i\in \{c_1,\cdots,c_{i-1}\}]+\sum_{i\geq M} P(x_i)Pr[c_i\in \{c_1,\cdots,c_{i-1}\}]\\ \leq &\sum_{i=1}^M P(x_i)\frac{M}{2^L}+2^{-O(n\delta^2)}\\ \leq &2^{-O(n\delta)}+2^{-O(n\delta^2)}\\ \end{aligned}$$

这个错误概率就很小了.

信道编码

定义信道为某种会”污染”信息的东西,或者干脆写称条件概率分布$P_{Y|X}$.此外定义信道容量$C=\max_{P_X}I(X;Y)$,其中$(X,Y)\sim P_XP_{Y|X}$.

现在我们考虑一个一般的信道编码,取$W\to \vec X\in \mathcal{X}^L\to \vec Y\in \mathcal{Y}^L\to \hat W$.

现在我们来证明以下性质:

1. $I(\vec X;\vec Y)\leq L\sdot C$
2. data-processing不等式:$I(W;\hat W)\leq I(\vec X;\vec Y)$

对于(1),由于$Y_i$独立地依赖于$X_i$,考虑:

$$\begin{aligned} I(\vec X;\vec Y)&=\sum_i I(\vec X;Y_i\mid Y_1\cdots Y_{i-1})\\ &=\sum_i I(X_i;Y_i)\\ &\leq L\sdot C \end{aligned}$$

至于(2),实际上是互信息的data-processing不等式.

接下来我们要搞定传送速率的问题.不妨设$n=H(W)$,现在我们将要证明:

$$n\leq\frac{LC+H(\epsilon)}{1-\epsilon}$$

其中$\epsilon$是可接受的最大错误概率,定义为$\epsilon=\max_w Pr[\hat W\ne W|W=w]$.

怎么证明呢?考虑取一个指示变量$Z$,当$\hat W\ne W$的时候$Z=1$,否则$Z=0$.不妨直接让$Z$多错一点,到达$Pr[Z=1|W=w]\equiv \epsilon$以方便我们下面的分析.这样的话$Z$和$W$就独立了.此时立刻见到:

$$(1-\epsilon)I(W;\hat W\mid Z=0)\leq I(W;\hat W\mid Z)\leq I(W;\hat W)+H(Z)$$

而$I(W;\hat W\mid Z=0)=I(W;W)=H(W)=n$.

极限的情况

尾不等式

留神到如果事件在$n$次中发生了$n_a$次,其实是不能说$\lim_{n\to \infty}\frac{n_a}{n}=P$的.因为后面总是会有微小的扰动.但似乎总能刻画这些微小扰动的代价.

设$f_n(A)=\frac{n_a}{n}$.如果我们能求出$P(|f_n-p|\geq \epsilon)=P(|n_a-E(n_a)|\geq n\epsilon)$的上界,看上去就会非常优秀.进一步地:

1. 尾不等式:给出$P(X\geq k)$的上界.
2. 集中不等式:给出$P(|X-E(X)|\geq k)$的上界.

Example1

对二项分布用Chebyshev不等式,轻易有:

$$P(|n_A-E(n_A)|\geq n\epsilon)\leq \frac{p(1-p)}{n\epsilon^2}$$

这个估计有点菜,右侧是$O(\frac{1}{n})$的,这个趋近也太慢了.

考虑一下它为什么菜,问题在于Chebyshev不等式只用到了”两两独立”这件事,但是实际上二项分布更强一点,它其实是”互相独立”的.

矩

定义$E(X^k)$为$X$的$k$阶原点矩,而将$E((X-E(X))^k)$称为$X$的$k$阶中心距.则期望是其一阶原点矩而方差是二阶中心矩.

对于随机变量$X$,定义$M_X(t)=E(e^{tX})$为$X$的矩生成函数.考虑:

$$\begin{aligned} E(e^{Xt})&=\sum_{k=0}^ne^{kt}P(X=k)\\ &=\sum_{k=0}^nP(X=k)\left(\sum_{j=0}^{+\infty}\frac{(kt)^j}{j!}\right)\\ &=\sum_{j=0}^{\infty}\frac{t^j}{j!}\sum_{k=0}^nP(X=k)k^j\\ &=\sum_{j=0}^\infty \frac{t^j}{j!}E(X^j) \end{aligned}$$

Example2

对$X\sim B(n,p)$,求$E((X-E(X))^4)$.

考虑其矩生成函数:

$$\begin{aligned} E(e^{Xt})&=\sum_{k=0}^ne^{kt}P(X=k)\\ &=\sum_{k=0}^ne^{kt}\binom{n}{k}p^k(1-p)^{n-k}\\ &=\sum_{k=0}^n\binom{n}{k}(pe^{t})^k(1-p)^{n-k}\\ &=(pe^t+(1-p))^n\\ &=(1+p(e^t-1))^n \end{aligned}$$

令$Y=X-E(X)$,则$E(e^{Yt})=E(e^{Xt})e^{-tpn}$,现在我们可以对其求四次导数得到:

$$E((X-E(X))^4)=np(1-p)^4+n(1-p)p^4+3n(n-1)p^2(1-p^2)$$

那这个有什么用呢?考虑对其用Markov不等式:

$$P((X-E(X))^4\geq (n\epsilon)^4)\leq \frac{O(n^2)}{(n\epsilon)^4}=O(\frac{1}{n^2\epsilon^4})$$

这的确给出了一个更好的估计.

但是再做六阶矩好像也很痛苦,而且这只能给出一个多项式估计,但看着这个逼近速度就不太可能是多项式估计,那怎么办呢?

Chernoff Bound

考虑直接对$e^{tX}$用Markov不等式:

1. 当$t>0$的时候,有$P(X\geq k)\leq M_X(t)e^{-tk}$.
2. 当$t<0$的时候,有$P(X\leq k)\leq M_X(t)e^{-tk}$.

左侧没有$t$而右侧有,那看上去只要找到能使右侧取到最小值的$t$就万事大吉了.

Example1

当$X\sim \pi(\lambda)$的时候,求$P(X\geq x)$的上界.其中$x>\lambda$.

先求此时的矩生成函数:

$$\begin{aligned} E(e^{Xt})&=e^{-\lambda}\sum_{k\geq 0}\frac{\lambda^k}{k!}e^{kt}\\ &=e^{-\lambda}\sum_{k\geq 0}\frac{(\lambda e^t)^k}{k!}\\ &=e^{\lambda (e^t-1)} \end{aligned}$$

当$t>0$的时候,我们想要优化$e^{\lambda(e^t-1)-tx}$的最小值,直接对$t$求导,发现当$t=\ln\frac{x}{\lambda}$时最小.

此时:

$$P(X\geq x)\leq \frac{e^{-\lambda}(e\lambda)^x}{x^x}$$

Example2

当$X\sim N(\mu,\sigma^2)$,求$P(X-E(X)\geq k\sigma)$的上界.

还是求矩生成函数,考虑:

$$E(e^{tX})=\int_{-\infty}^{+\infty}\frac{1}{\sqrt {2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}+tx}=e^{\mu t+\frac{\sigma^2t^2}{2}}$$

从而:

$$P(X\geq k\sigma+\mu)\leq e^{\mu t+\frac{\sigma^2t^2}{2}}e^{-t(\mu+k\sigma)}=e^{\frac{\sigma^2t^2}{2}-k\sigma t}$$

当$t=\frac{k}{\sigma}$的时候取最小值,从而最后的界是$e^{-\frac{k^2}{2}}$.

Example3

当$X\sim B(n,p)$,求$P(X-E(X)\geq n\epsilon)$的上界.

考虑$M_X(t)=(1-p+pe^t)^n$.

然后需要一个Lemma,我们说$(1-p)e^{-tp}+pe^{t(1-p)}\leq e^{\frac{t^2}{8}}$,这个会在后面的Hoeffding引理证明.

直接带入,右侧为:

$$\begin{aligned} M_X(t)e^{-t(E(X)+n\epsilon)}&=e^{-tn\epsilon}\left((1-p)e^{-tp}+pe^{t(1-p)}\right)^n\\ &\leq e^{-tn\epsilon+\frac{nt^2}{8}} \end{aligned}$$

取$t=4\epsilon$得到$e^{-2n\epsilon^2}$的上界.

此外取$t=-4\epsilon$得到$P(X-E(X)\leq -n\epsilon)$的上界为$e^{-2n\epsilon^2}$.

于是我们有$P(|X-E(X)|\geq n\epsilon)\leq 2e^{-2n\epsilon^2}$.

Hoeffding引理

若实数随机变量$a\leq X\leq b$,则$M_{X-E(X)}(t)=E(e^{t(X-E(X))})\leq e^{\frac{t^2(b-a)^2}{8}}$.

Example1(Chernoff-Hoeffding不等式)

若$X=\sum_{i=1}^n X_i$,其中$X_i$相互独立且$a\leq X_i\leq b$.则($k> 0$):

1. $P(X\geq E(X)+k)\leq e^{-\frac{2k^2}{n(b-a)^2}}$.
2. $P(X\leq E(X)-k)\leq e^{-\frac{2k^2}{n(b-a)^2}}$.

怎么证明呢,考虑$P(X\geq E(X)+k)\leq M_{X-E(X)}(t)e^{-tk}$.

然而:

$$\begin{aligned} M_{X-E(X)}(t)&=E(e^{t(X-E(X))})\\ &=E(\prod_i e^{t(X_i-E(X_i))})\\ &=\prod_i E(e^{t(X_i-E(X_i))})\\ &=\prod_i M_{X_i-E(X_i)}(t)\\ &\leq e^{n\frac{t^2(b-a)^2}{8}} \end{aligned}$$

接下来对后面那个东西最优化,可以发现$t=\frac{4k}{n(b-a)^2}$的时候足够优秀,这就证明了上面的不等式.

Sanov Bound

回忆到斯特林公式$n!\sim \sqrt{2\pi n}(\frac{n}{e})^n$.

先来看一个在二项分布上的版本,不妨设$X_1,\cdots,X_n\sim \mathrm{Bern}(p)$,而$q>p$,我们断言:

$$\frac{1}{n+1}\exp(-nd(q||p))\leq Pr[\sum_i^n X_i\geq qn]\leq (n(1-q)+1)\exp(-nd(q||p))$$

为此留神到$Pr[\sum_i^n X_i\geq qn]=\sum_{t=qn}^n\binom{n}{t}p^t(1-p)^{n-t}$,容易证明当$q>p$的时候,$\binom{n}{t}p^t(1-p)^{n-t}$单调下降.

此时来看$\binom{n}{qn}$的取值:

$$\begin{aligned} 1&\geq \binom{n}{qn}q^{qn}(1-q)^{n-qn}\\ \binom{n}{qn}&\leq \frac{1}{q^{qn}(1-q)^{n-qn}}\\ &=\left((\frac{1}{q})^q(\frac{1}{1-q})^{1-q}\right)^n\\ &=\left(\exp(q\ln \frac{1}{q}+(1-q)\ln \frac{1}{1-q})\right)^n\\ &=\exp(nh(q)) \end{aligned}$$

此外,我们知道$\binom{n}{t}q^{t}(1-q)^{n-t}$在$t=qn$处取最大值,从而$ \binom{n}{qn}q^{qn}(1-q)^{n-qn}\geq \frac{1}{n+1}$,于是给出$\exp(nh(q))\geq \frac{1}{n+1}\exp(nh(q))$.

此时观察:

$$\begin{aligned} \exp(nh(q))p^{qn}(1-p)^{n-qn}&=\exp(nh(q))\exp(n(q\ln p+(1-q)\ln (1-p)))\\ &=\exp(n(q\ln \frac{p}{q}+(1-q)\ln \frac{1-p}{1-q}))\\ &=\exp(-nd(q||p)) \end{aligned}$$

从而给出了上面的答案.

现在来看一个一般的版本.对于一个可能的空间$\Omega=\{v_1,\cdots v_L\}$,现在有一个分布$P:\Omega\to [0,1]$,记录$p_i=P(v_i)$.

现在从$P$中独立取样$x_1,\cdots,x_n$.考虑对于一个特定的可重集合$S$,求$Pr[\{x_1,\cdots ,x_n\}=S]$.回忆到可重集的定义为$S:\Omega\to\mathbb{N}$,不妨干脆记录$s_i=S(v_i)$.容易发现$Pr[\{x_1,\cdots ,x_n\}=S]=\binom{n}{s_1,\cdots,s_L}p_1^{s_1}\cdots p_L^{s_L}$.

现在考虑一个新的分布$Q:\Omega\to [0,1]$,其中$q_i=\frac{s_i}{n}$,此时如果采样$y_1,\cdots,y_n\sim Q$的时候,先来看看$Pr[\{y_1,\cdots,y_n\}=S]$.

容易见到$|\Omega\to \mathbb N|\leq \frac{1}{(n+1)^{L-1}}$,从而见到以下简单估计(需要证明当前的情况的概率是所有情况中最大的):

$$\begin{gathered} \frac{1}{(n+1)^{L-1}}\leq Pr[\{y_1,\cdots,y_n\}=S]\leq 1\\ \frac{1}{(n+1)^{L-1}}\leq \binom{n}{s_1,\cdots,s_L}\leq \left((\frac{1}{q_1})^{q_1}\cdots (\frac{1}{q_L})^{q_L}\right)^n\\ \frac{\exp(nH(Q))}{(n+1)^{L-1}}\leq \binom{n}{s_1,\cdots,s_L}\leq \exp(nH(Q))\\ \end{gathered}$$

这给出了$\binom{n}{s_1,\cdots,s_L}$的一个上下界.然而天然有:

$$p_1^{s_1}\cdots p_L^{s_L}=\exp(n\sum_i q_i\log p_i)=\exp(-nD(Q||P)-nH(Q))$$

从而:

$$\frac{\exp(-nD(Q||P))}{(n+1)^{L-1}}\leq Pr[\{x_1,\cdots ,x_n\}=S] \leq \exp(-nD(Q||P))\\$$

如果这里把$\{x_1,\cdots ,x_n\}=S$弱化到$\{x_1,\cdots ,x_n\}\in A$,则右边当然要补一个$|A|$,当然显然$|A|\leq (n+1)^{L-1}$.也可以写:

$$\frac{\max_{S\in A}\exp(-nD(Q_S||P))}{(n+1)^{L-1}}\leq Pr[\{x_1,\cdots ,x_n\}\in A] \leq |A|\max_{S\in A}\exp(-nD(Q_S||P))\\$$

Example1

考虑$X_1,\cdots,X_n,Y_1,\cdots,Y_n$是$2n$个独立地随机变量.其中$X_i\sim \mathrm{Bern}(p),Y_i\sim \mathrm{Bern}(q)$,有$p>q$,求最小的不依赖于$n$的常数$c$使得:

$$Pr[\sum_i^n X_i\leq \sum_i^n Y_i]\leq O(c^n)$$

考虑令$Z_i=X_i-Y_i$,得知$P(Z_i=1)=p(1-q),P(Z_i=-1)=(1-p)q$.

现在考虑一个均匀一点的分布$W$满足$E(W)=0$.我们的目的是求出$\max_{E(W)=0}D(W||Z)$.

不妨设$P(W=1)=c\leq \frac{1}{2}$,则:

$$\begin{align} D(W||Z)=c\log \frac{c}{p(1-q)}+c\log\frac{c}{q(1-p)}+(1-2c)\log\frac{1-2c}{1-p(1-q)-q(1-p)} \end{align}$$

好吧我投降了,我们来带入数值吧,$p=\frac{4}{5},q=\frac{1}{2}$,于是:

$$\begin{align} D(W||Z)&=2c\log (5c)+(1-2c)\log(2-4c)\\ \frac{\mathrm{d}D(W||Z)}{\mathrm{d}c}&=(2\log e)(\ln\frac{5c}{2-4c}) \end{align}$$

所以$C=\frac{9}{10}$最优.

大数定律

对于随机变量$\{X_i\}$,对于任意$\epsilon>0$,如果:

$$\lim_{n\to \infty} P(|\frac{1}{n}\sum_i^n X_i-\frac{1}{n}\sum_i^n E(X_i)|<\epsilon)=1$$

则称它们满足大数定律.

一般而言,对于一列随机变量$\{Y_i\}$和一个随机变量$Y$,如果$\forall \epsilon>0$,$\lim_{n\to \infty}P(|Y_n-Y|<\epsilon)=1$,则称其依概率收敛.

Markov大数定律

若$\mathrm{Var}(\sum X_i)\sim o(n^2)$,则$\{X_n\}$符合大数定律.

策略是考虑$\mathrm{Var}(\frac{\sum X_i}{n})=\frac{1}{n^2}\mathrm{Var}(\sum X_i)$.用Chebyshev不等式碾一下就好了.

Khinchin大数定律(弱大数定律)

设$\{X_i\}$独立同分布,且数学期望$\mu=E(X_i)$存在,则$\{X_i\}$满足大数定律.

特征函数

对于随机变量$X$,设$\phi_X(t)=E(e^{itX})$为其特征函数.容易见到$\phi_X(-it)=E(e^{tX})$.一些常见的特征函数:

1. $X\sim \pi(\lambda),M_X(t)=e^{\lambda(e^t-1)},\phi_X(t)=e^{\lambda(e^{it}-1)}$.
2. $X\sim N(\mu,\sigma^2),M_X(t)=e^{\mu t+\frac{\sigma^2t^2}{2}},\phi_X(t)=e^{i\mu t-\frac{\sigma^2t^2}{2}}$.
3. $X\sim B(n,p),M_X(t)=(1-p+pe^t)^n,\phi_X(t)=(1-p+pe^{it})^n$.
4. $X$服从柯西分布,$f(x)=\frac{1}{\pi(x^2+1)}$,则$\phi_X(t)=e^{-|t|}$.

随机变量的分布函数由其特征函数唯一确定.此外,依分布收敛等价于特征函数逐点收敛.

依照上面的结论,就可以拿到$X_n\sim \pi(n)$推出$\frac{X_n-n}{\sqrt n}\to N(0,1)$,原因正是上面的依分布收敛的性质.

中心极限定理

先来看Lindeberg-Levy版本:

设$\{X_n\}$独立同分布,而且$E(X_n)=\mu,\mathrm{Var}(X_n)=\sigma^2$,设$Y_n=\sum_i^n X_i$,而$\tilde{Y}_n=\frac{Y_n-E(Y_n)}{\sigma(Y_n)}=\frac{\sum_i^n (X_i-\mu)}{\sqrt n\sigma}$.

我们断言$\tilde Y_n$一定依分布收敛于$Z$,其中$Z\sim N(0,1)$.

为什么呢?用泰勒展开考虑$\Re \phi_{X_n-\mu}(t)=1-\frac{\sigma^2}{2}t^2+o(t^2)$.此时$\Re \phi_{\tilde Y_n}(t)=(1-\frac{t^2}{2n}+o(\frac{t^2}{n}))^n\to e^{-\frac{t^2}{2}}$.

现在来看一个强的版本:

Berry-Esseen定理:在上述版本的基础上,如果$E(|X_n-\mu|^3)$有限,则收敛速度有:

$$|P(\tilde Y_n\leq x)-P(Z\leq x)|\leq O(1)\frac{E(|X_n-\mu|^3)}{\sigma^3\sqrt{n}}$$

概率方法

Example1

求证拉姆齐数$R(k,k)>2^{\frac{k-1}{2}}$.

考虑一个随机图,任何两个点之间以$\frac{1}{2}$概率连边,现在取点集的一个大小为$k$的子集,它是一个完全图或者或独立集的概率都是$2^{-\frac{k(k-1)}{2}}$,立刻见到这个图所有的期望大小为$k$的完全图或独立集的期望为$\binom{n}{k}2^{1-\frac{k(k-1)}{2}}$,如果这个东西$<1$,就证明总有一个图二者皆不存在.于是取$n=2^{\frac{k-1}{2}}$,则:

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

Example2

考虑一个大小为$n$的集合$X$的若干大小为$k$的子集所组成的集合$\Omega$,并且要求$\forall S,T\in \Omega,S\cap T\ne \emptyset$.求证:$|\Omega|\leq \binom{n-1}{k-1}$.

这个上界显然是容易达到的,只需要让所有子集都包含同一个元素即可.

现在考虑随机一个置换$\sigma$,选定$A_i=[i,k+i-1]$,考虑$Pr[\sigma(S)=A_i]=\frac{1}{\binom{n}{k}}$于是$Pr[\sigma(S)\in \{A_0,\cdots,A_{n-1}\}]=\frac{n}{\binom{n}{k}}$.从而$E(\sum_{S\in \Omega}[\sigma(S)\in \{A_0,\cdots,A_{n-1}\}])=\frac{n}{\binom{n}{k}}|\Omega|$.然而这个数必定小于等于$k$,因为置换不会改变相交性,而如果要从$\{A_0,\cdots,A_{n-1}\}$中选出若干个两两相交的,最多只能选出$k$个.

Example3

取若干个集合$A_1,\cdots,A_n$,$B_1,\cdots,B_n$,要求$|A_i|=k,|B_j|=l$,此外要求$A_i\cap B_i=\emptyset$,而且当$i\ne j$时,要求$A_i\cap B_j\ne\emptyset$.求证$n\leq \binom{k+l}{k}$.

考虑取$X=\bigcup_i(A_i\cup B_i)$,考虑在$X$上随机一个序关系,并设事件$E_i$为:$A_i$中的所有元素都$\leq $$B_i$中的所有元素.但这个事不能发生两次,因为如果$E_i$和$E_j$都成立,如果$A_i\cap B_j\ne \emptyset$,则$A_j\cap B_i=\emptyset$,这就完蛋了.所以$Pr[E_i]\leq \frac{1}{n}$.然而$Pr[E_i]=\frac{1}{\binom{l+k}{k}}$,这就搞定了.

Example4

求证$\forall k\geq 2$和$\forall n$,总存在矩阵$M\in \{0,1\}^{n\times n}$,使得:

1. $M$中$1$的数量约为$\Omega(n^{2-\frac{2}{k+1}})$.
2. 不存在$k\times k$的全$1$子矩阵.

考虑每一位置按照$B(1,p)$随机,则全$1$的$k\times k$的子矩阵的期望个数为$p^{k^2}\binom{n}{k}^2$.对于这些问题,我们强行删它们中的一个$1$,在做完这些操作后,剩下的$1$的个数的期望就会$\geq pn^2-p^{k^2}\binom{n}{k}^2$,最终选定$p=(\frac{n^2}{k^2n^{2k}})^{\frac{1}{k^2-1}}$.

Example5

求证:对于$\forall k,l$,存在一个图,它的环的长度均$\geq l$,但它的最小染色数$\geq k$.

考虑一个两个点之间以$p$概率连边的随即图,存在一个长度为$i$的环的概率为$\frac{n^{\underline{i}}}{i}p^i\leq n^ip^i$.

考虑每个染色都是一个独立集,因此必定有$\chi(G)\alpha(G)\geq n$,其中$\chi(G)$是染色数,$\alpha(G)$是最大独立集大小.从而只需要让$\alpha(G)$足够小就行.

现在考虑$Pr[\alpha(G)\geq a]\geq \binom{n}{a}(1-p)^{\frac{a(a-1)}{2}}$.然后倒腾倒腾吧,取$p=n^{\frac{1}{2l}-1}$,懒得算了.

Example6

考虑一个有限集合$B\subseteq \mathbb{Z}\setminus\{0\}$,求证存在一个$A\subseteq B$,使得$|A|\geq \frac{|B|}{3}$,并且满足$\forall a_1,a_2\in A,a_1+a_2\notin A$.

假如我们在一个环上做这件事,比如$\mathbb{Z}_p$.当$B=\mathbb{Z}_p\setminus\{0\}$,其中$p=3k+2$的时候,此时可以选取$[k+1,2k+1]$中的元素,容易见到这占据了$\geq \frac{|B|}{3}$.而如果不然,我们可以随机一个$r$,使得$B\to \mathbb{Z}_p\setminus\{0\},b\mapsto br$.此时落在$[k+1,2k+1]$的期望就已经$\geq \frac{|B|}{3}$.$p$取足够大能包住$B$即可.

Example7

求证:存在一个竞赛图,其中的哈密顿路的数量$\geq \frac{n!}{2^{n-1}}$.

这个好像非常平凡,随机图上随机一个排列然后它是哈密顿路的概率就是$2^{n-1}$.

Example8

我们称竞赛图的$S_k$性质是,任何$k$个点组成的子集,都存在一个点赢过了这$k$个点.问是否总存在一个竞赛图满足$S_k$性质.

随机一个竞赛图,考虑其任何一个大小为$k$的子集.对于外面一个点$u$胜过了这$k$个点的概率是$2^{-k}$.外面一个点都没赢的概率是$(1-2^{-k})^{n-k}$.于是用Union Bound,存在一个问题的概率$\leq \binom{n}{k}(1-2^{-k})^{n-k}$.显然$n\to \infty$的时候这玩意趋近于$0$,所以肯定能找到满足条件的.

Example9

考虑一系列向量$\vec v_1,\cdots \vec v_n\in \{-1,1\}^l$,求证:

1. $\exists a_1,\cdots,a_n\in \{-1,1\}$,使得$\Vert\sum a_i\vec l_i\Vert^2\geq nl$.
2. $\exists a_1,\cdots,a_n\in \{-1,1\}$,使得$\Vert\sum a_i\vec l_i\Vert^2\leq nl$.

只要证明这玩意期望就是$nl$即可,随机$\{a_i\}$,容易见到$E(a_i)=0,E(a_i^2)=1,E(a_ia_j)=E(a_i)E(a_j)=0$.带进去算一下.

Example10

求证:随机一个$x\in[1,n]$,使得$P(|v(x)-\ln\ln n|>\lambda \sqrt{\ln\ln n})\leq \lambda^{-2}$.

拆贡献用Chebyshev不等式硬估,懒得抄过程了.

Example11

考虑一个随机图$G(n,m)$,也就是从$\frac{n(n-1)}{2}$中随机$m$条边留下.这上面可能有若干随着$m$单调的性质,比如连通性之类的.我们下面证明:对于一个单调性质$P$,存在一个函数$m^*(n)$,使得:

1. 当$m(n)=\omega(m^*(n))$时,总有$\lim_{n\to \infty}Pr_{G\sim G(n,m(n))}(G\in P)=1$.
2. 当$m(n)=o(m^*(n))$时,总有$\lim_{n\to \infty}Pr_{G\sim G(n,m(n))}(G\in P)=0$.

下面简单记$Pr_{G\sim G(n,m)}(G\in P)=Pr_{n,m}$.

现在考虑$Pr_{n,mk}$,显然我们可以随机$k$次,然后再把它们拼起来(虽然有重边,但是单调性质可以不管这个),从而$1-Pr_{n,mk}\leq (1-Pr_{n,m})^k$.

直接选取$m^(n)$为使得$Pr_{n,m^(n)}\geq \frac{1}{2}$的最小的解.则立刻就可以控制住.

不过,部分的单调性质有更强的性质,即$\forall \epsilon>0$,当$m(n)\geq(1+\epsilon)m^(n)$的时候就可以控制住,当$m(n)\leq (1-\epsilon)m^(n)$也可以控制住.甚至更强地,对于有的性质,这个$\epsilon$还可以换成$\epsilon(n)=o(1)$.

Example12

现在来看连通性的性质,假设以$\frac{\log n-\alpha(n)}{n}$的概率随机每条边,那么一个点成为孤点的概率就是$(1-\frac{\log n-\alpha(n)}{n})^{n-1}\approx \frac{1}{n}e^{\alpha(n)}$.从而孤立点个数(设为$W$)的期望就是$e^{\alpha(n)}$.

接下来算$\mathrm{Var}(W)$,拆开硬算算,得到$\mathrm{Var}(W)=e^{\alpha(n)}+O(1)$.

然而$W$非负,从而:

$$\begin{aligned} Pr[W=0]&\leq Pr[|W-E|\geq E]\\ &\leq \frac{\mathrm{Var}(W)}{E^2(W)}\\ &\approx \frac{e^{\alpha(n)}+O(1)}{e^{2\alpha(n)}} \end{aligned}$$

于是只要$\alpha(n)\to\infty$就完蛋了,这个图甚至会出现孤点.

现在假设以$\frac{\log n+\alpha(n)}{n}$的概率随机每条边,和上面一样,由于期望足够小,用Markov不等式,我们可以证明此时孤立点消失了.

然后需要把剩下的部分处理一下,存在一个大小为$k\in [2,\frac{n}{2}]$的块与外界不连通的概率是$\binom{n}{k}(1-p)^{k(n-k)}$,考虑$1-p\leq e^{-p}$和$\binom{n}{k}\leq (\frac{ne}{k})^k$,于是这个概率被$(\frac{ne}{k}e^{-p(n-k)})^k$限制住了.

当$k\in [2,\epsilon n]$的时候$n-k=O(n)$,从而这个概率立刻被限制住.反之当$k\in [\epsilon n,\frac{n}{2}]$的时候$k(n-k)=O(n^2)$,但是组合数被压到了$(\frac{e}{\epsilon})^{O(n)}$,这就足够跑赢了.

统计

点估计

将只依赖于样本,不依赖于任何位置参数的函数称作统计量.例如:

1. 样本均值$\bar X=\frac{1}{n}\sum_{i=1}^n X_i$.
2. 样本方差$S^2=\frac{1}{n-1}\sum_{i=1}^n(X_i-\bar X)^2$.
3. 样本$k$阶矩$A_k=\frac{1}{n}\sum_{i=1}^n X_i^k$.
4. 样本$k$阶中心矩$B_k=\frac{1}{n}\sum_{i=1}^n(X_i-\bar X)^k$.

对于$\theta$的估计量$\hat \theta$,定义偏差$\mathrm{Bias}(\hat \theta)=E(\hat \theta)-\theta$.如果其等于$0$,则称其是无偏的.如果$\lim_{n\to \infty}\mathrm{Bias}(\hat \theta)=\theta$,则称$\hat\theta$是渐进无偏的.

此外定义$\mathrm{MSE}(\hat \theta)=E\left((\hat\theta-\theta)^2\right)$.容易见到:

$$\begin{aligned} \mathrm{MSE}(\hat\theta)&=E\left((\hat\theta-\theta)^2\right)\\ &=E\left((\hat\theta-E(\hat\theta)+E(\hat\theta)-\theta)^2\right)\\ &=E\left((\hat\theta-E(\hat\theta))^2\right)+\left(E(\hat\theta)-\theta\right)^2\\ &=\mathrm{Var}(\hat \theta)+\left(\mathrm{Bias}(\hat\theta)\right)^2 \end{aligned}$$

因此对于无偏估计的$\mathrm{MSE}(\hat\theta)=\mathrm{Var}(\hat\theta)$.

此外,如果估计量依概率收敛,或言$\forall \epsilon>0$,$\lim_{n\to \infty}P\left(|\hat\theta_n-\theta|\geq \epsilon\right)=0$,则称$\hat\theta_n$是一致估计量.

我们有性质:如果$\lim_{n\to \infty}\mathrm{MSE}(\hat\theta_n)\to 0$,则$\hat\theta_n$为一致估计量.原因是:

$$\begin{aligned} &P\left(|\hat\theta_n-\theta|\geq \epsilon\right)\\ =&P\left((\hat\theta_n-\theta)^2\geq \epsilon^2\right)\\ \leq &\frac{\mathrm{MSE}(\hat\theta_n)}{\epsilon^2} \end{aligned}$$

Example1

假设$E(X)$和$\mathrm{Var}(X)$均存在,独立随机的样本序列$X_1,\cdots,X_n$,现在考虑$\hat\theta_A=\bar X$,$\hat \theta_B=X_1$.

显然它们都是$E(X)$的无偏估计.然而$\mathrm{MSE}(\hat\theta_A)=\frac{\mathrm{Var}(X)}{n}$,而$\mathrm{MSE}(\hat\theta_B)=\mathrm{Var}(X)$.

Example2

假设已知$X\sim U(0,\theta)$.考虑$\hat\theta_A=2\bar X$和$\hat\theta_B=\max_k\{X_k\}$.

容易见到$\hat\theta_A$无偏.现在来看$\hat\theta_B$,自然地:

$$\begin{aligned} F_{\hat\theta_B}(x)&=(F_X(x))^n\\&=(\frac{x}{\theta})^n\\ E(\hat\theta_B)&=\int_0^{+\infty}(1-F_{\hat\theta_B}(x))\mathrm{d}x\\ &=\int_0^\theta(1-(\frac{x}{\theta})^n)\mathrm{d}x\\ &=\frac{n}{n+1}\theta \end{aligned}$$

但至少$\hat\theta_C=\frac{n+1}{n}\hat\theta_B$无偏.

现在来看,容易见到$\mathrm{MSE}(\hat\theta)=\frac{\theta^2}{3n}$.留神到:

$$\begin{aligned} E(\hat\theta_B^2)&=\int_0^{\theta^2}\left(1-\frac{x^{\frac{n}{2}}}{\theta^n}\right)\mathrm{d}x\\ &=\theta^2-\frac{2}{n+2}\theta^2\\ &=\frac{n}{n+2}\theta^2 \end{aligned}$$

于是$\mathrm{Var}(\hat\theta_C^2)=(\frac{n+1}{n})^2\mathrm{Var}(\hat\theta_B^2)=\frac{\theta^2}{n(n+2)}$.

Example3

考虑$B_2$对$\mathrm{Var}(X)$的估计,显然有$B_2=\frac{1}{n}\sum_k X_k^2-(\bar X)^2$.也就是说$E(B_2)=E(X^2)-E(\bar X^2)$.看上去欣欣向荣,然而:

$$\begin{aligned} E(\bar X^2)&=E((\bar X-E(\bar X)+E(\bar X))^2)\\ &=E((\bar X-E(\bar X))^2)+(E(\bar X))^2\\ &=(E(\bar X))^2+\frac{\mathrm{Var}(X)}{n} \end{aligned}$$

这就出事了.

Example4(正态分布)

考虑估计一个正态分布$X\sim N(\mu,\sigma^2)$.取$\bar X$和$S^2$作为其期望和方差的估计量.现在我们将展示一个非常厉害的结论,那就是$\bar X$和$S^2$实际上是独立的.

考虑一个正交矩阵$U$,其第一行每个元素限定为$\frac{1}{\sqrt n}$,其余行任取.由于其正交性,这必然意味着其余行所有元素之和为$0$.现在来取$\vec Y=U\vec X$.从前的结论告知我们$\vec Y$服从$n$维高斯分布.而且:

1. $E(\vec Y)=(\sqrt n\mu,0,\cdots,0)$.
2. $\mathrm{Cov}(\vec Y)=\sigma^2I$.
3. $\sum_k Y_k^2=\sum_k X_k^2$.

其中(1)是由于除第一行外,每一行的所有元素和为$0$.(2)是因为原本的$\vec X$的各个分量独立.(3)是因为正交变换保模长.

此时必定有$\bar X=\frac{Y_1}{\sqrt n}$,事实上还有:

$$\begin{aligned} (n-1)S^2&=\sum_{i=1}^n(X_i-\bar X)^2\\ &=(\sum_k X_k^2)-n\bar X^2\\ &=\sum_{k=1}^nY_k^2-Y_1^2\\ &=\sum_{k=2}^nY_k^2 \end{aligned}$$

于是二者独立.还能得知$\bar X\sim N(\mu,\frac{\sigma^2}{n})$,以及$\frac{(n-1)S^2}{\sigma^2}\sim\chi^2(n-1)$.

矩法

显然$k$阶矩的估计总是无偏的.因此一个想法是将我们想要估计的量写成矩的函数,再分别估计矩(注意,这样做在该函数并非一次的时候当然未必无偏).

最大似然估计

尝试选择参数$\theta$,使得$L(\theta)=P(X_1=x_1,\cdots,X_n=x_n|\theta)$最大.

如果样本干脆是均匀随机的,那就只需要最大化对数似然函数$\ln L(\theta)=\sum_{i=1}^n \ln P(X_i=x_i|\theta)$.

这样做当然不可能是无偏的.

Example1

考虑一个均匀分布$U(0,\theta)$,对其进行最大似然估计的结果是$\hat\theta=\max\{x_1,\cdots,x_n\}$.

Example2

考虑一个分类函数$f:X\to Y$.现在我们已经有其采样的一些结果$(x_i,y_i)$,想要去估计一个函数$f_\theta$.根据上面说的,我们需要最小化$\sum_{i=1}^n-\ln f_\theta(y_i|x_i)$.

现在考虑一个标签分布$g(y|x_i)=[y=y_i]$.我们来看交叉熵:

$$\begin{aligned} H(g,f_\theta)&=-\sum_{y}g(y|x_i)\ln f_\theta(y|x_i)\\ &=-\ln f_\theta(y_i|x_i) \end{aligned}$$

区间估计

我们想要更进一步,对于一个想要估计量$\theta$,以及两个统计量$\hat\theta_L$和$\hat\theta_R$,如果必有$P(\hat\theta_L\leq \theta\leq \hat\theta_U)\geq 1-\alpha$,则称$[\hat\theta_L,\hat\theta_R]$为$\theta$的置信水平为$1-\alpha$的置信区间.类似还可以定义单侧置信下限和单侧置信上限.

Example1

对于一个$X\sim N(\mu,\sigma^2)$,假设$\sigma^2$已知,设计一个对$\mu$的置信水平为$1-\alpha$的估计.

考虑$\bar X\sim N(\mu,\frac{\sigma^2}{n})$.此时必定有$\frac{\bar X-\mu}{\frac{\sigma}{\sqrt{n}}}\sim N(0,1)$.只需要取一组$c,d$,使得$P(c\leq \frac{\bar X-\mu}{\frac{\sigma}{\sqrt{n}}}\leq d)=1-\alpha$即可.

现在取$\Phi(x)=\int_{-\infty}^x\frac{1}{\sqrt{2\pi}}e^{-\frac{t^2}{2}}\mathrm{d}t$为其分布函数,取$c=\Phi^{-1}(\frac{\alpha}{2}),d=\Phi^{-1}(1-\frac{\alpha}{2})$.留神到$c+d=0$.化简就有:

$$P(\bar X-\frac{\Phi^{-1}(1-\frac{\alpha}{2})\sigma}{\sqrt n}\leq \mu\leq \bar X+\frac{\Phi^{-1}(1-\frac{\alpha}{2})\sigma}{\sqrt n})=1-\alpha$$

不过这个估计因为要算$\Phi^{-1}$,可能意义不是特别大.回忆到Chernoff Bound给出:

$$P(X-E(X)\geq k\sigma)\leq e^{-\frac{k^2}{2}}$$

于是立刻有$P(|\bar X-\mu|\geq \frac{k\sigma}{\sqrt n})\leq 2e^{-\frac{k^2}{2}}$.

从而:

$$P(\bar X-\frac{\sigma\sqrt{2\ln(\frac{2}{\alpha})}}{\sqrt n}\leq \mu\leq \bar X+\frac{\sigma\sqrt{2\ln(\frac{2}{\alpha})}}{\sqrt n})\geq 1-\alpha$$

现在我们来干另一件事,众所周知,中心极限定理说大部分估计最后都会趋于一个正态分布.那么在此时,能否估计出$P(\mu=\bar X)=O(\frac{1}{\sqrt n})$呢?

考虑取$\alpha=1-O(\frac{1}{\sqrt n})$,就可以发现这个时候的$\mu$已经落在$\bar X\pm O(1)$的区间内了.

Example2

考虑对$X\sim B(1,p)$.设计$p$的置信水平$1-\alpha$的置信区间.

直接考虑Chernoff Bound,给出$P(|\bar X-p|>\epsilon)\leq 2e^{-2n\epsilon^2}$.取$\epsilon=\sqrt{\frac{\ln\frac{2}{\alpha}}{2n}}$,于是:

$$P(\bar X-\sqrt{\frac{\ln(\frac{2}{\alpha})}{2n}}\leq p\leq \bar X+\sqrt{\frac{\ln(\frac{2}{\alpha})}{2n}})\geq 1-\alpha$$

回归分析

考虑一个随机取样,满足$y=\alpha+\beta x+\epsilon$,其中$\epsilon$是随机误差,满足$E(\epsilon)=0,\mathrm{Var}(\epsilon)=\sigma^2<\infty$,而且若干次取样的误差互相独立.

我们的目标是给定数据$(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)$,去估计出$\hat \alpha$和$\hat \beta$.这里有若干种估计策略:

最小二乘估计

一元

最小化$Q(\alpha,\beta)=\sum_i^n(y_i-\beta x_i-\alpha)^2$.

最简单的最优化方式当然是直接求偏导,留神到:

$$\begin{align} \frac{\partial Q}{\partial \beta}&=-2\sum_i x_i(y_i-\beta x_i-\alpha)\\ \frac{\partial Q}{\partial \alpha}&=-2\sum_i(y_i-\beta x_i-\alpha) \end{align}$$

让上述均为$0$,可以解出:

$$\begin{align} \hat\beta &=\frac{\sum x_i y_i-\frac{1}{n}(\sum x_i)(\sum y_i)}{\sum x_i^2-\frac{1}{n}(\sum x_i)^2}\\ \hat \alpha &=\frac{1}{n}\sum y_i-\hat \beta \frac{1}{n}\sum x_i \end{align}$$

如果我们为了方便,记$s_{xx}=\sum (x_i-\bar x)(x_i-\bar x)$以及$s_{xy}=\sum (x_i-\bar x)(y_i-\bar y)$,则:

$$\begin{align} \hat\beta &=\frac{s_{xy}}{s_{xx}}\\ \hat \alpha &=\bar y-\hat \beta \bar x \end{align}$$

现在来看这个估计有多准,容易见到:

$$\begin{align} s_{xy}&=\sum(x_i-\bar x)(y_i-\bar y)\\ &=\sum(x_i-\bar x)(\alpha+\beta x_i+\epsilon_i-\bar y)\\ &=\sum (x_i-\bar x)(\beta x_i+\epsilon_i)\\ s_{xx}&=\sum(x_i-\bar x)(x_i-\bar x)\\ &=\sum x_i(x_i-\bar x) \end{align}$$

从而见到:

$$\begin{align} \hat \beta&=\frac{s_{xy}}{s_{xx}}\\ &=\beta+\frac{\sum (x_i-\bar x)\epsilon_i}{s_{xx}}\\ \hat \alpha&=\bar y-\hat \beta \bar x\\ &=\frac{\sum (\alpha+(\beta -\hat \beta)x_i+\epsilon_i)}{n}\\ &=\alpha+\frac{1}{n}(\sum \epsilon_i-\frac{(\sum x_i)(\sum(x_i-\bar x)\epsilon_i)}{s_{xx}})\\ &=\alpha+\sum \epsilon_i(\frac{1}{n}-\frac{(x_i-\bar x)\bar x}{s_{xx}}) \end{align}$$

容易见到如果$E(\epsilon_i)=0$,那上述两个估计都是无偏的.现在来看他们的方差吧.

$$\begin{align} \mathrm{MSE}(\hat\beta)=\mathrm{Var}(\hat\beta)&=\sum \mathrm{Var}(\epsilon_i)(\frac{x_i-\bar x}{s_{xx}})^2\\ &=\frac{\sigma^2}{s_{xx}}\\ \mathrm{MSE}(\hat \alpha)=\mathrm{Var}(\hat \alpha)&=\sigma^2\sum\left(\frac{1}{n}-\frac{(x_i-\bar x)\bar x}{s_{xx}}\right)^2\\ &=\sigma^2\sum\left(\frac{1}{n^2}-\frac{2}{n}\frac{(x_i-\bar x)\bar x}{s_{xx}}+(\frac{(x_i-\bar x)\bar x}{s_{xx}})^2\right)\\ &=\sigma^2\left(\frac{1}{n}+\frac{\bar x^2}{s_{xx}}\right) \end{align}$$

而它们的协方差:

$$\begin{align} \mathrm{Cov}(\hat\alpha,\hat\beta)&=E\left(\sum \epsilon_i^2(\frac{1}{n}-\frac{(x_i-\bar x)\bar x}{s_{xx}})(\frac{ (x_i-\bar x)}{s_{xx}})\right)\\ &=E\left(\sum_i \epsilon_i^2\frac{1}{n}\frac{x_i-\bar x}{s_{xx}}\right)-E\left(\sum_i \epsilon_i^2\bar x(\frac{x_i-\bar x}{s_{xx}})^2\right)\\ &=\sum_i \frac{1}{n}\frac{x_i-\bar x}{s_{xx}}\sigma^2-\sum_i \sigma^2\bar x(\frac{x_i-\bar x}{s_{xx}})^2\\ &=-\sigma^2\frac{\bar x}{s_{xx}} \end{align}$$

于是我们现在可以估计$\hat y_i=\hat \alpha+\hat\beta x_i$的情况,容易见到$E(\hat y_i)=y_i$,但是:

$$\begin{align} \mathrm{Var}(\hat y_i)&=\mathrm{Var}(\hat \alpha+\hat\beta x_i)\\ &=\mathrm{Var}(\hat \alpha)+x_i^2\mathrm{Var}(\hat\beta)+2x_i\mathrm{Cov}(\hat \alpha,\hat \beta)\\ &=\sigma^2\left(\frac{1}{n}+\frac{\bar x^2}{s_{xx}}\right)+x_i^2\frac{\sigma^2}{s_{xx}}-2x_i\sigma^2\frac{\bar x}{s_{xx}}\\ &=\sigma^2\left(\frac{1}{n}+\frac{(\bar x-x_i)^2}{s_{xx}}\right) \end{align}$$

现在来看:

$$\begin{align} \mathrm{Var}(\hat y_i-y_i)&=\mathrm{Var}(\hat y_i)+\mathrm{Var}(y_i)-2\mathrm{Cov}(\hat y_i,y_i)\\ &=\mathrm{Var}(\hat y_i)+\mathrm{Var}(y_i)-2\mathrm{Cov}(\hat \alpha+\hat\beta x_i,\alpha+\beta x_i+\epsilon_i)\\ &=\mathrm{Var}(\hat y_i)+ \sigma^2-2\mathrm{Cov}(\hat \alpha+\hat\beta x_i,\epsilon_i)\\ &=\sigma^2\left(\frac{1}{n}+\frac{(\bar x-x_i)^2}{s_{xx}}\right)+\sigma^2-2\sigma^2(\frac{1}{n}-\frac{(x_i-\bar x)\bar x}{s_{xx}})-2\sigma^2\frac{x_i-\bar x}{s_{xx}}x_i\\ &=\frac{n-1}{n}\sigma^2-\frac{(\bar x-x_i)^2}{s_{xx}}\sigma^2 \end{align}$$

从而:

$$\begin{align} E(\sum (\hat y_i-y_i)^2)&=\sum \mathrm{Var}(\hat y_i-y_i)\\ &=(n-1)\sigma^2-\frac{s_{xx}}{s_{xx}}\sigma^2\\ &=(n-2)\sigma^2 \end{align}$$

总结一下我们上面做的事情,我们搞定了:

1. $\hat \alpha$和$\hat \beta$是$\alpha$和$\beta$的无偏估计.
2. $s^2=\frac{1}{n-2}\sum (\hat y_i-y_i)^2$是$\sigma^2$的无偏估计.

此外,简单验证可以说明当$\epsilon_i\sim N(0,\sigma^2)$时,最小二乘估计出的$\hat \alpha$和$\hat \beta$就是最大似然估计,而且因为它们都是$\epsilon_i$的线性组合,它们实际上是一个二维高斯分布.

多元

考虑一个$y=\beta_0+\cdots +\beta_k x_k+\epsilon$,其中$E(\epsilon)=0,\mathrm{Var}(\epsilon)=\sigma^2$,并且每次独立误差.

现在考虑能否用若干组数据去估计$\hat \beta_0,\cdots,\hat \beta_k$.

造$\vec x_i=[1,x_{i,1},\cdots,x_{i,k}]^t\in \mathbb{R}^{k+1}$,以及$\vec \beta=[\beta_0,\cdots,\beta_k]\in \mathbb{R}^{k+1}$.并设$X\in \mathbb{R}^{n\times (k+1)}$,其中$X^t=[\vec x_1,\cdots,\vec x_n]$,也就是说$X$第$i$行是$\vec x_i^t$.当然有$\vec y=X\vec\beta+\vec \epsilon$,此外$E(\vec y)=X\vec \beta$,$\mathrm{Cov}(\vec y)=\sigma^2 I_n$.

现在我们仍然用最小二乘估计,设$Q(\vec \beta)=\sum_i (y_i-\vec x_i^t\vec \beta)^2=|\vec y-X\vec \beta|^2$.

来看一下如何让这个东西最小,lww告诉我们需要让$X\vec \beta$正好打向$\vec y$向$\mathrm{im} X$的投影.回忆到$(\mathrm{im}X)^\bot=\ker X^t$,于是只需要$X^tX\vec\beta=X^t\vec y$即可.

当$X$列满秩的时候,根据奇异值分解有$X^tX$可逆,这个时候就有$\hat \beta=(X^tX)^{-1}X^t(X\vec \beta+\vec \epsilon)=\vec \beta+(X^tX)^{-1}X^t\vec \epsilon$,从而必然有$E(\hat \beta)=\vec \beta$.此外回忆到$\mathrm{Cov}(AX)=A\mathrm{Cov}(X)A^t$,于是:

$$\begin{align} \mathrm{Cov}(\hat \beta)&=\sigma^2(X^tX)^{-1}X^t((X^tX)^{-1}X^t)^t\\ &=\sigma^2(X^tX)^{-1}X^tX(X^tX)^{-1}\\ &=\sigma^2(X^tX)^{-1} \end{align}$$

另外,我们的估计是$\hat y=X\hat \beta=X(X^tX)^{-1}X^t\vec y$,下面我们设$H=X(X^tX)^{-1}X^t$,这个矩阵看上去性质就很好.它事实上显然有如下的性质:

1. $\mathrm{trace}(H)=k+1$.
2. $H^2=H$.
3. $H^t=H$.
4. $H$的特征值只有$1$和$0$.
5. $H$半正定.
6. $HX=X$.
7. $(I-H)^2=I-H$.

那么就有:

$$\begin{align} \hat y-\vec y&=(H-I)\vec y\\ &=(H-I)(X\vec \beta+\vec \epsilon)\\ &=(H-I)\vec \epsilon\\ \mathrm{Cov}(\hat y-\vec y)&=\sigma^2(H-I)^2\\&=\sigma^2(I-H)\\ E(|\hat y-\vec y|^2)&=\mathrm{trace}(\mathrm{Cov}(\hat y-\vec y))\\ &=\sigma^2\mathrm{trace}(I-H)\\ &=\sigma^2(n-k-1) \end{align}$$

这就给出了$s^2=\frac{1}{n-k-1}|\hat y-\vec y|^2$是$\sigma^2$的无偏估计量.

这个估计有多准呢?来看$\epsilon_i\sim N(0,\sigma^2)$的情况,此时回忆到$\hat \beta=\vec \beta+(X^tX)^{-1}X^t\vec \epsilon$服从一个多维高斯分布$N(\vec \beta,\sigma^2(X^tX)^{-1})$.考虑正交对角化给出$I-H=Q^t\Lambda Q$,由于旋转不变性,$\frac{(I-H)\vec \epsilon}{\sigma}$实际上就是$n-k-1$个独立同分布服从标准正态分布的随机变量,于是$\frac{|\hat y-\vec y|^2}{\sigma^2}\sim \chi^2(n-k-1)$.顺便一提,这里可以看出$s^2$和$\hat \beta$实际上依赖的东西是正交的.它们事实上互相独立.

最后,当我们拿到一个新的向量$\vec x_0$的时候,观察此时的估计值$\vec y_0=\vec x_0^t\hat \beta$,显然有$E(\vec x_0^t\hat \beta)=\vec x_0^t\vec \beta$以及$\mathrm{Cov}(\vec x_0^t\hat \beta)=\sigma^2\vec x_0^t(X^tX)^{-1}\vec x_0$.

不过上面这些分析都没太给出定性的结果.现在让我们来看$r^2=1-\frac{\sum(y_i-\hat y_i)^2}{\sum(y_i-\bar y)^2}=\frac{\sum(\hat y_i-\bar y)^2}{\sum (y_i-\bar y)^2}$.它实际上解释了总平方和中,回归平方和所占的比例.

岭回归

考虑最小化$Q_\lambda(\vec \beta)=\sum (y_i-\vec x_i^t\vec \beta)^2+\lambda |\vec \beta|^2$.

TODO

Lasso回归

最小化$Q_\lambda(\vec \beta)=\sum (y_i-\vec x_i^t\vec \beta)^2+\lambda \Vert\vec \beta\Vert_1$.