势能函数和鞅的停时定理

考虑随机事件序列 \(\{A_0,A_1,\cdots \}\) ，随机变量 \(T\) 为它的停时。我们希望求出 \(E(T)\) ，但一般来说较为困难，因此我们考虑构造一个势能函数 \(\Phi(A)\) ，满足：

• \(\Phi(A_{i})<\infty\) ；
• \(E(\Phi(A_{i+1})-\Phi(A_i))=-1\) 。

那么，我们令 \(X_i=\Phi(A_i)+i\) ，则有 \(E(X_{i+1}-X_i)=0\) 。

于是，我们发现 \(\{X_0,X_1,\cdots \}\) 是鞅，若 \(T\) 也是 \(\{X_0,X_1,\cdots \}\) 的停时，则有：

\[\begin{aligned}E(X_T)&=E(X_0)\\E(T)&=E(\Phi(A_0))-E(\Phi(A_T))\end{aligned} \]

CF1025G Company Acquisitions

给定 \(n\) 个节点，每个节点有红/蓝的一个颜色。每个红点的儿子一定是蓝点，每个蓝点只有红爸爸。

每次随机两个红点 \(A,B\)，随机一个红点（比如 \(B\)）变成蓝点，接到 \(A\) 的儿子，并把 \(B\) 的所有儿子变成红点。

求只剩下一个红点的期望操作次数。

Solution

定义 \(c_i\) 表示 \(i\) 后面跟着几个点，我们考虑构造一个势能函数 \(\Phi(x)\) ，使得 \(f(x)=\sum\limits_{i=1}^{n}\Phi(c_i)\) 的变化量是个常量。

不妨假设随机的两个点的 \(c\) 值是 \(a, b\) ，那么就有：

\[\Phi(a)+\Phi(b)+1=\frac 12(\Phi(a+1)+(b-1)\Phi(0))+\frac 12(\Phi(b+1)+(a-1)\Phi(0)) \]

我们钦定 \(\Phi(0)=0\) ，那么：

\[\Phi(a)+\Phi(b)+1=\frac 12(\Phi(a+1)+\Phi(b+1)) \]

由于它对任意 \(a,b\) 均成立，因此：

\[\begin{aligned}2\Phi(a)+1&=\Phi(a+1)\\\Phi(a)&=2^a-1\end{aligned} \]

于是，起始态就是 \(E=\sum\limits_{i=1}^{n}2^{c_i}-1\) ，终止态就是 \(E'=2^{n-1}-1\) ，答案即为 \(E'-E\) 。

CF1575F Finding Expected Value

设有一个长为 \(n\) 的序列 \(b\) ，定义一次操作为随机选择一个下标 \(i\in [1,n]\) 和值 \(x\in [0,k)\) ，施 \(b_i\leftarrow k\) ，设 \(E(b)\) 表示期望操作次数，使得 $b_i $ 全相等。

给定一个长为 \(n\) 的序列 \(a\) ，满足 \(a_i\in [-1,k)\) 。将 \(a_i=-1\) 的位置随机填入 \([0,k)\) ，求 \(E(a)\) 的期望值。

\(2\le n\le 10^5,2\le k\le 10^9,-1\le a_i<k\) 。

Solution

先考虑如何计算 \(E\) ，定义 \(occ(x)\) 表示 \(x\) 在 \(b\) 序列中的出现次数，考虑构造势能函数满足 \(f_t=\sum\limits_{i=0}^{k-1}\Phi(occ_t(i))\) 。

\[E(f_{t+1}-f_t)=-1\\\sum_{i=0}^{k-1}\Phi(occ_{t+1}(i))=\sum_{i=0}^{k-1}\Phi(occ_t(i))-1\\\frac{1}{k}\sum_{i=0}^{k-1}\Phi(occ_{t}(i))+\sum_{x=0}^{k-1}\sum_{y=0}^{k-1}[x\neq y]\frac{occ_t(x)}{nk}\left(\sum_{i=0}^{k-1}\Phi(occ_t(i))- \\\Phi(occ_t(x))-\Phi(occ_t(y))+\Phi(occ_t(x)-1)+\Phi(occ_t(y)+1)\right)=\sum_{i=0}^{k-1}\Phi(occ_t(i))-1 \]

化简可得：

\[\sum_{x=0}^{k-1}\frac{(k-1)occ_t(x)}{nk}\left(\Phi(occ_t(x)-1)-\Phi(occ_t(x))\right)+\\\frac{n-occ_t(x)}{nk}\left(\Phi(occ_t(x)+1)-\Phi(occ_t(x))\right)+\frac{occ_t(x)}{n}=0 \]

我们希望对于每个 \(x\) ，它都等于 \(0\) 。令 \(a=occ_t(x)\) ，则：

\[\frac{(k-1)a}{nk}(\Phi(a-1)-\Phi(a))+\frac{n-a}{nk}(\Phi(a+1)-\Phi(a))+\frac{a}{n}=0 \]

化简得：

\[\Phi(a+1)=\frac{1}{a-n}\left((k-1)a\Phi(a-1)+(2a-ak-n)\Phi(a)+ak\right) \]

因此，只需要构造的 \(\Phi\) 符合上述递推式即可。

回到原题，我们可以 \(\mathcal O(n)\) 快速计算某个确定的 \(b\) 序列的期望。注意到对于每种数 \(x\) 的贡献是独立的，且只和出现次数相关。因此如果 \(a\) 序列中（剔除 \(-1\)）两种数出现次数相同，它对答案的贡献是相同的。

由于至多有 \(\sqrt{n}\) 种不同出现次数，因此总时间复杂度 \(\mathcal O(n\sqrt{n})\) 。

当然，你可以卷积做这事，复杂度优化到 \(\mathcal O(n\log n)\) 。