一、离散时间鞅
定义离散时间鞅为一个时间离散的随机过程 \(X_0, X_1, \ldots\)，使得 \(\forall n \in \mathbb{N}\)，均满足：
- \(E(|X_n|) < \infty\)。
- \(E(X_{n + 1} - X_n \mid X_0, X_1, \ldots, X_n) = 0\)。
易得：\(E(X_n) = X_0\)。
二、停时定理
设 \(T\) 为鞅过程 \(X_0, X_1, \ldots\) 的停时，则 \(E(X_T) = X_0\)，当且仅当以下三个条件之一成立：
- \(T\) 几乎必然有界。
- \(|X_{i + 1} - X_i|\) 一致有界，\(E(T)\) 有限。
- \(X_i\) 一致有界，\(T\) 几乎必然有限。
名词解释：
- \(X \in \mathbb{R} \cup \infty\) 有限：\(|X| < \infty\)。
- \(X \in \mathbb{R} \cup \infty\) 有界：\(\exist L, R \in \mathbb{R}, X \in [L, R]\)。
- \(X_i \in \mathbb{R} \cup \infty\) 一致有界：\(\forall i, \exist L, R \in \mathbb{R}, X_i \in [L, R]\)。
- 事件 \(A\) 几乎必然发生：\(P(A) = 1\)。
三、经典套路：势能函数法
对于随机事件序列 \(A_0, A_1, \ldots\)，设 \(T\) 为其停时，终止状态为 \(A_T\)，求 \(E(T)\)。
构造势能函数 \(\Phi(A)\)，满足：
- \(E(\Phi(A_{n + 1} - A_n) \mid A_0, A_1, \ldots, A_n) = -1\)。
- \(\Phi(A_T)\) 为常数且 \(\Phi(A_i) = \Phi(A_T)\) 当且仅当 \(i = T\)。
构造序列 \(X_i = \Phi(A_i) + i\)，则 \(E(X_{n + 1} - X_n \mid X_0, X_1, \ldots, X_n) = 0\)，即 \(X_0, X_1, \ldots\) 是鞅。
根据停时定理，可得 \(E(X_T) = E(X_0)\)，即 \(E(T) = E(\Phi(A_0)) - \Phi(A_T)\)。
四、例题
CF1025G Company Acquisitions
设一个活跃的有 \(x\) 个企业跟随的企业的势能函数为 \(f(x)\)，一个局面的势能函数 \(\Phi(A)\) 为所有活跃企业的势能函数之和。
一次操作势能变化量只与随出的两个企业有关，设两个企业分别有 \(x\) 和 \(y\) 个企业跟随。
\[f(x) + f(y) - 1 = \dfrac{1}{2} \times (f(x + 1) + y \cdot f(0) + f(y + 1) + x \cdot f(0))
\]
由于需要对任意 \(x, y\) 成立，可得：
\[f(x) - \dfrac{1}{2} x \cdot f(0) - \dfrac{1}{2} \cdot f(x + 1) = \dfrac{1}{2}
\]
感觉这个 \(f(0)\) 比较突兀，直接钦定 \(f(0) = 0\)，得到：
\[f(x + 1) = 2f(x) - 1
\]
归纳得到 \(f(x) = 1 - 2 ^ x\)，并且 \(\Phi(A_T) = 1 - 2 ^ {n - 1}\) 为常量。
最终计算 \(\Phi(A_0) - \Phi(A_T)\) 即可，时间复杂度 \(\Theta(n)\)。