鞅_杂项

鞅

直观来讲，鞅是满足下述条件的随机过程：已知过去的某个时刻 $s$ 及之前的所有观测值，对于以后的任意时刻 $t$，$t$ 的观测值的条件期望等 于 $s$ 的观测值。

形式化的定理考虑了很多边界情况，通常来说，使用鞅只需要构造势函数 $\phi$，使得对每个时刻 $t$ 都满足（$A_t$ 是该时刻的局面）：

$$\mathbb E(\phi(A_{t+1})-\phi(A_t)\mid A_{i=0}^t)=-1$$

由于 $\mathbb E(\phi(A_t)\mid A_{i=0}^t)=\phi(A_t)$，所以上式其实可以改写成推式子更友好的 $\phi(A_t)=\mathbb E(\phi(A_{t+1}\mid A_{i=0}^t))+1$。

如果题目中的操作是一个 Marcov 过程，即每步仅依赖上一步的状态，那式子还能进一步简化为 $\phi(A_t)=\mathbb E(\phi(A_{t+1}\mid A_t))+1$。

设 $\cal T$ 为停止时刻，我们还要保证 $\phi(A_\mathcal T)$ 是常数，这样我们可以构建 $\mathcal X_i=\phi(A_i)+i$，根据鞅的定义 $\mathcal X$ 是一个鞅，根据停时定理我们知道：

$$\mathbb E(\mathcal X_\mathcal T)=\mathbb E(\mathcal X_0)\Rightarrow \mathbb E(\mathcal T)=\phi(A_0)-\phi(A_\mathcal T)$$

常用的势函数是 $\phi(A)=\sum_{i=1}^nf(a_i)$。

来点例题：

CF1349D Slime and Biscuits

有 $n$ 个人，第 $i$ 个人有 $a_i$ 个饼干，每次在所有饼干中随一个，把它给除了自己所有者的随机一个人。

当一个人垄断了所有饼干时结束，问期望停止时刻。

$n\le 10^5,\sum a_i\le 3\times 10^5$。

在本题，每个局面含有的信息显然就是当前的 $a_{i=1}^n$，我们设 $\phi(A)=\sum_{i=1}^nf(a_i)$，如果不是该函数那我们也要找一个对每个元素平等的函数，毕竟本题每个元素的地位平等。

推一下，设 $m=\sum a_i$：

$$\begin{aligned}\mathbb E(\phi(A_{t+1})\mid A_{i=1}^t)&=\mathbb E(\phi(A_{t+1})\mid A_t)\\&=\sum_{i=1}^n\frac{a_i}{m}\left[f(a_i-1)+\sum_{j=1,j\ne i}^n\left[\frac{n-2}{n-1}f(a_j)+\frac{1}{n-1}f(a_j+1)\right]\right]\\&=\sum_{i=1}^n\left[\frac{a_i}{m}f(a_i-1)+\frac{m-a_i}{m}\left[\frac{n-2}{n-1}f(a_j)+\frac{1}{n-1}f(a_j+1)\right]\right]\end{aligned}$$

应用预设 $\phi(A_t)=\mathbb E(\phi(A_{t+1})\mid A_t)+1$：

$$\begin{aligned}\phi(A_t)&=\mathbb E(\phi(A_{t+1})\mid A_t)+1\\&=\sum_{i=1}^n\left[\frac{a_i}{m}f(a_i-1)+\frac{m-a_i}{m}\left[\frac{n-2}{n-1}f(a_j)+\frac{1}{n-1}f(a_j+1)\right]\right]+1\\&=\sum_{i=1}^n\left[\frac{a_i}{m}f(a_i-1)+\frac{m-a_i}{m}\frac{n-2}{n-1}f(a_j)+\frac{m-a_i}{m}\frac{1}{n-1}f(a_j+1)+\frac{a_i}{m}\right]\end{aligned}$$

显而易见地：

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

这是经典形式，我们可以求出 $f(x)$ 关于 $f(x-1),f(x-2)$ 的递推式，$x=0$ 代入得到 $f(1)=f(0)$，任取一个值便可推出所有 $f$ 值且无矛盾。

最后用 $\phi(A_0)-\phi(A_\mathcal T)$ 得到答案。

这个很厉害的一点在于虽然我们不知道结束时间，但是我们知道结束状态。

CF1025G Company Acquisitions

你有 $n$ 个点组成若干个菊花，每个菊花形如一个根携带 $\ge 0$ 个儿子，每次随机选两个菊花 $a,b$，解散 $a$，将 $a$ 的根接到 $b$ 的根下面当儿子，将 $a$ 的儿子全部变为新菊花的根，停时是只剩一个菊花，求停时期望步数。

$n\le 500$。

每个状态的信息显然有菊花个数 $m$ 和每个菊花的点数 $a_i$，需要注意 $m$ 是一个随时间变化的量而不是常量。

考虑仍然设 $\phi(A_t)=\sum_{i=1}^m f(a_{t,i})$。

$$\begin{aligned}\mathbb E(\phi(A_{t+1}))&=\sum_{i=1}^m\frac 1 m(a_i-1)f(1)+\frac{m-1}{m}(\frac{1}{m-1}f(a_i+1)+\frac{m-2}{m-1}f(a_i))\\&=\sum_{i=1}^m\frac 1 m(a_i-1)f(1)+\frac{1}{m}f(a_i+1)+\frac{m-2}{m}f(a_i)\end{aligned}$$

势函数的 $+1$ 这里就不再抄一遍了，直接换成 $+\frac 1 m$，于是得到：

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

你发现移项后刚好 $m$ 消掉了（若没消掉就应该换最初形式了）：

$$f(x+1)=2f(x)-(x-1)f(1)-1$$

随便钦定一个 $f(1)$，递推即可。

CF850F Rainbow Balls

有一袋球，第 $i$ 种颜色有 $a_i$ 个，每次选两个球出来把第二个涂成第一个的颜色，问什么时候所有球颜色相同。

$n\le 2500,a_i\le 10^5$。

设 $m=\sum_i a_i,\phi(A_t)=\sum_i f(a_i)$：

$$\begin{aligned}\mathbb E(\phi(A_{t+1}))&=\sum_{i=1}^n\frac{a_i}{m}(\frac{a_i-1}{m-1}f(a_i)+\frac{m-a_i}{m-1}f(a_i+1))+\frac{m-a_i}{m}(\frac{a_i}{m-1}f(a_i-1)+\frac{m-1-a_i}{m-1}f(a_i))\\&=\sum_{i=1}^n\frac{[a_i(a_i-1)+(m-a_i)(m-a_i-1)]f(a_i)+(m-a_i)a_if(a_i-1)+a_i(m-a_i)f(a_i+1)}{m(m-1)}\end{aligned}$$

这次的加一肯定拆成 $\frac{a_i}{m}$（拆成 $\frac 1 n$ 似乎也可以），整理可以得到：

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

由于不存在的颜色不会对停时过程产生影响，所以 $f(0)=0$，我们效仿第一题，随便钦定一个 $f(1)$ 然后跑其实就是对的。

求 $f(m)$ 可以用矩乘，但是根据我不会的推导可以得到 $f(m)=mf(1)-(m-1)^2$。

总结

好像稀里糊涂的做完了三题，我们可以提出很多疑点：

• 为什么这三题中总有一个量我们可以随便取，而最终的结果都是正确的？

应用势函数解题，势本身其实就是有相对性的（最后的答案也是求差来得到），随便取一个量相当于我们规定了一个基准参考系而已，无论用什么当基准答案都不会变。

• 为什么状态的所谓“势”必定存在，而不会像漩涡一样循环起来？

其实这是题目规定的有停时，所以每个状态和其转移出去的状态离那个停时的“距离”必定是不同的，否则就会出现无法停止的状况。

如果你自己尝试做一下第三题，你会发现在没化简的原版式子中带入 $x=m$ 会得到 $f(m)=f(m)+1$，这看上去正像是在说这个势函数非法，但实则不然，这完全是因为当你到了 $x=m$ 的状态后的操作只会转移回自己这个状态，从而陷入了循环，但我们使用 $x=m-1$ 的式子计算 $f(m)$ 就是对的，这是因为 $x=m-1$ 时我们转移到的 $f(m)$ 必定是第一次到这个状态，也就符合了题目对停时的定义。

同样的，第一题的操作也并不会自然停止，但我们无须关心停止后的状态，只需要满足我们设计的 $\phi(A_t)=\mathbb E(\phi(A_{t+1}\mid A_t))+1$ 且我们要用到的取值均有界即可应用。

所以在应用鞅解题时我们不仅只能做第二题这种规定停时 $=$ 自然停时的情况，对于一、三两道题，我们同样可以设计出一个状态来描述 $A$ 与 $B$ 在时间轴上的距离。