概率期望习题总结

Topcoder12984 TorusSailing

考虑矩阵的最后一行和最右一列，我们把所有方格的期望表示为这$n+m-1$个变量的方程。

然后考虑矩阵的第一行和最左一列，发现可以联立这些方程与最后一行、最右一列的方程。

这样就可以高斯消元了。消完了再带回去即可求出期望。

时间复杂度$O((n+m)^3)$。

代码

HDU4035 Maze

设$f(u)$表示结点$u$的期望，那么

$$f(u)=k_uf(1)+\frac{1-k_u-e_u}{d_u}\sum_{(u,v)}(f(v)+1)\\$$

我们尝试将$f(u)$表示成$a_uf(p)+b_u+c_uf(1)$的形式，其中$p$是$u$的父节点。首先设

$$A_u=\sum_{v\in Son(u)}a_v\\ B_u=\sum_{v\in Son(u)}b_v\\ C_u=\sum_{v\in Son(u)}c_v\\ D_u=\frac{d_u}{1-k_u-e_u}\\$$

那么把上式化简可以得到

$$f(u)=\frac{f(p)}{D_u-A_u}+\frac{B_u+d_u}{D_u-A_u}+\frac{D_uk_u+C_u}{D_u-A_u}f(1)\\$$

对于根结点的情况：

$$f(1)=\frac{B_1+d_1}{D_1-k_1D_1-A_1-C_1}$$

实现的时候注意判无解即可。注意，本题精度要开到$10^{-9}$。

代码

SHOI2017 分手是祝愿

考虑按灯泡的最优策略。我们显然是先找到最大的 1 把它变成 0，然后再找最大的 1 变成 0……

因此设$f(i)$表示把一个最优按$i$次能全 0 的局面变成按$i-1$次能全 0 的局面的期望步数。显然，当$i\le k$时你会选最优，即$f(i)=1$；否则，你有$\dfrac{i}{n}$的概率按到一个应该按的灯，剩余的概率则会转移到$f(i+1)$。因此得到

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

边界情况$f(n)=1,f(0)=0$。$f(n)=1$是因为你不论按哪个，都能按到你应该按的那个灯。

于是我们先求出初始局面在最优情况下需要按的次数，假设为$x$。那么答案为

$$n!\sum_{i=1}^x f(i)$$

时间复杂度$O(n\log_2n)$或$O(n\sqrt{n})$。

代码

歌唱王国

有$t$个字符集是$\{1,\ldots,n\}$的长度分明为$m_i$的字符串$s_i$（模式串）。有$t$次询问，第$i$次询问为：生成一个字符串$T$，每次随机在$T$末尾添加一个字符，一旦$T$中出现了$s_i$就停止生成。求$T$长度的期望。

$t\le 50, n\le 10^{18}, m_i\le 10^5$。

概率生成函数

固定$S = s_i$。

第一部分

设$f_i$表示长度为$i$时恰好结束的概率，$g_i$表示长度为$i$时没有结束的概率。

显然，对于$i<|S|$，有$f_i = 0$。

严谨定义补充

严谨地说，$f_i$表示随机生成长度为$i$的串，$S$仅做为$f_i$后缀出现且仅出现一次的概率。

而$g_i$表示随机生成长度为$i$的串，$S$未出现的概率。

首先根据定义有$f_i+g_i=g_{i-1}$。即在$i-1$的长度还没有结束，那么可能会在$i$或者大于$i$的长度结束。

特殊地，当$i=0$时，$f_0=0, g_0=1$。

对于串$S$，我们记录$a_i$表示$S[1,i]$与$S[|S|-i+1,|S|]$是否匹配（即是否是 border）。那么我在长度为$i$的状态下直接加入这个串，显然一定会结束。但是，我们还可能会在长度小于$i+|S|$的时候结束（即当我补完一个 border 的时候就结束了）。那么可以得到

$$\frac{g_i}{n^{|S|}}=\sum_{j=1}^{|S|}a_jf_{i+j}\frac{1}{n^{|S|-j}}$$

解释一下上式的含义：

• 左边：随机生成长度为$i+|S|$的串$T$满足$T[1,i]$中没有$S$且$T[i+1，i+|S|] = S$的概率。

• 右边：对$j$求概率和：随机生成长度为$i+j$的串$T$满足$T[1,i+j]$恰好以$S$结尾且$T[i+j+1,i+|S|] = S[j+1,|S|]$的概率。

两者都等价于：在长度属于$[i+1,i+|S|]$这个区间结束的概率。

整理一下得到$g_i=\sum_{j=1}^{|S|}a_jn^jf_{i+j}$。

第二部分

接下来我们用概率生成函数来改写上式。

概率生成函数

离散随机变量$X$的概率生成函数为

$$F_X(x)=\sum_{i=0}^\infty P(X=i)x^i$$

该函数有两个重要的性质：

1. $F_X(1)=\sum_{i=0}^\infty P(X=i)=1$；
2. $F_X'(1)=\sum_{i=0}^\infty P(X=i)\cdot i=E(X)$。

概率生成函数是普通生成函数的一种特殊情况（被赋予特殊的意义）。

设$F(x)=\sum_{i\ge 0}f_ix^i$，$G(x)=\sum_{i\ge 0} g_ix^i$。我们要求的就是$F'(1)$。

于是我们可以把定义式改写为

$$F(x)+G(x)=G(x)\cdot x+1$$

对两边求导得到

$$F'(x)+G'(x)=G'(x)x+G(x)\\ F'(x)=G(x)+G'(x)(x-1)$$

因此$F'(1)=G(1)$。

另一种理解方式

对于离散变量$x$，我们知道$E(x) = \sum_i P(x = i)\cdot i = \sum_{i\ge 1}P(x\ge i)$。

而$g_i$可以理解为长度$>i$的概率。因此要求的期望等价于$G(1)$。

把$g_i=\sum_{j=1}^{|S|}a_jn^jf_{i+j}$改写为

$$G(x) = \sum_{j=1}^{|S|}a_jn^jF(x)x^{-j}$$

注意，对于$i<|S|$有$f_i=0$，因此不会出现负指数项。令$x=1$可以得到

$$G(1) = \sum_{j=1}^{|S|}a_jn^jF(1)$$

因为$F(1)=1$，因此得到

$$G(1)=\sum_{j=1}^{|S|}a_jn^j$$

这样就做完了。

代码

硬币游戏

给出$n$个长度为$m$的互不相同的 01 串$s_i$。现在生成一个字符串$T$，每次在$T$末尾随机加入一个字符。一旦$T$中出现某个$s_i$就停止。对每个$s_i$求以$s_i$结尾的概率。

$n,m\le 300$。

概率生成函数 高斯消元 SDOI

设$F_i(x)=\sum_{j=0}^\infty f(i,j)x^j$，其中$f(i,j)$表示长度为$j$以$S_i$结尾结束的概率。

设$G(x)=\sum_{j=0}^\infty g(j)x^j$，其中$g(j)$表示长度为$j$仍未结束的概率。

我们要求的是$F_i(1),i\in[1,n]$。

类似地，首先有一个显然的等式：

$$G(x)+\sum_{i=1}^nF_i(x)=G(x)x+1$$

类似地，设$a_{i,j,k}$表示$S_i[1,k]$与$S_j[m-k+1,m]$是否匹配。那么我们强行在当前状态下插入$S_i$，可以得到

$$G(x)\left(\frac{x}{2}\right)^{|S_i|}=\sum_{j=1}^n F_j(x)\sum_{k=1}^m a_{i,j,k} \left(\frac{x}{2}\right)^{|S_i|-k}$$

相当于你在插入的过程中，可能在中途就以$S_j$结尾结束了。

根据第一个等式，取$x=1$得到

$$\sum_{i=1}^nF_i(1)=1$$

第二个等式取$x=1$得到

$$G(1)=\sum_{j=1}^nF_j(1) \sum_{k=1}^m 2^k a_{i,j,k}$$

那么对于$i\in[1,n]$再加上上面那个式子，我们可以$O(n^3)$高斯消元求出答案了。

注：eps 要开到$10^{-100}$。

代码

随机游走

给定一棵$n$个结点的树，你从点$x$出发，每次等概率随机选择一条与所在点相邻的边走过去。

有$Q$次询问，每次询问给定一个集合$S$，求如果从$x$出发一直随机游走，直到点集$S$中所有点都至少经过一次，期望游走几步。

特别地，点$x$（即起点）视为一开始就被经过了一次。

答案对$998244353$取模。

FMT 容斥 min-max 容斥 PKUWC

首先考虑 min-max 容斥。

min-max 容斥

对于全序集合$S$，有

$$\max S = \sum_{T\subseteq S}(-1) ^{|T|-1}\min T$$

设$x_i$表示走到$i$的时间的期望。那么我们要求的是$\max x_i$，转化为求$\min x_i$，即到达任意一个点的时间的期望。

这个可以用树上消元在$O(n)$的复杂度计算，答案就是根结点的期望。

最后容斥的时候可以使用 FMT，把容斥系数带进去即可。

总时间复杂度$O(2^nn)$。

代码

Circles of Waiting

主元法：对于一类消元问题，可以先将变量用一组主元表示，然后将这些变量的方程与主元联立求解，以降低复杂度。

对于这道题，我们可以把圆上左边界的点作为主元，具体来说是圆内每行 x 坐标最小的点。那么根据期望方程

$$F_{x,y}=p_1F_{x-1,y}+p_2F_{x,y-1}+p_3F_{x+1,y}+p_4F_{x,y+1}+1$$

我们可以得到$F_{x+1,y}$的方程式。这样就可以从左边推到右边界。由于右边界之外的点期望是 0，就可以列出$2R+1$个方程。于是高斯消元即可。时间复杂度$O(R^3)$。

Graph Game

考虑一棵树的情况。如果在某个时刻我们删掉$A$的时候$B$仍与$A$连通，那么$(A,B)$就会产生 1 的贡献。我们考虑这件事发生的概率。容易发现概率是 A,B 路径长度的倒数（确切地说，这里的长度是指点数）。因此把所有有向路径长度的倒数求和就是答案。

如果是基环树，那么从 A 到 B 就可能会出现两条路径（即中间夹一个环）。那么有两条路径，如果我们直接把贡献算成两条路径长度倒数和的话，会多算贡献。那么减掉路径并的长度倒数即可。

证明见官题。

Bingo

权值是 2 的幂，相当于子集枚举，可以理解其组合意义为每行每列被选择包含的概率的和。因此得到

$$\frac{1}{m^{\underline{n^2}}\binom{m}{k}}\sum_{i=1}^n\sum_{j=1}^n \binom{n}{i}\binom{n}{j}\binom{m}{k}k^{\underline{n^2-(n-i)(n-j)}}(m-(n^2-(n-i)(n-j)))^{\underline{(n-i)(n-j)}}\\ =\frac{1}{m^{\underline{n^2}}}\sum_{i=1}^n\sum_{j=1}^n \binom{n}{i}\binom{n}{j}k^{\underline{n^2-(n-i)(n-j)}}(m-(n^2-(n-i)(n-j)))^{\underline{(n-i)(n-j)}}$$

Slime and Biscuits

给出一个长度为$n$的序列$a$，设$s=\sum_{i=1}^n a_i$。每次有$\frac{a_i}{s}$的概率选择$i$，然后等概率选择$1,\cdots,n$中一个不等于$i$的数$j$，然后令$a_i$减一，$a_j$加一。当存在某个$a_i=s$时停止操作。问期望时间。

$n\le 10^5,s\le 3\times 10^5$。

概率 期望 消元

容易想到，设$E(x)$表示，在$a_x=s$时结束的期望。答案就是$\sum_{i=1}^n E(i)$。但是要注意，这不是普通意义上的期望。

普通意义的期望例如丢骰子，丢到$1$的期望时间。那么你丢无限次，丢到$1$的概率是无限趋近于$1$的。也就是说不论哪个局面都可以通过继续丢骰子来丢出$1$。

但是在题目中的游戏的条件下，一旦有某个$y(y\ne x)$使得$a_y=s$，那么游戏就结束了。这种情况对$E(x)$的贡献显然是$0$（因为不是在$x$处结束的）。但是它的时间（随机变量）却不一定是$0$。是在这个条件下我们强制它的贡献是$0$，这个规则是不符合普通期望的定义的。

换言之，$E(x)$其实是一个不完全期望——它只包含所有合法情况的概率乘随机变量值（时间）的和（对于普通的期望，所有的情况最后一定可以导出合法情况）。

理解了这个，我们再重新审视本题。

直接计算$E(x)$是困难的，因为我们要求在游戏过程中不能存在某个$y(y\ne x)$使得$a_y=s$。那么我们考虑减去不合法的情况。

设$E'(x)$表示仅当$a_x=s$时结束游戏时的期望时间。也就是说我们修改了游戏的规则。

这其中就有不合法的情况，比如先有$a_y=s$出现，然后再把$y$上的转移到$x$上。

因此我们设$P(i)$表示在原来的游戏规则下，游戏在$a_i=s$处结束的概率。显然有$\sum_{i=1}^nP(i)=1$。

设$C$表示在修改了游戏的规则的状态下，从$a_i=s$转移到$a_j=s(i\ne j)$的期望时间。显然这对于所有的$i,j(i\ne j)$都是相等的。

那么我们把不合法的情况减掉，建立等式：

$$E(x)=E'(x)-\sum_{y=1}^{n}[x\ne y](E(y)+P(y)C)$$

（$E(y)$是不用乘$P(y)$的，因为它计算的是不完全期望，概率已经算在里面了）

那么移项变换一下得到

$$\sum_{y=1}^nE(y) = E'(x)-C \sum_{y=1}^{n}[x\ne y]P(y)$$

这个是关于$x$的等式。我们把所有关于$1,\cdots,n$的等式累加，得到

$$n\sum_{y=1}^nE(y)=\sum_{y=1}^nE'(y)-C(n-1)$$

那么只要我们能求出$E'(x)$和$C$，就可以求出答案。

而在修改了游戏的规则的状态下，我们只关心$a_x$的值。其他的值满了$s$也没关系。因此设$f_i$表示$a_x$的值当前为$i$，从$i$变成$i+1$的期望时间。那么

• 有$\frac{i}{s}$的概率选中自己，那么就会变成$i-1$；
• 否则有$\frac{s-i}{s}$的概率选中别的数，那么：
  • 有$\frac{1}{n-1}$的概率选中自己，变成$i+1$；
  • 否则不变。

因此就得到了

$$f_i=\frac{i}{s}(f_{i-1}+f_i+1)+\frac{s-i}{s}\left(\frac{1}{n-1}+\frac{n-2}{n-1}(1+f_i) \right)$$

解得

$$f_i=(if_{i-1}+s)\frac{n-1}{s-i}$$

$f_0$是可以直接求的。那么显然有$E'(x)=\sum_{i=a_x}^{s-1}f_i$。然后$C=\sum_{i=0}^{s-1}f_i$。

时间复杂度$O(n\log_2n)$。