概率论

约 569 个字预计阅读时间 2 分钟

概率论¶

因为面向ACMer写的，所以不会很严谨

计算某个事件的概率和期望

当概率论和DP复合时，问题转化为图上问题，状态看成点，状态转移看成边

如果该问题无后效性，那么按照拓扑序DP，否则高斯消元

如果纯概率论题，套公式即可

简要概念&公式¶

随机变量¶

值无法预先确定，仅以一定可能性取值的量

按照值的数量分为

离散型，值数量有限

连续型，值数量无限

以下按照这个分类讲述

连续型概率¶

$\forall a，P(X=a)=0$

设随机变量 $X$ ，设密度函数 $f$

$P(a<X\le b)=\int_{a}^bf(x)dx$

密度满足

$\int_{-\infty}^{+\infty}f(x)dx=1$

分布函数 $F(x)$

$F(x)=P(X\le x)=\int_{-\infty}^xf(x)dx$

若 $F(x)$ 处处连续可微，则

$F'(x)=f(x)$

分布函数性质¶

$F(-\infty)=0，F(+\infty)=1$
$F(x)$ 单调非递减

离散型概率¶

发生事件 $A$ 的概率，记做 $P(A)$

加法公式

$P(A\cup B)=P(A)+P(B)-P(A\cap B)$

$P(A\cup B)$ 表示发生A或B的概率

$P(A\cap B)$ 表示同时发生A和B的概率，以下简写为 $P(AB)$

条件概率

$P(B|A)=\frac{P(AB)}{P(A)}$

$P(B|A)$ 表示已经发生 $A$ ，再发生 $B$ 的概率

乘法公式

$P(AB)=P(A)P(B|A)=P(B)P(A|B)$

全概率公式

$P(B)=\sum\limits_{i=1}^nP(A_i)P(B|A_i)$

贝叶斯公式

$P(B_i|A)=\frac{P(B_i)P(A|B_i)}{\sum\limits_{j=1}^nP(B_j)P(A|B_j)}$

连续型期望¶

$E(X)=\int_{-\infty}^{+\infty}xf(x)dx$

离散型期望¶

$E(X)=\sum\limits_{i=1}^nx_iP_i$

期望性质¶

全期望公式

$E(Y)=\sum P(X=a)E(Y|X=a)$

期望的线性性

$E(aX+b)=aE(x)+b$

$E(X+Y)=E(X)+E(Y)$

若 $X，Y$ 独立，则

$E(XY)=E(X)E(Y)$

独立： $P(AB)=P(A)P(B)$

概率DP¶

根据全概率公式，设点 $v$ 的入边的另一个点 $u$

$P(v)=\sum P(u)P(v|u)$

期望DP¶

递推公式¶

$P(X)，E(X)$ 表示

起点到 $X$ 的概率，期望
$X$ 到终点的概率，期望

第二种用的比较多，因为第二种定义的概率常常为 1，方便编写；或者有自环，用第一种定义甚至连初态都不知道

如果有自环，需要移项使得两边没有同样的式子

第二种需要建反图跑DP

第1种定义（统计入边）

$E(Y)=\sum [E(X)+W(X\rightarrow Y)P(X)]P(Y|X)$

第2种定义（统计出边）

$E(Y)=\sum [E(X)+W(Y\rightarrow X)P(Y)]P(X|Y)$

第一种递推公式证明¶

第二种类似

设 $x_i$ 为起点到 $X$ 的入边的另一个点 $Y$ 的路径长度， $p_i$ 为走该路径的概率

有一条 $Y$ 到 $X$ 的边,边权为 $w_j$

定义得

$E(Y)=\sum x_ip_i$

$E(X)=\sum (x_i+w_j)p_iP(X|Y)$

$P(X|Y)$ 提到前面去， $p_i$ 乘法分配律

$E(X)=P(X|Y)\sum x_ip_i+w_jp_i$

求和号可以拆成两个，前面一个就是 $E(Y)$ ， $w_j$ 提到前面去

$E(X)=P(X|Y)[E(Y)+w_j\sum p_i]$

显然后面一个就是 $P(Y)$

$E(X)=P(X|Y)[E(Y)+w_jP(Y)]$

期望和概率的一个联系¶

全集有 n 种数，手上有 i 种数，全集中随机选数

获得新数的概率是 $\frac {n-i}n$

取得新数要取的次数的期望为 $\frac 1p=\frac n{n-i}$

那么获得全集的次数为 $\sum\limits_{i=0}^{n-1} \frac n{n-i}=\sum\limits_{i=1}^{n-1} \frac ni$

Q:为什么期望是概率分之一

A:如果你平均取 n 个球才会出现 1 个红球，也就是说期望是 n，那又可以说成是平均每 n 个球中出现 1 个红球，所以概率是 $\frac{1}{n}$

也可以用DP解释

设 $f_i$ 表示已取到 i 种数，还需要取的次数的期望

可得 $f_{i}=f_{i+1}\times \frac {n-i}n+f_{i}\times \frac {i}n+1$

可得 $f_{i}=f_{i+1}+\frac n{n-i}$

min-max容斥计算期望¶

$max(S)=\sum\limits_{T\subseteq S}min(T)(-1)^{|T|-1}$

max表示满足所有条件的期望，min表示满足至少一个条件的期望