P4548 的直观理解的通俗严格化
WYXkk
·
·
题解
在这篇题解内，我提到了这里的情景“事实上可以严格化”。这里我打算用比较通俗的方式（感觉 Union_of_Britain 的题解有点不讲人话）来说明如何将这个直观证明严格化。不过仍然有许多可省略的细节被略去了。
先简单回顾一下细节：假设有一个提供公平赌博的赌场，每秒会来一个带着 1 元的新赌徒，赌徒会连续全部押注，赌从他来的那一刻起正好能够连续唱出给定字符串，在此之后就不再参与押注。
以下记字符集大小为 c，字符串长度为 l。
停时
一列不断加细的样本空间的一个停时 T，指的是，细分到第 n 个样本空间后，一定可以完整检查 T=n 是否成立。
比如你投硬币，检查何时第一次出现“正正反”的连续子串，则第一次出现的时间 T 就是一个停时。
鞅
一列不断加细的样本空间的一个鞅 \{X_n\}，指的是，第 n 个样本空间上有一个随机变量 X_n，且细分到第 n 个样本空间后，对于任意 m>n，X_m 的期望都等于 X_n 的已确定值，那么这一列随机变量是一个鞅。
比如你还是投硬币，设正面加 1 分反面扣 1 分，令 X_n 为第 n 轮时的得分，那么 \{X_n\} 是一个鞅。
应用定义
本题中唱出的无限字符串可以用来逐个细分样本空间。
第一次出现需求的字符串的时间 T 当然是一个停时。
对于第 k 个赌徒，设他在第 n 轮结束时拥有 W_n^{(k)} 元。容易验证，\{W_n^{(k)}\} 是一个鞅。
给一个鞅加一个常数，以及对几个鞅进行求和，得到的显然还是一个鞅。那么，M_n=\sum\limits_{k}(W_n^{(k)}-1) 是一个鞅。它的含义是所有赌徒的总利润。
## 可选停止定理
可选停止定理有几个不同的条件。下面验证以下条件：
- 停时的期望是有限的，且鞅中每一项与前一项的差的期望都有限
前半句：$T$ 至少比每 $l$ 轮再检查一次要好，这样的话每次检查都是独立的 $c^{-l}$ 概率，此时的期望为有限的 $lc^l$，所以 $T$ 的期望也是有限的。
后半句：最新的结果只会影响最近的 $l$ 个赌徒的资产，而单个赌徒的资产有上界 $c^l$ 和下界 $0$，因此每一步最多导致 $M_n$ 产生 $lc^l$ 的变化。
于是，应用可选停止定理，即得 $E[M_T]=E[M_0]$。
这也就是说 $\sum\limits_{a[1,k]=a[l+1-k,l]}c^k-E[T]=0$，所以 $E[T]=\sum\limits_{a[1,k]=a[l+1-k,l]}c^k$。
这就得到了本题需求的结论了。