前言

标题致敬某神仙选手。

由于我并不清楚某些前置知识,所以以下内容不一定正确。

一些术语:

  • $a\in \mathbb R\cup \{\infty\}$ 有限:$|a|< \infty$.(可以很大,但不能无穷大)
  • $a\in \mathbb R\cup \{\infty\}$ 有界:存在 $l,r\in \mathbb R$,使得 $a\in[l,r]$.
  • $a_1,a_2,\cdots\in \mathbb R\cup \{\infty\}$ 一致有界:存在 $l,r\in \mathbb R$,使得 $a_1,a_2,\cdots\in[l,r]$.
  • 事件 $A$ 几乎必然发生:$\operatorname{P}(A) = 1$。

鞅和停时定理

时间离散的随机过程是一个随机变量序列 $\{X_0,X_1,\cdots\}$。

离散时间(Martingale)是一个时间离散的随机过程 $\{X_0,X_1,\cdots\}$,使得对所有的 $n\in \mathbb N$,均满足:

  • $\mathbb E[|X_n|] < \infty$.
  • $\mathbb E[X_{n+1}\mid X_0,X_1,\cdots,X_n] = X_n$.

即,对于一个随机过程 $\{X_0,X_1,\cdots\}$,其所有随机变量有限,且下一个随机变量的条件期望等于这一个随机变量的观测值。

由此,我们可以得到鞅的一个性质:

鞅的性质:有一个离散时间鞅 $\{X_0,X_1,\cdots\}$,则对于所有 $n\in \mathbb N$,$\mathbb E[X_n] = \mathbb E[X_0]$.

我们还有一个更一般的离散时间鞅的定义:

关于随机过程的离散时间鞅:两个时间离散的随机过程 $\{X_0,X_1,\cdots\}$,$\{Y_0,Y_1,\cdots\}$,使得对所有的 $n\in \mathbb N$,均满足:

  • $\mathbb E[|Y_n|] < \infty$.
  • $\mathbb E[Y_{n+1}\mid X_0,X_1,\cdots,X_n] = Y_n$.

则称 $\{Y_0,Y_1,\cdots\}$ 是关于 $\{X_0,X_1,\cdots\}$ 的离散时间鞅。

停时和停时定理

对于一个随机过程,其停时 $\tau\in \mathbb N\cup\{\infty\}$ 是个随机变量,满足 $\tau = t$ 仅取决于 $X_0,X_1,\cdots,X_t$.

可选停时定理(Optional Stopping Theorem):有鞅过程 $\{X_0,X_1,\cdots\}$,其停时为 $\tau$,$\mathbb E[X_{\tau}] = \mathbb E[X_0]$ 当以下三个条件中至少一个成立:

  • $\tau$ 几乎必然有界。
  • $|X_{n+1}-X_n|$ 一致有界,且 $\mathbb E[\tau]$ 有限。
  • $X_n$ 一致有界,且 $\tau$ 几乎必然有限。

可以发现,这三个条件中关于 $\tau$ 的限制是逐渐放松的,而关于 $X_n$ 的限制是逐渐加强的。

一个简单的例子是,停时定理指出:对于一个抛掷公平硬币的游戏,输了失去赌注,赢了获得等于赌注的金额,若一个赌徒只拥有有限的时间和财产,无论采取什么策略,均不会赚钱。

势能函数

方法

对于随机事件序列 $\{A_0,A_1,\cdots,A_{\tau}\}$,$\tau$ 为其停时,终止状态为 $A_{\tau}$,而我们希望求得 $\mathbb E[\tau]$.

我们可以构造势能函数 $\Phi(A)$,满足:

  • $\mathbb E[\Phi(A_{n+1})-\Phi(A_{n})\mid A_0,A_1,\cdots,A_n] = -1$.
  • $\Phi(A_{\tau})$ 为常数,且 $\Phi(A) = \Phi(A_{\tau})$ 当且仅当 $A = A_{\tau}$.

设随机变量 $X_n = \Phi(A_n) + n$,则随机过程 $\{X_0,X_1,\cdots,X_{\tau}\}$ 是个离散时间鞅。

由 $\Phi(A) = \Phi(A_{\tau})$ 当且仅当 $A = A_{\tau}$ 我们可以推得 $\tau$ 也为 $\{X_0,X_1,\cdots,X_{\tau}\}$ 的停时,那么根据停时定理,我们有:

$$ \mathbb E[X_{\tau}] =\mathbb E[X_0] \Rightarrow \mathbb E[\Phi(A_0)] - \Phi(A_{\tau}) = \mathbb E [\tau] $$

例 1 Company Acquisitions

(Codeforces 1025G)有一个 $n$ 个点的菊花图森林,每次进行以下操作直到整个森林变为一棵树:

  • 等概率随机选取两个根 $u,v$。
  • 将与 $v$ 相连的所有边断开。
  • 将 $v$ 连向 $u$.

求期望进行的步数,对 $10^9 + 7$ 取模。

$1\le n\le 500$.

分析

对于这类多个元素的问题,有一个常见的套路是对每个元素设定一个势能函数 $f(x)$ 表示拥有 $x$ 个孩子的根的势能,然后令全局势能函数 $\Phi(A)$ 为所有根的势能函数之和。

设我们每次随机出来两个根,分别拥有 $u,v$ 个孩子,那么 $\mathbb E[\Delta \Phi(A)]$ 显然只和这两个元素有关。

那么我们有:

$$ \mathbb E[\Phi(A')] = \frac 12(f(u+1)+vf(0))+\frac 12(f(v + 1) + uf(0)) $$

它应等于 $f(u) + f(v) - 1$,为了化简式子,我们注意到我们只关心势能函数的差,所以 $f(0)$ 是多少并没有影响,于是考虑设 $f(0) = 0$。

那么就有:

$$ \frac 12f(u+1)+\frac 12f(v + 1) = f(u) + f(v) - 1 $$

我们希望这个式子对任意 $u,v$ 均成立,于是考虑分离变量:

$$ \frac 12f(u + 1) = f(u) - \frac 12 $$

解得:

$$ f(u) = 1-2^u $$

容易求得起始局面和终止局面的势能函数,且容易发现终止局面的势能是严格最小的,所以可以应用停时定理。

时间复杂度 $\mathcal O(n)$.

例 2 Rainbow Balls

(Codeforces 850F)袋子里有 $n$ 种颜色的球,第 $i$ 种颜色有 $a_i$ 个,每次进行以下操作,直到袋中只剩一种颜色的球:

  • 依次等概率随机取出两个球(它们的颜色可能一样)。
  • 将第二个球的颜色染成第一个球的颜色。
  • 将这两个球放回袋中。

求期望进行的步数,对 $10^9 + 7$ 取模。

$1\le n\le 2500$,$1\le a_i\le 10^5$.

分析

我们考虑类似地写出 $\Phi(A) = \sum f(a_i)$,$f(a)$ 需要满足的条件:

$$ \sum_i f(a_i) - 1 $$

应与下式相等:

$$ \sum_i \frac 1{m^{\underline 2}}((a_i^{\underline 2} + (m-a_i)^{\underline 2})f(a_i) + a_i(m-a_i)(f(a_i - 1) + f(a_i + 1))) $$

把右边的 $f(a_i)$ 移过来,再展开一下式子可以得到:

$$ \sum_i \frac {a_i}{m^{\underline 2}}((a_i-m)2f(a_i) + (m-a_i)(f(a_i - 1) + f(a_i + 1))) = -1 $$

(我们有下降幂的完全平方公式 $(x-y)^{\underline 2} = x^{\underline 2} - 2xy + (-y)^{\underline 2}$)

$$ \sum_i \frac {a_i(m-a_i)}{m^{\underline 2}}(f(a_i - 1) - 2f(a_i) + f(a_i + 1)) = -1 $$

发现这个形式神似二维差分,于是我们设 $g(x) = f(x + 1) - f(x)$.

$$ \sum_i \frac {a_i(m-a_i)}{m^{\underline 2}}(g(a_i) - g(a_i - 1)) = -1 $$

经验表明,对于要将所有元素集中在一个集合的这类问题,我们可能可以以正比于某个集合的大小的期望减少这个集合的势能。

即:

$$ \frac {a(m-a)}{m^{\underline 2}}(g(a) - g(a - 1)) + \frac am = 0 \\ g(a) - g(a - 1) = \frac{m-1}{a-m} < 0 $$

容易发现,这样设置总能满足 $\mathbb E[\Delta \Phi(A)] = -1$ 的条件,并且在本题中差分单调递减,又由于 $\sum a_i$ 不变,可以看作一个经典的背包模型,势能的最低点必然是把一个函数取完而其它不取。

于是我们证明了 $\Phi(A) = \Phi(A_{\tau})\Rightarrow A = A_{\tau}$.

不妨设 $f(0) = 0, g(0) = -\frac{m-1}{m}$(容易发现,我们几乎可以随意给 $g(0)$ 定一个值,只需要其满足 $\Phi(A) = \Phi(A_{\tau})\Rightarrow A = A_{\tau}$)

然后问题在于求 $f(m)$($f(a_i)$ 可以直接递推求):

$$ f(m) = \sum_{i=0}^{m-1}\sum_{j=0}^{i} \frac{m-1}{j-m} = \sum_{j=0}^{m-1}(m-j) \frac{m-1}{j-m} = -m(m-1) $$

于是这道题就做完了。

时间复杂度 $\mathcal O(n + \max a_i)$.

参考资料

最后修改:2021 年 02 月 26 日 10 : 55 PM