【数学】概率与期望

· · 个人记录

本篇博文将对概率与期望进行讲解。

Part 1. 概率

Part 1.1 概念

定义 P(A) 表示事件 A 的发生概率。

例如，若事件 A 表示抛一枚硬币正面朝上，那么由生活常识可得 P(A)=\dfrac{1}{2}。

Part 1.2 公式

一个小练习：P(\overline{A})=0.3,P(B)=0.4,P(A\overline{B})=0.5,P(B|(A\cup \overline{B}))=?

拆一下式子：

P(B|(A\cup \overline{B}))=&\dfrac{P(B\cap(A\cup \overline{B}))}{P(A\cup \overline{B})} \\=&\dfrac{P(A\cap B)}{P(A)+P(\overline{B})-P(A\cap\overline{B})} \\=&\dfrac{P(A\cap B)}{0.7+0.6-0.5} \\=&\dfrac{P(A\cap B)}{0.8} \end{aligned}

然后注意到 P(A)-P(A\cap B)=P(A\cap\overline{B})，代值可得 P(A\cap B)=0.2，所以答案是 \dfrac{0.2}{0.8}=\dfrac{1}{4}。

Part 2. 期望

Part 2.1 概念

期望是指在对于 X 取值有限的情况，设其取值为 x_1,x_2,x_3,\cdots,x_n，则 X 的期望为 E(x)=\sum\limits_{i=1}^n x_i\times P(X=x_i)。

Part 2.2 公式与性质

E(x)=&\sum\limits_{i=1}^\infin i\times P(x=i) \\=&\sum\limits_{i=1}^\infin P(x=i)\sum\limits_{j=1}^i1 \\=&\sum\limits_{j=1}^{\infin}\sum\limits_{i=j}^\infin P(x=i) \\=&\sum\limits_{j=1}^{\infin} P(x\ge j) \end{aligned}

引入：抛一枚硬币正面次数朝上的期望？显然是 0.5。

抛两枚硬币正面朝上次数的期望？\dfrac{1}{4}\times 2+\dfrac{2}{4}\times 1+\dfrac{1}{4}\times 0=1。

抛三枚？手求一下发现是 1.5。

发现抛两枚硬币的期望值是一枚的两倍，抛三枚硬币的期望值是一枚的三倍，这是巧合吗？

对于两个任意随机变量 X,Y，有 E(X+Y)=E(X)+E(Y)。对于随机变量 X 与常数 k，有 E(kX)=E(X)\cdot k。由此可得上面的情况并非巧合。

对于两个独立的随机变量 X,Y，有 E(XY)=E(X)\cdot E(Y)。

对于两个随机变量 X,Y，E(X|Y=y_i) 表示当 Y=y_i 时 X 的期望。

E(E(X|Y))=E(X)

Part 2.3 例题

设随机变量 S=\max\limits_{i=1}^n \langle X_i\rangle，则我们要求的 E(S) 可以化为：

E(S)=\sum\limits_{i=1}^m P(S=i)\times i

使用前缀和技巧，P(S=i)=P(S\le i)-P(S\le i-1)，然后 P(S\le j)=\langle X_i\rangle_{i=1}^n\le j=(\dfrac{j}{m})^n，所以代回原式就可得到：

E(S)=\sum\limits_{i=1}^m ((\dfrac{i}{m})^n-(\dfrac{i-1}{m})^n)\times i=m-\dfrac{1}{m^n}\sum\limits_{i=1}^{m-1}i^n \end{aligned}

由题可得 E(x)=\sum\limits_{i=1}^\infin P(x=i)i。

同样是利用前缀和思想可得 E(x)=\sum\limits_{i=1}^\infin (P(x\ge i)-P(x\ge i+1))i

代回原式可得 $E(x)=\sum\limits_{i=1}^\infin ((1-p)^{i-1}-(1-p)^i)i=\sum\limits_{i=0}^\infin (1-p)^i$。 根据几何级数求和公式 $s=\dfrac{a}{1-r}$（其中 $a$ 为首项，$r$ 为公比）可得 $E(x)=\dfrac{1}{1-(1-p)}=\dfrac{1}{p}$。 - 箱子里有 $n$ 个球 $1,2,\cdots,n$，每次取出一个后放回，取 $m$ 次，求取出数字之和的期望。 由于会放回所以取球相互独立，一次取球的期望是 $E(x)=\sum\limits_{i=1}^n P(x=i)i=\dfrac{n+1}{2}$，答案就是 $\dfrac{m(n+1)}{2}$。 - 箱子里有 $n$ 个球 $1,2,\cdots,n$，每次取出一个后不放回，取 $m$ 次，求取出数字之和的期望。 相当于从 $n$ 个球中选 $m$ 个，每个球被选到的概率是 $\dfrac{m}{n}$，答案还是 $\dfrac{m(n+1)}{2}$。 - 箱子里有 $n$ 个球 $1,2,\cdots,n$，每次取出一个放回并添加一个相同的球，取 $m$ 次，求取出数字之和的期望。 每个球被取出的概率仍然是相同的，因此答案还是 $\dfrac{m(n+1)}{2}$。 - 在一条 $n$ 个点的链上随机游走，求从一端走到另一端的期望步数。 设 $E(i)$ 表示处在第 $i$ 个点走到第 $i+1$ 个点的期望步数，那么显然有 $E(1)=1,E(i)=\dfrac{1}{2}+\dfrac{1}{2}(E(i-1)+E(i)+1)(i>1)$，即 $E(i)=E(i-1)+2$。 那么答案就是 $E(S)=\sum\limits_{i=1}^{n-1}E(i)$，但算出来就会发现 $E(S)=(S-1)^2$。 - 在一张 $n$ 个点的完全图上随机游走，求从点 $1$ 到点 $n$ 的期望步数。 相当于链上乱跳（但不能跳自己），则 $E=\dfrac{1}{n-1}+\dfrac{n-2}{n-1}E+1$，解得 $E=n$。 - 在一张 $2n$ 个点的完全二分图上随机游走（每边 $n$ 个点），求从点 $1$ 到点 $n$ 的期望步数。 $E_1$ 表示当前点与终点在同侧的期望， $E_2$ 表示当前点与终点在异侧的情况，那么 $E_1=E_2+1,E_2=\dfrac{1}{n}+\dfrac{n-1}{n}(E_1+1)$，解得 $E_1=2n,E_2=2n-1$。 ### Part 3. 例题 - [CF1823F](https://www.luogu.com.cn/problem/CF1823F) 给定 $n$ 个点的一棵树，求从 $s$ 走到 $t$ 每个点的期望经过次数。 设 $f_u$ 表示第 $u$ 个点的期望经过次数，则有（$deg_u$ 表示 $u$ 的度数） $$ f_u=\begin{cases}1,&u=t \\1+\sum\limits_{(u,v)\in E\wedge v\neq t}\dfrac{f_v}{deg_v},&u=s\\ \sum\limits_{(u,v)\in E\wedge v\neq t}\dfrac{f_v}{deg_v},&\operatorname{otherwise}\end{cases}$$ 高斯消元求解是 $O(n^3)$ 的，但因为这是在树上所以我们有更优的做法。 考虑设 $f_u=A_uf_{fa_u}+B_u(u\neq t)$，我们的目标就是求解 $A_u$ 与 $B_u$。 将上面的 $u=s$ 和 $\operatorname{otherwise}$ 的两个式子化为一个，再把 $f_{fa_u}$ 提出来，得： $$\begin{aligned} f_u=&\dfrac{f_{fa_u}}{deg_{fa_u}}+\sum\limits_{(u,v)\in E\wedge v\neq t\wedge v\neq fa_u}\dfrac{f_v}{deg_v}+[u=s]\\ =&\dfrac{f_{fa_u}}{deg_{fa_u}}+\sum\limits_{(u,v)\in E\wedge v\neq t\wedge v\neq fa_u}\dfrac{A_vf_u+B_v}{deg_v}+[u=s]\\ =&\dfrac{f_{fa_u}}{deg_{fa_u}}+\sum\limits_{(u,v)\in E\wedge v\neq t\wedge v\neq fa_u}\dfrac{A_v}{deg_v}f_u+\sum\limits_{(u,v)\in E\wedge v\neq t\wedge v\neq fa_u}\dfrac{B_v}{deg_v}+[u=s] \end{aligned}$$ 然后移项： $$\begin{aligned} (1-\sum\limits_{(u,v)\in E\wedge v\neq t\wedge v\neq fa_u}\dfrac{A_v}{deg_v})f_u=&\dfrac{f_{fa_u}}{deg_{fa_u}}+\sum\limits_{(u,v)\in E\wedge v\neq t\wedge v\neq fa_u}\dfrac{B_v}{deg_v}+[u=s]\\ \end{aligned}$$ 这样你只要把左边除过去就能得到 $A_u$ 和 $B_u$ 了。时间复杂度是 $O(n\log p)$ 的。 - [P1654](https://www.luogu.com.cn/problem/P1654) 考虑如何维护 $(x+1)^3$，可以用二项式定理拆成 $1,x,x^2$ 的形式，分别维护即可。 - [P3750](https://www.luogu.com.cn/problem/P3750) 考虑最优操作方法，显然每次将最高位亮着的灯泡熄灭，这样一定是最优的。 然后设 $E(i)$ 表示从最多按 $i$ 次开关到最多按 $i-1$ 次开关的期望步数，显然若 $i\le k$，则 $E(i)=1$。若 $i>k$，则 $n$ 个开关中有 $i$ 个按了是能减少操作次数的，所以 $E(i)=\dfrac{i}{n}+\dfrac{n-i}{n}(E(i+1)+E(i)+1)$，解得 $E(i)-\dfrac{n-i}{i}E(i+1)+\dfrac{n}{i}$，注意当 $i=n$ 时 $E(i)=1$，因为无论你按哪个开关都能减少操作次数。 那么设初始最多按 $x$ 次关掉所有灯，则 $ans=n!\sum\limits_{i=1}^xE(i)$。 - [CF518D](https://www.luogu.com.cn/problem/CF518D) 显然第 $t$ 秒未上电梯的人中会有 $p$ 的概率上电梯，那么第 $i$ 秒电梯中为 $j$ 个人的概率是 $f_{i,j}=f_{i-1,j-1}\times p+f_{i-1,j}\times(1-p)$，期望可以通过概率去算。注意只有 $n$ 个人。 - [P4316](https://www.luogu.com.cn/problem/P4316) 考虑设 $f_i$ 表示从 $i$ 点走到终点的期望距离，显然 $f_n=0$，考虑建反边转移，那么 $f_i=\sum\limits_{(v\to i)\in E}\dfrac{f_v+w_{v\to i}}{deg_i}$，答案即为 $f_1$。 - [P3232](https://www.luogu.com.cn/problem/P3232) 发现不好直接求每条边的期望经过次数（高斯消元时间复杂度 $O(n^3)$，直接跑边会炸）于是改为求每个点的期望经过次数 $F_u$，那么对于每条边 $(u,v)$，它的期望经过次数 $E_i=\dfrac{F_u}{deg_u}+\dfrac{F_v}{deg_v}$，直接暴力算即可。至于分配编号按期望经过次数大小排序贪心分配即可。 - [P4550](https://www.luogu.com.cn/problem/P4550) 记 $f_i$ 表示当前手里有 $i$ 张邮票达到目标的期望次数，那么有 $f_i=\dfrac{n-i}{n}f_{i+1}+\dfrac{i}{n}(f_i+1)$，解得 $f_i=f_{i+1}+\dfrac{n}{n-i}$。 记 $g_i$ 表示当前手里有 $i$ 张邮票达到目标的期望价格，那么有 $g_i=\dfrac{n-i}{n}(g_{i+1}+f_{i+1}+1)+\dfrac{i}{n}(g_i+f_i+1)$，解得 $g_i=g_{i+1}+f_{i+1}+\dfrac{i}{n-i}f_i+\dfrac{n}{n-i}$。 那么 $f_n=g_n=0$，答案即为 $g_0$。