概率简介

概率，是我们日常生活中的常见概念。
它可以实际的理解为一个事情发生的频率。

例如：
筛\(30\)次色子，\(4\)次筛出\(10\)。
我们就可以认为筛出\(4\)的频率，即筛出\(4\)这一事件的概率为\(\frac{10}{30}=\frac{1}{3}\)。
显然当筛的次数较小时，其频率会有相对大的起伏。
但随着筛的次数的增大，其频率就会逐渐趋向于稳定，并最终变为一个定值。

因此这引出了我们对于概念的定义：
我们定义一个随机变量\(x\)的概率为\(=\frac{x发生的次数}{总实验次数}\)。
记做\(P(x)\)。
严谨来说，事件的概率会是一个定值，且是由上述很多个简单到无法继续分解的互斥(即\(A\)发生时\(B\)不发生，\(B\)发生时\(A\)不发生)随机变量组成的。

加法法则

公式：
\(P(A \cup B)=P(A)+P(B)-P(AB)\)。
推论：
对于互斥事件\(A\)与\(B\)(即\(A\cap B=\phi\))。
有:
\(P(AB)=0\)。
\(P(A \cup B)=P(A)+P(B)\)。

条件概率

记在\(B\)发生的条件下\(A\)发生的概率,记为:\(P(A|B)\)。
额外:
当\(A\)与\(B\)无关时，\(P(A|B)=P(A)\)。
公式：
\(P(A|B)=\frac{P(AB)}{P(B)}(P(B)\neq 0)\)。
推论(乘法法则)：
\(P(AB)=P(A|B)\times P(B)=P(B|A)\times P(A)\)

乘法法则

见上：
\(P(AB)=P(A|B)\times P(B)=P(B|A)\times P(A)\)

全概率公式

设有互斥事件\(A_1\)~\(A_n\)。若\(\sum_{i=1}^n A_i=\Omega\)(称\(A\)构成一个完备事件组)
则对于任一事件\(B\)有公式：
\(P(B)=\sum_{i=1}^n P(B|A_i)\times P(A_i)\)。
(感性的理解为所有情况下\(B\)发生的概率)

OI概率应用

知名\(OIer\)鲁迅曾经曾经说过鲁迅：我没说过：

概率顺推，期望逆推。

这并非没有道理的。
以下是概率问题的推导：

题面

给出一张\(n\)个点\(m\)条边的有向无环图，起点为\(1\)，终点为\(n\)，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

\(hhx\)从起点出发，走向终点。到达每一个顶点时，如果该节点有\(k\)条出边，\(hhx\)可以选择任意一条边离开该点，并且走向每条边的概率为\(\frac{1}{k}\)。现在\(hhx\)想知道，经过每个节点的概率是多少？

顺推

设事件\(A_i\)为经过\(i\)。
考虑递推，很容易想到将\(P(A_i)\)用全概率公式展开给入边点集。
但是一个痛苦的问题是入边的点之间可能相互有连边，并不互斥。
考虑添加限制使其互斥。
设事件\(B_{j,k}\)为第\(k\)步到\(j\)。
此时\(B\)事件互斥。
推导：
首先展开给入边点集，然后枚举\(k\)展开给每一步。
我们考虑\(k\)的边界情况：
当\(k=0\)：不可能走到非起点节点。即\(P(B_{j,0}=0)\)。
当\(k=n\): 在最差情况为一条链时，任不可能走到任意节点。即\(P(B_{j,n})=0\)。
所以\(\forall 1\leq k\leq n-1\)等价于\(\forall 0\leq k\leq n\)

显然\(\sum^{k=0}_n P(B_{j,k})\)构成\(P(A_j)\)

倒推

倒推就显得很不靠谱了。
关键的点在于所求的概率的事件为经过而并非去终点，因此无法推导和确定状态。

期望简介

期望可以理解为实验结果的平均权，也可以理解为带权概率和。
感性的理解为某个权在结果中的情况占比的贡献之和。
这也引出了期望的定义式：
对于某随机变量\(x\)，记其期望为\(E(x)\)。
\(E(x)=P(x)\times w\)(其中\(w\)为权)。

期望的线性性

期望的线性性指的是两个随机变量\(X\)和\(Y\)。
有\(E(X+Y)=E(X)+E(Y)\)。
对于额外的常数\(k\)，也有\(E(k\times X)=k\times E(X)\)。
性感的理解这个性质，这里的\(E(X+Y)\)不是交集，也不是并集，可以看做两个单独的事件（尽管他们可能并不互斥）。而期望是个权，权是可以相加的，而这也是概率不具备线性性的原因：他们会互相影响。

条件概率

记在\(B\)发生的条件下\(A\)发生的期望,记为:\(E(A|B)\)。
易知有\(E(A|B)=\frac{E(A)}{P(B)}\)
移项得：
\(E(A|B)\times P(B)=E(A)\)

全期望公式

对于事件\(X\)。
有\(E(X)=P(X)\times w\)。
用全概率公式展开，有：
设\(\sum^{i=1}_n B_i构成一个完备事件组\)
\(E(X)=\sum^{i=1}_n P(B_i)\times P(X|B_i)\times w\)
这一步可以感性理解为\(w\)只于\(X\)有关，而\(P(X|B_i)\)相当于又补了个概率：
\(E(X)=\sum^{i=1}_n P(B_i)\times E(X|B_i)\)

OI期望应用

题面

给出一张\(n\)个点\(m\)条边的有向无环图，起点为\(1\)，终点为\(n\)，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

\(hhx\)从起点出发，走向终点。到达每一个顶点时，如果该节点有\(k\)条出边，\(hhx\)可以选择任意一条边离开该点，并且走向每条边的概率为\(\frac{1}{k}\)。现在\(hhx\)想知道，到达终点经过的边数的期望是多少？

顺推

设\(A_i\)为起点到\(i\)的步数,\(B_{j,k}\)为\(k\)步走到\(j\)。
其中\(k\)的范围在概率已经证过，不再赘述。
\(E(A_i)=\sum^{k=0}_nk\times P(B_{i,k})\)
用之前的概率公式展开得：
\(E(A_i)=\sum^{k=0}_n \sum^{j \in OUT_i}(k\times \frac{P(B_{j,k})}{OUT_j}+\frac{P(B_{j,k})}{OUT_j})\)
\(E(A_i)=\sum^{j \in OUT_i}\frac{E(A_j)+P(A_j)}{OUT_j}\)
然而这样并不方便，因为我们还要求一个概率，这使我们的难度和码量翻倍。

倒推

设\(A_i\)为到终点的步数\(B_{j,i}为j一步到i\)
则有：
\(E(A_i)=\sum^{j \in IN_i} P(B_{j,i})\times E(A_i|B_{j,i})\)
\(E(A_i)=\sum^{j \in IN_i} \frac{E(A_j)+1}{IN_i}\)
\(E(A_i)=\frac{\sum^{j \in IN_i} E(A_j)}{IN_i}+1\)
\(tips:\)关于这里的概率可能有人觉得不对，应该用\(frac{到j方案数}{总方案数}\)但其实，从\(j\)到\(i\)的概率如果不考虑之前的路线，就是等价的。而之前的情况，已经在期望里推过了。