期望势能函数及其应用

定义

对于样本 $X\in \Omega$ ，定义其势能函数为 $\phi(X)$ 。

若势能函数 $\phi$ 满足对于任意样本 $X_t\in\Omega$ ，有：

$$E[\phi(X_{t+1})|X_t]=\phi(X_t)-1$$

则从样本 $s$ 到样本 $t$ 的期望操作次数为 $\phi(s)-\phi(t)$ 。

证明好像要用到一个叫做 鞅的时停定理 的东西，很复杂，不过这里给一个不那么完善的简单证明。

特别的，这个势能函数往往需要根据题目猜测。

证明

让我们看看势能函数的条件到底是什么。

$$\begin{aligned} E[\phi(X_{t+1})|X_t] &=\sum_{X}Pr[X_{t+1}=X|X_t]\phi(X)\\ \phi(X_t)&=1+E[\phi(X_{t+1})|X_t]\\ &=1+\sum_{X}Pr[X_{t+1}=X|X_t]\phi(X) \end{aligned}$$

再看看图上随机游走的式子是什么。

定义 $x_i$ 为从 $i$ 开始随机游走，到目标 $t$ 的所需步数的期望。

那么就有：

$$x_i=1+\sum_jPr[i\to j|i]x_j$$

这和势能函数的本质似乎是一样的。

不妨把势能函数当成图上随机游走看待，那么就有初始到目标的游走次数的期望为初始状态 $s$ 的 $x_s$ 去除掉目标 $t$ 的 $x_t$ ，因为到 $t$ 停止。这恰恰是上面那个 鞅的时停定理 证明的东西。

于是我们就绕过了 鞅的时停定理 证明完毕了。

CF1025G Company Acquisitions

只能用这个写。

题目链接： CF1025G Company Acquisitions 。

题目内容：

有 $n$ 家公司，有些被收购了，有些是独立的。

每秒会随机两个独立公司 $i$ 和 $j$ ，然后 $i$ 收购 $j$ 。

当公司 $i$ 收购公司 $j$ 时，公司 $j$ 的状态会变为被 $i$ 收购，且所有原来公司 $j$ 收购的公司会拜托被收购状态，变为独立的。

当存在一个公司收购了所有的其他公司时，游戏结束。

求期望操作秒数。

定义 $a_i$ 为公司 $i$ 收购的公司数目，那么样本空间为 $(a_1,\cdots,a_k)$ ，其中 $k$ 为当前独立公司数目。

猜测势能函数 $\phi((a_1,\cdots,a_k))=\sum\limits_{i=1}^k g(a_i)$ 。

为了满足条件，必须满足：

$$\begin{aligned} E[\phi(a'_1,\cdots,a'_k)|(a_1,\cdots,a_k)]-\phi(a_1,\cdots,a_k)&=-1\\ \frac{1}{k(k-1)}\sum_{i,j,i\ne j}-g(a_i)-g(a_j)+g(a_i+1)+a_jg(0)&=-1\\ \end{aligned}$$

不妨钦定 $g(0)=0$ ，那么：

$$\begin{aligned} -2(k-1)\sum_{i}g(a_i)+(k-1)\sum_{i}g(a_i+1) &=-k(k-1)\\ \sum_{i=1}^k g(a_i+1)-2g(a_i) &= -k \end{aligned}$$

不妨设 $g(a_i+1)-2g(a_i)=-1$ ，那么满足了势能函数要满足的条件。

然后基于此继续推导：

$$\begin{aligned} g(i)&=2g(i-1)-1\\ g(0)&=0\\ g(1)&=2g(0)-1\\ &=-1\\ g(2)&=2g(1)-1\\ &=-3\\ \vdots\\ g(x)&=1-2^x \end{aligned}$$

然后初始状态 $(a_1,\cdots,a_n)$ ，结束状态 $(n-1)$ ，用定理就行。

CF1349D Slime and Biscuits

这个用势能函数非常简单，不用则比较困难。

题目链接： CF1349D Slime and Biscuits 。

题目内容：

有 $n$ 个人，第 $i$ 个人有 $a_i$ 块饼干。

每秒随机一个饼干并随机一个除了饼干主人之外的人，主人将这块饼干给他。

当所有饼干都集中在一个人身上时游戏结束。

求游戏持续时间期望。

$n\le10^5$ ，$m=\sum a_i \le 3\times10^5$ 。

样本空间显然为 $(a_1,\cdots,a_n)\in \Omega$ ，其中 $a_i$ 为当前 $i$ 的饼干数量。

猜测势能函数 $\phi$ 为 $\sum g(a_i)$ ，将条件写下：

$$E[\phi(a'_1,\cdots,a'_k)|(a_1,\cdots,a_k)]-\phi(a_1,\cdots,a_k)=-1\\ \sum E[\Delta(g(a_i))] =-1\\ E[\Delta(g(a_i))]=\frac{a_i}{m}(g(a_i-1)-g(a_i))+\frac{m-a_i}{m}\cdot\frac{1}{n-1}(g(a_i+1)-g(a_i))\\$$

不妨令 $E[\Delta(g(a_i))]=\frac{a_i}{m}$ ，那么：

$$\frac{a_i}{m}(g(a_i-1)-g(a_i))+\frac{m-a_i}{m}\cdot\frac{1}{n-1}(g(a_i+1)-g(a_i))=\frac{a_i}{m}$$

令 $d_{a_i}=g_{a_i+1}-g_{a_i}$ ，那么就有：

$$-a_id_{a_i-1}+\frac{m-a_i}{n-1}d_{a_i}=a_i\\ \frac{m-a_i}{n-1}d_{a_i}=a_i+a_id_{a_i-1}\\ d_{a_i}=\frac{a_i(n-1)}{m-a_i}(d_{a_i-1}+1)\\ d_x=\frac{x(n-1)}{m-x}(d_{x-1}+1)$$

然后钦定 $d_0=g_0=0$ ，递推 $d,g$ 就行。

代码只有 $1KB$ 。