概率与期望

离散概率

基本定义

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

事件:的一个子集.

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

概率:若,我们称它发生的概率为,有且.

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

联合分布:如果两个随机变量和定义在同一个概率空间上,对于每一个在取值范围内的以及在取值范围内的,我们称为它们的联合分布.

独立:如果对于每一个在取值范围内的以及在取值范围内的,,我们称和是独立的.

期望(均值):我们设概率空间上的随机变量的期望.

中位数:我们设概率空间上的随机变量的中位数为满足的所组成的集合.

众数:我们设概率空间上的随机变量的众数为满足的所组成的集合.

方差:我们设概率空间上的随机变量的方差.

标准差:我们设概率空间上的随机变量的标准差.

期望的简单运算

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

1. .

2. .

3. 如果和互相独立,那么.

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

此外(3)的逆命题不成立.考虑取分别以的概率选取和,取,则.

方差的简单运算

我们考虑方差的定义式:

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

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

而又有:

则:

即:独立随机变量之和的方差等于它们的方差之和.此外显然也有.

事实上,容易见到可以定义协方差.容易见到以下性质:

1. .
2. .
3. .
4. .
5. 若相互独立,则.然而逆命题不成立.
6. .
7. .

随机抽样调查

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

.

.

这里的似乎与定义不是那么相符.但是它拥有更好的性质:.

证明如下:

条件概率

已知事件B发生时事件A发生的概率为.

贝叶斯公式

贝叶斯公式:如果有是样本空间的一个划分,即,有,并且有.则有.

简化形式:.

另外,我们考虑设,称为贝叶斯算子,则同理可得:

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

概率生成函数

如果是定义在概率空间上的随机变量,那么它的概率生成函数为.

不难发现需要满足的条件:所有系数都非负并且.

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

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

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

另外,我们不难发现:.

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

换句话说,若,那么这个式子与直接对使用求导的那个公式是等价的.注意,这里并没有要求这些生成函数的系数是非负的.

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

Example1

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

考虑设为所有不包含THTTH的硬币序列的生成函数,为所有只有结尾为THTTH的硬币序列的生成函数,令,为空集,我们显然有:

解方程即可.

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

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

我们的方程将会变为:

如果我们设为将字符串中的H替换成,T替换成之后的值,那么显然有:

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

令.

令,,.

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

如果硬币是均匀的()我们引入另一个符号:我们设.那么显然期望需要的抛硬币次数就是.

Example2(Penney游戏)

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

我们设为所有以HHT结尾的硬币序列的生成函数,设为所有以HTT结尾的硬币序列的生成函数.为其它的硬币序列的生成函数,令.

我们显然有:

解方程并带入,可以有得知以HHT结尾的概率为.

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

Example3([SDOI2017] 硬币游戏)

是Example2的超级加强版.

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

1. .

2. .

第一个式子的用处在于带入,发现.

把(2)化简一下,有:

带入,有:

不难发现对于不同的,(2)的右边不同,而左边一定相同,这样就给出了个等式,算上(1)一共有个等式,可以算出这个未知数.

二项式分布

现在有一个大小为的概率空间,其中,我们把这样的概率序列称为二项式分布.

如果我们令,不难发现二项式分布的生成函数为.

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

与二项式分布相对应的还有负二项式分布,它的生成函数形如:.

我们考虑如何求的方差和均值,不妨设,则.

不难发现满足二项式分布.也就是说,以为参数的负二项式分布也就是以为参数的二项式分布.

模型

树上随机游走

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

Example1

给一棵所有边长都为的个点的树,问所有点对中,从走到的期望距离的最大值是多少.

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

对于,我们有:

对于,我们有:

Example2

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

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

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

如果只有黑点,那么显然答案就是路径的期望长度,我们设表示以为起点的路径的期望长度,不难注意到且.这个dp转移显然是有后效性的,可以使用高斯消元做,但有一个经典做法:我们求得,然后就可以采取带入化简的方法做了.

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

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

计数与期望的转换

Example(CodeChef Secplayer)

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

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

把所有人权值从大到小排序,设表示只考虑前个人的时候的期望,不难发现:.

一些小技巧

Example1(CF865C)

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

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

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

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

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

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

Example2(猎人杀)

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

offline

Example3(AGC019F)

人类智慧题...

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

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

然后咧?

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

所以呢?由于从走到一定会经过条有向边,所以期望贡献一定要加上一个.而如果我走到了直线上,那接下来的贡献是.我们只需要枚举一下走到了多少次即可.

一些不等式

Union Bound

即:,取等当且仅当所有互斥.

Markov 不等式

若,则.

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

Chebyshev 不等式

当时,有 证明的话直接考虑设,用Markov不等式得到:

一些离散分布

泊松分布

取二项分布的极限情况.设此时,每个东西有的概率选入,则对于一个固定的常数,当的时候,,记作.

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

此时来看,留神到无非是上面那个东西转移了一下子,因此.

来看,自然有: 所以.

几何分布

伯努利试验中首次发生结果的次数,记作.

显然,此外.

设,则,,.

很重要的一个性质是无记忆性.即.

负二项分布

伯努利实验中结果发生次的重复次数.则,记作.显然.必然有.

首先要验证: 而:

连续随机变量

给定随机变量和实数,定义为随机变量的分布函数.

分布函数有如下性质:

1. 有界性:,而且.
2. 单调性:单调不减.
3. 右连续:.

如果存在一个,使得,则称是连续随机变量,而是其概率密度函数.它还应当满足以下性质:

1. 非负性:.
2. 正则性:.

对于连续随机变量.此时还满足左连续.

由此还可以得出连续随机变量在任何一点处取值必然为零,因为.

由此可以定义期望:当,则定义.注意这里要求的是绝对可积而不是可积.

现在我们来搞定:.

策略是反证:如果.此时任取一个使得.

此时,这就矛盾了.

接下来来做Markov不等式,对于非负随机变量,若,则.原因是: 此时还可以定义.

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

高斯分布

概率密度函数.

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

1. 对称性:.
2. .
3. .
4. .
5. .
6. .

其中(5)的证明见: 还可以对此进行推广,考虑,记.只需取,就可以转换回标准正态分布,并且此时.

指数分布

对于,定义概率密度函数,记作.其分布函数.

它同样也有无记忆性.考虑,从而.

伽马分布

对于,定义伽马函数.我们见过很多次这个东西了,请看:

1. .
2. .
3. .
4. .
5. .

对于,定义概率密度函数,称此时符合伽马分布,记作.

先把正则性验证了吧,令,则,则,于是搞定了.

然后是其期望: 类似地,,从而算出.显然当时，.

当的时候,我们得到了指数分布.

另一个特例是,.此时我们称其为自由度为的卡方分布.记作,其数学期望为,方差为.当的时候,.

多维离散随机变量

重期望公式

考虑把视作一个,则.原因是.

多维连续随机变量

设.应该有:

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

1. 有界性:,而且.
2. 单调性:当时,;当时,.
3. 右连续:,.
4. 非负性:.

当连续时,如果能找到函数满足,称为联合密度函数.

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

当都有,则称相互独立.

容易检验,而且当相互独立的时候,,于是自然也有.

二维正态分布

即: 现在来验证正则性,取.而​.于是: 此外请看: 于是当,则.

此外: 也就是说,当时,,容易见到相互独立当且仅当.

Example1

设的矩阵中每个元素独立服从.求.

考虑.直接套期望就知道.

显然.

而中,每一个,于是.

重期望公式

定义.则.

协方差

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

Example1

证明二维正态分布的.

容易见到: 然而: 带入得到结果.

相关系数

可以定义相关系数.一个很好玩的事是两个变量的任意线性变换后,仍有: 一个显然结论是当标准化后即后相关系数不变.

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

1. .
2. 如果等价于存在关系使得.

(1)(2)其实就是柯西不等式对吧,因为其实是某种内积,所以当然有.

协方差矩阵

设随机变量,定义为其数学期望向量,而为的协方差矩阵.也就是.容易见到其半正定,原因是.

事实上应该总有,原因是:

Example1

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

显然为: 此外.其逆矩阵.

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

Example2

求证:当,则,其中必须行满秩.

当是方阵的时候,直接可逆,于是: 此外,一般的多为高斯分布可以看作独立同分布标准正态分布线性变换后的结果,原因是当,当然有.

特别地,把一个有一定信息关系的东西变成也只需要,这个过程一般叫白化.因为信息被缩简单了.

然而,考虑如果,如果,此时的结果似乎只和有关,而与竟然无关.特别地,如果是一个正交矩阵,则干脆和服从同样的分布.

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

卷积

若相互独立,考虑,则.

熵

离散情况下将熵定义为.如果设,则容易见到.

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

首先检验是下凸函数,原因是而.于是琴生不等式给出,或说.

另外一个很重要的工具是对数求和不等式,对于任何非负实数和正数,记,则: 一个重要的性质是证明其是上凸函数,对于任意分布和,都有: 原因是考虑: 可以见到以下性质:

1. .
2. .
3. 作为(2)的推论,互信息.
4. 对于一个确定性函数,.
5. .
6. .
7. 当满足Markov规则,或者说,或说,则.这自然推出,也即这个过程中信息不会增多.

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

(2)的话考虑: 不妨令.容易见到.于是上式变为: 对于(4),轻易地: 然而后者非负,于是显然.特别地,当是一个单射的时候,.

对于(5),留神到,考虑: 然而.

对于(6),考虑: 然而,而,于是显然.

对于(7),考虑: 此外: 于是,这就证毕.

KL散度

定义.其中如果而的情况出现,我们就说此时其为.我们想要证明:.考虑: 从而这的确是某种衡量偏离程度的算子.

此外还应当定义条件KL散度.考察: 将后面的部分定义为.顺便应该有.

此外还应当证明KL散度凸性.对于概率分布对,以及任意,令.下面我们证明下凸:

此外,有趣的性质是证明,不过这个只需简单转化即可.

另外,对任意和kernel,令,. 散度的data-processing不等式给出:.

Example1

求证.

具体来说,.

编码

一般无损编码

考虑一个编码-解码过程,要求编码器Encode是一个到的单射,从而存在其的一个左逆Decode满足.

对于编码,我们非常在意的是它的长度.考虑设,我们下面将会估计的大小.

首先证明其下界,我们断言: 由于,因此其实只需要证明.由于该编码无损,不妨设为满足的数量,容易见到,立刻有.于是: 此外我们还想要估计具体有多大,事实上: 下面来看一种比较优秀的编码方式.不妨假设,于是自然有.取码长.其实就是按照出现的频率用小码,则:

前缀码

一个更合适的例子是前缀码,对于一个函数,我们声称存在前缀码使得,当且仅当,原因是在二叉树上表示一下.

众所周知Huffman编码是最优编码,现在我们来看它为什么优秀,我们说其满足,下面我们来证明这个结论.

先证上界,由于Huffman编码是最优编码,我们只要选取任意一个编码,使得它的界即可.根据上面的引理,我们直接将映射到一个长度为的前缀编码.此时: 再来看下界.来证明任意前缀编码都会被这个下界控制住.

对于一个前缀编码,实际上是把映射到了另一个处.由于这是一个单射,所以有.然而: 来看一个特定的,如果此时已经能解码了,那就一定是空白,因此此时熵为;反之,则要么是要么是,伯努利分布的最大值只有.因此我们可以发现,对于一个特定的和对应的,一定有.

所以实际上.

几乎无损压缩

对于独立同分布,如果满足: 则称其为几乎无损压缩.不妨记录.

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

1. ,存在编码方案使得,并且错误概率趋近于.
2. ,如果,则无论怎么编码,错误概率趋近于.

先来证明(1),考虑直接取,并且编码出现概率最大的前个元素,剩下的扔掉.不妨可以发现我们只会扔掉所有的,原因是比这个阈值大的不可能超过个.然而留意到: 可是的期望恰好为,因此根据Chernoff-Hoeffding Bound,这个错误概率.

那么反过来的界怎么证明呢?此时最多可编码个元素.仍然用Chernoff Bound就可以搞定了.

通用压缩

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

当编码的时候不知道分布,但解码的时候知道分布的时候,事实上可以做到:,其中可以任意小.

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

假设,并且,取一个阈值,以及现在来看失败概率也就是: 这个错误概率就很小了.

信道编码

定义信道为某种会"污染"信息的东西,或者干脆写称条件概率分布.此外定义信道容量,其中.

现在我们考虑一个一般的信道编码,取.

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

2. data-processing不等式:

对于(1),由于独立地依赖于,考虑: 至于(2),实际上是互信息的data-processing不等式.

接下来我们要搞定传送速率的问题.不妨设,现在我们将要证明: 其中是可接受的最大错误概率,定义为.

怎么证明呢?考虑取一个指示变量,当的时候,否则.不妨直接让多错一点,到达以方便我们下面的分析.这样的话和就独立了.此时立刻见到: 而.

极限的情况

尾不等式

留神到如果事件在次中发生了次,其实是不能说的.因为后面总是会有微小的扰动.但似乎总能刻画这些微小扰动的代价.

设.如果我们能求出的上界,看上去就会非常优秀.进一步地:

1. 尾不等式:给出的上界.
2. 集中不等式:给出的上界.

Example1

对二项分布用Chebyshev不等式,轻易有: 这个估计有点菜,右侧是的,这个趋近也太慢了.

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

矩

定义为的阶原点矩,而将称为的阶中心距.则期望是其一阶原点矩而方差是二阶中心矩.

对于随机变量,定义为的矩生成函数.考虑:

Example2

对,求.

考虑其矩生成函数: 令,则,现在我们可以对其求四次导数得到: 那这个有什么用呢?考虑对其用Markov不等式: 这的确给出了一个更好的估计.

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

Chernoff Bound

考虑直接对用Markov不等式:

1. 当的时候,有.
2. 当的时候,有.

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

Example1

当的时候,求的上界.其中.

先求此时的矩生成函数: 当的时候,我们想要优化的最小值,直接对求导,发现当时最小.

此时:

Example2

当,求的上界.

还是求矩生成函数,考虑: 从而: 当的时候取最小值,从而最后的界是.

Example3

当,求的上界.

考虑.

然后需要一个Lemma,我们说,这个会在后面的Hoeffding引理证明.

直接带入,右侧为: 取得到的上界.

此外取得到的上界为.

于是我们有.

Hoeffding引理

若实数随机变量,则.

Example1(Chernoff-Hoeffding不等式)

若,其中相互独立且.则():

1. .
2. .

怎么证明呢,考虑.

然而: 接下来对后面那个东西最优化,可以发现的时候足够优秀,这就证明了上面的不等式.

Sanov Bound

回忆到斯特林公式.

先来看一个在二项分布上的版本,不妨设,而,我们断言: 为此留神到,容易证明当的时候,单调下降.

此时来看的取值: 此外,我们知道在处取最大值,从而,于是给出.

此时观察: 从而给出了上面的答案.

现在来看一个一般的版本.对于一个可能的空间,现在有一个分布,记录.

现在从中独立取样.考虑对于一个特定的可重集合,求.回忆到可重集的定义为,不妨干脆记录.容易发现.

现在考虑一个新的分布,其中,此时如果采样的时候,先来看看.

容易见到,从而见到以下简单估计(需要证明当前的情况的概率是所有情况中最大的): 这给出了的一个上下界.然而天然有: 从而:

如果这里把弱化到,则右边当然要补一个,当然显然.也可以写:

Example1

考虑是个独立地随机变量.其中,有,求最小的不依赖于的常数使得: 考虑令,得知.

现在考虑一个均匀一点的分布满足.我们的目的是求出.

不妨设,则: 好吧我投降了,我们来带入数值吧,,于是: 所以最优.

大数定律

对于随机变量,对于任意,如果: 则称它们满足大数定律.

一般而言,对于一列随机变量和一个随机变量,如果,,则称其依概率收敛.

Markov大数定律

若,则符合大数定律.

策略是考虑.用Chebyshev不等式碾一下就好了.

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

设独立同分布,且数学期望存在,则满足大数定律.

特征函数

对于随机变量,设为其特征函数.容易见到.一些常见的特征函数:

1. .
2. .
3. .
4. 服从柯西分布,,则.

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

依照上面的结论,就可以拿到推出,原因正是上面的依分布收敛的性质.

中心极限定理

先来看Lindeberg-Levy版本:

设独立同分布,而且,设,而.

我们断言一定依分布收敛于,其中.

为什么呢?用泰勒展开考虑.此时.

现在来看一个强的版本:

Berry-Esseen定理:在上述版本的基础上,如果有限,则收敛速度有:

概率方法

Example1

求证拉姆齐数.

考虑一个随机图,任何两个点之间以概率连边,现在取点集的一个大小为的子集,它是一个完全图或者或独立集的概率都是,立刻见到这个图所有的期望大小为的完全图或独立集的期望为,如果这个东西,就证明总有一个图二者皆不存在.于是取,则:

Example2

考虑一个大小为的集合的若干大小为的子集所组成的集合,并且要求.求证:.

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

现在考虑随机一个置换,选定,考虑于是.从而.然而这个数必定小于等于,因为置换不会改变相交性,而如果要从中选出若干个两两相交的,最多只能选出个.

Example3

取若干个集合,,要求,此外要求,而且当时,要求.求证.

考虑取,考虑在上随机一个序关系,并设事件为:中的所有元素都中的所有元素.但这个事不能发生两次,因为如果和都成立,如果,则,这就完蛋了.所以.然而,这就搞定了.

Example4

求证和,总存在矩阵,使得:

1. 中的数量约为.
2. 不存在的全子矩阵.

考虑每一位置按照随机,则全的的子矩阵的期望个数为.对于这些问题,我们强行删它们中的一个,在做完这些操作后,剩下的的个数的期望就会,最终选定.

Example5

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

考虑一个两个点之间以概率连边的随即图,存在一个长度为的环的概率为.

考虑每个染色都是一个独立集,因此必定有,其中是染色数,是最大独立集大小.从而只需要让足够小就行.

现在考虑.然后倒腾倒腾吧,取,懒得算了.

Example6

考虑一个有限集合,求证存在一个,使得,并且满足.

假如我们在一个环上做这件事,比如.当,其中的时候,此时可以选取中的元素,容易见到这占据了.而如果不然,我们可以随机一个,使得.此时落在的期望就已经.取足够大能包住即可.

Example7

求证:存在一个竞赛图,其中的哈密顿路的数量.

这个好像非常平凡,随机图上随机一个排列然后它是哈密顿路的概率就是.

Example8

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

随机一个竞赛图,考虑其任何一个大小为的子集.对于外面一个点胜过了这个点的概率是.外面一个点都没赢的概率是.于是用Union Bound,存在一个问题的概率.显然的时候这玩意趋近于,所以肯定能找到满足条件的.

Example9

考虑一系列向量,求证:

1. ,使得.
2. ,使得.

只要证明这玩意期望就是即可,随机,容易见到.带进去算一下.

Example10

求证:随机一个,使得.

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

Example11

考虑一个随机图,也就是从中随机条边留下.这上面可能有若干随着单调的性质,比如连通性之类的.我们下面证明:对于一个单调性质,存在一个函数,使得:

1. 当时,总有.
2. 当时,总有.

下面简单记.

现在考虑,显然我们可以随机次,然后再把它们拼起来(虽然有重边,但是单调性质可以不管这个),从而.

直接选取为使得的最小的解.则立刻就可以控制住.

不过,部分的单调性质有更强的性质,即,当的时候就可以控制住,当也可以控制住.甚至更强地,对于有的性质,这个还可以换成.

Example12

现在来看连通性的性质,假设以的概率随机每条边,那么一个点成为孤点的概率就是.从而孤立点个数(设为)的期望就是.

接下来算,拆开硬算算,得到.

然而非负,从而: 于是只要就完蛋了,这个图甚至会出现孤点.

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

然后需要把剩下的部分处理一下,存在一个大小为的块与外界不连通的概率是,考虑和,于是这个概率被限制住了.

当的时候,从而这个概率立刻被限制住.反之当的时候,但是组合数被压到了,这就足够跑赢了.

统计

点估计

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

1. 样本均值.
2. 样本方差.
3. 样本阶矩.
4. 样本阶中心矩.

对于的估计量,定义偏差.如果其等于,则称其是无偏的.如果,则称是渐进无偏的.

此外定义.容易见到: 因此对于无偏估计的.

此外,如果估计量依概率收敛,或言,,则称是一致估计量.

我们有性质:如果,则为一致估计量.原因是:

Example1

假设和均存在,独立随机的样本序列,现在考虑,.

显然它们都是的无偏估计.然而,而.

Example2

假设已知.考虑和.

容易见到无偏.现在来看,自然地: 但至少无偏.

现在来看,容易见到.留神到: 于是.

Example3

考虑对的估计,显然有.也就是说.看上去欣欣向荣,然而: 这就出事了.

Example4(正态分布)

考虑估计一个正态分布.取和作为其期望和方差的估计量.现在我们将展示一个非常厉害的结论,那就是和实际上是独立的.

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

1. .
2. .
3. .

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

此时必定有,事实上还有: 于是二者独立.还能得知,以及.

矩法

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

最大似然估计

尝试选择参数,使得最大.

如果样本干脆是均匀随机的,那就只需要最大化对数似然函数.

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

Example1

考虑一个均匀分布,对其进行最大似然估计的结果是.

Example2

考虑一个分类函数.现在我们已经有其采样的一些结果,想要去估计一个函数.根据上面说的,我们需要最小化.

现在考虑一个标签分布.我们来看交叉熵:

区间估计

我们想要更进一步,对于一个想要估计量,以及两个统计量和,如果必有,则称为的置信水平为的置信区间.类似还可以定义单侧置信下限和单侧置信上限.

Example1

对于一个,假设已知,设计一个对的置信水平为的估计.

考虑.此时必定有.只需要取一组,使得即可.

现在取为其分布函数,取.留神到.化简就有: 不过这个估计因为要算,可能意义不是特别大.回忆到Chernoff Bound给出: 于是立刻有.

从而: 现在我们来干另一件事,众所周知,中心极限定理说大部分估计最后都会趋于一个正态分布.那么在此时,能否估计出呢?

考虑取,就可以发现这个时候的已经落在的区间内了.

Example2

考虑对.设计的置信水平的置信区间.

直接考虑Chernoff Bound,给出.取,于是:

回归分析

考虑一个随机取样,满足,其中是随机误差,满足,而且若干次取样的误差互相独立.

我们的目标是给定数据,去估计出和.这里有若干种估计策略:

最小二乘估计

一元

最小化.

最简单的最优化方式当然是直接求偏导,留神到: 让上述均为,可以解出: 如果我们为了方便,记以及,则: 现在来看这个估计有多准,容易见到: 从而见到: 容易见到如果,那上述两个估计都是无偏的.现在来看他们的方差吧. 而它们的协方差: 于是我们现在可以估计的情况,容易见到,但是: 现在来看: 从而: 总结一下我们上面做的事情,我们搞定了:

1. 和是和的无偏估计.
2. 是的无偏估计.

此外,简单验证可以说明当时,最小二乘估计出的和就是最大似然估计,而且因为它们都是的线性组合,它们实际上是一个二维高斯分布.

多元

考虑一个,其中,并且每次独立误差.

现在考虑能否用若干组数据去估计.

造,以及.并设,其中,也就是说第行是.当然有,此外,.

现在我们仍然用最小二乘估计,设.

来看一下如何让这个东西最小,lww告诉我们需要让正好打向向的投影.回忆到,于是只需要即可.

当列满秩的时候,根据奇异值分解有可逆,这个时候就有,从而必然有.此外回忆到,于是: 另外,我们的估计是,下面我们设,这个矩阵看上去性质就很好.它事实上显然有如下的性质:

1. .
2. .
3. .
4. 的特征值只有和.
5. 半正定.
6. .
7. .

那么就有: 这就给出了是的无偏估计量.

这个估计有多准呢?来看的情况,此时回忆到服从一个多维高斯分布.考虑正交对角化给出,由于旋转不变性,实际上就是个独立同分布服从标准正态分布的随机变量,于是.顺便一提,这里可以看出和实际上依赖的东西是正交的.它们事实上互相独立.

最后,当我们拿到一个新的向量的时候,观察此时的估计值,显然有以及.

不过上面这些分析都没太给出定性的结果.现在让我们来看.它实际上解释了总平方和中,回归平方和所占的比例.

岭回归

考虑最小化.

TODO

Lasso回归

最小化.