期望经典问题入门

一些概念

随机变量$X$：有多种可能取值的变量。

$P(A)$：$A$事件发生的概率。

$E(X)$：随机变量$X$的期望值，$E(X)=\sum_iP(X=i)\cdot i$。

独立事件：两个事件互不影响，满足$P(AB)=P(A)P(B),E(AB)=E(A)E(B)$。
证明：

$$\begin{aligned} E(AB)&=\sum_{i}\sum_jP(A=i\wedge B=j)\cdot i\cdot j\\ &=\sum_{i}\sum_jP(A=i)P(B=j)\cdot i\cdot j\\ &=E(A)E(B) \end{aligned}$$

期望的线性性：对于任意两个随机变量$X,Y,E(X+Y)=E(X)+E(Y)$。
证明：

$$\begin{aligned} E(X+Y)&=\sum_i\sum_jP(X=i\wedge Y=j)(i+j)\\ &=\sum_i\sum_jP(X=i\wedge Y=j)i+\sum_i\sum_jP(X=i\wedge Y=j)j\\ &=\sum_ii\sum_jP(X=i\wedge Y=j)+\sum_jj\sum_iP(X=i\wedge Y=j)\\ &=\sum_ii\cdot P(X=i)+\sum_jj\cdot P(Y=j)\\ &=E(X)+E(Y)\\ \end{aligned}$$

前缀和技巧：对于离散变量（取值只有整数）x，$P(x=k)=P(x\le k)-P(x\le k-1)$。

A

有 n 个随机变量$\langle X_i\rangle$，每个随机变量量都是从$[1,m]$中随机一个整数，求$\max\left\langle X_i\right\rangle$的期望。

设$S=\max \left\langle x_i\right\rangle_{i=1}^n$，则我们要求的是$E(S)$。根据期望的定义式得到

$$E(S)=\sum_{i=1}^mP(S=i)i$$

我们使用前缀和技巧，得到$P(S=i)=P(S\le i)-P(S\le i-1)$。然后我们推一波式子，你发现$S\le i$等价于$\left\langle x_j\right\rangle_{j=1}^n \le i$，那么就可以得到

$$P(S\le i)=P(\left\langle x_i\right\rangle_{i=1}^n\le i)=\left(\frac{i}{m}\right)^n\\ P(S=i)=\left(\frac{i}{m}\right)^n-\left(\frac{i-1}{m}\right)^n\\$$

于是得到

$$E(S)=\sum_{i=1}^mi\left(\left(\frac{i}{m}\right)^n-\left(\frac{i-1}{m}\right)^n\right)=m-\frac{1}{m^n}\sum_{i=1}^{m-1}i^n$$

B

证明：概率为$p$的事件期望$\frac{1}{p}$次发生。

设随机变量$x$表示这个事件在第$x$次发生。于是我们需要求$E(x)$。套公式得到

$$\begin{aligned} E(x)=&\sum_iP(x=i)i\\ E(x)=&\sum_i(P(x\ge i)-P(x\ge i+1))i\\ \end{aligned}$$

于是问题转化为我们要求$P(x\ge i)$，它表示这个事件在第$i$次及以后发生。显然它在前$i-1$次都未发生过，概率为$(1-p)^{i-1}$。因此得到

$$\begin{aligned} E(x)&=\sum_{i=1}^\infty ((1-p)^{i-1}-(1-p)^i)i\\ &=\sum_{i=0}^\infty(1-p)^i \end{aligned}$$

根据小 Trick 得到

$$E(x)=\frac{1}{1-(1-p)}=\frac{1}{p}$$

事实上，对于求期望，可以将其转化为求概率的和：

$$\begin{aligned} E(x)=&\sum_{i=1}^\infty P(x=i)\sum_{j=1}^i1\\ =&\sum_{j=1}^\infty\sum_{i\ge j} P(x=i)=\sum_{j=1}^\infty P(x\ge j) \end{aligned}$$

C 拿球

C1

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

这题是一个标准的一眼题。每次取的期望是一样的，所以很容易得到答案为$\dfrac{(n+1)m}{2}$。但我们还是严谨地做一下。

设随机变量$x_i$表示第 i 次取出来的值。那么数字之和的期望即为

$$E\left(\sum_{i=1}^mx_i\right)=\sum_{i=1}^mE(x_i)$$

根据期望的定义得到

$$E(x_i)=\sum_{j=1}^nP(x_i=j)j$$

于是我们要求$P(x=j)$的概率。显然不论$j$取何值，概率都是相等的，为$\dfrac{1}{n}$，因此得到

$$E(x_i)=\sum_{j=1}^n\frac{j}{n}=\frac{1}{n}\frac{(n+1)n}{2}=\frac{n+1}{2}$$

于是答案即为$\dfrac{(n+1)m}{2}$。

C2

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

我们设随机变量$x_i$表示

$$x_i=\begin{cases} i&\text{if i is chosen}\\ 0&\text{if i isn't chosen} \end{cases}$$

设答案为$S$，得到$S=\displaystyle\sum_{i=1}^nx_i$，于是我们要求

$$E(S)=E\left(\sum_{i=1}^nx_i\right)=\sum_{i=1}^nE(x_i)\\$$

展开$E(x_i)$得到

$$E(x_i)=\sum_{j}P(x_i=j)j=P(x_i=i)i$$

显然$P(x_i=i)$表示$i$被取出的概率。而拿球后不放回，相当于在 n 个球中取 m 个，因此概率为$\dfrac{m}{n}$，于是得到

$$E(x_i)=\frac{m}{n}\cdot i\\ E(S)=\sum_{i=1}^n\frac{m}{n}\cdot i=\frac{m(n+1)}{2}$$

C3

箱子里有$n$个球$1,2,\cdots, n$，你要从里面拿$m$次球，拿了后以$p_1$的概率放回，$p_2$的概率放回两个和这个相同的球（相当于增加一个球），求取出的数字之和的期望。

我们仍然设一个随机变量$x_i$，它表示$i$被拿出来的次数乘$i$，即对答案的贡献。形式化地，我们设$y_i$表示$i$被拿了几次，那么$x_i=y_i\cdot i$。假设数字之和为$S$，那么

$$\begin{aligned} S&=\sum_{i=1}^nx_i\\ E(x_i)&=E(y_i)\cdot i\\ E(S)&=\sum_{i=1}^nE(y_i)\cdot i\\ \end{aligned}\\$$

然后我们考虑求$E(y_i)$。首先我们知道，每一个球是平等的，意味着概率是均等的，意味着它们被拿出来的次数的期望是一样的，即$E(y_1)=E(y_2)=\cdots=E(y_n)$。而我们知道，他们被拿出来的次数的和是$m$（因为你只拿了$m$个球出来），而$E(m)=m$，即

$$E\left(\sum_{i=1}^ny_i\right)=\sum_{i=1}^nE(y_i)=m$$

因此得到$E(y_i)=\dfrac{m}{n}$，带回上式得到$E(S)=\dfrac{m(n+1)}{2}$。

D 游走

D1

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

假设步数是$S$，求$S$的期望。我们定义一个随机变量$x_i$表示从$i$出发随机游走，第一次到$i+1$的步数。

$$\begin{aligned} S&=\sum_{i=1}^{n-1}x_i\\ E(S)&=E\left(\sum_{i=1}^{n-2}x_i\right)=\sum_{i=1}^{n-1}E(x_i)\\ \end{aligned}$$

我们手推一下期望的式子，发现

$$\begin{array}{l} E(x_1)&=&1\\ E(x_2)&=&\frac{1}{2}+\frac{1}{2}(1+E(x_1)+E(x_2))&=&3\\ E(x_i)&=&\frac{1}{2}+\frac{1}{2}(1+E(x_{i-1})+E(x_i))&=&E(x_{i-1})+2 \end{array}$$

就可以递推做了。但算出来就会发现，$E(S)=(S-1)^2$。

D2

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

设期望步数为$E$，得到

$$E=\frac{1}{n-1}+\frac{n-2}{n-1}E+1$$

解得$E=n-1$。

D3

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

$E_1$表示异侧点的期望，$E_2$表示同侧点的期望。

$$\begin{aligned} E_1&=\frac{1}{n}+\frac{n-1}{n}(E_2 + 1)\\ E_2&=E_1+1\\ E_1&= 2n - 1 \end{aligned}$$

D4

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

类似的方法。

D5

在一棵$n$个点的树上游走，求从根走到$x$的期望步数。

对每条边$(u\to v)$记录从$u$走到$v$的期望步数。$S_u$表示$u$的儿子数（有根树）

$$\begin{aligned} E(u,v)&=\frac{1}{|S_u|+1}+\sum_{(u\to v')\in E,v'\neq v}\frac{1}{|S_u|+1}(1+E(v',u)+E(u,v))\\ E(u,v)&=|S_u|+1+\sum_{(u\to v')\in E,v'\neq v}E(v',u)\\ \end{aligned}$$

怎么算这个式子？把$v$当作$u$的父节点，那么$v'$一定是$u$的子节点。这就是一个树形 DP。算完到 root 后再从根到子节点算一下向下走的边的期望。这题本来可以直接$f[u]$表示从$u$走到$u$的父节点的期望步数来 DP，但上述方法更可拓展（多组询问）。

D6

构造一张 200 个点的无向图, 使得上面从 S 走到 T 的随机游走期望步数大于等于 1000000 步。

我们构造一个$n=100$个点的团，以及一个 100 个点的链，考虑他们的连接点$u$，则$u$沿着链走一步的期望步数为

$$E(u)=\frac{1}{n}+\frac{n-1}{n}(n-1+E(u))\\ E(u)=1+(n-1)^2$$

而我们知道在链上走的期望，于是得到走到终点的总期望为

$$\frac{(E(u)+E(u)+2n)(n+1)}{2}$$

可以达到要求。

E 经典题

E1

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

设$f[i]$表示凑齐了$i$个数，期望几次凑齐所有数。

$$f[i]=\frac{i}{n}(f[i]+1)+\frac{n-i}{n}(f[i+1]+1)\\ f[i]=f[i+1]+\frac{n}{n-i}$$

有一个有趣的问题，就是这个问题的答案为什么不是每个数第一次被凑出的时间的和的期望？如果这样算那么$E(S)=n^2$。但事实上凑出的时间相当于次数的前缀和，因此是不对的。

E2

随机一个长度为$n$个排列$p$，求$\langle p_j\rangle_{j=1}^i$中$p_i$是最大的数的概率。

其实这题很简单。由于每个数是均等的，因此他们成为最大值的概率也是一样的，于是答案为$\dfrac{1}{i}$。

E3-1

随机一个长度为$n$个排列$p$，求$\langle p_{j}\rangle_{j=1}^i$中$p_i$是最大的数的个数（即前缀最大值的个数）的期望。

设随机变量$x_i$

$$x_i=\begin{cases} 1 & p_i=\max\left\langle p_j\right\rangle_{j=1}^i\\ 0 & \text{Otherwise} \end{cases}$$

则可以得到

$$E(S)=\sum_{i=1}^nE(x_i)=\sum_{i=1}^nP(x_i=1)=\sum_{i=1}^n\frac{1}{i}$$

E3-2

随机一个长度为$n$个排列$p$，求$\langle p_{i}\rangle_{j=1}^i$中$p_i$是最大的数的个数（即前缀最大值的个数）的平方的期望。

首先要明确一点，就是平方的期望不等于期望的平方，即$E(x^2)\ne E^2(x)$，因为$x$是随机变量不是常量。

于是我们按套路出牌，设随机变量$x_i$

$$x_i=\begin{cases} 1&p_i=\max \left\langle p_j\right\rangle_{j=1}^i\\ 0&\text{Otherwise} \end{cases}$$

于是我们得到

$$E(S^2)=E\left(\left(\sum_{i=1}^nx_i\right)^2\right)=\sum_{i\ne j}E(x_ix_j)+\sum_{i=1}^nE(x_i^2)$$

由于$x_i\in\{0,1\}$，因此其实$x_i^2\Leftrightarrow x_i$，于是我们需要求$E(x_i)$。仔细理解一下，其实这就是$p_i=\max \left\langle p_j\right\rangle_{j=1}^i$的概率！于是我们得到$E(x_i)=\dfrac{1}{i}$。

接下来考虑$E(x_ix_j)$，在此之前我们思考一下$x_ix_j$的取值，有

$$x_ix_j=\begin{cases} 1& (p_i=\max \left\langle p_k\right\rangle_{k=1}^i) \wedge( p_j=\max \left\langle p_k\right\rangle_{j=1}^i)\\ 0& \text{otherwise} \end{cases}$$

那么一个有趣的问题是，$p_i=\max \left\langle p_k\right\rangle_{k=1}^i$与$p_j=\max \left\langle p_k\right\rangle_{j=1}^i$两个事件是否相关？

答案是，他们不相关！不管他们是在何种情况下同时发生，要么 i<j 要么 i>j，其中一个总是覆盖另一个的范围，即比另一个的所有数都大，因此不会受到另一个的选择的影响。于是我们得到

$$E(x_ix_j)=E(x_i)E(x_j)=\frac{1}{ij}$$

综上，我们得到

$$E(S^2)=\sum_{i\ne j}\frac{1}{ij}+\sum_{i=1}^n\frac{1}{i}$$

E4

随机一个⻓度为$n$的排列$p$，求$i$在$j$的后面的概率。

直观理解，$i$和$j$是平等的，因此谁在前面的概率是相等的，答案即为

$$\begin{cases} \frac{1}{2}&i\ne j\\ 0&i=j \end{cases}$$

E5-1

随机一个⻓度为 n 的排列$p$，求它包含$\left\langle w_i\right\rangle_{i=1}^m$作为子序列的概率。

对于一个排列$p$，你把$w_i$中的元素抽出来，那么这一定是一个$w$的排列，而我们不关心其他的数的情况，因此概率显然为$\dfrac{1}{m!}$。一个有趣的问题是：根据之前的问题，$i$在$j$后面的概率是$\frac{1}{2}$，那这题的概率为什么不是$\frac{1}{2^{m-1}}$？原因是你想在一个数的后面接一个数，但它不一定放得了。

E5-2

随机一个⻓度为 n 的排列$p$，求它包含$\left\langle w_i\right\rangle_{i=1}^m$作为连续子序列的概率。

我们设一个随机变量$x_i$，其中$i$表示一个排列$p$的情况，（相当于我们有$\dbinom{n}{m}m!$个随机变量）

$$x_i=\begin{cases} 1&\left\langle w_i\right\rangle_{i=1}^m\text{ occurs as a continuous subsequence}\\ 0&\text{Otherwise} \end{cases}$$

由于$p$中出现连续的$w$做为子序列只有$n-m+1$种位置，因此我们设$T=\displaystyle\sum_{i=1}^{\binom{n}{m}m!}x_i=n-m+1$。现在我们想知道$w$做为连续子序列的概率，相当于求$x_i$的期望。而根据平等原则，每一种情况出现的概率是相等的，因此得到

$$P(x_i=1)=E(x_i)=\frac{n-m+1}{\binom{n}{m}m!}$$

E6

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

设随机变量$x_i$表示第$i$堆石头是第几个被拿走的，显然我们有

$$x_1=1+\sum_{i=2}^n[x_i&lt; x_1]$$

于是我们要求$E(x_1)$，根据期望的线性性转化为$E([x_i&lt;x_1])$，由于艾弗森括号表达式是一个布尔表达式，因此这个期望等价于$P(x_i&lt;x_1)$，于是得到

$$E(x_1)=1+\sum_{i=2}^nP(x_i&lt;x_1)$$

而根据 E4，我们稍作拓展，其实$\dfrac{a_i}{\sum_{i=1}^na_i}$表示的就是第$i$堆石子被拿走的概率。因此$P(x_i&lt;x_1)$表示的就是第$i$堆石子比第$1$堆石子先被拿走的概率，显然为$\dfrac{a_i}{a_i+a_1}$，于是得到

$$E(x_1)=1+\sum_{i=2}^n\frac{a_i}{a_i+a_1}$$

E7

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

令$x_i$表示$\left\langle s_j\right\rangle_{j=1}^i$中所有为$1$的段的长度的平方之和，因此$E(S)=E(x_n)$。再令$y_i$表示$\left\langle s_j\right\rangle_{j=1}^i$中最后一段$1$的长度。我们先求$x_i,y_i$的转移式。考虑第$i$位上的值。

$$\begin{aligned} &y_i=\begin{cases} 0&s_i=0\\ y_{i-1}+1&s_i=1 \end{cases}\\ &x_i=\begin{cases} x_{i-1}&s_i=0\\ x_{i-1}-y_{i-1}^2+(y_{i-1}+1)^2=x_{i-1}+2y_{i-1}+1&s_i=1 \end{cases} \end{aligned}$$

于是我们考虑求$E(x_i),E(y_i)$，于是我们简单地把概率套到上面的转移式就能得到

$$\begin{aligned} E(y_i)&=p(E(y_{i-1})+1)\\\\ E(x_i)&=p(E(x_{i-1})+2E(y_{i-1})+1)+(1-p)E(x_{i-1})\\ &=E(x_{i-1})+2pE(y_{i-1})+p \end{aligned}$$

E8

给一个序列$1,2,\cdots,n$，每次随机删除一个元素, 问$i$和$j$在过程中相邻的概率。

直接组合计数一波，相当于考虑一个排列中$i,j$相邻的概率。我们只用考虑他们中间的数，不用关心外面的数，于是得到

$$P=\frac{(j-i-1)!2!}{(j-i+1)!}=\frac{1}{\binom{j-i+1}{2}}$$

E9

给定一棵树，将他的边随机一个顺序后依次插入，求$u,v$期望什什么时候连通。

那么我们只需要考虑在插入边的序列中，$u,v$路径上出现时间最晚的边的位置（位置即时间）的期望。

假设$u,v$路径长度为$k$，总边数是$n-1$，那么枚举最后一条边的位置$i$，那么首先我们考虑剩下$k-1$条边的选法，然后是这$k$条边的顺序，然后是剩下的$n-k-1$条边的顺序（总共$n-1$条边），最后除以全排列即可。

$$\frac{\sum_{i=k}^{n-1}k!\binom{i-1}{k-1}(n-k-1)!}{(n-1)!}$$

E10

给$1,2,\cdots,n$这$n$个数，每次随机选择一个还在的数，删掉他的所有约数。求期望几次删完。

直接做的话，每一次删掉的数的个数不方便统计，不妨换一下思路。我们考虑这个问题：
给$1,2,\cdots,n$这$n$个数，初始时每个数都是白的。每次随机选择一个还在的数，如果它是黑的就删掉它，否则就把它的约数标黑再删掉它。求期望删掉几个白色的数。

仔细思考可以发现，这个问题与原问题是等价的。原因是删除黑色的点不影响白色点被选到的概率。这样转化的好处在于，我们每次只会删掉一个数。于是我们可以定义随机变量$x_i$表示

$$x_i=\begin{cases} 1&\text{The i-th number is white}\\ 0&\text{The i-th number is black} \end{cases}$$

（注意，这里的第$i$个数是指删到第$i$个数时这个数的颜色）于是我们要求的是

$$E(S)=\sum_{i=1}^nE(x_i)$$

根据这个随机变量的定义，$E(x_i)\Leftrightarrow P(x_i=1)$，于是我们要求$i$被删时是白色的概率。显然如果$i$是白色，那么$i$的所有倍数都没被删，且为白色。我们选到不是$i$的倍数时，对$i$的概率不影响，我们只需要考虑这$\left\lfloor\dfrac{n}{i}\right\rfloor$个数中$i$最先被选中的概率。显然为$\dfrac{1}{\left\lfloor\frac{n}{i}\right\rfloor}$，于是得到

$$E(S)=\sum_{i=1}^nE(x_i)=\sum_{i=1}^n\frac{1}{\left\lfloor\frac{n}{i}\right\rfloor}$$

F 期望线性性练习题

F1

给定$n$个硬币，第$i$个硬币的价值为$w_i$，每次随机取走一个硬币，获得的收益是左右两个硬币的价值的乘积，求期望总价值。

设随机变量$x_{i,j}$表示

$$x_{i,j}=\begin{cases} 1&i,j\text{ contributed}\\ 0&\text{Otherwise} \end{cases}$$

总价值为$S=\displaystyle\sum_{i&lt;j}x_{i,j}w_iw_j$，于是得到$E(S)=\displaystyle\sum_{i&lt;j}E(x_{i,j})w_iw_j$，问题转化为求$P(x_{i,j}=1)$，显然就是这两个数相邻的概率，相当于是说中间的数都在他们前面被删完的概率，于是把这$j-i+1$个数抽出来，那么$i,j$排最后的概率就是$\dfrac{2}{(j-i+1)(j-i)}$。于是得到

$$E(S)=\sum_{i&lt;j}\frac{2w_iw_j}{(j-i+1)(j-i)}$$

F2

有$N$个数$\left\langle a_i\right\rangle_{i=1}^n$，每次等概率选出两个数，然后合并成一个新的数放回来，得到的收益是新的数的值，求总收益的期望。

我们设随机变量$x_i$表示$a_i$对答案的贡献次数，显然收益为$S=\displaystyle\sum_{i=1}^nx_ia_i$。一波套路转化为求$E(x_i)$。要求期望的贡献次数，就是求期望的合并次数。每次合并都会减少一个数，而在$k$个数中选两个数，选到包含$a_i$的概率是$\dfrac{2}{k}$，于是就可以统计每次合并的期望，得到

$$E(x_i)=\sum_{j=1}^{n-1}\frac{2}{n-j+1}\\$$

于是收益期望为

$$E(S)=\sum_{i=1}^na_i\sum_{j=1}^{n-1}\frac{2}{n-j+1}$$

F3

给定一个数列$\left\langle w_i\right\rangle_{i=1}^n$，随机一个排列$H$，如果$H_i$比$H_{i-1}$和$H_{i+1}$都大，就获得$w_i$的收益，求期望收益。

设随机变量$x_i$

$$x_i=\begin{cases} 1 & h_i&gt;\max (h_{i-1},h_{i+1})\\ 0 & \text{Otherwise} \end{cases}$$

得到$S=\displaystyle\sum_{i=1}^nx_iw_i$，一波套路转化为求$P(x_i=1)$，即相邻三个数中中间的数最大的概率。众生平等，答案为$\dfrac{1}{3}$，如果在边上就为$\dfrac{1}{2}$。于是计算一下答案即可。

F4

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

染黑相当于删除，问题转化为每个点在它到根的路径上的点集中最先被删的概率，答案为

$$E(S)=\sum_{i=1}^n\frac{1}{dep_x}$$

总结

需要使用期望的性质解决的问题，通常都可以设出随机变量，并利用期望转概率、前缀和（容斥）、组合计数等技巧去解决。在解题的过程中也要灵活应用，重在理解题目的含义，发掘一些性质。