鞅与停时定理

Arghariza · 2023-10-09 20:36:05 · 算法·理论

其实这是一篇正经的科普文章。

一些约定

• 随机过程：对一个参数集随机的一组变量集合，参数集通常是时间 T，若 \forall t\in T，X_t 为随机变量，那么 \{X_t|t\in T\} 就是一个随机过程。
• 条件概率：P(A|B)，即 A 事件在 B 事件条件下发生的概率。
• 条件期望：E(A|B)，类比条件概率，即 A 事件在 B 事件条件下的期望。
• 几乎一定：事件 A 几乎一定发生，当且仅当 P(A)=1。A 不发生的情况集合可能非空，但它们的概率为 0。样本空间有限时，“几乎一定”和“一定”通常没有区别；但是当样本空间无限时，就有区别了。比如 [0,1] 中均匀随机一个实数 x，则 P(x>0)=1，可以说选出的 x 几乎一定大于 0，但理论上确实可以存在 x=0 的样本。

离散时间鞅

一个离散时间鞅为一个以时间为参数集合的随机过程，即随机过程 \{X_0,X_1,\cdots \}，满足对于任意时刻 n\in \mathbb{N}，均有：

第二个条件看起来不知所云，其实意思就是当 X_{0},X_{1},\cdots ,X_{n} 已经确定时，X_{n+1} 的期望等于 X_n。类似一个公平赌博游戏，若我们已经得到了前 n 场赌博后你所拥有的财产（观测值），那么要求第 n+1 场的观测值的期望等于第 n 场的观测值（不亏不赚），才能满足公平赌博游戏的定义（所以公平赌博游戏其实差不多就是鞅www）。

同时不难发现鞅的线性加减、增减常数都不影响其鞅的性质。

停时

关于随机过程 \{X_{0},X_{1},\cdots\} 的停时为一个非负的随机变量 T（可能为 ∞，即操作无限进行），满足对任意时刻 n，你可以通过观测 X_0,X_1,\cdots,X_{n} 的取值得出 n 和 T 的大小关系/等量关系。即 [n=T],[n<T],[n>T] 三个随机变量的取值仅与 X_{0},X_{1},\cdots ,X_{n} 有关。

对于随机过程 \{X_0,X_1,\cdots\}，对应带停时为 T 的随机过程 \{\overline {X_0},\overline {X_1},\cdots\} 的定义为：

即 \{\overline {X_{1}},\overline {X_{2}},\cdots \} 为将 \{X_0,X_1,\cdots \} 在 T 之后的项全部覆盖为 T 后的随机过程，可以看作在时刻 T 终止随机操作。（所以停时也可以理解为操作的停止时间。）

由于 \overline{X_n} 中 n\le T 时 \overline{X_n}=X_n 期望不变，而 n>T 时我们钦定它期望不变，所以满足鞅期望观测值不变的性质，所以 \{\overline{X_1},\overline{X_2},\cdots\} 也是一个鞅。

鞅的停时定理

设 T 为离散时间鞅 \{X_0,X_1,\cdots\} 的停时，且 T 几乎一定有限，当下面三个条件之一成立时，有 E(X_T)=E(X_0)

• E(|X_{i+1}-X_i|)$ 几乎一定有界，且 $E(T)$ 有限，即存在常数 $K$ 使得 $P(E(|X_{i+1}-X_i|)\le K)=1
• \overline{X_i}$ 几乎一定有界，即存在常数 $K$ 使得 $P(|\overline{X_i}|\le K)=1

为了帮助理解，给出下面若干例子：

• 数轴上从 0 开始随机向右游走，每次走 1 或 2 的距离，走过一个常数 K 后停止。那么 T 一定有界，满足第一个条件。
• 从 [0,1] 中随机选择实数，直到选出非 0 数为止。T 几乎一定有界，满足第一个条件。
• 数轴上从 0 开始随机左右游走，每次走 1 的距离，走到区间 [-K,K]（K 为常数） 边界后停止。由于 \overline{X_n} 有界 [-K,K]，满足第三个条件。
• 你在读这篇文章，假设你每次随机向目前阅读位置的后面跳一个位置然后开始读，读完为止。那么很显然 \overline{X_n} 有界（文章长度），也满足第三个条件。
• 第二个条件是大多数题目所包含的（比如让你求停时的期望，每次操作带有的变化量有界等等）。

势能分析

考虑经典模型：

假设现在有随机过程 \{X_0,X_1,\cdots \}，T 为其停时，给定初始状态 X_0，终止状态 \overline{X_T}，求 E(T)。

考虑构造势能函数 \varphi(X)，同时描述了时间和状态两个变量：

• E(\varphi(X_{n+1})-\varphi(X_{n})|X_{0},X_{1},\cdots,X_{n})=-1
• \varphi(X_{T})$ 为常数，且 $\nexists i<T,\varphi(X_{i})=\varphi(X_T)

第一个限制保证了每个时刻，势能的变化量期望为 -1，那么 E(\varphi(X_0))-E(\varphi(X_n))=n；第二个限制保证了末状态势能唯一，也就是保证末状态为第一个满足终止条件的状态的需要。

构造 Y_i=\varphi(X_i)+i，根据定义，\{Y_0,Y_1,\cdots\} 为一个离散时间鞅。那么根据停时定理，可以得到 E(Y_T)=E(Y_0)，即 E(\varphi(X_T)+T)=E(\varphi(X_0))，即 E(T)=E(\varphi(X_0))-E(\varphi(X_T))，根据定义右边两项都是常数值，于是就能方便地求出 E(T)。

有的地方也把 \varphi 取相反数，那么就是每次期望 +1，期望停时为初状态的势能减去末状态的势能。

对于一般题目来讲，构造关于题面中状态有关量为自变量的函数，然后根据第一条限制解函数方程/递推，并使用鞅与停时定理求出期望停时即可。

势能具有相对性，这允许我们对于一些常数 C，钦定 f(C) 的值。这通常会使函数方程大大简化。

CF1025G Company Acquisitions

定义整个局面 X 的势能函数为 \varphi(X)，由于我们只关心每个点跟在屁股后面的点的个数，定义单个点 u 的势能为 f(c_u)，c_u 为局面 X 下跟在 u 后的点的个数，f 为关于 c 的函数，令 \varphi(X)=\sum\limits_{u}f(c_u)。

则 X\to X' 的势能变化量只和每次随机选出来的两个点 u,v 的 c 有关，令 c_u=x,c_v=y：

我们令 f(0)=0：

要求对任意 x,y 均成立，那么一个简单的想法是直接拆两半：

结合 f(0)=0 得到：

那么答案就是 \left(\sum\limits_{u}f(c_u)\right)- f(n)，复杂度 O(n)。

CF1479E School Clubs

我们只关心每个组内的人数，所以依旧令局面 X 的势能值 \varphi(X)=\sum\limits_{i=1}^{m}f(a_i) 为各个组势能之和，一组的势能定义为其人数 a_i 的 f 值。

每次操作，将随机发电的那个人所在的组拎出来，设为第 i 组：

• 这个人新开了一个组：\varphi(X')=\varphi(X)-f(a_i)+f(a_i-1)+f(1)。
• 这个人回到了原来的组：\varphi(X')=\varphi(X)。
• 这个人跑到了其他组，设为 j 组：\varphi(X')=\varphi(X)-f(a_i)-f(a_j)+f(a_i-1)+f(a_j+1)

然后就是一些 Dirty Work 了：

不妨设 f(1)=-2：

然后 O(n) 递推 f 的值即可。这是能过的。