鞅的停时定理

鞅

定义离散时间的随机过程 \(X = \{X_n, n\ge 0\}\) 是关于自身的鞅，当且仅当满足：

• \(\forall n \ge 0, E(|X_n|) < \infty\)。

• \(\forall n \ge 0, E(X_{n+1} | X_0,X_1,\ldots X_n) = X_n\)。

即对于任意时间 \(s\)，状态 \(X_0 \sim X_s\) 都确定时，\(X_{s+1}\) 的期望值等于 \(X_s\)。

同理，定义 \(Y = \{Y_n, n\ge 0\}\) 是关于 \(X\) 的鞅，当且仅当满足：

• \(\forall n \ge 0, E(|Y_n|) < \infty\)。

• \(\forall n \ge 0, E(Y_{n+1} | X_0,X_1,\ldots X_n) = Y_n\)。

例如，定义随机过程 \(X = \{X_t, t \ge 0\}\)，设 \(X_{t+1} = X_t + d_{t+1}\)，且 \(P(d_i = 1) = P(d_i = -1) = \dfrac{1}{2}\)，即 \(X_t\) 为从原点出发，每个时间等概率向左或向右走 \(1\) 单位长度，经过 \(t\) 时刻的位置，则 \(X\) 是一个鞅。

\[\begin{align} E(|X_n|) &\le n < \infty \tag{1} \\ E(X_{n+1} | X_0 \sim X_n) &= E(X_n + d_{n+1}) \notag \\&=X_n + E(d_{n+1}) \notag \\&=X_n \tag{2} \end{align} \]

继续定义 \(Y_t = X_t^2 - t\)，则 \(Y\) 是一个关于 \(X\) 的鞅。

\[\begin{align} E(|Y_n|) &= E(|X_n^2 - n|) \le E(|X_n^2|) + n \notag \\ &\le n^2 + n < \infty\tag{1} \\ E(Y_{n+1} | Y_0 \sim Y_n) &= E((X_n + d_{n+1})^2 - (n+1)) \notag \\&= E(X_n^2 +2X_n d_{n+1} + d_{n+1}^2 - (n+1)) \notag \\&=X_n^2 + 2X_n E(d_{n+1}) + E(d_{n+1}^2) - n - 1 \notag \\&=X_n^2 - n=Y_n\tag{2} \end{align} \]

停时

定义时间变量 \(T(T \ge 0)\) 为停时与随机过程 \(X\)，满足当知道 \(X_0 \sim X_n\) 时能判断 \(T\) 是否等于 \(n\)，则令停止过程 \(\bar{X}\) 为

\[ \bar{X} = \begin{cases} X_n, & n\le T \\ X_T & n > T \end{cases} \]

鞅的停时定理

若鞅 \(X\) 与停时 \(T\) 满足以下三个条件之一，则有 \(E(X_T)=E(X_0)\)。

• \(\bar{X}\) 有界。

• \(T\) 有界。

• \(E(T)\) 有限，且 \(E(|X_{n+1} - X_n|)\) 有界。

例如，求从 \(p(0\le p \le n)\) 位置出发，每次等概率往两边走，第一次走到 \(0\) 或 \(n\) 的时间 \(T\) 的期望。

设 \(X_t\) 为 \(t\) 时刻的位置，则 \(X\) 是一个鞅，由于 \(T\) 有界，则有 \(E(X_T) = E(X_0) = p\)

设 \(q\) 为 \(T\) 时刻到达 \(0\) 的概率，由于 \(E(X_T) = p = q \cdot 0 + (1-q)\cdot n\)，则 \(q = \dfrac{n-p}{n}\)。

设 \(Y_t = X_t^2 - t\)，则 \(Y_t\) 是一个关于 \(X\) 的鞅，则有 \(E(Y_T)=E(Y_0)\)，即 \(E(X_T^2 - T) = E(X_0^2) = p^2\)，所以 \(E(T) = E(X_T^2) - p^2 = q \cdot 0^2 + (1-q) \cdot n^2 - p^2 = p(n-p)\)。

势能函数

在 OI 中，通常势能函数 \(\Phi(A_t)\) 描述 \(t\) 时刻的局面，其满足 \(E(\Phi(A_{t + 1}) - \Phi(A_t) | A_0 \sim A_t) = -1\)，然后构造 \(X_t = \Phi(A_t)+t\)，那么 \(X_t\) 是一个鞅。

再根据鞅的停时定理，有 \(E(X_T) = E(X_0)\)，那么 \(E(T) = \Phi(A_0) - \Phi(A_T)\)。

例题

CF1025G Company Acquisitions

题目链接

设 \(\Phi(A_t) = \sum f(a_i)\)，其中 \(a_i\) 是每个活跃公司的大小（包括自身）。

假设随机选到了 \(a_i = x, a_j = y\)，由于有 \(E(\Phi(A_{t+1})-\Phi(A_t))=-1\)，所以 \(x,y\) 变化后的期望势能要等于 \(f(x)+f(y)-1\)，即

\[\begin{align} f(x)+f(y)-1&= \dfrac{1}{2}\cdot(f(x+1)+(y-1)\cdot f(1))+ \dfrac{1}{2}\cdot(f(y+1)+(x-1)\cdot f(1)) \end{align} \]

考虑直接钦定 \(f(x)-\dfrac{1}{2}=\dfrac{1}{2}\cdot(f(x+1)+(x-1)f(1))\)，不妨假设 \(f(1)=0\)，则有 \(f(x)=-(2^{x-1} - 1)\)。

答案即为 \(\sum f(c_i) - f(n)\)，复杂度 \(O(n)\)。

CF1349D Slime and Biscuits

题目链接

设 \(\Phi(A_t) = \sum f(a_i)\)，其中 \(a_i\) 是每个人的饼干数量，\(m = \sum a_i\)。

可以直接考虑一个人的势能变化，期望为 \(\dfrac{x}{m}\cdot f(x-1) + \dfrac{m-x}{m}\cdot \dfrac{1}{n-1} \cdot f(x+1) + \dfrac{m-x}{m}\cdot \dfrac{n-2}{n-1} \cdot f(x)\)。

由于有 \(E(\Phi(A_{t+1})-\Phi(A_t))=-1\)，所以 \(\sum\limits f(x) - 1 = \sum\limits \dfrac{x}{m}\cdot f(x-1) + \dfrac{m-x}{m}\cdot \dfrac{1}{n-1} \cdot f(x+1) + \dfrac{m-x}{m}\cdot \dfrac{n-2}{n-1} \cdot f(x)\)。

把 \(1\) 拆成 \(\dfrac{1}{n} \cdot n\)，那么就可以钦定 \(\dfrac{x}{m}\cdot f(x-1) + \dfrac{m-x}{m}\cdot \dfrac{1}{n-1} \cdot f(x+1) + (\dfrac{m-x}{m}\cdot \dfrac{n-2}{n-1} - 1) \cdot f(x) + \dfrac{1}{n} = 0\)

答案即为 \(\sum f(c_i) - f(m)\)，复杂度 \(O(m)\)。

CF850F Rainbow Balls

题目链接

设 \(\Phi(A_t) = \sum f(a_i)\)，其中 \(a_i\) 是每个颜色的球数量，\(m = \sum a_i\)。

考虑 \(f(x)\) 的变化，有 \((\dfrac{x(x-1)}{m(m-1)}+\dfrac{(m-x)(m-x-1)}{m(m-1)}) \cdot f(x) + \dfrac{x(m-x)}{m(m-1)} \cdot (f(x+1)+f(x-1))\)。

那么钦定 \((\dfrac{x(x-1)}{m(m-1)}+\dfrac{(m-x)(m-x-1)}{m(m-1)} - 1) \cdot f(x) + \dfrac{x(m-x)}{m(m-1)} \cdot (f(x+1)+f(x-1)) + \dfrac{1}{n} = 0\) 且 \(f(m)=0\)。

化简可得 \(f(x+1)-2f(x)+f(x-1)=-\dfrac{m(m-1)}{nx(m-x)}\)，设 \(g(x)=f(x)-f(x-1)\) 即可快速得到 \(f(m)\)。

答案即为 \(\sum f(c_i) - (f(m)+(n-1)\cdot f(0))\)，复杂度 \(O(\max a)\)。