概率期望
本文主要参(chao(shan))考(xi(jian))自
《浅析信息学竞赛中概率论的基础与应用》--胡渊鸣
1.概率
1.1基础知识
概率就是对事情发生的可能性的度量。
竞赛用到的初等概率论有三个主要内容，样本空间\(\Omega\)，事件集合\(F\)，概率测度\(P\)。 常说的事件，是样本空间\(\Omega\)的一个子集。在竞赛中，往往可以认为样本空间\(\Omega\)的每一个子集都是一个事件，所有事件的集合即为\(F\)。概率测度\(P\)是事件集合到实数的一个函数。一个合理的概率测度，需要满足以下三个公理：
对于任意的事件\(A\)，满足\(P(A)\le 1\)
\(P(\Omega)=1\)
对于任意的事件\(A,B,A\cap B=\emptyset\)，满足\(P(A\cup B)=P(A)+P(B)\)
我们称满足条件的三元组\((\Omega,F,P)\)为概率空间。
1.2条件概率
条件概率就是已知一些条件之后，概率就会发生变化。例如：
有\(\alpha\)和\(\beta\)两所大学，\(\alpha\)大学99%是男生，\(\beta\)大学99%是女生(我也要去)，假设两所大学人数相等。从两所学校中抽取一个人，求被选到的人是男生的概率有多么大。
很显然，这个概率就是50%，如果我们又得知了他来自\(\alpha\)大学，那么他是男生的概率就是99%。由此可见，当我们得到了更多的信息后，概率就会发生变化。
如果我们设\(P(A|B)\)为在知道B事件发生的情况后A事件发生的概率，那么
\[P(A|B)=\frac{P(A,B)}{P(B)}\]
其中，\(P(A,B)\)就是\(P(A\cap B)\)，也可写作\(P(AB)\)。
1.3全概率公式
设\(B_1,B_2,\cdots,B_k\)是样本空间的一个划分，那么
\[P(A)=\sum_{i=1}^kP(A|B_i)P(B_i)\]
如前面的例子，\(P(♂)=P(♂|U_{\alpha})P(U_{\alpha})+P(♂|U_{\beta})P(U_{\beta})=99\%\times50\%+1\%\times50\%=50\%\)
全概率公式在概率论中有很重要的作用，在做题的时候也经常会用到，概率论中很多问题都涉及这个公式。
1.4Bayes公式
考虑\(P(A|B)P(B)=P(AB)=P(B|A)P(A)\)，那么把中间去掉，就能得到
\[P(A|B)=\frac{P(B|A)P(A)}{P(B)}\]
把Bayes公式和全概率公式结合起来，可以得到
\[P(A_j|B)=\frac{P(B|A_j)P(A_j)}{\sum_kP(B|A_k)P(A_k)}\]
例如已知选到的人是男生，求他是\(\alpha\)大学的概率。
\[P(U_\alpha|♂)=\frac{P(♂|U_\alpha)P(U_\alpha)}{P(♂|U_\alpha)P(U_\alpha)+P(♂|U_\beta)P(U_\beta)}=\frac{99\%\times50\%}{99\%\times50\%+1\%\times50\%}=99\%\]
2.随机变量与期望
期望是概率题中又一个常出现的概念，他是随机变量的一个属性。
2.1随机变量
随机变量(random variable)实际上并不随机，也不是一个变量，而是一个定义在样本空间\(\Omega\)上的一个确定的实值函数。
函数\(X : \Omega \Rightarrow \mathbb R\)是一个随机变量
在大多数情况下，有了随机变量就可以抛弃对原本样本空间的关注，而是集中于对于每个实值，随机变量能取到的概率。这实际是对样本空间的一个划分，将其随机变量值相同的事件划为一类。
2.2随机变量的期望
期望是对随机变量在平均情况下的一种刻画。对于一个随机变量\(X\)，其期望为：
\[E[X]=\sum_\omega X(\omega)P(\omega)=\sum_k kP(X=k)\]
其中\(X=k\)表示的是\(\{\omega|\omega\in\Omega,X(\omega)=k\}\)这个集合。
前一个式子是枚举每一个事件，而后一个式子就是对样本空间进行了划分。
2.3随机变量的独立性与乘积的期望
对于两个随机变量\(X_1,X_2\)和实数\(x_1\in X_1(\Omega),x_2\in X_2(\Omega)\)，如果有\(P(X_1=x_1,X_2=x_2)=P(X_1=x_1)P(X_2=x_2)\)，就称\(X_1,X_2\)相互独立。
两个相互独立的随机变量的重要性质是其积的期望等于其期望的积。
\[ \left . \begin{array}{ccl} E[X_1X_2]&=&\sum_{x\in(X_1X_2)(\Omega)}xP(X_1X_2=x)\\ &=&\sum_{x\in(X_1X_2)(\Omega)}xP(X_1=x_1)P(X_2=x_2)\\ &=&\sum_{x\in(X_1X_2)(\Omega)}x\sum_{x_1\in X_1(\Omega)}P(X_1=x_1)P(X_2=\frac{x}{x_1})\\ &=&\sum_{x\in(X_1X_2)(\Omega)}\frac{x}{x_1}P(X_2=\frac{x}{x_1})\sum_{x_1\in X_1(\Omega)}x_1P(X_1=x_1)\\ &=&\sum_{x_2\in X_2(\Omega)}x_2P(X_2=x_2)\sum_{x_1\in X_1(\Omega)}x_1P(X_1=x_1)\\ &=&E[X_1]E[X_2] \end{array} \right . \]
2.4期望的线性性
不论随机变量是否独立，总有：
\[E[\alpha X_1+\beta X_2]=\alpha E[X_1]+\beta E[X_2]\]
这个性质非常常用，下面就是一道例题：
Maze (Codeforce 123E)
给定一颗树，从根节点S出发，到叶子节点T停止，求DFS算法的期望步数。其伪代码如下：
DFS(x)
if x == exit vertex then
finish search
flag[x] <- TRUE
random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen
for i <- 1 to length[V] do
if flag[V[i]] = FALSE then
count++;
DFS(y);
count++;分析：
首先，明确样本空间为从S到T的全部路径，期望变量X为路径的长度(加上弹栈的代价)。我们要求的就是\(E[X]\)。
我们构造一些小的随机变量\(X_e\)，其中，e是图上的一条边。\(X_e[\omega]\)就是一条路径经过e的次数。对于\(\forall \omega \in \Omega , X[\omega]=\sum_eX_e[\omega]\)，记为\(X=\sum_e X_e\)。利用期望的线性性，可以得到\(E[X]=\sum_eE[X_e]\)。
如果e在S到T的必经之路上，那么经过次数显然为1，否则为0或2，所以难点就在于求出不在必经之路上的边的期望经过次数。
考虑一条不在必经之路上的边，设距离他最近的在必经之路上的点为u，这条边在u的儿子v对应的子树中，T在u的儿子w对应的子树中。可以发现，\(v\ne w\)，否则最近的点可以是w。那么这条边能否被遍历到就取决于从u先遍历了v还是w，那么就是在边的排列中v是否排在w的前面。而在一个随机排列中，一个元素排在另一个的前面的概率就是\(\frac{1}{2}\)！所以这条边的期望经过次数就是1。
综上，所有边的期望经过次数都是1，那么如果树有n个点，不论树的形状如何，所求的答案都是n-1！
2.5全期望公式
首先来考虑一个与条件概率相似的问题，在一些条件下，如已知A一定发生，样本空间\(\Omega\)上的随机变量\(X\)会如何变化？
如果将这个受约束的随机变量记为\(X|A\),那么
\[P((X|A)=x)=\frac{P(X=x,A)}{P(A)}\]
而另一个更奇怪的公式就是对于两个随机变量\(X,Y\)，\(E[E[X|Y]]=E[X]\)
根据上面的分析，\(X|Y=y\)是在一个新的样本空间\(Y=y\)上的一个随机变量。当我们不指明随机变量\(Y\)的取值时，\(E[X|Y]\)是一个新的随机变量，其期望等于当\(Y\)在各种特殊输出y时，\(E[X|Y=y]\)按照\(P(Y=y)\)加权的和。具体推导过程如下：
\[ \left . \begin{array}{ccl} E[E[X|Y]]&=&\sum_{y\in Y(\Omega)}E[X|Y=y]P(Y=y)\\ &=&\sum_{y\in Y(\Omega)}\sum_{x\in X(\Omega)}xP(X=x|Y=y)P(Y=y)\\ &=&\sum_{y\in Y(\Omega)}\sum_{x\in X(\Omega)}xP(X=x,Y=y)\\ &=&\sum_{x\in X(\Omega)}x\sum_{y\in Y(\Omega)}P(X=x,Y=y)\\ &=&\sum_{x\in X(\Omega)}x\sum_{y\in Y(\Omega)}P(X=x|Y=y)P(Y=y)\\ &=&\sum_{x\in X(\Omega)}xP(X=x)\\ &=&E[X] \end{array} \right . \]
举一个例子，在全年级同学(样本空间\(\Omega\))中，等概率抽取一个人，求其成绩的期望值。
第一种方法，其期望值为全年级同学的平均分；
第二种方法，每个班统计平均分，然后按照抽到每个班的概率进行加权求和。
第二种方法实质上就是新建了一个随机变量表示抽到的同学的班级，通过这个新的随机变量将原来的样本空间进行了划分。
3.概率转移网络上的相关问题
概率转移网络是一个有向网络，由点集(状态集)V,转移概率矩阵\(G:V\times V \rightarrow [0,1]\)，以及起点\(v_0\)组成。\(\forall u\in V,\sum_v G[u,v]\le1\)。其意义就是在某一个时刻t，当前状态处于\(u\),那么就有\(G[u,v]\)的概率转移到状态\(v\)，还有\(1-\sum_v G[u,v]\)的概率消失。
下面来看两道例题：
3.1例题 Museum（Codeforces 113D）
两个人参观博物馆，博物馆由\(n(n\le 22)\)个房间和连接房间的一些走廊构成。然而，两个人忘记了约定在哪里集合，于是他们决定进行随机移动。每一次移动时也有\(p_i\)的概率留在原来的房间，有\(1-p_i\)的概率从当前的房间连接的走廊中随机选择一条。只有当两个人同时位于同一个房间时才算相遇，两个人不能在走廊里相遇。显然，经过足够的时间后，他们一定能够相遇。现在两个人分别在\(a,b\)两个房间，你需要求的就是对于每个房间i，最终在房间i相遇的概率。
3.1.1 分析
由于有两个人，所以我们的状态要设置为一个二元组\((u,v)\)其中，\(u,v\)分别是第一个人和第二个人所在的位置。显然有\(n^2\)个状态，初始状态\(v_0=(a,b)\)，终止状态集合为\(\{(x,x)|x\in [1,n]\}\)，状态转移矩阵\(G\)也很容易得出。
3.1.2 方法1 ： 迭代
如果把终止状态集合中的元素的转移只有向自己为1，其余全部为0，那么，设\(x^t\)为时间为t时每个状态的概率。显然，t为0时，只有初始状态为1，其余全部为零。\(x^{t+1} = x^t\cdot G\)。那么做k次矩阵快速幂后就可以得到\(x^{2^k}\)。当做的次数足够多时，就可以无限逼近答案。当数据比较弱时有可能能够通过，但是遇到比较强的数据就无能为力了。
3.1.3 方法2 ： 列方程
与上一种方法不同的是，这里我们把终止状态集合中的元素的转移全部设为0，即到达了终止状态后就会消失。
那么我们考虑在消失之前，每个状态的期望经过次数\(E_u\)。很显然，\(E_u=\sum_tx^t_u\)。那么，
\[E_u=x^0_u+\sum_{t\ge 1}x^t_u=x_u^0+\sum_{t\ge 1}\sum_vx^{t-1}_vG[v,u]=x^0_u+\sum_vG[v,u]\sum_{t\ge 0}x^t_v=x^0_u+\sum_vG[v,u]E_v\]
那么我们就得到了\(n^2\)个方程，解之即可。事件复杂度为\(O(n^6)\)
3.2 例题 SDOI2012 走迷宫
这道题建模与上一道题相似。我们把终点的出边删掉，设\(E[X_v]\)是\(v\)点到终点的期望经过步数，显然\(E[X_T]=0\)。那么\(E[X_u]=\sum_vG[u,v]E[X_v]+1\)。
我们想一下为什么这样是对的。我们新设一个随机变量\(Y_u\)表示从\(u\)开始的出边到达的点。这个随机变量是从\(\Omega\)到\(V\)的映射。那么直接用全期望公式\(E[X_u]=E[X_u|Y_u]\)即可。
4. 两个常用不等式
4.1 Markov不等式
对于非负随机变量\(X\)存在：
\[P(X\ge a)\le \frac{E[X]}{a}\]
简单证明：
\[E[X]=\sum_x xP(X=x)\]
把x分为两类：
\[E[X]=\sum_{x\ge a}xP(X=x)+\sum_{x<a}xP(X=x)\]
那么：
\[\frac{E[X]}{a}=\frac{\sum_{x\ge a}xP(X=x)}{a}+\frac{\sum_{x<a}xP(X=x)}{a}\]
因为：
\[\frac{\sum_{x\ge a}xP(X=x)}{a}\ge P(X\ge a),\frac{\sum_{x<a}xP(X=x)}{a}\ge 0\]
所以
\[P(X\ge a)\le \frac{E[X]}{a}\]
这个不等式说明了随机变量表现出一个较大值的概率和它期望的关系，在我们队一个随机变量只知道其期望的时候非常实用。而在大多数情况下等号是取不到的，而且左边会远小于右边。
4.2 Chebyshev不等式
我们称随机变量\(X\)的方差\(Var[X]\)为\(E[(X-E[X])^2]\)，标准差\(\sigma\)为\(\sqrt{Var[X]}\)。
如果我们知道了随机变量的方差，就可以进一步对随机变量以大于某一幅度偏移其期望的概率进行估计。对于随机变量\(X\)和正实数\(a\)，有：
\[P(|X-E[X]|\ge a)\le \frac{Var[X]}{a^2}\]
如果用\(a=c\sigma\)代替可以得到：
\[P(|X-E[X]|\ge c\sigma)\le \frac{1}{c^2}\]
上式表明在仅知道标准差的情况下，随机变量偏移其期望\(c\)倍标准差的概率小于等于\(\frac{1}{c^2}\)。