鞅和停时定理解决期望停时问题
Vocalise
·
·
题解
鞅
鞅是一种随机变量序列 \{X_n\}_{n\ge0}，满足
\mathrm E(X_{n+1} - X_n | X_0,X_1,X_2,\cdots,X_n) =0
即：不管之前的序列如何，每个位置下一位的值期望不变。
注意到 | 表示条件期望：对所有可能的 X_i(1\le i\le n) 求条件概率加权。
并且不能简单认为 \mathrm E(X_{n+1}-X_n|X_0,\cdots,X_n)=\mathrm E(X_{n+1}-X_n) 对于任意情况成立（但是对于鞅显然成立）。
定义一个离散随机变量，当 X_i 第一次出现 1 之后都一定是 1。
那么这个期望就不对之前的结果独立。
停时定理
我们知道对于鞅 X_n，\forall n\in \mathbb N,\mathrm E(X_n) = \mathrm E(X_{n-1})=\cdots=\mathrm E(X_0)。对于我们的研究对象，初始值一般一定。
又有一个随机变量（可能与 X 有关）T 取 T\in \mathbb N，称 T 为该鞅的停时。
我们尝试回答是否 \mathrm E(X_T) = \mathrm E(X_0)：并不一定。
但是对于以下三种情况之一成立的 T ，上式成立：
-
-
-
一致有界：有与 X 和 n 无关的上界。
我们定义有限为一定在 \mathbb R 中；有界是有常数上界，显然强于有限。比如 \dfrac 1x(x\in (0,1))，它有限，无界。
至于无限：实践中应该遇不到。所以第 2,3 中后半段可以认为恒真。
势能函数法
对于一个随机过程 A_n（不必要是实数），我们构造势能函数 \varphi(A_n) 使
\mathrm E(\varphi(A_{n+1}) - \varphi(A_n)|A_n,A_{n-1},\cdots A_n) = 1
另一个随机过程 X_n = \varphi(A_n) - n，则
\mathrm E(X_n - X_{n-1}|\cdots) = \mathrm E(\varphi(A_n) - \varphi(A_{n-1})|\cdots) - 1 = 0
所以我们知道假如 $X_n$ 满足停时定理条件，则
$$
\mathrm E(X_T) = \mathrm E(\varphi(A_T)) - \mathrm E(T) = \mathrm E(X_{0}) = \mathrm E(\varphi(A_0)) = \varphi(A_0)
$$
$$
\mathrm E(T) = \mathrm E(\varphi(A_T)) - \varphi(A_0)
$$
这里的 $\mathrm E(\varphi(A_T))$ 仍然不太容易考虑；但是**假如 $T$ 取值 $S$，且对于停时状态 $A_t(t\in S)$，$\varphi(A_t)$ 相同，而且对于其它状态都不取 $\varphi(A_T)$，$\mathrm E(\varphi(A_T))$ 就是 $\varphi(A_T)$。这一个条件往往归化成 $\varphi(A_T)$ $\min/\max$ 值**。
可以求出停时的期望。
### $\text{CF1349D Slime and Biscuits}
容易发现该随机状态为一个可重集 A = \{a_i\}_{i=1}^n；且变化只和最后的状态有关。
所以构造 \varphi(A_n) = \sum\limits_{i=1}^nf(a_{n,i})，记 S = \sum\limits_{i=1}^na_i 使
\begin{aligned}
\mathrm E(\varphi(A_{n+1}) - \varphi(A_n)|A_n) &= \sum_{i=1}^n\mathrm E(f(a_{n+1,i})|A_n)) - f(a_{n,i}) = 1 \\
&= \sum_{i=1}^n f(a_{n,i} - 1)\times \frac{a_{n,i}}S + f(a_{n,i} + 1)\times (1 - \frac{a_{n,i}}S)\frac 1{n-1}+f(a_{n,i})\times(1-\frac{a_{n,i}}S)(1-\frac 1{n-1}) - f(a_{n,i}) \\
&= \sum_{i=1}^n f(a_{n,i} - 1)\times \frac{a_{n,i}}S + f(a_{n,i} + 1)\times (1 - \frac{a_{n,i}}S)\frac 1{n-1} - f(a_{n,i})\times(\frac{a_{n,i}}S+\frac1{n-1}-\frac{a_{n,i}}{S(n-1)}) \\
\end{aligned}
可以进一步强化性质：使和式中每一项有确定值。
f(a_{n,i} - 1)\times \frac{a_{n,i}}S + f(a_{n,i} + 1)\times (1 - \frac{a_{n,i}}S)\frac 1{n-1} - f(a_{n,i})\times(\frac{a_{n,i}}S+\frac1{n-1}-\frac{a_{n,i}}{S(n-1)}) = \frac{a_{n,i}}S
f(a_{n,i} - 1)\times a_{n,i} + f(a_{n,i} + 1)\times\frac {S - a_{n,i}}{n-1} - f(a_{n,i})\times(a_{n,i} + \frac S{n-1}-\frac {a_{n,i}}{n-1}) = a_{n,i}
可得到递推式：
f(x+1) = f(x)\times(\frac{x(n-1)}{S-x}+1)+(1-f(x-1))\times \frac{x(n-1)}{S-x}
我们可以指定一个初值，使该函数可以直接求。
最后需要满足的条件是 \varphi(A_n) = \varphi(A_T) 当且仅当 A_n 是终止状态，以及 \varphi(A_n)-n 有界（条件 3）。
我们再令 \varphi(A_T) 为最大值，这样两个条件就都满足了。
~~继续分析：~~ 分析不出，下面忽略。
~~考虑最终状态是「最集中」的状态，尝试证明 $\forall x_1\le x_2$，~~
$$
f(x_1) + f(x_2) < f(x_1-1) + f(x_2+1)
$$
~~接着进行归纳即可证明不断将小 $x$ 并入大 $x$ 中会取得最大。~~
~~容易发现这也就是函数的下凸性。令 $g(x) = \dfrac{x(n-1)}{S-x}$，变形递推式：~~
$$
f(x + 1) - f(x) = (f(x) - f(x - 1))g(x) + g(x)
$$
$$
\Delta f(x) - \Delta f(x-1) = (\Delta f(x-1)+1)(g(x) - 1) + 1> 0
$$
~~考虑 $g(x) - 1 < 0$ 的情况。不妨令 $n = 2$，有 $-1< g(x) - 1 < 0$，解得 $x < \dfrac 12S$，此时令 $\Delta f(x-1)\le -1$。~~
~~$g(x) - 1\ge 0$ 的情况下，令 $\Delta f(x-1)\ge -1$ 即可。~~
---
$\text{upd:}$ 看到有人证了，发现上面证明过于强了。我们只需证明 $\forall x_1,x_2>0,f(x_1+x_2)+f(0) > f(x_1) + f(x_2)$。
即：每次将一两堆完全合并一定更优。
因为 $x\in \mathbb N$，所以等价于 $f(x+1)+f(0) > f(x) + f(1)$。当我们令 $f(0) = 0$ 时可以解得 $f(1) = 0$，所以就等价于 $f(x)$ 严格递增。
由上面的式子
$$
f(x + 1) - f(x) = (f(x) - f(x - 1) + 1)g(x)
$$
且 $f(1) - f(0) = 0$，且 $x > 0$ 时 $g(x) > 0$ 可以归纳得证。
本题就做完了。
答案为 $f(S) - \sum\limits_{i=1}^nf(a_{0,i})$。时间 $\mathcal O(\sum\limits_{i=1}^n a)$。
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
const int N = 100001;
const int M = 300001;
const int p = 998244353;
char buf[1 << 25] ,*p1 = buf ,*p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf ,1 ,1 << 21 ,stdin) ,p1 == p2) ? EOF : *p1++)
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
inline int fastpow(int a,int b) {
int r = 1;
while(b) {
if(b & 1) r = 1ll * r * a % p;
a = 1ll * a * a % p;
b >>= 1;
}
return r;
}
int n,a[N],f[M];
int main() {
n = read();
int A = 0;
for(int i = 1;i <= n;i++) a[i] = read(), A += a[i];
f[0] = f[1] = 0;
for(int x = 1;x < A;x++) {
int g = 1ll * x * (n - 1) % p * fastpow(A - x,p - 2) % p;
f[x + 1] = (f[x + 1] + 1ll * f[x] * (g + 1)) % p;
f[x + 1] = (f[x + 1] + 1ll * (1 - f[x - 1] + p) * g) % p;
}
int ans = f[A];
for(int i = 1;i <= n;i++) ans = (ans - f[a[i]] + p) % p;
std::printf("%d\n",ans);
return 0;
}
```
### 歌唱王国
这个经典 PGF 问题也具有停时的形式。
不妨暂时离开势能函数的形式，再来分析一下（当然形式化地构造函数自然是可行的）。
对于一个赌场，我们首先明确它在期望下是不赚不赔的。将代价（钱币）分配到每个赌徒身上，自然需要使每个人期望也是不赚不赔的。
那么，确定一个停时条件，这家赌场的老板会在达成条件后立刻终止所有活动。
此时想要分析赌场的期望收益，显然，就是需要满足停时定理：如果满足，那么期望收益为 $0$。
我们在此时若能够得知赌徒们的资产代数和为常量，且每天进入赌场的钱币数都是 $1$——那么，这个资产和就是期望停时。
感觉这个描述不如直接势能函数？哈哈，其实唯一略有不同的一步就是将期望不变的鞅拆成了若干个鞅的总和罢了。
代入这个问题，怎么分析呢？
假设赌局是这样进行的——每天有一个新的赌徒进入赌场，带来了 $1$ 个钱币。
因为我们想要从终止条件（唱出字符串恰是 $a_1\cdots a_m$）对应到一个唯一的赌徒收益情况，所以必然要有所联系。
某个拥有 $x$ 钱币的赌徒在进入赌场的第 $i$ 天，首先会将所有 $x$ 钱币赌上当天唱出的是 $a_i$，失败则失去所有钱币，成功则会得到 $(n-1)x$ 的钱币。
显然这样是公平的。
在终止时，很容易发现，只有还剩 $x$ 天入场的所有赌徒没有失去所有钱币，其中 $x$ 还要满足是 $a$ 的 border；他的资产是 $n^x$。
这些赌徒带走了所有钱币，这些钱币期望下是所有赌徒带来的钱币数。
根据结论，停时就是 $\sum_{x\in \mathrm{Border}(a)}n^x$。
至于停时定理，后两种情况好像不满足，因为是指数增长的。但是再看细想一下，发现变量有明确上界 $n^m$，因为至多从头猜对到尾，那么若干个变量之和就对于时间呈线性了。
期望有限？......题目是这样保证的，那么就是对的了。应该能证，就是一个收敛问题。