概率与期望

发表于 2025-06-23 更新于 2025-11-25 分类于具体数学 Waline：

离散概率

基本定义

概率空间$\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$是定义在同一个概率空间上的两个随机变量,那么:

$E ( X + Y ) = EX + EY$.
$E ( \alpha X ) = \alpha EX$.
如果$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)$.容易见到以下性质:

$\mathrm{Cov}(X,X)=\mathrm{Var}(X)$.
$\mathrm{Cov}(X,Y)=\mathrm{Cov}(Y,X)$.
$\mathrm{Cov}(aX,bY)=ab\mathrm{Cov}(X,Y)$.
$\mathrm{Cov}(X_1+X_2,Y)=\mathrm{Cov}(X_1,Y)+\mathrm{Cov}(X_2,Y)$.
若$X,Y$相互独立,则$\mathrm{Cov}(X,Y)=0$.然而逆命题不成立.
$\mathrm{Var}(\sum_{i}X_i)=\sum_{i}\sum_j\mathrm{Cov}(X_i,X_j)$.
$\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 + xG ( x ) = \sum_k F_k ( x ) + G ( x )$.
$( \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$的分布函数.

分布函数有如下性质:

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

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

非负性:$f(x)\geq 0$.
正则性:$\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}}$.

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

对称性:$f(x)=f(-x)$.
$f(x)_{\max}=f(0)$.
$\lim_{x\to -\infty}f(x)=\lim_{x\to +\infty}f(x)=0$.
$E(X)=\int_{-\infty}^{+\infty}f(x)x\mathrm{d}x=0$.
$E(X^2)=\int_{-\infty}^{+\infty}f(x)x^2\mathrm{d}x=1$.
$\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$.我们见过很多次这个东西了,请看:

$\Gamma(1)=1$.
$\Gamma(\frac{1}{2})=\sqrt{\pi}$.
$\Gamma(\alpha+1)=\alpha\Gamma(\alpha)$.
$\Gamma(n+1)=n!$.
$\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)$.应该有:

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

有界性:$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$.
单调性:当$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)$.
右连续:$F(x_0+0,y)=F(x_0,y)$,$F(x,y_0+0)=F(x,y_0)$.
非负性:$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} \] 带入得到结果.

协方差矩阵

设随机变量$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)$.

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))$.

可以见到以下性质:

$H[X,Y]=H[X]+H[Y|X]$.
$H[X|Y]\leq H[X]$.
作为(2)的推论,互信息$I(X,Y)=H[X]+H[Y]-H[X,Y]\geq 0$.
对于一个确定性函数$g$,$H[X]\geq H[g(X)]$.
$I(X;YZ)=I(X;Z)+I(X;Y|Z)$.
当$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} \] 然而后者非负,于是显然.

对于(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;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) \]

频率

尾不等式

留神到如果事件在$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)$的上界,看上去就会非常优秀.进一步地:

尾不等式:给出$P(X\geq k)$的上界.
集中不等式:给出$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不等式:

当$t>0$的时候,有$P(X\geq k)\leq M_X(t)e^{-tk}$.
当$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$):

$P(X\geq E(X)+k)\leq e^{-\frac{2k^2}{n(b-a)^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$.

对于一个可能的空间$\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}$的一个上下界.

现在回看: \[ \begin{aligned} Pr[\{x_1,\cdots ,x_n\}=S]&=\binom{n}{s_1,\cdots,s_L}p_1^{s_1}\cdots p_L^{s_L}\\ &\leq \exp(nH(Q))\exp(n\sum_i q_i\log p_i)\\ &=\exp(nH(Q))\exp(-nD(Q||P)) \end{aligned} \]

大数定律

对于随机变量$\{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\}$满足大数定律.

离散概率

基本定义

期望的简单运算

方差的简单运算

随机抽样调查

条件概率

贝叶斯公式

概率生成函数

Example1

Example2(Penney游戏)

Example3([SDOI2017] 硬币游戏)

二项式分布

模型

树上随机游走

Example1

Example2

计数与期望的转换

Example(CodeChef Secplayer)

一些小技巧

Example1(CF865C)

Example2(猎人杀)

Example3(AGC019F)

一些不等式

Union Bound

Markov 不等式

Chebyshev 不等式

一些离散分布

泊松分布

几何分布

负二项分布

连续随机变量

高斯分布

指数分布

伽马分布

多维离散随机变量

重期望公式

多维连续随机变量

二维正态分布

Example1

重期望公式

协方差

Example1

相关系数

协方差矩阵

Example1

Example2

卷积

熵

KL散度

频率

尾不等式

Example1

矩

Example2

Chernoff Bound

Example1

Example2

Example3

Hoeffding引理

Example1(Chernoff-Hoeffding不等式)

Sanov Bound

大数定律

Markov大数定律

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