前言·参考资料

这里介绍 OI 中常见的简化了的离散概率理论。

很多初学者觉得概率期望难， 大多数情况下并不是初学者智商上的锅， 是信息源质量奇差的锅， 当然本文就是那些傻逼信息源的其中之一……

参考资料：

《浅析信息学竞赛中概率论的基础与应用》胡渊鸣 （写得不好 ，相互独立的离散期望的乘积等于乘积的期望的证明有大的漏洞）

《具体数学》 正道的光， 我认为最好的教程

《算法竞赛进阶指南》主要习题来源

《算法竞赛入门经典 训练指南》主要习题来源

概率

定义

把一个随机实验的某种可能结果称为 样本点， 所有样本点构成的集合称为 样本空间， 通常记为 $\Omega$ (\Omega) 。一个 随机事件 是样本空间的一个子集， 记所有随机事件的集合为 $F$ 。

记概率测度 $P : F \rightarrow \Bbb R$ ， 其需要满足以下三条公理：

1.对于任意事件 $A$ ， 有 $P(A) \ge 0$

2.$P(\Omega) = 1$

3.对于事件 $A$ 和 $B$ ， 若 $A \cap B = \emptyset$ ， 则 $P(A\cup B) = P(A) + P(B)$

条件概率

记事件 $B$ 发生的前提下， 事件 $A$ 发生的概率为 $P(A\mid B)$ 。
$$ P(A \mid B) = \dfrac{P(AB)}{P(B)} $$
$P(A\cap B)，$$P(AB)$ ， $P(A,B)$ 都表示事件 $A$ 和事件 $B$ 同时发生的概率。

全概率公式

如果 $B_1 \cdots B_k$ 是对样本空间的一个划分， 那么
$$ P(A) = \sum_{1\le i \le k} P(A\mid B_i) P(B_i) $$

贝叶斯(Bayes)公式

由于 $P(A\mid B)P(B) = P(AB) = P(B\mid A)P(A)$ ， 得到：
$$ P(A\mid B) = \dfrac{P(B \mid A)P(A)}{P(B)} $$

期望

随机变量

函数 $X : \Omega \rightarrow \Bbb R$ 被称为一个随机变量。

随机变量的期望

对于一个随机变量 $X$ ， 定义其期望为
$$ E[X] = \sum_{\omega \in \Omega} P(\omega)X(\omega) $$
对于 $\{\omega\mid \omega\in \Omega, X(\omega)=x\}$ ， 可以记为 $X=x$ 。

显然 $E[X]$ 也可以表示为
$$ \sum_{x \in X(\Omega)}x\sum_{\omega \in X=x} P(\omega) $$
$X(\Omega)$ 是随机变量 $X : \Omega \rightarrow \Bbb R$ 的值域。

$\sum\limits_{\omega \in X=x} P(\omega)$ 可以写成 $P(X=x)$ 。

随机变量的独立性和两个随机变量乘积的期望

对于两个随机变量 $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$ 相互独立。

对于两个随机变量 $X_1$ 和 $X_2$ ， 它们的积 $X_1X_2$ 是一个随机变量 $X_1X_2 : \Omega \rightarrow \Bbb R$ ， 满足 $(X_1X_2)(\omega) = X_1(\omega)X_2(\omega)$ 。

两个独立的随机变量的积的期望等于这两个随机变量期望的积， 证明如下：
$$ E[X_1X_2] = \sum_{\omega\in\Omega}X_1(\omega)X_2(\omega)P(\omega)$$
$$=\sum_{x_1\in X_1(\Omega)} \sum_{x_2 \in X_2(\Omega)} x_1x_2 P(X_1=x_1,X_2=x_2)$$
$$= \sum_{x_1\in X_1(\Omega)} \sum_{x_2 \in X_2(\Omega)} x_1x_2 P(X_1=x_1)P(X_2=x_2)$$
$$= E[X_1]E[X_2]$$

期望的线性性

对于两个随机变量 $X_1$ 和 $X_2$ ， 它们的和是一个随机变量 $X_1+X_2 : \Omega \rightarrow \Bbb R$ ， 满足 $(X_1+X_2)(\omega) = X_1(\omega) + X_2(\omega)$ 。

不管两个随机变量 $X_1$ 和 $X_2$ 是否独立， 总有：
$$ E[\alpha X_1 + \beta X_2] = \alpha E[X_1] + \beta E[X_2] $$
证明如下：
$$E[X_1+X_2] = \sum_{\omega\in\Omega} P(\omega)(X_1+X_2)(\omega)$$
$$= \sum_{\omega\in\Omega} P(\omega)[X_1(\omega)+X_2(\omega)]$$
$$= \sum_{\omega\in\Omega} P(\omega)X_1(\omega)+\sum_{\omega\in\Omega} P(\omega)X_2(\omega)$$
$$= E[X_1] + E[X_2] \tag{1}$$

$$E[cX] = \sum_{\omega\in\Omega} P(\omega)cX(\omega) = cE[X] \tag{2}$$

全期望公式

不会证。也不知道是啥。

训练指南里给出的一个定义是：把所有情况不重不漏分成若干类， 每类计算期望， 然后按概率加权求和。似乎很显然， 以后再证。

题目

UVA11427 玩纸牌

每晚都玩纸牌， 单局游戏获胜的概率是 P， 每次游戏结束后， 计算获胜局数和总局数的比， 如果严格大于 P 就睡觉， 明晚继续玩。 每晚最多玩 n 局， 如果第 n 局结束后， 胜局比还是不超过 P， 就再也不玩纸牌了。计算玩纸牌次数的期望。

首先计算每晚再也不玩纸牌的概率 Q 。设 f(i,j) 表示前 i 局胜局比都不超过 P， 一共获胜 j 局的概率， 有：f(i,j) = f(i-1,j)(1-P) + f(i-1,j-1)P (当 j/i<=p时)， f(i,j) = 0 (其他情况)， 边界为 f(0,0)=1, f(0,1)=0。 则 Q = $\sum_if(n,i)$ 。

设随机变量 X 为玩游戏的天数， 则：

$$E[X] = Q + 2Q(1-Q) + 3Q(1-Q)^2 + \cdots + kQ(1-Q)^{k-1} + \cdots$$

$$E[X]/Q - E[X] (1-Q)/Q = (1-Q)+(1-Q)^2+(1-Q)^3+\cdots = E[X] = 1/Q$$

UVA11762 得到 1

给出一个整数 N， 每次在不超过 N 的素数中随机选择一个 P， 如果 P | N， 则把 N 变成 N/P， 否则 N 不变。 问期望多少次把 N 变成 1？

设 f(i) 为当前数为 i 时期望多少次变成 1 。p(i) 为不超过 i 的素数有多少个， g(i) 为不超过 i 且是 i 的约数的素数有多少个。

$$f(i) = 1+\frac{p(i)-g(i)}{p(i)}f(i) + \sum_{d是i的素因子} \frac{1}{p(i)}f(\frac{i}d)$$

$$[1-\frac{p(i)-g(i)}{p(i)}]f(i) = 1 + \sum_{d是i的素因子} \frac{1}{p(i)}f(\frac{i}d)$$

$$f(i) = \frac{p(i)}{g(i)}[ 1 + \sum_{d是i的素因子} \frac{1}{p(i)}f(\frac{i}d)]$$

$$f(i) = {p(i)+\sum\limits_{d是i的素因子} f(\frac{i}d) \over g(i)}$$