鞅的停时定理

· · 算法·理论

Part I

首先我们现在假设一下，我跟你玩这样子的一个小游戏：你每次送我 x 杯冰红茶，我有 \frac{1}{2} 的几率给你 2x 杯冰红茶，\frac{1}{2} 的几率啥都不给你。

为了方便表示，我们规定：在一次游戏中，如果我什么都没还给你，则我们称你输了；如果我还给你了 2x 杯冰红茶，则我们称你赢了。

我们先来把这个问题变得稍微形式化一点：有一组变量 \{s_1,s_2,\dots\} 表示场面上的输赢情况。其中，s_i=1 表示你第 i 局赢了，s_i=-1 表示你第 i 局输了。这里的话我们发现 s 之间其实是相互独立的，且 E[s_i]=0。

然后我们再假设 t_i 表示你第 i 局给我的冰红茶数量，显然 t_i 与 s_1,s_2,\dots,s_{i-1} 有关。

然后我们再设 X_i 表示第 i 局之后你手上的冰红茶数量，显然

X_i=X_0+\sum s_i t_i

现在，我们试着来推出 X_{n+1} 的期望值：

E[X_{n+1} \mid \{s_1,s_2,\dots s_n\}]\\ =E[X_{n}+s_{n+1}t_{n+1} \mid \{s_1,s_2,\dots s_n\}] \\ =X_n+t_{n+1}E[s_{n+1} \mid \{s_1,s_2,\dots s_n\}]\\ =X_n

这说明了一点：无论如何，都不存在一种策略使得你可以获利。

于是，现在我们引入一个听起来很厉害的名词：设 \{Y_n\},\{X_n\} 为两组随机变量序列，X_{n} 由 Y_1,Y_2,\dots,Y_n 确定，同时

E[X_{n+1} \mid \{Y_1,Y_2,\dots,Y_n\}]=X_n

则 X 是 Y 的一个鞅。

比方说在上面的例子当中，X 就是 s 的一个鞅。

Part II

这个时候你可能会觉得这个鞅有啥用啊，能满足鞅的条件的情况不都看起来很简单吗？

并不是。有的时候，我们可以通过在某个特定的时间退出游戏来保证自己的收益。

于是，我们引入停时。停时是一个随机变量 T，我们可以通过 X_1,X_2,\dots,X_n 来确定 T 和 n 的关系。换句话说，我们可以根据之前的结果决定是否退出游戏。

那么，这个时候的收益就是 E[X_T]。我们现在需要知道，是否有

E[X_T]=X_0

如果这一点成立，换句话说，我们无论在什么时候停时都注定是徒劳。

但问题来了，我们该如何判断上面的这个等式是否成立呢？很遗憾，我们目前暂时没有找到一个充要条件。但是，我们有以下三个充分条件：

这就是鞅的停时定理。

用 Part I 中的例子，我们有一种策略：第一次你给我一杯冰红茶，第二次给我两杯，第三次给我四杯，第四次给我八杯，以此类推，如果中间有赢就马上跑路。

这个策略看起来好合理对不对，但事实上，你仔细思考一下就会发现：你初始时有 X_0 杯冰红茶，因此 T < \log X_0，因为当你初始时的冰红茶被耗尽了之后你只能被迫收手。这符合停时定理的第一条。因此，这个策略其实是没法保证收益的。

Part III

但这个东西又有什么用呢？或者说，在 OI 中我们对于这一类问题应该怎么处理呢？

首先先把我们可能遇到的问题表述一下：有一个随机的过程，且我们的时间是离散的。第 i 时刻的局面是 A_i。我们的停时时间是 t，我们的终止状态是 A_t。求 E(t)。

这个时候，我们有一个很帅的操作：构造一个势能函数 \Phi(A)，满足：

于是，E(A_t)=E(A_0)。

但根据我们对于势能函数定义的第一点，我们不难得到

E(\Phi(A_x)-\Phi(A_y))=y-x

于是

E(\Phi(A_t)-\Phi(A_0))=-E(t)

整理得

E(t)=E(\Phi(A_0))-\Phi(A_t)

大功告成！等式的右边已经足够简洁了。

由此可见，对于这一类问题，核心在于 \Phi 函数的设计以及具体的计算。

Part IV

来道例题试试手吧！请看 CF1025G。请先自己阅读题目后再来看下文。

我们现设 f(x) 为一个有 x+1 个点的连通块的势能函数，\Phi 为整体的势能函数。显然，\Phi(A)=\sum f(x)。

考虑我们在某一次操作中所选择的连通块是 u,v，这两个连通块大小分别是 x+1,y+1。根据定义，E(\Phi(A_{i+1})-\Phi(A_i))=-1。

我们先来考虑求出操作前两个连通块的势能函数之和，很显然是 f(x)+f(y)。

而操作之后呢？

综合上述情况，写成期望就是 \frac{1}{2}(yf(0)+f(x+1))+\frac{1}{2}(xf(0)+f(y+1))。

代入 E(\Phi(A_{i+1})-\Phi(A_i))=-1 ，得到

f(x)+f(y)-1=\frac{1}{2}(yf(0)+f(x+1))+\frac{1}{2}(xf(0)+f(y+1))

这个方程似乎很难硬解，但我们充分发扬人类智慧：直接令 x=y，得到

2f(x)-1=xf(0)+f(x+1)

这一步直接瞪眼出 f(0)=0,f(x)=1-2^x。

现在我们有了 f(x)，考虑怎么用这个东西。先考虑怎么算 E(\Phi(A_0))。显然，我们只需要算出初始时每个连通块的 f 值加起来就好了。

然后 \Phi(A_t) 就更简单了，因为终止时一定是一个大小为 n 的连通块，于是 \Phi(A_t)=f(n-1)。

于是就做完了。时间复杂度 O\left(n \log n\right)。

试试看！

参考资料