鞅与停时定理：概率论科技

littlez_meow · 2023-10-15 21:00:34 · 算法·理论

Part 0：前言

你打开了一道期望题。题目是一个随机过程，要求结束时间的期望。

你想着如何 dp，却发现不好 dp。

你打开题解，发现里面提到了你看都看不懂的名词：鞅的停时定理。

在学习后，你发现这是一个很好用的东西，于是你决定分享出来。

Part 1：鞅

在遥远的过去，猜硬币的赌博还很流行。小 Z 今天来到赌场，想通过猜硬币赚得盆满钵满。

赌场规定，参与的人必须下赌注 x 元，赢了可以获得 2x 元，输了不得钱。为了方便，我们称每个人手上拿着的钱为赌资。

掷硬币的规则很简单首先下赌注，然后掷一枚均匀硬币（正反面概率均为 50\%），正面则赢，反面则输。

经过简单的计算，设赌资为 x，赌注为 y，我们可以得到这种赌博方式在下一局的期望赌资为：

E(x')=x-y+(0\times \dfrac 1 2+2y\times\dfrac 1 2)=x

根据期望的线性性，无论进行多少局，期望赌资永远等于初始赌资，即期望收益始终为 0。

因此，聪明的小 Z 发明了一种方法：每输一局就翻倍赌注。这样，假设输了 n-1 局，在第 n 局赢了，就有收益为：

2^{n}-(2^0+2^1+2^2+\cdots+2^{n-1})=1

这种策略看似期望收益为 1，但是其忽略了初始赌资有限的事实。在有限的赌资下，这种策略有极大概率收益为 1，极小概率收益为 -2^n，因此期望仍是 0。

这种输后加倍下注的赌法被称为 martingale，即“鞅”。

时光荏苒，如今赌博已经不再流行。但 martingale 这个名字，被拓展进了数学中。

结合赌博时期望收益始终为 0 的特点，我们给出数学中鞅的定义。

【定义 1】（鞅） 若一个时间离散的随机过程 \{X_0,X_1,X_2,\cdots\} 满足：

\forall t\in\mathbb{N},E(|X_t|)<\infty
\forall t\in\mathbb{N},\forall X_0,X_1,\cdots,X_t,E(X_{t+1}-X_t|X_0,X_1,\cdots,X_t)=0

则称随机过程 \{X_0,X_1,X_2,\cdots\} 是鞅过程，简称鞅。

（更准确地说应是离散时间鞅，鞅还有许多不同的推广，不过 OI 中仅会用到离散时间鞅。）

让我们考虑每一条在赌博中对应的实际意义。第一条的意思就是在任意有限的时刻，赌资的期望有限；第二条就是无论先前的结果如何，新一局期望收益始终为 0。

为什么要加粗？因为假设硬币存在记忆，满足某种条件是就永远正面，此时整体期望收益仍然为 0，但在某些情况下每局的收益可能不为 0。因此，E(X_{t+1}-X_t|X_0,X_1,\cdots,X_t)=0 是 E(X_{t+1}-X_t)=0 的充分条件。

显然，根据定义 1，我们可以得到：

【推论】 \forall t\in\mathbb{N},E(X_t)=E(X_0)

Part 2：停时

对于很多随机过程，它停止的时间不是固定的，而是个随机变量。

这个随机变量被我们称为停时。下面给出不严谨的定义。

【定义 2】（停时） 若非负随机变量 \tau 和随机过程 \{X_0,X_1,X_2,\cdots\} 满足 \forall t\in T,\{\tau=t\}\in\mathcal{F}_t，则称 \tau 为 \{X_0,X_1,X_2,\cdots\} 的停时。

其中 \mathcal{F}_t 为 \sigma 代数，可以理解为 \{X_0,X_1,\cdots,X_t\} 提供的所有信息。

（事实上，上面的定义仅在 T 为可数集时成立，不可数集需改为 \forall t\in T,\{\tau\le t\}\in\mathcal{F}_t。不过离散情况下，T=\mathbb{N}，可以就使用上面的定义。）

上面的定义可以通俗理解为，0-t 时刻的所有信息可以让我判断 t 时刻是否停下。

既然停时是随机变量，可能是无穷大的，那么在鞅中的停时满足什么呢？

Part 3：鞅的停时定理

为了解决上面这个非常自然的问题，人们发现了鞅的停时定理。

【定理】（鞅的停时定理） 设 \tau 是鞅过程 \{X_0,X_1,X_2,\cdots\} 的停时，当下面三个条件之一成立时，有 E(X_{\tau})=E(X_0)。

其中，“几乎一定”的意思为概率为 1，“E(\tau) 有限”的意思是 |E(\tau)|<\infty，“X_t 有界”的意思是 \exists l,r,l\le X_t\le r 且 l,r 与 t 无关。

（注意，下面三个条件仅为充分条件，可以放宽得到更强的停时定理，但在此不讨论。）

证明：为了理解方便，证明可能不太严谨。

首先由于 \tau 是随机变量，只有其有界时才能直接使用推论。

下面先求当 \tau 无界时，E(X_\tau) 和 E(X_t) 的差距。其可分为两部分，\tau\le t 和 \tau>t，因此有：

E(X_\tau)-E(X_t)=P(\tau\le t)E(X_\tau-X_t|\tau\le t)+P(\tau>t)E(X_\tau-X_t|\tau>t)

对于 P(\tau\le t)E(X_\tau-X_t|\tau\le t)，由于此时 \tau\le t 是有界的，根据定义 1，有 E(X_\tau-X_t|\tau\le t)=0。因此得到：

E(X_\tau)-E(X_t)=P(\tau>t)E(X_\tau-X_t|\tau>t)

下面分三类证明。

当条件一成立时：

此时取 t 为 \tau 的上界，则 E(X_\tau)=E(X_t)。

根据推论，E(X_t)=E(X_0)=E(X_\tau)。原命题得证。

当条件三成立时：

由于 \tau 有限，我们有 \lim\limits_{t\to\infty}P(\tau>t)=0；由于 \forall t\in\mathbb{N},X_t 有界，我们有 E(X_\tau-X_t|\tau>t) 有界。

因此有：

\lim\limits_{t\to\infty}E(X_\tau)-E(X_t)=\lim\limits_{t\to\infty}P(\tau>t)E(X_\tau-X_t|\tau>t)=0

再根据推论，得到 E(X_t)=E(X_0)=E(X_\tau)。原命题得证。

当条件二成立时：

相比于条件三，条件二中的 |X_{t+1}-X_t| 有界并不能保证 E(X_\tau-X_t|\tau>t) 有界，不能直接求极限。

考虑缩放，我们有：

|P(\tau>t)E(X_\tau-X_t|\tau>t)|\le P(\tau>t) \sum\limits_{k=t+1}^\infty|E(X_k-X_t)| P(\tau=k|\tau>t)

因为 P(\tau>t)P(\tau=k|\tau>t)=P(\tau=k)，乘法分配律得到：

=\sum\limits_{k=t+1}^\infty |E(X_k-X_t)|P(\tau=k)

由于 |X_{t+1}-X_t| 有界，因此 \exists C,|E(X_a-X_b)|\le C\times(a-b)，其中 C 为常数。代入得到：

\le\sum\limits_{k=t+1}^\infty C(k-t)P(\tau=k)

依题 t\ge 0，去掉括号里的 t 并提出 C 有：

\le C\sum\limits_{k=t+1}^\infty kP(\tau=k)

我们发现 E(\tau)=\sum\limits_{k=0}^\infty kP(\tau=k)，E(\tau) 有限代表该级数收敛。

而 \sum\limits_{k=t+1}^\infty kP(\tau=k) 为该级数的余项，有 \lim\limits_{t\to\infty}C\sum\limits_{k=t+1}^\infty kP(\tau=k)=0

根据夹逼定理，有 \lim\limits_{t\to\infty}E(X_\tau)-E(X_t)=\lim\limits_{t\to\infty}P(\tau>t)E(X_\tau-X_t|\tau>t)=0。

同上一类，由推论得到 E(X_t)=E(X_0)=E(X_\tau)。原命题得证。

综上，鞅的停时定理得证。

还是拿上面的赌博方法举例子。由于每次赌注翻倍，停时 \tau 显然有界，满足条件一。根据停时定理，E(X_\tau)=E(X_0)，即期望收益为 0。

Part 4：势函数

上面鞅的停时定理看起来在 OI 里一点用都没有。我们该如何把它运用上？

我们要求结束时间的期望，如果能把这玩意和某些东西线性组合在一起，使得到一个鞅，就能运用停时定理和期望的线性性求出结束时间的期望。

这时，就要借用一个叫势函数的东西。

设过程为 \{X_0,X_1,\cdots\}，\tau 是其停时，X_t 为 t 时刻的状态。

尝试构造函数 \Phi(X)，其中 X\in\{X_0,X_1,\cdots\}，使其满足 \forall t\in\mathbb{N},E(\Phi(X_{t+1})-\Phi(X_t)|X_0,X_1,\cdots,X_t)=-1。

这里的 \Phi(X) 就是我们口中的势函数。

此时，我们惊奇地发现，随机过程 Y=\{\Phi(X_i)+i|i\in\mathbb N\}，是个鞅，且停时仍然是 \tau！

因此，使用停时定理，E(Y_\tau)=E(Y_0)，代入得 E(\Phi(X_\tau)+\tau)=E(\Phi(X_0))。

移项并拆开期望，得到 E(\tau)=E(\Phi(X_0))-E(\Phi(X_\tau))。

为了计算方便，我们还需要 \Phi(X_\tau) 是个常数，就有：

E(\tau)=E(\Phi(X_0))-\Phi(X_\tau)

这就是应用了。

Part 5：例题

CF1025G Company Acquisitions

我们发现影响答案的只有连通块的大小和个数，每个连通块里面具体是谁我们并不关注。因此我们设计这个随机过程的状态 A 为除选中点外大小分别为 a_1,a_2,\cdots,a_k 的连通块构成的集合，即 A=\{a_1,a_2,\cdots,a_k\}。设除选中点外大小为 x 的连通块的势函数为 \varphi(x)，则有：

\Phi(A)=\sum\limits_{a_i\in A}\varphi(a_i)

现在尝试推出 \varphi(x)。由于合并的两点是随机选取，我们直接设它们分别包含 u,v 个非选中点。为了方便，包含 u 个的称为 u 点，另一个称为 v 点。根据 E(\Phi(X_{t+1})-\Phi(X_t)|X_0,X_1,\cdots,X_t)=-1，除了选中两点外的其他项都消掉了，只剩选中的两点的项。设经过一次操作，两点变化后势的和的期望为 E，因此有：

E-(\varphi(u)+\varphi(v))=-1

至于 E，其有 \dfrac 1 2 的概率让 u 点接上 v 点，另外 \dfrac 1 2 反之，因此：

E=\dfrac 1 2(\varphi(v+1)+u\varphi(0))+\dfrac 1 2(\varphi(u+1)+v\varphi(0))

联立列方程：

\dfrac 1 2(\varphi(v+1)+u\varphi(0))+\dfrac 1 2(\varphi(u+1)+v\varphi(0))-\varphi(u)-\varphi(v)=-1

由于势函数是人为构造的，可以强行定义 \varphi(0)=0，检验得该函数存在。

化简得到：

\varphi(u+1)+\varphi(v+1)=2\varphi(u)+2\varphi(v)-2

其对所以 u,v\in\mathbb{N} 均成立。取 u=v，有：

2\varphi(u+1)=4\varphi(u)-2

改下变量名，即：

\varphi(x+1)=2\varphi(x)-1

再加上 \varphi(0)=0，该递推式可用等比数列求和解出 \varphi(x)=1-2^x。

初态 \Phi(A_0) 可以 O(n\log n) 根据输入计算；终态 \Phi(A_\tau)=\varphi(n-1)。代入即可求。