概率问题

Published: May 16, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• 随机递增序列
• 一些期望计算问题
• 一类乘积期望计算问题
• 图上随机游走问题
• 循环概率递推
• 赌博破产问题
• 多重排列的概率计算
• 条件期望
• 鞅的停时定理
• 用期望计算概率
• 一些生存概率问题
• 骰子问题
• 一类最大值的期望问题
• 摸瞎问题
• 树上的随机游走
• 无向连通图上的随机游走
• 收集问题
• 参考资料

随机递增序列

假设有n个未知整数，我们需要$O(C)$的时间复杂度比较一个未知整数和一个已知整数的大小关系，但是要知道某个整数的真实值需要$O(H)$的时间复杂度，而$H$远远大于$C$，可以认为

$$H\geq C\log_2n$$

现在我们想找到这n个整数中最大整数的值。

当然，我们可以直接查询所有未知整数的值，得到最终结果，时间复杂度为$O(nH)$。

我们现在希望能减少时间复杂度。

有一种显然正确的策略，先取第一个数，查出其真实值，作为持有数。之后遍历后面的数，如果这个数比持有数大，将持有数替换为该数。重复这个过程，自然就能找到最大值了，其最坏时间复杂度为$O(n(C+H))=O(nH)$

注意到时间上界是来自于替换的发生，但是事实上，替换不会真的发生n次。如我们对原始的数组进行打乱，我们可以证明一个非常优秀的时间复杂度。

记$f(i)$表示已经检查过$i$个数，后面检查$n-i$个数会发生替换操作次数的期望。那么考虑一个新的数$x$，只有当$x$比我们之前检查过的$i$个数都大的情况下，才会发生替换。因此可以推出期望公式：

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

我们要求的是$f(0)$，即检查$n$个数发生的替换总次数的期望，可以推出：

$$f(0)=f(1)+\frac{1}{1}\\ =f(2)+\frac{1}{1}+\frac{1}{2}\\ \ldots\\ =f(n)+\sum_{i=1}^n\frac{1}{i}\\ =\sum_{i=1}^n\frac{1}{i}\\ \approx \ln n$$

因此期望的时间复杂度为$O(nC+H\ln n)$

这是非常优秀的时间复杂度。

一些期望计算问题

问题1：给定n个石头，其处于一条直线上，从左到右的下标分别为$x_1,x_2,\ldots,x_n$，满足$x_1<x_2<\ldots<x_n$。现在我们每次要等概率挑选一个石头（不能选最靠右的那个），将这个石头右移直到碰撞到右边第一个石头，如果碰撞了，那么两个石头就合成了一块石头。重复上面的操作$n-1$次，问所有石头移动的总距离的期望是多少？

考虑到期望的线性性质，我们可以独立计算第$i$个石头被选择后移动的总距离$d_i$，之后我们要求的就是$E(\sum_{i=1}^{n-1}d_i)=\sum_{i=1}^{n-1}E(d_i)$。考虑第$i$个石头，它停在$x_j$处的概率为$\frac{(j-i-1)!}{(j-i+1)!}$，特殊的停在$x_n$处的概率为$\frac{1}{n-i}$。利用这些性质我们就可以独立求出$E(d_i)$，加总就好了，这样我们的时间复杂度为$O(n^2)$。

但是这个问题实际上并不要求我们算出所有石头移动距离的期望，它要求的只是总期望而已。我们可以拆解$d_i$，记录$t_{i,j}$表示石头$i$在$x_{j-1}$与$x_j$之间通过距离的期望，那么$d_i=\sum_{j=i+1}^nt_{i,j}$。而我们知道$t_{i,j}$仅可能取两个值：$0$或$x_j-x_{j-1}$，其中$P(t_{i,j}=x_j-x_{j-1})=\frac{1}{j-i}$。因此我们重写我们要求的总距离的期望，可以得到：

$$\begin{aligned} &E(\sum_{i=1}^{n-1}d_i)=E(\sum_{i=1}^{n-1}\sum_{j=i+1}^nt_{i,j})\\ =&E(\sum_{j=2}^n\sum_{i=1}^{j-1}t_{i,j})=\sum_{j=2}^n\sum_{i=1}^{j-1}E(t_{i,j})\\ =&\sum_{j=2}^n\sum_{i=1}^{j-1}\frac{x_j-x_{j-1}}{j-i}\\ =&\sum_{j=2}^n(x_j-x_{j-1})\sum_{i=1}^{j-1}\frac{1}{j-i}\\ =&\sum_{j=2}^n(x_j-x_{j-1})\sum_{i=1}^{j-1}\frac{1}{i} \end{aligned}$$

注意到右边的$\sum_{i=1}^{j-1}\frac{1}{i}$我们可以线性时间内预处理出来，因此总的时间复杂度可以优化到$O(n)$。

问题2：有$P$只北极熊，$B$只棕熊，$G$只灰熊。现在每次不断随机挑选两只熊代价，输的熊被消除，直到最后剩下一只熊。最后第$i$只熊的排名为自己被消除的时候场上还剩下多少只熊（最后幸存的熊为第一名）。并且灰熊实力强于北极熊，而北极熊则强于棕熊。如果选择的两只熊种族不同，则实力较强的获胜，否则则每只熊都有五成的概率获胜。Limak是一只北极熊，问最后Limak的排名的期望。这里$1\leq P,B,G\leq 2000$。

首先如果Limak是一种灰熊或棕熊，我们可以通过DP计算概率$O(n^2)$暴力得出排名的期望值，这里$n=P+B+G$。我们记两个排名分别为$E_G$和$E_B$。

但是如何计算北极熊幸存的概率呢。我们可以利用期望的线性性质，记$p_i$表示第$i$只北极熊的排名，$b_i$为第$i$只棕熊的排名，$g_i$为第$i$只灰熊的排名。那么我们会发现存在等式：

$$E[\sum_{i=1}^Pp_i+\sum_{i=1}^Bb_i+\sum_{i=1}^Gg_i]=\frac{(n+1)n}{2}\\ \Rightarrow PE_P+BE_B+GE_G=\frac{(n+1)n}{2}\\ \Rightarrow E_P=(\frac{(n+1)n}{2}-BE_B-GE_G)/P$$

提供一道题目SRM768 PBG。

问题3：一场比赛，有两个玩家。每回合玩家1获胜的概率为$p_1$，玩家2获胜的概率为$p_2$，且$0<p_1+p_2\leq 1$，其余情况为平局。如果一个玩家累计获胜$n$局，那么比赛结束。问回合数的期望是多少。其中$n\geq 10^6$

很容易想到一个DP公式$dp(i,j)$表示玩家1胜利$i$场，玩家$2$胜了$j$场，问剩下的回合数的期望。这个DP公式的时间复杂度为$O(n^2)$。

我们记$s=(a,b)$为游戏结束的状态，即最终玩家1胜了$a$场，玩家$b$胜了$b$场。其中很显然$a,b$中正好一个数等于$n$。

好的，现在我们需要计算最终游戏的状态恰好为$(a,b)$的概率是多少，不失一般性，令$a=n$，可以得到：

$$p(s=(n,b))={n+b-1\choose n-1}(\frac{p_1}{p_1+p_2})^n(\frac{p_2}{p_1+p_2})^b$$

接下来我们记$x$为玩家1胜利的场次，$y$为玩家2胜利的场次，$z$为平局的场次，则可以发现我们要求的是$E[x+y+z]$。根据全期望公式可以得到：

$$E[x+y+z]\\ =\sum_{s=(a,b)}E[x+y+z|s=(a,b)]p(s=(a,b))\\ =\sum_{s=(a,b)}(a+b+E[z|s=(a,b)])p(s=(a,b))$$

其中如果我们记$z_i$为第$i-1$次一方胜利后到第$i$次一方胜利前的平局数，则有：

$$E[z|s=(a,b)]\\ =E[z_1+z_2+\ldots+z_{a+b}|s=(a,b)]\\ =(a+b)E[z_i|s=(a,b)] =(a+b)(\frac{1}{p_1+p_2}-1)$$

一类乘积期望计算问题

题目1：给定$n$个数，$a_1,\ldots,a_n$，以及另外一组未知变量$b_1,\ldots,b_n$，且已知$\sum_{i=1}^nb_i=m$，位置变量的每一个赋值方案都是等概率的（即总共${n+m-1\choose n-1}$种可能都是等概率的）。现在问$E[\prod_{i=1}^n(a_i+b_i)]$。其中$1\leq n,m\leq 10^5$。

我们可以将期望公式展开开来，记$N={1,\ldots,n}$，得到：

$$E[\prod_{i=1}^n(a_i+b_i)]=E[\sum_{S\subseteq N}\prod_{i\notin S}a_i\prod_{i\in S}b_i]\\ =\sum_{S\subseteq N}\prod_{i\notin S}a_iE[\prod_{i\in S}b_i]$$

注意到$E[\prod_{i\in S}b_i]$不取决与$S$，仅取决于$|S|$。我们可以记$f(k)=\sum_{S\subseteq N\land |S|=k}\prod_{i\in S}a_i$，这个可以通过生成函数在$O(n(\log_2n)^2)$时间复杂度内算出来。那么我们实际上要求的就是：

$$\sum_{k=0}^nf(n-k)E[\prod_{i=1}^kb_i]$$

而其中右边的期望公式可以进行化简（详细可以看我的另外一篇博客《组合数学》中的隔板法的问题1。）：

$$E[\prod_{i=1}^kb_i]=\frac{ n+m-1\choose n+k-1 }{ n+m-1\choose n-1 }$$

因此结果为：

$$\sum_{k=0}^nf(n-k)\frac{ n+m-1\choose n+k-1 }{ n+m-1\choose n-1 }$$

总的时间复杂度为$O(n+m+n(\log_2n)^2)$

提供一道题目：SRM763 ProductAndProduct。

题目2：给定$n$个数，$a_1,\ldots,a_n$，之后我们随机执行$m$次独立操作，每次等概率选择一个下标$i$，并将$a_i$增加$1$。设最后得到的序列为$b_1,\ldots,b_n$，要求计算$E[\prod_{i=1}^nb_i]$。这里$1\leq n\leq 10^5,1\leq m\leq 10^9$。

我们不能用题目1的方式解决这个问题，因为不同结果的概率是不同的。但是我们可以用生成函数来求解。生成函数NB。

我们要求的是：

$$E[\prod_{i=1}^na_i+b_i]=\frac{m!}{n^m}\sum_{b_1+\ldots+b_n=m}\frac{1}{b_1!\ldots b_n!}\prod_{i=1}^n(a_i+b_i)$$

它实际是多项式$f(x)=\frac{m!}{n^m}\prod_{i=1}^n\sum_{j\geq 0}\frac{(a_i+j)}{j!}x^j$的$x^m$的系数。下面我们来讨论多项式$f(x)$。考虑$\sum$中的项，通过泰勒展开公式进行化简：

$$\sum_{j\geq 0}\frac{(a_i+j)}{j!}x^j=\sum_{j\geq 0}\frac{a_i}{j!}x^j+\sum_{j\geq 0}\frac{j}{j!}x^j=a_ie^x+xe^x$$

带回到多项式中，得到：

$$f(x)=\frac{m!}{n^m}\prod_{i=1}^n(a_ie^x+xe^x)\\ =\frac{m!}{n^m}e^{nx}\prod_{i=1}^n(a_i+x)$$

我们可以利用多项式卷积在时间复杂度$O(n(\log_2n)^2)$时间内算出

$$\prod_{i=1}^n(a_i+x)=\sum_{i=0}^nc_ix^i$$

接下来我们展开$e^{nx}$：

$$e^{nx}=\sum_{i\geq 0}\frac{n^i}{i!}x^i$$

$f$肯定是算不了的，但是我们只需要求$f_m$就够了：

$$f_m=\frac{m!}{n^m}\sum_{i+j=m}c_i\cdot \frac{n^j}{j!}\\ =\sum_{i+j=m}c_i\cdot \frac{(j+1)\cdot \ldots \cdot m}{n^{i}}$$

上面这个问题可以在$O(n)$时间复杂度内求解。因此总的时间复杂度为$O(n(\log_2n)^2)$。

还有一种偏导数的做法。

记

$$f(x)=\prod_{i=1}^n x_i^{a_i} (\sum_{i=1}^nx_i)^m \\= \frac{1}{n^m}\sum_{b_1+\ldots+b_n=m}\frac{m!}{b_1!\ldots b_n!}\prod_{i=1}^nx_i^{a_i+b_i}$$

可以发现

$$E[\prod_{i=1}^na_i+b_i]=\frac{1}{n^m}\sum_{b_1+\ldots+b_n=m}\frac{m!}{b_1!\ldots b_n!}\prod_{i=1}^n(a_i+b_i)\\=\frac{\partial f}{\partial x_1\ldots \partial x_n}(1,\ldots,1)$$

我们可以直接进行求偏导，得到

$$\begin{aligned} \frac{\partial f}{\partial x_1\ldots \partial x_n}(1,\ldots,1)&=\sum_{I\subseteq N}\frac{A_{m}^{n-|I|}}{n^{n-|I|}} \prod_{i\in I}a_i\\ &=\sum_{t = 0}^n \frac{A_{m}^{t}}{n^{t}}\sum_{I\subseteq N\land |I|=n-t} \prod_{i\in I} a_i \end{aligned}$$

上面的公式右侧可以用FFT得到，总的时间复杂度为$O(n(\log_2n)^2)$

提供一道题目。

题目3：给定数列$A_1,\ldots,A_n$，以及一个整数$m$，现在所有组合$t_1+\ldots+t_n=m$的方案都等概率的前提下，计算$\prod_{i=1}^nA_i^{t_i}$的期望值，结果对素数$P$取模。其中$1\leq n\leq 10^3$，$1\leq m\leq 10^{18}$，$1\leq A_i<P$

提供一道题目

直接给公式：

$$\begin{aligned} E[\prod_{i=1}^nA_i^{t_i}]&=\frac{1}{m+n-1\choose m} \sum_{t_1+\ldots+t_n=m} \prod_{i=1}^nA_i^{t_i}\\ &=\frac{1}{m+n-1\choose m} [x^m]\prod_{i=1}^n \sum_{j} (A_ix)^j\\ &=\frac{1}{m+n-1\choose m} [x^m]\prod_{i=1}^n \frac{1}{1-A_ix}\\ &=\frac{1}{m+n-1\choose m} [x^m]\sum_{i=1}^n \frac{c_i}{1-A_ix}\\ &=\frac{1}{m+n-1\choose m} [x^m]\sum_{i=1}^n \sum_{j} c_i(A_ix)^j\\ &=\frac{1}{m+n-1\choose m} \sum_{i=1}^n c_i A_i^m\\ \end{aligned}$$

其中$c_i=(1-A_1x)(1-A_2x)\ldots (1-A_{i-1}x)(1-A_{i+1}x)\ldots (1-A_nx)$，其中$x=\frac{1}{A_i}$。这里用到的知识点是一个真分式可以唯一表示为多个最简分式之和。

图上随机游走问题

问题1：考虑一副连通图，我们从点$1$出发，在图上随机游走（等概率选择一条出边），图上有几个出口，我们一旦抵达出口，就会离开，问我们从各个出口离开的概率是多少。

最简单的方式是直接模拟，只是有点慢。考虑到转移实际上是一个矩阵，因此结合倍增技术，就可以$O(n^3\log_2M)$求出一个近似解出来。

记$f(i)$表示整个流程经过$i$的期望次数，如果$i$是出口，此时$f(i)$实际上也等于从$i$出口离开的概率。之后可以发现对于$i>1$，有：

$$f(i)=\sum_{(j,i)\in E}\frac{f(j)}{deg(j)}$$

而对于$i=1$，则满足：

$$f(1)=1+\sum_{(j,1)\in E}\frac{f(j)}{deg(j)}$$

我们将$f$相关的部分全部移动到左边，则得到一个方程组$Ax=b$，其中$b=(1,0,0,\ldots,0)^T$，我们要求的就是$x$，其中$x_i=f(i)$。

我们将$A$取逆乘到右边去即可。这里不难发现$x$实际上等于$A^{-1}$的第一列。如果我们从第$i$个点出发，则$x$等于第$A^{-1}$的第$i$列。

矩阵取逆的时间复杂度为$O(n^3)$。

题目2：考虑一副连通图，我们从点$1$出发，在图上随机游走（等概率选择一条出边），图上有唯一的出口，我们一旦抵达出口，就会离开。现在图上有一些点上有陷阱，我们一进入带陷阱的房间会失去一点血量。初始血量为$k$，一旦我们血量减少为$0$就会被困在图中。问我们从出口离开的概率是多少。保证出口和起点没有陷阱。最多有$100$个点带陷阱，$1\leq n\leq 500$，$1\leq k\leq 10^{18}$

提供一道题目。

首先我们为出口也加一个陷阱，同时提高血量一点，很显然能离开的概率是不变的。首先我们可以找到初次到每个陷阱点的概率$x$，以及从每个无陷阱点$i$第一次到某个陷阱点，这个陷阱点是$j$的概率$p_{i,j}$。

之后我们可以算出从某个陷阱$i$离开，下一次进入陷阱点，进入的是$j$的概率，得到一个转移矩阵$A$。很显然我们要求的是$A^{k}x$，这里用快速幂就可以了。

时间复杂度为$O(100^3\log_2100+100^2n+n^3)$。

循环概率递推

问题2：假设有一个很长的走廊，可以分为$n+1$段，每段长度为1。从左到右记作$0,1,\ldots,n$。我们起始在第$0$段，每秒可以移动到下一段。在第$1$到$n-1$段，都有一个陷阱，陷阱一旦触发将会传送我们回到起点。第$i$段的陷阱触发概率为$p_i$，保证$0\leq p_i<1$。一旦我们抵达$n$段后就获得了胜利。问我们获得胜利的期望时间。

可以记$E_i$表示处于第$i$段，胜利的期望时间，那么答案就是$E_0$。可以推出：$E_i=pE_0+(1-p)E_{i+1}+1$。可以发现这里也有循环递推，但是我们发现这里的递推公式是一个线性函数。我们将每个递推公式都表示为$E_i=a_iE_0+b_i$的形式，其中$0\leq a_i<1$。当然也就得到了$E_0=a_0E_0+b_0$，由于$0\leq a_0<1$，因此可以得出$E_0=\frac{b_0}{1-a_0}$。这里的过程可以$O(n)$完成。

最后再考虑一种也是概率重置游戏状态的问题。

问题3：假设有一个游戏，我们需要在$R$秒内通关。游戏总共有$n$关（我们需要打过前一关才能打后一关），第$i$关我们以概率$p_i$在$F_i$秒内通过，以$1-p_i$的概率在$S_i$秒内通过，这里$F_i<S_i$，且$0<p_i<1$，满足$\sum_{i=1}^nF_i\leq R$。当然我们在通过每关后，可以选择进入下一关，或者重置游戏（游戏的计时恢复$0$），问我们要通关，花费的现实时间的期望是多少。这是一道CF原题。

我们用DP的方式解决这个问题，定义$dp(i,j)$表示在第$i$关开始时，游戏计时为$j$，之后通关需要花费的现实时间的期望。那么可以推出转移公式：$dp(i,j)=\min(dp(1,0),p\cdot (dp(i+1,j+F_i)+F_i)+(1-p)(dp(i+1,j+S_i)+S_i))$。这个问题的难点就是$dp(i,j)$的递推公式中有一个$\min$函数，而非关于$dp(1,0)$的线性函数。那这玩意怎么做呢。

做法就是定义一个新的未知数$x$，记$dp_x(i,j)=\min(x,p\cdot (dp_x(i+1,j+F_i)+F_i)+(1-p)(dp_x(i+1,j+S_i)+S_i))$。记$f(x)=dp_x(1,0)$。可以发现$f$是个递增函数，且当$x=dp(1,0)$的时候，一定有$f(x)=x$。这就允许我们用二分来解决这个问题。事实上，$f$还满足当$x<dp(1,0)$时有$f(x)<x$，当$x>dp(1,0)$时有$f(x)>x$。整体的时间复杂度为$O(nR\log_2M)$，其中$M$是精度要求。

你以为完了吗，来看看下面这道题。

问题4：给定一个轮盘，轮盘上分成$n$个连续区域，记作$1,\ldots,n$（由于轮盘是圆形的，因此$1$和$n$是相邻的）。初始时指针等概率随机指向某个区域。之后你可以重复下面操作：假设当前指针指向的轮盘区域为$i$

1. 花费费用$b_i$，指针等概率转向$i-1$或$i+1$。
2. 获得$a_i$，并结束游戏。

你始终会选择是自己期望收益最大的操作。问收益的期望是多少。这里$1\leq n\leq 10^5, 1\leq a_i,b_i\leq 10^8$

首先由于初始时指针所指的位置是随机的，记$f(i)$为初始时指针指向$i$时的收益的期望，那么我们要求的实际上是$\frac{1}{n}\sum_{i=0}^{n-1}f(i)$。

现在我们考虑怎么计算收益的期望。可以发现有：

$$f(i)=\max(a_i,\frac{1}{2}(f(i-1)+f(i+1))-b_i)$$

但是这个公式完全无法解决问题有木有，即使没有这个$\max$也无法用矩阵求逆的方式计算（因为$n$太大了），更何况加上这个恐怖的$\max$，完全搞不了。

不用急，一步步拆解这个问题。可以发现在$a_i$最大的时候，一旦指针指在区域$i$，我们一定会直接选择退出（收益不可能更大了），因此我们可以发现$f(i)=a_i$，这样环就被拆了开来，成了一个序列。现在问题变成了下面形式。

有一个长度为$n+1$的序列$x_1,\ldots,x_n,x_{n+1}$，其中$x_1$和$x_{n+1}$已知，且对于$1<i\leq n$满足

$$x_i=\max(a_i,\frac{1}{2}(x_{i-1}+x_{i+1})-b_i)$$

可以发现问题稍微变得简单点了（没有了环），但是好像还是不太好做。我们可以引入一些新的整数变量$c_1,\ldots,c_{n+1}$，对于$1\lt i\leq n$满足$c_i=\frac{1}{2}(c_{i-1}+c_{i+1})-b_i$。其中$c_1$可以自由定义为某个整数，由于$c_{i+1}=2c_i-c_{i-1}+2b_i$，因此可以推出整个$c$序列。

那么我们将递推公式稍作转换可以得到：

$$x_i-c_i=\max(a_i-c_i,\frac{1}{2}(x_{i-1}+x_{i+1})-b_i-(\frac{1}{2}(c_{i-1}+c_{i+1})-b_i))\\ \Rightarrow x_i-c_i=\max(a_i-c_i,\frac{1}{2}((x_{i-1}-c_{i-1})+(x_{i+1}-c_{i+1})))\\ \Rightarrow y_i=\max(a_i-c_i,\frac{1}{2}(y_{i-1}+y_{i+1}))$$

这里$y_i=x_i-c_i$。

由于这里$a_1$和$a_{n+1}$已知，因此$y_1$和$y_{n+1}$也是已知的。现在这个问题变成了一个赋值问题，这个问题可以通过凸包解决。有兴趣可以参考我们的另外一篇博客《凸包技巧》的二维凸包一节中的题目2。简单说就是计算顶点$(i,a_i-c_i)$构成的上凸包。而$y_i$就是这个上凸包在点$i$处的高度。

这里我们可以$O(n\log_2n)$构建凸包（当然实际上可以线性构建），就可以解决问题了。

提供一道题目。

问题5：你需要搜集$n$种不同的卡牌，你目前手头已经拥有了$m$张种类不同的卡牌，之后你可以不断得到新的一张卡牌（直到凑集到所有类型的卡牌），卡牌的种类等概率为任意一种。问收集到所有卡牌时，你手头拥有的期望卡牌数。其中$1\leq m\leq n \leq 10^6$

记$f(i)$表示已经拥有$i$类卡牌，搜集完所有类型卡牌的期望步骤数。很显然结果为$f(m)+m$。

可以发现

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

但是这里实际上是存在循环的，我们可能在原地踏步。有环的话一般我们可以采用高斯消元的技术解决，时间复杂度为$O(n^3)$。但是这里我们只需要将右边的$f(i)$移动到左边就可以解决循环。

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

其中$f(n)=0$。可以发现每个状态的计算都仅依赖值更大的项目，因此递推公式无环，是可以直接线性求解的。

问题6：给定一个长度为$n$的单元格，从左到右记作$1,2,\ldots,n$。记$f(i)$表示放一只蚂蚁在第$i$个单元格，蚂蚁从1的左侧离开或从$n$的右侧离开的期望时间，这里蚂蚁每一秒都会等概率向左移动一格、向右移动一格，或保持原地不动。要求计算$f(1),\ldots,f(n)$并输出结果。其中$1\leq n\leq 10^6$

这个是经典的循环递推问题。很容易得到公式：

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

可以发现这里存在了循环，且不能简单通过移项解决这个问题。但是如果我们把右边除了$f(i+1)$项外全部移动到左边，则有：

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

可以发现上面的递推公式中，参数较大的状态仅依赖于参数较小的状态，因此上面的递推关系无环，我们可以直接线性求解。

但是这里有一个问题，上面的公式仅对$1\leq i\leq n$是适用的，换言之我们可以用其计算$f(2),\ldots,f(n+1)$，但是对于$f(1)$是不适用的。我们该如何计算$f(1)$呢？要知道算不出$f(1)$，后面的所有状态也是算不出的。

这种问题有一个非常重要的技巧，就是记$x=f(1)$，接下来我们发现进行递推的时候会满足$f(i)=a_ix+b_i$，即是$x$的线性函数。由于$f(n+1)=a_{n+1}x+b_{n+1}=0$，因此$x=-\frac{b_{n+1}}{a_{n+1}}$。之后求解出$x$后，重新代入就可以算出任意$f(i)$了。

提供一道题目：SRM752 1000。

题目7：给定一个包含$n$个顶点的单向图。之后每个回合你允许沿着出现的边前进或者在原地等待。每个回合开始前边$(i,j)$出现的概率为$p_{i,j}$。在最优策略下，问从顶点$1$到顶点$n$所需回合数的期望。其中$2\leq n\leq 2000$，如果不可达输出$-1$。

很容易发现期望关系存在循环，因此我们需要用松弛操作来实现，这样的话时间复杂度为$O(n^3)$，太慢了。

这里我们实际上可以用上Dijkstra。我们从顶点$n$作为起点倒推。考虑一个顶点$u$在决策的时候，不妨设其余顶点根据期望大小排序为$a_1,a_2,\ldots,a_{n-1}$，那么最优决策的时候我们一定选择某个$k$，如果前面$k$个顶点任意一个可以抵达，则直接沿着期望最小的顶点出发，否则就等待。对于顶点$a,b$，当且仅当$E(a)\lt E(b)$，才有可能通过$a$优化$b$，但是优化后依旧有$E(a)\lt E(b)$成立。这个非常类似于最短路。因此我们每次取当前期望最小的顶点跑松弛，我们可以用$O(V^2)$的Dijkstra算法，时间复杂度为$O(n^2)$。

提供一道题目。

假设$u$的当前期望公式为$E(u)=Ap+(1-p)E(u)+1$，则可以简化为$E(u)=A+\frac{1}{p}$。考虑一个概率为$t$，记$q=(1-p)t$，且期望为$A+\frac{1}{p}+\delta$的优化：

$$E(u)=Ap+(A+\frac{1}{p}+\delta)q+(1-p-q)E(u)+1$$

简化后的公式为：

$$E(u)=A+\frac{1}{p}+\delta \times \frac{p}{p+q}$$

因此当且仅当$\delta\lt 0$，能产生优化效果。

赌博破产问题

考虑你有$n$的本钱，你参加赌博，每轮有$p$的概率得到$1$单位钱，或以$1-p$的概率失去$1$单位钱。一旦你的钱为$0$或者达到你的预期值$S=n+m$，那么你就必须立即结束赌博，如果钱为$0$，就认为你赌博失败，否则认为赌博成功。

这个问题可以描述为一维空间中的随机游走问题，一开始我们处于点$n$，我们以$p$的概率往左移动，或者以$1-p$的概率往左移动一步。当我们抵达$S$或$0$时过程结束，到达$S$时获胜，到达$0$时失败。

现在我们考虑我们在结束时成功的概率（即移动到$S$）。记$f(i)$表示为手头有$i$本钱下成功的概率，容易发现$f(0)=0,f(S)=1$。

要计算$f(n)$，我们可以发现对于$0<i<S$，一定有$f(i)=pf(i+1)+(1-p)f(i-1)$。这为我们提供了一个递推式：

$$f(i+1)=\frac{1}{1-p}(f(r)-pf(r-1))$$

有递推式，但是我们还不知道$f(1)$。要计算$f(1)$，我们可以设其为$x$，则根据递推式将所有值都改写为$f(i)=a_ix+b_i$的形式，根据$a_{S}x+b_{S}=1$得出$x=\frac{1-b_S}{a_S}$。这个过程是线性的，但是如果我们发现$a_i$和$b_i$的计算时独立的，因此我们可以用矩阵快速幂的技术在$O(\log_2S)$时间复杂度内分别求出$a_S$和$b_S$。

一旦我们知道了$f(0)$与$f(1)$，我们就可以用快速幂在时间复杂度$O(\log_2n)$内求出任意一个$f(n)$。

这里特殊说一下，当$p=\frac{1}{2}$时，$f(i)=\frac{i}{S}$。

上面我们讨论了怎么计算退出时成功失败的概率，下面讲一下怎么计算退出前移动次数的期望，这里的推出可能是抵达$S$或$0$。记$g(i)$表示当前处于点$i$时，退出前期望移动次数。那么可以推出递推公式，那么特殊的$g(0)=g(S)=0$

$$g(i)=pg(i+1)+(1-p)g(i-1)+1$$

这玩意也是递推公式，我们可以用求$f(n)$相同的方式$O(\log_2S)$求$g(n)$。

多重排列的概率计算

考虑这样一个问题。

问题1：有$m$种颜色的球，第$i$种球有$a_i$个，$\sum_{i=1}^ma_i=n$。现在随机将这些球排成一行，要求计算相同种类的球紧密排列的概率。

由于是多重排列，因此不太好算。如果每种球上都有一个编号的话，会发现每种排列的概率都是$\frac{1}{n!}$。但是事实上，可以发现每种多重排列（即相同颜色的球交换认为是同一种排列），多对应$\prod_{i=1}^ma_i!$（这是一个常数哦）种带编号的排列，因此不同的多重排列的概率都是相等的。

那么现在我们就是求有多少种多重排列能紧密排列这些球，很显然有$m!$种多重排列，因此答案为$m!/\frac{n!}{\prod_{i=1}^ma_i!}$。

这里可以发现，带编号的随机均匀排列，也意味着不带编号（多重排列）的均匀排列。

条件期望

这一篇我想写很久了。先看一个问题吧：

问题1：考虑手头有一个计数器，初始为0。之后每回合它会以概率$p_1$，增加1，以概率$p_2$减少1，以及概率$1-p_1-p_2$保持不变。当计数器变成非0时，就不再改变。已知计数器最终变成了$1$，问计数器变成1时经过的回合数的期望。

这个问题我之前用错误的想法来做，所以得到的结果总是错误。先看一下我的错误方法。记$x$表示已知最终变成$1$，需要的步骤数的期望。那么可以推出：

$$x=\frac{1-p_1-p_2}{1-p_2}x+1\Rightarrow x=\frac{1-p_2}{p_1}$$

这个公式简单代入会发现好像是那么回事，但是这是错误的。考虑在已知最终变成$-1$的前提下，经过的回合数的期望为$y$，可以容易得出$y=\frac{1-p_1}{p_2}$。之后根据全期望公式得到：

$$E=\frac{p_1}{p_1+p_2}x+\frac{p_2}{p_1+p_2}y=\frac{1-p_2}{p_1+p_2}+\frac{1-p_1}{p_1+p_2}=\frac{2}{p_1+p_2}-1$$

其中$E$表示计数器变成非$0$前经过的回合数期望，容易知道$E=(1-p_1-p_2)E+1\Rightarrow E=\frac{1}{p_1+p_2}$，和我们之前推出的部分是不同的。

那么为什么我们算出来的结果是错的呢，因为转移公式写的好像都没什么问题啊。事实上，转移写的是没问题的，但是概率却错了，在已知所有数变成$1$的前提下，记$\delta$表示第一次变动的值，$s$表示技数器最终显示的值，需要知道$\frac{p(\delta=0)}{p(\delta=1)}\neq \frac{p(\delta=0\mid s=1)}{p(\delta=1\mid s=1)}$，即有条件概率和不带条件的概率，二者不一定能满足等比。

事实上很显然有$p(\delta=-1\mid s=1)=0$，是不可能发生的。而

$$p(\delta=1\mid s=1)=\frac{p(\delta=1\land s=1)}{p(s=1)}=\frac{p_1}{\frac{p_1}{p_1+p_2}}=p_1+p_2$$

同理可以得到

$$p(\delta=0\mid s=1)=\frac{p(\delta=0\land s=1)}{p(s=1)}=\frac{(1-p_1-p_2)p(s=1)}{p(s=1)}=1-p_1-p_2$$

也可以通过全概率公式可以得到：

$$p(\delta=0\mid s=1)=1-p(\delta=1\mid s=1)-p(\delta=-1\mid s=1)=1-p_1-p_2$$

即停止不动的条件概率并没有因为条件的加入而增大，保持了不变，而原先$\delta=-1$的概率加入到了$\delta=1$的概率中。因此正确的期望公式应该写作：

$$x=(1-p_1-p_2)x+1\Rightarrow x=\frac{1}{p_1+p_2}$$

这时候还会惊讶的发现$x=y=E$的成立。

提供一道题目。

上面的是不是很神奇，我们将学到的知识再次应用到下面的问题中。

问题2：你有参加了一场赌博，本金为$n$，每次的赌注为$1$。之后赢的概率为$p_1$，输的概率为$p_2$，以概率$1-p_1-p_2$不输不赢。当手头金额为$0$或达到$m$后就会退出，如果最终本金达到$m$就称为获胜，否则称为失败。问在获胜前提下，期望参加赌博的局数。其中$1\leq n\leq m\leq 10^6$，$p_1+p_2\leq 1$，且$0<p_1$。

这是赌博破产问题，我们可以$O(m)$对所有$0\leq i\leq m$求出$w(i)$，即本金为$i$，获胜的概率。

现在来求期望。可以令$f(i)$表示本金为$i$到游戏结束的期望步数，即指示变量$s=1$表示最终胜利，$s=0$表示最终失败。考虑本金为$i$时，下一轮游戏的金钱变化量$\delta$，可以发现

$$\begin{aligned} &p(\delta=1\mid s=1)=\frac{p(\delta=1\land s=1)}{p(s=1)}=\frac{p_1w(i+1)}{w(i)}\\ &p(\delta=-1\mid s=1)=\frac{p(\delta=-1\land s=1)}{p(s=1)}=\frac{p_2w(i-1)}{w(i)}\\ &p(\delta=0\mid s=1)=1-p(\delta=1\mid s=1)-p(\delta=-1\mid s=1) \end{aligned}$$

这样我们就可以推出$f$的转移公式：

$$\begin{aligned} &f(i\mid s=1)=p(\delta=1\mid s=1)f(i+1\mid s=1)+p(\delta=-1\mid s=1)f(i-1\mid s=1)+p(\delta=0\mid s=1)f(i\mid s=1)+1\\ &p(\delta=1\mid s=1)f(i+1\mid s=1) =(1-p(\delta=0\mid s=1))f(i\mid s=1) -p(\delta=-1\mid s=1)f(i-1\mid s=1)-1 \end{aligned}$$

于是我们可以用经典的方式（用$x$表示$f(1)$，将其它数表示成关于$x$的线性函数）$O(m)$时间复杂度内对所有$0\leq i\leq m$计算出所有$f(i)$。

鞅的停时定理

离散时间鞅是对于所有$n$都满足

• $\mathbf {E} (\vert X_{n}\vert )<\infty$
• $\mathbf {E} (X_{n+1}\mid X_{1},\ldots ,X_{n})=X_{n},\quad n\in \mathbb {N}$

的时间离散的随机过程 $X1,X2,X3,\ldots$，也就是说，已知之前所有观测值，若下一次观测值的条件期望等于本次观测值，则称这一随机过程（即随机变量序列）是离散时间鞅。

鞅的停时定理：设$T$是鞅过程$X_t$的停止时间，则当下面三个条件之一成立时，有$E[X_T]=X_0$：

• $\exists B(P(T\leq B)=1)$。
• $\exists B\forall t(|X_{t+1}-X_t|\leq B)$，且$E[T]<\infty$。
• $\exists B\forall t(|X_t|\leq B)$，且$P(T<\infty)=1$。

三个条件，对$X_t$的要求越来越高，对$T$的要求越来越松。

利用参考文献《一类概率期望问题的杀器：势函数和鞅的停时定理》中提到的方式，我们可以用鞅的停时定理解决很多问题。

对于随机过程$A_0,A_1,\ldots$，构造一个特殊的函数$\phi(A_t)$，记$T$是随机过程的停时，且满足

• $E[\phi(A_{t+1})-\phi(A_{t})|A_t,\ldots,A_0]=-1$
• $\phi(A_T)$为常数

接下来我们定义$X_t=\phi(A_t)+t$。则一定有：

$$E[X_{t+1}-X_{t}|X_t,\ldots,X_0]=0$$

如果同时$X_0,X_1,\ldots$是鞅，且$X_t$与$T$满足停时定理的要求，则根据停时定理可以得出：

$$E[T]=E[T+X_0-X_T]=\phi(A_0)-\phi(A_T)$$

题目1：给定$n$种不同颜色，第$i$种颜色有$a_i$个球。之后重复下面操作直到所有求的颜色相同。每次取两个球，将后取出的球的颜色变成先取出的球的颜色，问期望操作次数。其中$1\leq n,a_i\leq 10^5$, $\sum_{i}a_i\leq 10^9$

这是CF原题。

记$m=\sum_{i=1}^na_i$。

我们可以用停时定理解决这个问题。记$A_t=(a_{t,1},\ldots,a_{t,n})$，其中$a_{t,i}$表示第$t$轮结束后颜色为$i$的球的数目。

记$\phi(A_t)=\sum_{i=1}^nf(a_{t,i})$，那么可以得到：

$$\begin{aligned} E[\phi(A_{t+1})|A_t,\ldots,A_0]&=\sum_{i=1}^nE[f(a_{t+1,i})|A_t,\ldots,A_0]\\ &=\sum_{i=1}^n\frac{a_{t,i}(m-a_{t,i})}{m(m-1)}(f(a_{t,i}+1)+f(a_{t,i}-1))+(1-\frac{2a_{t,i}(m-a_{t,i})}{m(m-1)})f(a_{t,i})\\ &=\phi(A_t)+\sum_{i=1}^n\frac{a_{t,i}(m-a_{t,i})}{m(m-1)}(f(a_{t,i}+1)+f(a_{t,i}-1)-2f(a_{t,i})) \end{aligned}$$

考虑到我们希望

$$\begin{aligned} E[\phi(A_{t+1})-\phi(A_t)|A_t,\ldots,A_0]&=-1\\ \phi(A_t)+\sum_{i=1}^n\frac{a_{t,i}(m-a_{t,i})}{m(m-1)}(f(a_{t,i}+1)+f(a_{t,i}-1)-2f(a_{t,i}))&=\phi(A_t)-1\\ \sum_{i=1}^n\frac{a_{t,i}(m-a_{t,i})}{m(m-1)}(f(a_{t,i}+1)+f(a_{t,i}-1)-2f(a_{t,i}))+\frac{a_{t,i}}{m}&=0 \end{aligned}$$

上面的公式中，如果我们可以令：

$$\frac{x(m-x)}{m(m-1)}(f(x+1)+f(x-1)-2f(x))+\frac{x}{m}=0$$

那么可以得出：

$$\begin{aligned} \frac{x(m-x)}{m(m-1)}(f(x+1)+f(x-1)-2f(x))+\frac{x}{m}&=0\\ f(x+1)+f(x-1)-2f(x)&=-\frac{(m-1)}{(m-x)} \end{aligned}$$

记$g(x)=f(x)-f(x-1)$，可以得出：

$$g(x+1)-g(x)=-\frac{m-1}{m-x}$$

可以得出$g(x)=g(0)-\sum_{i=0}^{x-1}\frac{m-1}{m-i}$。对应的

$$\begin{aligned} f(x)&=f(0)+\sum_{i=1}^xg(i)\\ &=f(0)+\sum_{i=1}^x[g(0)-\sum_{j=0}^{i-1}\frac{m-1}{m-j}]\\ &=f(0)+xg(0)-\sum_{j=0}^{x-1}\frac{m-1}{m-j}\sum_{i=j+1}^x\\ &=f(0)+xg(0)-(m-1)\sum_{j=0}^{x-1}\frac{x-j}{m-j}\\ &=f(0)+xg(0)-(m-1)\sum_{j=0}^{x-1}\frac{x-m+m-j}{m-j}\\ &=f(0)+xg(0)-(m-1)\sum_{j=0}^{x-1}\frac{x-m+m-j}{m-j}\\ &=f(0)+xg(0)-(m-1)x-(m-1)(x-m)\sum_{j=0}^{x-1}\frac{1}{m-j} \end{aligned}$$

这里我们可以让$f(0)=0$，$g(0)=m-1$，那么我得到：

$$\begin{aligned} f(x)&=(m-1)(m-x)\sum_{j=0}^{x-1}\frac{1}{m-j} \end{aligned}$$

此时有$\phi(A_T)=\sum_{i=1}^nf(a_{T,i})=0$，是个常数，因此可以用停时定理得到：

$$\begin{aligned} E[T]&=\phi(A_0)-\phi(A_T)\\ &=\phi(A_0)\\ &=\sum_{i=1}^nf(a_{i}) \end{aligned}$$

时间复杂度为$O(\max_i(a_i)+n)$。

话说推出这些东西，比赛应该已经结束了吧。

用期望计算概率

考虑一副有$n$个顶点，$m$条边的有向图$G=(V,E)$，$A,B\subseteq V$。我们等概率向某个$A$中顶点放置一只蚂蚁，蚂蚁每秒钟，都会等概率沿着一条边移动到一个相邻的顶点上。如果蚂蚁一旦从抵达$B$中顶点，就结束。保证对于每个点都存在至少一条路径，以它开始，以某个$B$中顶点结束。要求计算蚂蚁从各个可能的$B$中顶点离开的概率。

可以删掉所有从$B$中顶点出发的边，因为这些不可能走过。

我们可以发现这个问题并不好求解，比如用$dp(i,j)$表示第$i$时蚂蚁在顶点$j$，但是由于蚂蚁的离开时间可能任意大，因此这个方式无法求解。

记$L$表示蚂蚁最终从哪个顶点离开。我们可以记$T_v$表示蚂蚁经过顶点$v$的期望次数，可以发现如果$v$是终点，当蚂蚁最终从这个顶点离开，那么有$T_v=1$，否则$T_v=0$，可以发现$E[T_v]=p(L=v)$，因此我们只需要对所有顶点$v$求出$E[T_v]$即可。

我们可以推出恒等式：

$$E[T_v]=\frac{1}{|A|}[v\in A]+\sum_{(u, v)\in E}E[T_u]$$

这个等式最后可以通过线性方程组求解，时间复杂度为$O(n^3)$。

一些生存概率问题

给定$n$个史莱姆排成一行，每回合都会等概率挑选两只相邻的史莱姆进行战斗，并且等概率一方胜利，另一方退场（之后退场的史莱姆两端的史莱姆就相邻了）。重复上面过程，直到只剩下一只史莱姆。对于所有$i$，问第$i$只史莱姆的存活概率$P_i$为多少。

在第$i$只史莱姆存活的前提下，很显然对于$x<i<y$，$x,y$都不会发生战斗，因此我们可以将$n$只史莱姆拆成两段，分别为$i$只史莱姆和$n-i+1$只史莱姆，且都是最左边的史莱姆存活，两边是独立事件，因此概率为二者之积。

记$f(i)$表示有$i$只史莱姆排成一列，最左边的史莱姆胜出的概率。则有$P_i=f(i)f(n-i+1)$。

可以发现$f(1)=1$，且对于$i>1$，有

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

上面的过程可以$O(n)$求解。

题目：给定$n$个史莱姆排成一行，每回合都会等概率挑选两只相邻的史莱姆进行战斗，第$i$只史莱姆的强度为$a_i$。如果两只强度分别为$x,y$的史莱姆战斗，前者胜利的概率为$\frac{x}{x+y}$，后者胜利的概率为$\frac{y}{x+y}$。胜者留下，另一方退场（之后退场的史莱姆两端的史莱姆就相邻了）。重复上面过程，直到只剩下一只史莱姆。对于所有$i$，问第$i$只史莱姆的存活概率$P_i$为多少。

这是SRM 759的EllysTournament.

定义$f(l,r,x)$表示仅考虑$[l,r]$区间中的史莱姆，其中第$x$只史莱姆胜出的概率。同时定义$L(l,r),R(l,r)$分别表示仅考虑区间$[l,r]$中的史莱姆战斗，左边/右边获胜的概率。

先考虑$f(l,r,x)$怎么计算，很显然有$f(l,r,x)=R(l,x)L(x,R)$。

再来考虑$L(l,r)$怎么计算，这有一个套路，就是枚举最后与$l$战斗的史莱姆的编号$x$，则有：

$$\begin{aligned} L(l,r)&=\sum_{l<x}\sum_{l\leq m<x}\frac{1}{r-l}L(l,m)f(m+1,r,x)\frac{a_l}{a_l+a_x}\\ &=\frac{1}{r-l}\sum_{l<x}\frac{a_l}{a_l+a_x}\sum_{l\leq m<x}L(l,m)L(x,r)R(m+1,x)\\ &=\frac{1}{r-l}\sum_{l<x}\frac{a_l}{a_l+a_x}L(x,r)\sum_{l\leq m<x}L(l,m)R(m+1,x) \end{aligned}$$

对于$\sum_{l\leq m<x}L(l,m)R(m+1,x)$，我们可以用另外一个函数$g(l,x)$指代。于是结果为：

$$L(l,r)=\frac{1}{r-l}\sum_{l<x}\frac{a_l}{a_l+a_x}L(x,r)g(l,x)$$

同理可以得出$R$的递推公式：

$$\begin{aligned} R(l,r)&=\sum_{x<r}\sum_{x\leq m}\frac{1}{r-l}R(m+1,r)f(l,m,x)\frac{a_r}{a_r+a_x}\\ &=\frac{1}{r-l}\sum_{x<r}\frac{a_r}{a_r+a_x}\sum_{x\leq m}R(m+1,r)L(x,m)R(l,x)\\ &=\frac{1}{r-l}\sum_{x<r}\frac{a_r}{a_r+a_x}R(l,x)\sum_{x\leq m}R(m+1,r)L(x,m)\\ &=\frac{1}{r-l}\sum_{x<r}\frac{a_r}{a_r+a_x}R(l,x)g(x,r) \end{aligned}$$

可以发现处理$g,f,L,R$的时间复杂度都是$O(n^3)$，因此总的时间复杂度为$O(n^3)$。

题目3：给定$n$个史莱姆排成一行，每回合都会等概率挑选两只相邻的史莱姆进行战斗，第$i$只和第$j$只史莱姆战斗的结果是已知的，为$a_{i,j}$。胜者留下，另一方退场（之后退场的史莱姆两端的史莱姆就相邻了）。重复上面过程，直到只剩下一只史莱姆。问哪些史莱姆有机会成为冠军。

一道Atcoder的题目

用类似上一题的技术，我们可以直接得到一个$O(n^3)$时间复杂度的算法。但是实际上由于我们不求概率而是是否有机会存活，因此可以用BitSet进行优化，将时间复杂度优化到$O(\frac{n^3}{64})$。

题目4：给定一棵树，树上有$n$个顶点，上面标号分别为$1,2,\ldots,n$，以及$n-1$条边。之后会等概率取一条没取过的边，记作$(u,v)$，之后等概率将所有$u$的标号替换为$v$的标号或将所有$v$的标号替换为$u$的标号。重复上面操作$n-1$次，很显然所有标号都会相同，要求对所有标号$i$计算最后所有标号都是$i$的概率$P_i$。

一道CF原题。

考虑以$1$作为根的情况，我们希望计算$P_1$。

算概率比较麻烦，我们可以通过计算方案数，最后除去总的方案数$2^{n-1}(n-1)!$就是概率了。

• 记$f(u,i)$表示$u$子树中的共$deg(u)-1$条边被处理了$i$条后，顶点$u$的标号变成了$1$的方案数。
• 记$p$为$u$的父顶点，记$g(u,i)$表示$u$子树中的边加上$(u,p)$这条边，总共$deg(u)$条边，前$i$条边处理完后，$p$的标号变成$1$的方案数。

先考虑如何计算$f(u,i)$，假设$u$的孩子有$a,b,c$三个，则有

$$f(u,i)=\sum_{x+y+z=i}g(a,x)g(b,y)g(c,z)\frac{i!}{a!b!c!}\frac{(deg(u)-1-i)!}{(deg(a)-x)!(deg(b)-y)!(deg(c)-z)!}$$

上面的公式其实类似于卷积，由于任意两个顶点只会在二者LCA处产生一次贡献，因此计算$f$的总时间复杂度为$O(n^2)$。

之后考虑如何计算$g(u,i)$，我们可以枚举$(u,p)$这条边被处理的时机，设$j$为$(u,p)$在$u$的所有子树中的边+$(u,p)$边中，属于前$j$条被处理的。

• 如果$j\leq i$，则处理$(u,p)$的时候$p$的标号还不是$1$，此时$u$在前$i-1$条子树中的边被处理后变成标号1，因此贡献为$2f(u,i-1)$，其中乘上2是因为处理$(u,p)$的时候标号有两种取法。
• 如果$j>i$，则此时处理$(u,p)$边的时候，保留的标号只能取$1$。且此时对$g(u,i)$产生的贡献大小为$f(u,j-1)$。

因此有：

$$g(u,i)=\sum_{1\leq j\leq i}2f(u,i-1)+\sum_{i<j}f(u,j-1)$$

上面的$g$我们可以利用前缀和的方式加速计算，计算$g$的总的时间复杂度为$O(n^2)$。

而我们要求得结果为$f(1,0)$。

对一个顶点跑一次算法的时间复杂度为$O(n^2)$，对每个顶点跑一次算法的时间复杂度为$O(n^3)$。

题目5：给定$n$个人，只有$1$个狼人和$n-1$个村民。第$i$个人的嫌疑程度为$a_i$。之后重复下面流程直到只剩下一个人。

在剩余的人中随机选择一个人，选择第$k$个人的概率为$a_k/S$，其中$S$为剩下的人的嫌疑程度之和。并将他投票出局。

现在已知玩家$n$是狼人，问狼人获胜的概率是多少。其中$1\leq n\leq 10^5$，$1\leq a_i$且$\sum_{i=1}^na_i\leq 10^5$。结果对素数$M$取模。

提供一道题目。

踢人操作比较麻烦，我们可以改为把玩家标记为删除，之后如果某个被删除的玩家被选中，就重复标记就好了。现在问题要求问我们第$n$人是被最后标记的概率。

我们可以考虑狼人失败的概率是多少。狼人失败当且仅当它在一个村民出局之前出局。很显然狼人作为第一人出局的概率为$a_n/S$。

记$A_i$表示狼人在第$i$个村民之前出局的概率。那么我们计算$P(X)$，狼人在$X$代表的村民集合中任意村民出局前出局的概率。之后通过容斥求出狼人失败的概率。

由于范围比较大，DP不好做。我们可以用生成函数来计算，其中$f_i(x)=-x^{a_i}+1$，而$F=f_1f_2\cdots f_{n-1}$。其中$-[x^i]F$表示的是所有总嫌疑为$i$的集合，奇大小集合数减去偶大小集合数的结果。我们可以用$F$直接做容斥。时间复杂度$O(\sum_{i=1}^na_i \times (\log_2 \sum_{i=1}^na_i)^2)$。

题目6：给定$n$个人，只有$1$个狼人和$n-1$个村民。第$i$个人的嫌疑程度为$a_i$。之后重复下面流程直到只剩下一个人。

在剩余的人中随机选择一个人，选择第$k$个人的概率为$a_k/S$，其中$S$为剩下的人的嫌疑程度之和。并将他投票出局。

现在已知玩家$1$到玩家$m$都是狼人，问所有村民出局的期望回合数是多少。其中$1\leq n\leq 10^5$，$1\leq a_i$且$\sum_{i=1}^na_i\leq 10^5$，$1\leq m\leq \min(n,100)$。结果对素数$M$取模。

提供一道题目。

我们要讨论所有村民出局的回合数，自然是$n-m$加上出局的狼人数。考虑到期望的线性性质，因此可以单独考虑每个狼人，考虑这个狼人在某个村民出局前出局的概率。这时候问题变成了题目5，如法炮制即可。

时间复杂度为$O(\sum_{i=1}^na_i \times (\log_2 \sum_{i=1}^na_i)^2+m\sum_{i=1}^na_i)$。

骰子问题

题目1：屏幕上有一个数字$x$，之后执行$m$次操作。每次操作将$x$等概率替换为$0$到$x$中的某个数。提供$P=(p_0,p_1,\ldots,p_n)$，分别表示初始值$x$为$i$的概率（它们的和保证为$1$），要求执行$m$次操作后，屏幕上的数字为$0,1,\ldots,n$的概率分别是多少。其中$1\leq n\leq 10^5$，$0\leq m\leq 10^{18}$，结果对某个素数$p$取模。

提供一道题目。

可以推出概率矩阵如下：

$$A=\left[ \begin{array}{cccccc} \frac{1}{1} & \frac{1}{2} & \frac{1}{3} & \ldots & \frac{1}{n} &\frac{1}{n+1}\\ 0 & \frac{1}{2} & \frac{1}{3} & \ldots & \frac{1}{n} & \frac{1}{n+1}\\ 0 & 0 & \frac{1}{3} & \ldots & \frac{1}{n} &\frac{1}{n+1}\\ 0 & 0 & 0 & \ldots & \frac{1}{n} &\frac{1}{n+1}\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots\\ 0 & 0 & 0 & \ldots & 0 & \frac{1}{n+1}\\ \end{array} \right]$$

可以发现它是上三角矩阵，我们可以直接得到$A$的特征值$\Lambda=(\frac{1}{1}, \frac{1}{2}, \ldots, \frac{1}{n+1})$。借助特征值可以得到由对应的特征向量组成的矩阵$V$，其中$V_{i,j}=(-1)^{j-i}{j\choose i}$，而它的逆矩阵为$V^{-1}_{i,j}={j\choose i}$。

根据特征值分解可以得到：$A=Vdiag(\Lambda)V^{-1}$，而$A^m=Vdiag(\Lambda)^mV^{-1}$。

到这一步时间复杂度已经优化到$O(n^2)$，但是还是不够快。我们可以引入多项式卷积，可以发现

$$\begin{aligned} (V^{-1}P)_i&=\sum_{j=0}^n {j\choose i} P_j\\ &=\frac{1}{i!}\sum_{j=0}^n (j!P_j)\cdot (\frac{1}{(j-i)!}) \end{aligned}$$

这是个等差卷积。可以直接用FFT解决。同理$V(diag(\Lambda)V^{-1}P)$的乘积也可以用类似的卷积公式的出，总的时间复杂度为$O(n\log_2n)$。

这里简单证明一下$V^{-1}$的形式。记$W=VV^{-1}$，可以发现对于对角线元素

$$\begin{aligned} W_{i,i}&=\sum_{k=0}^nV_{i,k}V^{-1}_{k,i}\\ &=\sum_{k=0}^n(-1)^{k-i}{k\choose i}{i\choose k}\\ &=(-1)^{i-i}{i\choose i}{i\choose i}\\ &=1 \end{aligned}$$

由于$V$和$V^{-1}$都是上三角矩阵，因此$W$一定也是上三角矩阵。考虑$W_{i,j}$，其中$j>i$的情况

$$\begin{aligned} W_{i,j}&=\sum_{k=0}^nV_{i,k}V^{-1}_{k,j}\\ &=\sum_{k=0}^n(-1)^{k-i}{k\choose i}{j\choose k}\\ &=\sum_{k=0}^n(-1)^{k-i}\frac{j!}{i!(k-i)!(j-k)!}\\ &=\frac{j!}{(j-i)!i!}\sum_{k=0}^n(-1)^{k-i}\frac{(j-i)!}{(k-i)!(j-k)!}\\ &=\frac{j!}{(j-i)!i!}\sum_{k=0}^n(-1)^{k-i}{j-i\choose k-i}\\ &=\frac{j!}{(j-i)!i!}\sum_{k=0}^{j-i}(-1)^k{j-i\choose k}\\ &=\frac{j!}{(j-i)!i!}(1-1)^{j-i}\\ &=0 \end{aligned}$$

因此我们可以发现$W=I$，到此证明了$V$和$V^{-1}$互逆。

一类最大值的期望问题

题目1：给定$n$个相互独立的随机变量$x_1,\ldots,x_n$，每个随机变量可以在$[1,m]$之间均匀取值。要求计算$E[\max_{i=1}^nx_i]$。其中$n\leq 10^3$,$1\leq m\leq 10^9$

我们要求的是：

$$\begin{aligned} E[\max_{i=1}^nx_i]&=\sum_{j=1}^mj\cdot p(\max_{i=1}^nx_i=j)\\ &=\sum_{j=1}^mj\cdot (p(\max_{i=1}^nx_i\leq j)-p(\max_{i=1}^nx_i\leq j-1))\\ &=m\cdot p(\max_{i=1}^nx_i\leq m)-\sum_{j=1}^{m-1}p(\max_{i=1}^nx_i\leq j)\\ &=m-\sum_{j=1}^{m-1}(\frac{j}{m})^n \end{aligned}$$

其中后者是$k$次幂前缀和问题，我们可以插值后求解。总的时间复杂度为$O(n)$。

题目2：给定$n$个相互独立的随机变量$x_1,\ldots,x_n$，每个随机变量可以在$[0,1]$之间均匀取值。要求计算$E[\max_{i=1}^nx_i]$

记$y=\max_{i=1}^nx_i$，我们考虑一下$y$的概率密度函数。我们知道其分布函数为：

$$F_y(t)=P(y\leq t)=t^n$$

而对分布函数求导可以的到概率密度函数：

$$f_y(t)=F'_y(t)=nt^{n-1}$$

代入到期望公式中可以得出：

$$\begin{aligned} E[\max_{i=1}^nx_i]&=\int_{0}^1 tf_y(t)dt\\ &=\int_{0}^1 nt^ndt\\ &=\frac{n}{n+1} \end{aligned}$$

题目3：给定$n$个相互独立的随机变量$x_1,\ldots,x_n$，每个随机变量可以在$[0,1]$之间均匀取值。记$y$为$n$个随机变量中第$k$小的变量，要求计算$E[y]$

这个问题在参考资料中的《n个随机变量中第k小值的期望》一文中有一种很秀的解法。我们额外加入一个新的随机变量$x_0$，我们考虑$E[y]$的公式：$\int_{0}^1 tf_y(t)dt$。同时考虑一下$P(x_0\lt y)$的概率，其公式为：$\int_{0}^1 tf_y(t)dt$。可以发现$E[y]=P(x_0\lt y)$。接下来我们考虑计算$P(x_0\lt y)$来得到结果。

这等价于有$n+1$个随机变量，第$0$个随机变量为最小的$k$个随机变量中的一个。由于所有$n+1$个变量的排列等概率，其中仅$kn!$是有效的，因此概率为$\frac{k}{n+1}$。

摸瞎问题

考虑一个游戏，你需要蒙住眼睛去找自己的$n$个伙伴。每次你抓住一个伙伴后，需要猜出他的编号。如果每个伙伴都被你抓住且猜对后，游戏结束。但是你在抓住某个伙伴并提出猜想后，伙伴回到游戏中，且你不知道之前的猜想是否正确，只有在你完成目标后，裁判会宣布游戏结束。你需要选择策略，使得游戏进行的轮数的期望（抓人次数）最小化，输出在最优策略下轮数的期望。且第$i$个小伙伴被抓住的概率为$p_i$，在每一轮的游戏中这个概率不变，且$\sum_{i=1}^np_i=1$。其中$p_i\geq 0.01$，$1\leq n\leq 100$

提供一道题目。

我们记录$g_i$表示在给定策略下游戏会在前$i$轮结束的概率。则结果为：

$$\sum_{i=1}^{\infty} i (g_i-g_{i-1})$$

我们可以写成极限的形式：

$$\lim_{N \rightarrow \infty} \sum_{i=1}^N i(g_i-g_{i-1})=\lim_{N \rightarrow \infty} Ng_N-g_{N-1}-\ldots-g_1$$

其中由于$N$足够大的之后，$g_N$无限接近$1$，因此我们可以重新写作：

$$\lim_{N \rightarrow \infty} N-g_{N-1}-\ldots-g_1$$

我们可以暴力计算$g$的前面若干项来得到一个近似解。考虑到此时答案为$N-g_{N-1}-\ldots-g_1$，要让总轮数最小，等价于要让$g_{N-1}+\ldots+g_1$最大。

首先假设在前$N$轮中第$i$个小伙伴猜了$x_i$次，则游戏在前$N$轮结束的概率为$\prod_{i=1}^n 1-(1-p_i)^{x_i}$。由于$1-(1-p_i)^{x_i}$是上凸函数，因此$\ln 1-(1-p_i)^{x_i}$也是上凸函数，最大化$\prod_{i=1}^n 1-(1-p_i)^{x_i}$等价于最大化$\sum_{i=1}^n\ln 1-(1-p_i)^{x_i}$。而这个函数我们可以利用贪心算法同时使得$g_1,g_2,\ldots,g_{N-1}$最大化。

最后如何保证精度呢。我们可以发现答案实际可以写作$1+\sum_{i=1}^N1-g_i$。对于给定的$N$，我们可以简单的均分给每个人，即$g_N\geq (1-0.99^{\frac{N}{100}})^100\geq 1-100\cdot 0.99^{\frac{N}{100}}$。因此被忽略的尾部项目的和为：

$$\begin{aligned} &100\sum_{i=N}^{\infty}0.99^{\frac{i}{100}}\\ =&100\cdot 0.99^{\frac{N}{100}}\sum_{i=0}^{\infty}(0.99^{1/100})^i =&100\cdot 0.99^{\frac{N}{100}}\frac{1}{1-0.99^{1/100}} \end{aligned}$$

这里我们取$N=300000$，误差可以收敛到$8.006174315646058\times 10^{-8}$。如果不放心取到$N=10^6$即可收敛到$2.2376245821062606\times 10^{-38}$。

时间复杂度为$N(\log_2n+\log_2M)$。

树上的随机游走

题目1：给定一个树，每条树边都有一个长度。初始所有顶点都是非拥挤的。一个顶点如果是拥挤的，那么下一个顶点的选择是均匀随机的，否则可以任意选择。接下来处理$q$个请求，请求分两类：第一类请求，某个非拥挤顶点变成拥挤的。第二类请求：查询在最优策略下，从顶点$x$移动到顶点$1$的最短期望移动距离。其中$1\leq n,q\leq 5\times 10^5$。

提供一道题目。

以$1$为根，第二类请求变成了到根的期望距离。

如果所有第一类请求出现在第二类请求之前，这时候我们用期望公式会很容易计算。每个结点的期望值都可以表示为父亲结点的期望值的仿射函数。即$E_u=a_uE_{F_u}+b_u$。而仿射函数是很容易复合的，因此问题非常简单，我们只需要dfs一次即可。

现在考虑完整的问题。这时候我们可以得到一个非常重要的观察，即$a_u=1$对于所有$u$都恒成立。实际上考虑计算公式：

$$\begin{aligned} E_u&=\frac{1}{k}(E_{F_u}+W(u,F_u)+\sum_{v\in C(u)} E_{F_v}+W(v,u))\\ E_u&=E_{F_u}+W(u,F_u)+\sum_{v\in C(u)} b_{F_v}+W(v,u) \end{aligned}$$

因此我们只需要维护每个结点$u$的$b_u$即可。而第二类请求就是查询路径的$b$属性和。可以通过公式发现，对于第一类请求，我们将顶点$u$变成拥挤的，它的$b_u$属性增大$\sum_{v\in C(u)} b_{F_v}+W(v,u)$。而对于它的所有祖先结点$a$，它们的$b_a$属性同样要增大相同值，直到遇到第一个非拥挤结点位置。

这个涉及的所有操作都可以通过LCT实现。时间复杂度为$O((n+q)\log_2n)$。

无向连通图上的随机游走

考虑一个人处于$n$个顶点$m$条边的无向连通图上的某个顶点，他每回合都会随机等概率选择一条边移动。现在问经历了足够多的回合，他处在每个顶点上的概率。

这个问题实际上是马尔可夫链问题，我们可以搞出马尔可夫矩阵来解决，时间复杂度为$O(n^3+m)$。

但是实际上还有一个$O(n+m)$的解法。由于稳态概率分布是唯一的，因此如果我们将顶点$u$的概率设定为$\frac{deg(u)}{2m}$，那么可以发现概率分布之和为$1$，且满足稳态的要求。可以简单这样理解，每条边的两端都站着一个人，每回合开始时边两端的人移动到另外一端去，可以发现每个顶点上的人数是不变的，而每个顶点的人数实际上是这个顶点的度数，且人数对标的就是概率。因此我们可以发现我们的设定实际上就是最终的概率分布。

下面考虑另外一个问题，我们要计算对于每个顶点，当人初始处于这个顶点的时候，下一次再回到这个顶点的期望回合数。

这个问题可以这样理解，我们经历足够多的回合$N$后，会发现其中顶点$u$的出现次数接近于$\frac{deg(u)}{2m}\times N$。掐头去尾后回合数依旧接近于$N$（删除第一次出现$u$以及之前的结果，删除最后一次出现$u$之后的结果）。从而我们可以推出任意两次回到顶点$N$之间的回合数平均为$\frac{2m}{deg(u)}$，而期望回合数也是这个值。

提供一些题目：

• SRM797 div1 900

收集问题

题目1：一个屏幕每秒都会分别以概率$p_1/m,\ldots,p_n/m$显示整数$1,\ldots,n$，如果屏幕已经显示了$k$种不同的整数，那么屏幕就会关闭。现在要求计算屏幕关闭的期望时间，假设现在为时间$0$，且屏幕未显示过任何数字。其中$1\leq k\leq n\leq 1000$，且$k\leq 10$，$\sum_{i=1}^np_i=m\leq 10^4$，且$1\leq p_i$。

假设屏幕不会关闭，记$x_i$表示数字$i$第一次出现的时间。那么我们要求的实际上是$x_1,\ldots,x_n$中第$n-k+1$大的数。使用k大min-max容斥可以得到公式：

$$E[\max^{n-k+1}(S)]=\sum_{T\subseteq S} (-1)^{|T|-(n-k+1)}{|T|-1\choose n-k}E[\min(T)]$$

其中$E[\min(T)]$仅取决于$T$中随机变量对应的概率和。因此我们可以用动态规划$dp(i,t,z)$表示仅考虑前$i$个数，集合大小为$i-t$，集合的权重和为$z$。很显然它只有$kn\sum_i p_i$种状态，每个状态的转移只有两种。之后利用dp做min-max容斥即可。

题目2：一个屏幕每秒都会分别以概率$p_1/m,\ldots,p_n/m$显示整数$1,\ldots,n$，如果屏幕已经显示了$k$种不同的整数，那么屏幕就会关闭。现在要求计算屏幕关闭的期望时间，假设现在为时间$0$，且屏幕未显示过任何数字。其中$1\leq k\leq n\leq 1000$，且$k\geq n-10$，$\sum_{i=1}^np_i=m\leq 10^4$，且$1\leq p_i$。

提供一道题目。

类似题目2，推出：

$$E[\max^{n-k+1}(S)]=\sum_{T\subseteq S} (-1)^{|T|-(n-k+1)}{|T|-1\choose n-k}E[\min(T)]$$

可以发现$n-k$很小，这时候我们可以将因此我们可以将${|T|-1\choose n-k}$视作我们还需要在选中的集合中标记正好$n-k$个元素，并且集合中下标最小的元素不允许被标记，记$dp(i,s,t,z)$表示仅考虑前$i$个数，集合大小的奇偶性为$s$，集合中已经标记了$t$个元素，集合的权重和为$z$。可以发现只有$2kn\sum_i p_i$种状态，每种状态只有三种转移。之后利用dp做min-max容斥即可。

题目3：给定整数集合$S=\left\{1,2,\ldots,n\right\}$，一个屏幕每秒都会分别以概率$p_T$显示$S$的子集$T$中所有的数字。如果屏幕已经显示了$n$种不同的整数，那么屏幕就会关闭。现在要求计算屏幕关闭的期望时间，假设现在为时间$0$，且屏幕未显示过任何数字。其中$1\leq n\leq 20$，$\sum_{T\subseteq S}^np_T=1$。

提供一道题目。

考虑初始的概率向量为$p$，记$F$表示FWT矩阵，记$q$为期望向量。我们要求的是：

$$\begin{aligned} q_j=&\sum_{i=1}^{\infty} i (p_j^i - p_j^{i-1})\\ =&\sum_{i=1}^{\infty} i ((F^{-1}(Fp)^i)_j - (F^{-1}(Fp)^{i-1})_j) \end{aligned}$$

左右两边都乘上$F$，化成点值的形式。

$$\begin{aligned} (Fq)_j&=\sum_{i=1}^{\infty} i((Fp)_j^i-(Fp)_j^{i-1})\\ &=-\sum_{i=0}^{\infty} (Fp)^i_j\\ &=\frac{1}{(Fp)_j-1} \end{aligned}$$

很显然如果$(Fp)_j=1$，那么$(Fq)_j=0$，否则答案为$\frac{1}{1-(Fp)_j}$。

求出$Fq$后，做IFWT操作还原出$q$即可，时间复杂度为$O(n2^n)$。

参考资料

• https://www.cnblogs.com/TinyWong/p/12887591.html
• 一类概率期望问题的杀器：势函数和鞅的停时定理
• 10036 赌徒的长征(3)——鞅的停时定理
• 鞅 (概率论)
• n个随机变量中第k小值的期望