鞅的停时定理

学了一些比较有意思的东西，记录一下。

关于 AI ：本文使用蓝色大肥鱼进行查错和标准化，可能会有一点人机味道，保证人类贡献大于 AI。

鞅

设 \((\Omega,\mathcal F,\mathbb P)\) 是概率空间。

随机过程 \(\{M_n\}_{n\ge 0}\) 称为关于 \(\{\mathcal F_n\}\) 的鞅，如果对于任意 \(n\) 存在：

\(\mathbb E[|M_n|]<\infty\)
\(\mathbb E[M_{n+1}\mid \mathcal F_n]=M_n\)

容易得到 \(\mathbb E[M_n]=\mathbb E[M_0]\)。

停时

取值于 \(\{0,1,2,\dots\}\cup\{\infty\}\) 的随机变量 \(T\) 称为关于 \(\{\mathcal F_n\}\) 的停时，如果对每个 \(n\)，

\[\{T\le n\}\in \mathcal F_n. \]

设 \(\{M_n\}\) 是鞅，\(T\) 是停时。若满足以下任意一条：

有界停时：

\[\exists C,\quad T\le C \quad \text{几乎必然}. \]

有限期望 + 增量有界：

\[\mathbb E[T]<\infty, \qquad \exists K,\quad |M_{n+1}-M_n|\le K \quad \text{对所有 }n

一致有界：

\[\exists K,\quad |M_{n\wedge T}|\le K\quad \text{几乎必然},\qquad\mathbb P(T<\infty)=1. \]

那么就符合停时定理。

感觉记不住，感性理解一下大概就是停止时刻不会无限延伸，并且每一步的收益不会突然增长特别多。

停时定理：

在满足上面的任意条件之一的情况下有：

\[\mathbb E[M_T]=\mathbb E[M_0]. \]

势能函数：

在我们做题的时候需要构造一个势能函数，满足 \(\varphi\)：使对每个非终止局面 \(A\notin\mathcal S\)，

\[\mathbb E[\varphi(A_{t+1})\mid A_t=A]=\varphi(A)-1. \]

令

\[M_t=\varphi(A_t)+t. \]

则对 \(t，

\[\begin{aligned} \mathbb E[M_{t+1}\mid \mathcal F_t] &=\mathbb E[\varphi(A_{t+1})\mid \mathcal F_t]+t+1\\ &=\varphi(A_t)-1+t+1\\ &=\varphi(A_t)+t\\ &=M_t. \end{aligned} \]

所以 \(M_t\) 是鞅。

对 \(M_t\) 用停时定理。

那么有：

\[\mathbb E[\varphi(A_T)+T] = \mathbb E[\varphi(A_0)]. \]

移项：

\[\mathbb E[T]=\mathbb E[\varphi(A_0)]-\mathbb E[\varphi(A_T)]. \]

一般 \(\mathbb E[\varphi(A_0)]\) 和 \(\mathbb E[\varphi(A_T)]\) 容易得到，那我们就可以得出 \(\mathbb E[T]\)。

但是构造 \(\varphi\) 函数的过程比较人类智慧。

一些习题：

例题一：一个公平游戏，每局 \(\pm1\)。规则是“第一次赢到 \(+1\) 就停”。

感性理解一下发现不能停时定理，因为注意到 \(T\) 可能趋近于 \(\infty\)。

例题二：你初始有 \(k\) 元，每局赢 \(1\) 元或输 \(1\) 元，概率各 \(1/2\)。
当你到达 \(0\) 元或 \(N\) 元时停止。求：

最终到达 \(N\) 元的概率；
平均玩多少局。

设 \(M_t\) 为第 \(t\) 局之后的钱数，初始 \(M_0=k\)。

注意到 \(\mathbb E[M_{t+1}\mid M_t]=M_t\)，所以 \(M_t\) 就是鞅。由于 \(0\le M_t\le N\)，也就是 \(M_t\) 有界。所以满足鞅的停时定理。

所以有：

\[\mathbb E[M_T] = \mathbb E[M_0] = k = 0\cdot\mathbb P(M_T=0)+N\cdot\mathbb P(M_T=N). \]

将 \(\mathbb P(M_T=0)+\mathbb P(M_T=N)=1\) 带入得：

\[\mathbb P(M_T=N)=\frac{k}{N}. \]

第二问求停时，那肯定得停时定理。

考虑设计一下 \(\varphi\) 函数。

既然需要满足

\[\mathbb E[\varphi(A_{t+1})\mid A_t=A]=\varphi(A)-1, \]

那我们有：

\[\frac{\varphi(x+1)+\varphi(x-1)}{2}=\varphi(x)-1. \]

移项变成：

\[\varphi(x+1)-2\varphi(x)+\varphi(x-1)=-2. \]

左边是二阶差分。记一阶差分

\[\Delta\varphi(x)=\varphi(x)-\varphi(x-1), \]

则二阶差分就是 \(\Delta\varphi(x+1)-\Delta\varphi(x)\)。方程变成：

\[\Delta\varphi(x+1)-\Delta\varphi(x)=-2. \]

\(\Delta\varphi\) 每增加 \(x\) 一步就减少 \(2\)。也就是说 \(\Delta\varphi\) 是公差为 \(-2\) 的等差数列。

由等差数列：

\[\Delta\varphi(x)=\Delta\varphi(1)-2(x-1). \]

记为

\[\Delta\varphi(x)=C-2x+2, \]

其中 \(C=\Delta\varphi(1)\) 是任意常数（取决于 \(\varphi(1)\) 的选法）。

再求和得到 \(\varphi(x)\)：

\[\varphi(x)=\varphi(0)+\sum_{k=1}^{x}\Delta\varphi(k) =\varphi(0)+\sum_{k=1}^{x}(C+2-2k). \]

计算这个和：

\[\sum_{k=1}^{x}(C+2-2k) =(C+2)x-2\cdot\frac{x(x+1)}{2} =(C+2)x-x^2-x =(C+1)x-x^2. \]

所以

\[\varphi(x)=\varphi(0)-x^2+(C+1)x. \]

然后注意到一次项和常数项不会影响答案，所以我们得到 \(\varphi(x)=-x^2\)。

应用停时定理得

\[\mathbb E[T]=\varphi(k)-\mathbb E[\varphi(M_T)] =(-k^2)-\left(0\cdot\frac{N-k}{N}-N^2\cdot\frac{k}{N}\right) =k(N-k). \]

是不是来点感觉了。

例题三：CF1025G Company Acquisitions

题目大意：有 \(n\) 个公司，一部分是活跃公司，每个非活跃公司都跟随恰好一个活跃公司。每回合随机等概率选出两个不同的活跃公司 \(x,y\)，掷硬币决定谁收购谁：若 \(x\) 收购 \(y\)，则 \(y\) 变为非活跃并跟随 \(x\)，而原本跟随 \(y\) 的所有公司全部重新变为活跃。当只剩一个活跃公司时停止，求期望天数。

设势能函数。一个局面只需要知道每个活跃公司手下有多少个跟随者。设 \(a_i\) 为第 \(i\) 个活跃公司当前的跟随者数量，定义

\[\varphi(\text{局面})=\sum_{i} f(a_i). \]

对非终止局面计算一步期望变化。假设本回合选中的两个活跃公司的跟随数分别为 \(x\) 和 \(y\)。

若 \(x\) 收购 \(y\)：\(x\) 的跟随数变为 \(x+1\)，\(y\) 不再活跃，而原来跟随 \(y\) 的 \(y\) 个公司各变成一个活跃公司，每个的跟随数为 \(0\)。这一步之后，这两个“旧关键点”的势能和变为

\[f(x+1)+y f(0). \]

若 \(y\) 收购 \(x\)，对称地，势能和变为

\[f(y+1)+x f(0). \]

掷硬币等概率，所以这对关键点贡献的期望势能是

\[\frac12\left(f(x+1)+y f(0)\right)+\frac12\left(f(y+1)+x f(0)\right). \]

其余活跃公司的跟随数没有变，势能不变。原来这两家贡献的是 \(f(x)+f(y)\)，因此整局势能的期望变化量为

\[\frac12 f(x+1)+\frac12 y f(0)+\frac12 f(y+1)+\frac12 x f(0)-f(x)-f(y). \]

我们希望一步之后势能期望减少 \(1\)，即

\[\mathbb E[\varphi(A_{t+1})\mid A_t]=\varphi(A_t)-1. \]

于是令上式等于 \(-1\)。为方便取 \(f(0)=0\)，方程化为

\[\frac12 f(x+1)+\frac12 f(y+1)-f(x)-f(y)=-1. \]

移项并拆开：

\[\left(\frac12 f(x+1)-f(x)\right)+\left(\frac12 f(y+1)-f(y)\right)=-1. \]

这个式子要对任意的 \(x,y\) 都成立。左边是只含 \(x\) 的一项与只含 \(y\) 的一项之和，如果这个和恒为常数 \(-1\)，那么每一项本身也必须是常数，并且两个常数之和为 \(-1\)。于是存在常数 \(C\) 使得

\[\frac12 f(x+1)-f(x)=C \]

对每个 \(x\) 成立，且 \(2C=-1\)，即 \(C=-\frac12\)。所以

\[\frac12 f(x+1)-f(x)=-\frac12, \]

乘以 \(2\)：

\[f(x+1)=2f(x)-1. \]

结合 \(f(0)=0\)，递推两步就能看出规律：

\[f(1)=2\cdot0-1=-1,\quad f(2)=2(-1)-1=-3,\quad f(3)=2(-3)-1=-7,\dots \]

归纳得

\[f(k)=1-2^k. \]

终止局面的势能。终止时只有一个活跃公司，它跟随了其余全部 \(n-1\) 个公司，所以 \(a=n-1\)，终态势能

\[\varphi(A_T)=f(n-1)=1-2^{n-1}. \]

停时定理给出

\[\mathbb E[T]=\varphi(A_0)-\mathbb E[\varphi(A_T)]. \]

终态确定，所以

\[\mathbb E[T]=\varphi(A_0)-\varphi(A_T) =\sum_{i} \left(1-2^{a_i}\right)-\left(1-2^{n-1}\right). \]

答案是：

\[\mathbb E[T]=\left(2^{n-1}-1\right)-\sum_{i}\left(2^{a_i}-1\right). \]

其中 \(a_i\) 是第 \(i\) 个活跃公司当前的跟随者数量，求和只遍历活跃公司。

例题四：CF1349D Slime and Biscuits

有 \(n\) 个人，第 \(i\) 个人有 \(a_i\) 块饼干，总数 \(m=\sum_{i=1}^n a_i\) 每回合随机等概率选一块饼干，再随机等概率选一个不是它当前主人的人，把这块饼干给那个人。求第一次出现“某个人拥有全部 \(m\) 块饼干”的期望步数。

一个局面只需要知道每个人手里有多少块饼干。设第 \(i\) 个人有 \(a_i\) 块，定义

\[\varphi(\text{局面})=\sum_{i=1}^n f(a_i). \]

对非终止局面计算一步的期望变化。假设本回合选中的饼干属于第 \(i\) 个人，概率为 \(a_i/m\)；把它送给第 \(j\) 个人，\(j\ne i\)，概率为 \(1/(n-1)\)。这一步之后

\[a_i\to a_i-1,\qquad a_j\to a_j+1. \]

势能变化为

\[f(a_i-1)-f(a_i)+f(a_j+1)-f(a_j). \]

于是

\[\begin{aligned} \mathbb E[\Delta\varphi] &=\sum_{i=1}^n \frac{a_i}{m}\cdot\frac1{n-1} \sum_{j\ne i}\Bigl[f(a_i-1)-f(a_i)+f(a_j+1)-f(a_j)\Bigr]. \end{aligned} \]

拆成两部分。第一部分：

\[\sum_{i=1}^n \frac{a_i}{m}\cdot\frac1{n-1}\cdot(n-1)\bigl[f(a_i-1)-f(a_i)\bigr] = \sum_{i=1}^n \frac{a_i}{m}\bigl[f(a_i-1)-f(a_i)\bigr]. \]

第二部分交换求和：

\[\begin{aligned} &\sum_{i=1}^n \frac{a_i}{m}\cdot\frac1{n-1} \sum_{j\ne i}\bigl[f(a_j+1)-f(a_j)\bigr]\\ &=\frac1{n-1}\sum_{j=1}^n \bigl[f(a_j+1)-f(a_j)\bigr] \sum_{i\ne j}\frac{a_i}{m}\\ &=\frac1{n-1}\sum_{j=1}^n \bigl[f(a_j+1)-f(a_j)\bigr]\cdot\frac{m-a_j}{m}. \end{aligned} \]

合并得到

\[\mathbb E[\Delta\varphi] = \sum_{i=1}^n\left[ \frac{a_i}{m}\bigl(f(a_i-1)-f(a_i)\bigr) + \frac{m-a_i}{m(n-1)}\bigl(f(a_i+1)-f(a_i)\bigr) \right]. \]

我们希望

\[\mathbb E[\varphi(A_{t+1})\mid A_t]=\varphi(A_t)-1, \]

也就是 \(\mathbb E[\Delta\varphi]=-1\)。一个充分条件是每一项都贡献 \(-a_i/m\)，因为

\[\sum_{i=1}^n \frac{a_i}{m}=1. \]

于是对每个 \(k=a_i\)，要求

\[\frac{k}{m}\bigl(f(k-1)-f(k)\bigr) + \frac{m-k}{m(n-1)}\bigl(f(k+1)-f(k)\bigr) = -\frac{k}{m}. \]

乘以 \(m\)：

\[k\bigl(f(k-1)-f(k)\bigr) + \frac{m-k}{n-1}\bigl(f(k+1)-f(k)\bigr) = -k. \]

令

\[\Delta(k)=f(k)-f(k-1), \]

则

\[f(k-1)-f(k)=-\Delta(k), \qquad f(k+1)-f(k)=\Delta(k+1). \]

代入得

\[-k\Delta(k)+\frac{m-k}{n-1}\Delta(k+1)=-k. \]

移项：

\[\frac{m-k}{n-1}\Delta(k+1)=k\Delta(k)-k, \]

所以

\[\Delta(k+1)=\frac{(n-1)k\bigl(\Delta(k)-1\bigr)}{m-k}. \]

取 \(f(0)=f(1)=0\)，则 \(\Delta(1)=f(1)-f(0)=0\)。从 \(k=1\) 递推到 \(k=m-1\)，再用

\[f(k+1)=f(k)+\Delta(k+1) \]

前缀和即可得到所有 \(f(k)\)。

终止局面：一个人有 \(m\) 块，其余 \(n-1\) 个人有 \(0\) 块。因此终态势能

\[\varphi(A_T)=f(m)+(n-1)f(0)=f(m). \]

初始势能

\[\varphi(A_0)=\sum_{i=1}^n f(a_i). \]

停时定理条件满足。由

\[\mathbb E[T]=\varphi(A_0)-\mathbb E[\varphi(A_T)] \]

得到

\[\mathbb E[T]=\sum_{i=1}^n f(a_i)-f(m) \]

总结：

输入：初始局面 \(A_0\)，终止集合 \(\mathcal S\)。

大概就是这样一个过程：

设 \(\varphi(\text{局面})=\sum f(\text{分量})\)。
对非终止局面 \(A\notin\mathcal S\)，计算 \(\mathbb E[\varphi(A_{t+1})\mid A_t=A]\)，令它等于 \(\varphi(A)-1\)，整理成 \(f\) 的递推/方程。
指定 \(f\) 的一个初值（如 \(f(0)=0\)）。
解出所有需要的 \(f(k)\)。
计算 \(\varphi(A_0)\) 和 \(\mathbb E[\varphi(A_T)]\)；若终止局面势能确定，就是 \(\varphi(A_T)\)。
输出 \(\mathbb E[T]=\varphi(A_0)-\mathbb E[\varphi(A_T)]\)；若终止势能确定，则输出 \(\varphi(A_0)-\varphi(A_T)\)。