本文主要参(chao(shan))考(xi(jian))自
《浅析信息学竞赛中概率论的基础与应用》--胡渊鸣
概率就是对事情发生的可能性的度量。
竞赛用到的初等概率论有三个主要内容，样本空间\(\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)\)为概率空间。
条件概率就是已知一些条件之后，概率就会发生变化。例如：
有\(\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)\)。
设\(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\%\)
全概率公式在概率论中有很重要的作用，在做题的时候也经常会用到，概率论中很多问题都涉及这个公式。
考虑\(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\%\]
期望是概率题中又一个常出现的概念，他是随机变量的一个属性。
随机变量(random variable)实际上并不随机，也不是一个变量，而是一个定义在样本空间\(\Omega\)上的一个确定的实值函数。
函数\(X : \Omega \Rightarrow \mathbb R\)是一个随机变量
在大多数情况下，有了随机变量就可以抛弃对原本样本空间的关注，而是集中于对于每个实值，随机变量能取到的概率。这实际是对样本空间的一个划分，将其随机变量值相同的事件划为一类。
期望是对随机变量在平均情况下的一种刻画。对于一个随机变量\(X\)，其期望为：
\[E[X]=\sum_\omega X(\omega)P(\omega)=\sum_k kP(X=k)\]
其中\(X=k\)表示的是\(\{\omega|\omega\in\Omega,X(\omega)=k\}\)这个集合。
前一个式子是枚举每一个事件，而后一个式子就是对样本空间进行了划分。
对于两个随机变量\(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 . \]
不论随机变量是否独立，总有：
\[E[\alpha X_1+\beta X_2]=\alpha E[X_1]+\beta E[X_2]\]
这个性质非常常用，下面就是一道例题：
给定一颗树，从根节点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！
首先来考虑一个与条件概率相似的问题，在一些条件下，如已知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\))中，等概率抽取一个人，求其成绩的期望值。
第一种方法，其期望值为全年级同学的平均分；
第二种方法，每个班统计平均分，然后按照抽到每个班的概率进行加权求和。
第二种方法实质上就是新建了一个随机变量表示抽到的同学的班级，通过这个新的随机变量将原来的样本空间进行了划分。
概率转移网络是一个有向网络，由点集(状态集)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]\)的概率消失。
下面来看两道例题：
两个人参观博物馆，博物馆由\(n(n\le 22)\)个房间和连接房间的一些走廊构成。然而，两个人忘记了约定在哪里集合，于是他们决定进行随机移动。每一次移动时也有\(p_i\)的概率留在原来的房间，有\(1-p_i\)的概率从当前的房间连接的走廊中随机选择一条。只有当两个人同时位于同一个房间时才算相遇，两个人不能在走廊里相遇。显然，经过足够的时间后，他们一定能够相遇。现在两个人分别在\(a,b\)两个房间，你需要求的就是对于每个房间i，最终在房间i相遇的概率。
由于有两个人，所以我们的状态要设置为一个二元组\((u,v)\)其中，\(u,v\)分别是第一个人和第二个人所在的位置。显然有\(n^2\)个状态，初始状态\(v_0=(a,b)\)，终止状态集合为\(\{(x,x)|x\in [1,n]\}\)，状态转移矩阵也很容易得出。
如果把终止状态集合中的元素
原文：https://www.cnblogs.com/shanxieng/p/10455847.html