概率期望 学习笔记

基础知识

概率定义

\(P(A)\) 为事件 \(A\) 发生的概率， \(P(A|B)\) 为在 \(B\) 事件发生的前提下 \(A\) 事件发生的概率。

概率性质

1. 加法公式：\(A,B\) 独立，则 \(P(A\or B)=P(A)+P(B)\)。（ \(P(A\or B)\) 就是 \(A\) 发生或者 \(B\) 发生）

   广义加法公式：\(A,B\) 任意，则 \(P(A\or B)=P(A)+P(B)-P(A\and B)\)。（ \(P(A\and B)\) 就是 \(A\) 发生且 \(B\) 发生）

2. 乘法公式：

   \(A,B\) 独立， \(P(A*B)=P(A)*P(B)\)。

   \(A,B\) 任意，\(P(A*B)=P(A)*P(B|A)=P(B)*P(A|B)\)。

3. 全概率公式、贝叶斯定理……（略）

期望定义

\(E(A)\)。

期望性质

1. 若 \(A\) 是事件， \(C\) 是常数，则 \(E(CA)=C*E(A)\)

   证明：

   设 \(A\) 的多个随机变量为 \(Ca_1,Ca_2...Ca_n\)，对应出现的概率为 \(p_1,p_2...p_n\)，则有：

   \[E(CA)=\sum\limits_{i=1}^n*(Ca_ip_i)=C\sum\limits_{i=1}^n*(a_ip_i)=C*E(A)

   \]

2. \(A,B\) 任意，则 \(E(A+B)=E(A)+E(B)\)。
3. \(A,B\) 独立，则 \(E(AB)=E(A)E(B)\)。
4. 期望等于所有的方案数的贡献除以方案数。

票券收集问题

题意

[链接](SP1026 FAVDICE - Favorite Dice - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

有 \(n\) 种票券，每次等概率抽取一张票券，求抽到所有 \(n\) 种票券的抽取次数的期望。

解法 1

如果手上已经有 \(i-1\) 种票券，

则 \(\large P(取一个票券为新票券)=\frac{n-i+1}{n}\)，

则 \(\large E(取到新票券)=\frac{1}{P(...)}=\frac{n}{n-i+1}\)，

则总期望为 \(\large\sum\limits_{i=1}^n\frac{n}{n-i+1}=\sum\limits_{i=1}^n\frac{n}{i}\)。

解法 2

期望 DP ！！

设 \(f_i\) 为取了 \(i\) 种票券后，还要去多少票券才能集齐的期望。

显然 \(f_n=0\)，考虑逆推。

考虑到抽到 \(i\) 种票券后再抽一个是新票券的概率是 \(\Large \frac{n-i}{n}\) ，旧票券概率是 \(\Large \frac i n\)，则有方程 \(\Large f_i=\frac{n-i}{n}f_{i+1}+\frac i n f_i+1\)。（加一是因为一定要投一次）。

\[\frac{n-i}nf_i=\frac{n-i}nf_{i+1}+1\\

f_i=f_{i+1}+\frac{n}{n-i}\\

f_i=f_{i+2}+\frac n {n-i-1}+\frac n {n-i}\\

...\\

f_0=\sum \frac{n}{n-i+1}=\sum \frac n i

所以答案为 \(\Large \sum \frac n i\)。

走图1

[链接](P4316 绿豆蛙的归宿 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

有边权无向图 \(G\)，从 \(1\) 出发到 \(n\)，在一个点会等概率选择一个出度并走去下一个点，求到 \(n\) 经过的边权和的期望。（保证从 \(1\) 能走到任何点，任何点都能走到 \(n\)）。

解法

设 \(f_i\) 为 \(i\to n\) 的期望路径长。显然 \(f_n=0\)。

那么设 \(i\) 点出度为 \(k\)，有 \(f_i=\frac1 k(\sum f_v+w_E)\)。

然后拓扑或 dfs 决定更新顺序。

走图2

有无向图 \(G\)，求随机选择一条路径走过的边数的期望。

用期望性质4，设 \(sum\) 为所有路径长度总和，\(cnt\) 为路径个数。