2020-05-29 17:57 已编辑山东大学计算机类

关注

概率期望从入门到入坟

基础知识

期望的线性性质

$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的概率。然后枚举两个物种，计算相遇的概率转移即可。计算概率时注意减去相同的两个物种相遇的情况。