概率 & 期望

概率 & 期望

古典概型（离散概率）

考虑在有限的总事件中符合方案的事件个数。

$P(A):=\frac{|A|}{|\Omega|}$

条件概率

在 $B$ 条件下 $A$ 发生的概率写作 $Pr[A|B]$

$Pr[A|B] = \frac{Pr[A\bigcap B]}{Pr[B]}$

独立概率

$Pr[A|B] = Pr[A] \\ Pr[A\bigcap B] = Pr[A] \times Pr[B]$

贝叶斯定理

$Pr[A\bigcap B] = Pr[A]Pr[B|A] = Pr[B]Pr[A|B]$

三门问题

一个简单的思路，我们考虑第一次选择的门正确的概率为 $\frac{1}{3}$，其余两扇门正确的总概率则为 $\frac{2}{3}$，那么我们换门实际上得到是 $\frac{2}{3}$ 的概率。所以换门正确概率大于不换门。

离散期望

$E(X) = \sum_{k=1}^{\infty} X_k P_k$

连续非负随机期望

$E(X) = \sum_{k = 1}^{\infty} P(X \geq k)$

期望线性性

$E(aX + bY) = a\cdot E(X) + b \cdot E(Y)$

但 $X,Y$ 相互独立时

$E(X\cdot Y) = E(X) \cdot E(Y)$

方差期望

$E(X-E(X))^2 = E(X^2 - 2 X \cdot E(X) + E^2(X)) \\ =E(X^2) - 2E^2(X) + E^2(X) \\ =E(X^2) - E^2(X)$

Ehrenfest 模型

考虑对于点 $i$ 随机游走到 $i-1$ 的概率为 $\frac{i}{n}$，到 $i + 1$ 的概率为 $\frac{n-i}{i}$，无法跨越边界。

考虑从边缘开始列式，令 $f_i$ 表示走到第 $i$ 个位置的概率

$f_0 = \frac{1}{n} f_1 \\ f_1 = f_0 + \frac{2}{n} f_2 \\ \cdots$

高斯消元后我们易知

$f_i = \frac{n !}{(n-i)! i!} f_0 \\ f_i = \dbinom{n}{i} f_0$

考虑到所有事件概率和为 $1$，故 $f_0 = (\sum \dbinom{n}{i})^{-1}$，即 $f_0 = 2^{-n}$，依此可以解得所有 $f_i$。

例题Ⅰ

求随机排列的上升序列长度。

考虑离散期望，考虑第 $j$ 位放 $i$ 对答案的贡献，则原式可表示为

$\frac{1}{n!}\sum_{i=1}^{n}\sum_{j=1}^{i}\dbinom{i-1}{j-1}\cdot (j-1)! \cdot (n-j)!$

通过拆分化简组合数恒等式得到

$\sum_{i=1}^{n} \frac{1}{i} \approx \ln{n}$

另外，我们发现对于当前位置填数是否会产生贡献，取决于此时的前缀 max 值。那么对于前缀 max 值为 $i$ 的情况，我们此时填数会对答案产生贡献的概率为 $\frac{1}{n-i}$，所以期望长度为 $\sum \frac{1}{i} \approx \ln{n}$。

SRM 409 900PTS

虽然不知道是哪里的题。

每次操作随机选取一个点对，将他们所组成的矩形染色。$k$ 次操作后求被染色格子的期望数。

此时我们考虑对于每个格子的期望贡献。令当前考虑到 $(i,j)$ 处的格子，那么当所有的点对都不存在：其中一个点位于矩形 $(1,1,i,j)$ 中，另一个点位于矩形 $(i,j,n,n)$ 中时，那么他的贡献为 $0$，否则为 $1$。

$k$ 次操作等价于 $p^k$。简单容斥，时间复杂度为 $\text{O}(nm\log{k})$。感觉可以优化。