基础知识

期望的线性性质

$E(X + Y) = E(X) + E(Y)$
证明:

$E(X + Y) = \sum\limits_i\sum\limits_jP(X=i \&\& Y=j)(i+j)$
$= \sum\limits_i\sum\limits_jP(X=i \&\& Y=j)i + \sum\limits_i\sum\limits_jP(X=i \&\& Y=j)j$
$=\sum\limits_ii\sum\limits_jP(X=i\&\&Y=j)j+\sum\limits_ij\sum\limits_jP(X=i\&\&Y=j)i$
$=\sum\limits_iP(X=i)i+\sum\limits_jP(Y=j)j$
$=E(x) + E(Y)$

前缀和技巧

有 n 个随机变量X[1…n]，每个随机变量都是从 1…S 中随机一个整数，求 Max(X[1…n]) 的期望

solution

$E(Y)=\sum\limits_{i=1}^SP(Y=i)i=\sum\limits_{i=1}^Si(P(Y\le i) - P(Y \le i - 1))=i({\frac{i}{S}}^n-{\frac{(i-1)}{S}}^n)$

小结论

概率为 $p$ 的事件期望 $\frac{1}{p}$ 后发生。如抛硬币，抛出正面的概率为 $\frac{1}{2}$ 期望抛两次后发生。

取球游戏

取球游戏1

箱子里有 $n$ 个球 $1...n$ ，你要从中拿 $m$ 次球，拿了后不放回，求取出的数字之和的期望。

solution

$E(\sum\limits_{i=1}^nX_i)=\sum\limits_{i=1}^nE(X_i)=\sum\limits_{i=1}^nP(X=i)i=\sum\limits_{i=1}^n\frac{m}{n}\times i=\frac{m}{n}\sum\limits_{i=1}^ni=\frac{m}{n}\times \frac{n(n+1)}{2}=\frac{m(n+1)}{2}$

取球游戏2

箱子里有 $n$ 个球 $1...n$ ，你要从中拿 $m$ 次球，拿了后放回，求取出的数字之和的期望。

solution

取到每个球的概率均为 $\frac{m}{n}$ ,故答案仍为 $\sum\limits_{i=1}^n\frac{m}{n}i=\frac{m(n+1)}{2}$

取球游戏3

箱⼦子⾥有 n 个球 1…n，你要从⾥面拿 m 次球，拿了后以 p1 的概率放回，以 p2 的概率放回两个和这个相同的球，求取出的数字之和的期望

solution
仍然为 $\sum\limits_{i=1}^n \frac{m}{n}i=\frac{m(n+1)}{2}$

这三个问题都可以考虑所有的n个球是面临相同情况，所以被选中的概率都是 $\frac{m}{n}$

游走问题

游走问题1

在一条 n 个点的链上随机游走，求从一段端走到另一端的期望步数

solution
$E(S)= \sum\limits_{i=1}^{n-1}E(X_i)$

$X_i$ 表示第一次从i到达 $i+1$ 的期望步数。

因为有 $\frac{1}{2}$ 的概率会直接从 $i$ 走到 $i+1$ ，有 $\frac{1}{2}$ 的概率会走回 $i-1$ ，所以 $X_i=\frac{1}{2}+\frac{1}{2}\times (1 + X_{i-1}+X_i)=2+X_{i-1}$

游走问题2

在一个 $n$ 个点的完全图上游走，求从一个点到另一个点期望步数。

solution
因为是完全图。不论当前在哪个点，到达目标点的概率均为 $\frac{1}{n-1}$ ,所以概率为 $\frac{1}{n-1}$ ，根据概率为 $p$ 的事件期望 $\frac{1}{p}$ 次后发生。所以达到目标点的期望步数为 $n-1$

游走问题3

在一张 2n 个点的完全二分图上游走，求从一个点走到另一个点的期望步数

solution

分为两点在同一侧和不同侧讨论。
A表示位于不同侧的期望步数，B表示位于同一侧的期望步数。 $B=1+A$

$A=\frac{1}{n}+\frac{n-1}{n}B$

解方程

$A=\frac{1}{n}+\frac{n-1}{n}(1+A)$

$\frac{1}{n}A=\frac{1}{n}+\frac{n-1}{n}$

$A=1+n-1 = n$

$B=n+1$

游走问题4

在一张 n 个点的菊花图上游走，求从一个点⾛走到另一个点的期望步数。

solution

1.叶子->中心：1
2.叶子->叶子A=1+B
3.中心->叶子 $B=\frac{1}{n-1}+\frac{n-2}{n-1}(A+1)$

解方程 $B=\frac{1}{n-1}+\frac{n-2}{n-1}(B+2)$

$B=\frac{1}{n-1}+\frac{n-2}{n-1}B+\frac{2(n-2)}{n-1}$

$\frac{1}{n-1}B=\frac{1}{n-1}+\frac{2(n-2)}{n-1}$

$B=1+2(n-2)=2n-3$

游走问题5

在一个n个点的树上游走，问从根走到x的期望步数

solution

设从x走到y，则以y为根

设 $f[x]$ 表示第一次走到 $x$ 的期望步数。

$f[x] = \frac{1}{d[x]}+\frac{1}{d[x]}\sum\limits_{y为x的儿子}(1+f[y]+f[x])$

游走问题6

构造一张200个点的无向图，使得上面从S走到T的随机游走期望步数 $\ge$ 1000000

solution

类似于第一题。在链上， $x_2=1$ 所以总的步数为 $n^2$ 级别。只要让 $x_2=n$ 就可以达到 $n^3$ 级别了。所以在最开始用 $100$ 个点连出一张无向完全图，然后用 $100$ 个点连出一条链。

经典问题

经典问题1

每次随机一个[1,n]的整数，问期望几次能凑出所有数

solution
$S=\sum\limits_{i=1}^nX_i$

$S$ 表示总次数。 $X_i$ 表示现在手里有 $i-1$ 个数字。不断的取一直取到第 $i$ 个数字所需要的步数

$E(S) = \sum\limits_{i=1}^nE(X_i)$

$P(X_i)=\frac{n-i+1}{n}$

$E(x_i)=\frac{n}{n-i+1}$

$E(S)=\sum\limits_{i=1}^n\frac{n}{n-i+1}=\sum\limits_{i=1}^n\frac{n}{i}$

经典问题2

随机一个长度为n的排列p，问前i个数字中p[i]是最大数字的概率。

solution

前i个数字中，每个数字最大的概率都相同。所以p[i]是最大数字的概率就是 $\frac{1}{i}$

经典问题3

求上题中i的个数的平方。

solution

设 $X_i$ 表示第 $i$ 个数字是(1)不是(0)前i个数字中的最大数字。

$E(S) = \sum\limits_{i=1}^nE(X_i)$

$E(S^2)=\sum\limits_{i=1}^nE(X_i^2) \\ =\sum\limits_{i!=j}E(X_i且X_j)+\sum\limits_{i=1}^nE(X_i)^2 \\ =\sum\limits_{i!=j}\frac{1}{ij}+\sum\limits_{i=1}^n{\frac{1}{i}}^2$

经典问题4

随机一个长度为n的排列p，问i在j后面的概率

solution

因为i与j等价，且要么i在j前面，要么j在i前面(i=j除外)，所以概率为 $\frac{1}{2}$

经典问题5

随机一个长度为 n 的排列 p，求它包含 w[1…m]作为子序列的概率

solution

w共有 $m!$ 种排列方式。其中只有一种符合条件。

所以答案为 $\frac{1}{m!}$

经典问题6

随机一个长度为 n 的排列 p，求它包含 w[1…m]作为连续子序列的概率。

solution

w的所有情况共有 $C(_n^m)m!$ 种，在n***有 $n-m+1$ 个排列。所以答案为 $\frac{n-m+1}{C(_n^m)m!}$

经典问题7

有n堆石头，第i堆个数为a[i]，每次随机选一个石头然后把那一整堆都扔了，求第1堆石头期望第几次被扔。

solution

$A[i]$ 表示第 $i$ 堆石头期望第几次被扔。

$A[1]=\sum\limits_{i=1}^n[A[i]\le A[1]]$

$E(A[1])=\sum\limits_{i=1}^nE([A[i] \le A[1])$

$E(A[i]\le A[1]) = P(A[i] \le A[1])$

$E(A[1]) = 1 + \sum\limits_{i=2}^nP(A[i]\le A[1])$

$P(A[i] \le A[1]) = \frac{a[i]}{a[i]+a[1]}$

经典问题8

随机一个长度为n的01串，每个位置是1的概率为p，定义x 是每段连续的1的长度的平方之和。求 $E(x)$

solution

$f[i]$ 表示前i个的答案。 $g[i]$ 表示以i为结尾的1的个数。

如果第 $i+1$ 个为1，那么 $g[i+1] = g[i] + 1$ , $f[i + 1] = f[i] - g[i]^2+(g[i]+1)^2=f[i]+2g[i]+1$ ,

否则 $g[i + 1]=0$ , $f[i+1]=f[i]$

$f[i+1] = f[i]+ \frac{1}{2}(2g[i]+1)$
$g[i+1] = \frac{1}{2}g[i]$

经典问题9

给一个序列，每次随机删除一个元素，问第i个和第j个在过程中相邻的概率

solution

将所有元素按照删除顺序组成一个排列。

i和j相邻相当于从i到j这 $j-i+1$ 个元素所组成的子序列中，i和j位于最后。这 $j-i+1$ 个元素所组成的全部可能序列共有 $(j-i+1)!$ 种，其中满足条件的共有 $2(j-i-1)!$ 种。所以答案为 $\frac{2(j-i-1)!}{(j-i+1)!}=\frac{2}{(j-i+1)(j-i)}$

练习题

练习题1

给定n个硬币，第i个硬币的价值为w[i],每次随机取走一个硬币，获得的价值为左右两个硬币的价值的乘积，求期望的总价值。

solution

两个硬币产生价值，只当这两个数字及其之间的所有数字中，这两个数字最后被取走。这个的概率可以由经典问题9知道。所以这个问题的答案就是 $\sum\limits_{i=1}^{n-2}\sum\limits_{j=i+2}^n\frac{2w[j]w[i]}{(j-i+1)(j-i)}$

练习题2

有 N 个数 a[1…N]，每次等概率选出两个数，然后合并成一个新的数放回来，得到的收益是新的数的值，求总收益的期望

solution

$S=X_ia_i$

$X_i$ 表示第i个数字产生贡献的次数。

$E(S)=\sum\limits_{i=1}^nE(X_i)a_i$

$E(X_i)=P(X_i)=\sum\limits_{i=2}^n\frac{2}{i}$

$E(S)=\sum\limits_{i=2}^n\frac{2}{i}\sum\limits_{j=1}^na_i$

练习题3

给定一个数列W[1…N]，随机一个排列 H，如果 H[i] 比 H[i-1] 和 H[i+1] 都大，就获得 W[i] 的收益，求期望收益

solution

$E(S)=\sum\limits_{i=1}^nP(H[i]>H[i-1]\&\&H[i]>H[i+1])W[i]$

因为 $H[i],H[i-1],H[i+1]$ 这三个数字等价，且一定有一个最大的。所以 $H[i]$ 最大的概率就是 $\frac{1}{3}$ ，所以答案为 $\frac{1}{3}\sum\limits_{i=1}^nw[i]$

练习题4

codeforces280C

给出一棵树，一开始每个点都是白的，每次选一个⽩点将他子树里所有点染黑，求期望几次染黑整个树

solution

对于一个点 $x$ ，只有当 $x$ 和其所有祖先中 $x$ 最先被染黑。 $x$ 才会产生贡献。概率为 $\frac{1}{dep_i}$

$E(S)=\sum\limits_{i=1}^nE(X_i)$

$X_i$ 表示第 $i$ 个点被染黑的期望操作次数。

$E(X_i)=\frac{1}{dep[i]}$

$E(S)=\sum\limits_{i=1}^n\frac{1}{dep[i]}$

课后练习

换教室

noip2016

solution

$f[i][j][0/1]$ 表示前i个时间段，是(1)否(0)申请，期望花费的最小体力。
然后大力分类讨论转移即可。

具体转移方程如下

$f[i + 1][j][0] = min(f[i][j][0] + dis[c[i]][c[i + 1]],\\f[i][j][2] + dis[d[i]][c[i + 1]] * K[i] + dis[c[i]][c[i + 1]] * (1 - K[i]))$

$f[i + 1][j + 1][3] = min(\\f[i][j][0] + \\dis[c[i]][d[i + 1]] * K[i + 1] + \\dis[c[i]][c[i + 1]] * (1 - K[i + 1]),\\f[i][j][4] + \\dis[d[i]][d[i + 1]] * K[i] * K[i + 1] + \\dis[d[i]][c[i + 1]] * K[i] * (1 - K[i + 1]) + \\dis[c[i]][d[i + 1]] * (1 - K[i]) * K[i + 1] + \\dis[c[i]][c[i + 1]] * (1 - K[i]) * (1 - K[i + 1]))$

区间交

定义一种随机生成区间的方法如下。 $L=random(1,N),R=random(L,N)$ 。通过这种方法随机出两个区间，问这两个区间相交的概率。 $N \le 1000000$

solution

将问题取反，转化为求区间不相交的概率。

也就是需要一个区间的左端点小于另一个区间的右端点。

用 $f[i]$ 表示右端点小于等于i的区间的概率

$ans=\frac{1}{n}\sum\limits_{i=1}^{n - 1}f[i]$

$g[i]$ 表示右端点为 $i$ 的区间的概率。

$f[i]=\sum\limits_{j=1}^ig[i]$

$g[i]=\frac{1}{n} \sum\limits_{l=1}^n\frac{1}{n-l+1}$

收集邮票

luogu4550

有n( $n\le 10000$ )种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票需要支付k元钱。
现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望.

solution

用 $f[i]$ 表示现在手里已经有 $i$ 张邮票，取到 $n$ 张所需要的步数。有 $\frac{n-i}{n}$ 的概率取到新的邮票。所以期望取 $\frac{n}{n-i}$ 次。所以 $f[i] = f[i + 1] + \frac{n}{n-i}$

用 $g[i]$ 表示现在手里有 $i$ 张邮票。取到 $n$ 张所需要花费的钱。这里每次取得价格依旧从1开始记。只要每次取都后面取时的花费+1就能保证满足题意了。有 $\frac{i}{n}$ 的概率取到已有的邮票。有 $\frac{n-i}{n}$ 的概率取到新的邮票。所以 $g[i] = \frac{i}{n}(g[i]+f[i]+1)+\frac{n-i}{n}(g[i+1]+f[i+1]+1)=\frac{i(f[i]+1)}{n-i}+f[i+1]+g[i+1]+1$

Puzzles

CF696B

solution

将某个节点x与其兄弟进行随机排列之后，对于其他的任意一个兄弟y，x在y前面的概率都为 $\frac{1}{2}$ ,如果 $x$ 在 $y$ 后面，那么访问完整棵 $y$ 子树后才会访问 $x$ 节点。用 $siz[i]$ 表示以i为根的子树的大小。 $ans[x] = ans[fa]+1+\frac{1}{2}(siz[fa]-siz[x] - 1)$ ,( $fa$ 表示 $x$ 的父亲)

Bad Luck Island

CF540D

厄运岛上居住着三种物种：Rock、Scissors和Paper。在某些时刻，两个随机的个体相遇（所有的个体都可以平等地相遇），如果他们属于不同的物种，那么一个个体杀死另一个：Rock杀死Scissors，Scissors杀死Paper，Paper杀死Rock。你的任务是为每一个物种确定在足够长的时间之后，这个物种将是唯一居住在这个岛上的物种的概率。

solution

$f[i][j][k]$ 表示还剩下i个Rock,j个Scissors,k个Paper的概率。然后枚举两个物种，计算相遇的概率转移即可。计算概率时注意减去相同的两个物种相遇的情况。

Fish

有n条鱼，每天会有两条鱼相遇，任意两条鱼相遇的概率都是相同的。两条鱼i,j相遇之后，会有 $a[i][j]$ 的概率i吃掉j，有 $1-a[i][j]$ 的概率j吃掉i。对于每条鱼x，问最后剩下x的概率。

$1\le n\le 18$

solution

状压一下。枚举当前状态下相遇的两条鱼，计算概率，然后转移即可。

概率期望从入门到入坟

基础知识

期望的线性性质

前缀和技巧

小结论

取球游戏

取球游戏1

取球游戏2

取球游戏3

游走问题

游走问题1

游走问题2

游走问题3

游走问题4

游走问题5

游走问题6

经典问题

经典问题1

经典问题2

经典问题3

经典问题4

经典问题5

经典问题6

经典问题7

经典问题8

经典问题9

练习题

练习题1

练习题2

练习题3

练习题4

课后练习

换教室

区间交

收集邮票

Puzzles

Bad Luck Island

Fish