概率问题

Published: by Creative Commons Licence

  • 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

可以考虑这样一个问题,我们现在有1000份简历,我们需要面试1000个人,并从中找出能力最优秀的候选人。

面试能帮助我们了解应聘人是否比我们已经招募的那个人(通过了试用期)更加优秀。我们可以邀请一个人参加试用,在试用期结束后,我们就能得到这个人的真实能力。

由于岗位有限,同时最多只能有一个人处于试用期。面试一个人,需要一个小时,试用期则长达1个月。问我们最少需要多少时间才能找到最优秀的人。

假如我们每个人都邀请参加试用,那么会需要1000个月,要面到大家都退休。或者我们使用贪心策略,却不保证随机(比如HR按自己的观感将候选人从差到优进行排序),也可能会需要1000个月。

现在我们随机打乱所有的简历,并采用贪心策略,那么我们的所需的期望时间仅仅为1000个小时加上10个月,估摸是一年内可以结束。

一些期望计算问题

问题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}$。因此我们重写我们要求的总距离的期望,可以得到:

\[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}\\\]

注意到右边的$\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)$。

提供一道题目

循环概率递推

问题1:考虑一副连通图,我们在图上随机游走,图上有几个出口,问我们从各个出口离开的概率是多少。

这个问题可以用马尔科夫链直接解决,建立一个概率矩阵,理论上保证了概率矩阵一定有逆,因此求逆后就可以求出从每个出口离开的概率了。这个方法适合用于图中顶点比较少的时候(比如顶点不超过$500$),因为上面的方法概率求逆的时间复杂度为$O(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<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。

赌博破产问题

考虑你有$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)$。

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

一道Atcoder的题目

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

给定一棵树,树上有$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)$。

筛子问题

题目1:屏幕上有一个数字$x$,之后执行$m$次操作。每次操作将$x$等概率替换为$0$到$x$中的某个数。提供$P=(p_0,p_1,\ldots,p_n\right)$,分别表示初始值$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\]

由于$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}$互逆。

参考资料