鞅与停时 - 一种特别的概率论问题

讨论一个有趣的概率问题：

[P3334 ZJOI2013] 抛硬币 - 洛谷

实际上是一个猴子打字问题，考虑一直无规律随即打字的猴子，键盘上只有A-Z一共26个字母，对于一个特定的字符串 $S$ ： ABCABCAB ，能否在有限的打字次数后精确得到这个字符串。

所需的打字次数的期望是有限的，但是打字次数是呈指数增长的。

期望次数是 $26^8+26^5+26^2$ （与前后缀相同 (border) 的长度有关系）

一个巧妙的证明可以用 停时与鞅的性质 来完成。

首先介绍停时的概念：停时，通俗而言，一个事件停止的时间，并且这个事件停止的时间只依赖于停止之前的所有状态。形式上，停时是一个随机变量 $\tau$，指的是对于任意的时间 $t\in I$ ，满足 { τ ≤ t } ∈ F t \{\tau\leq t\} \in F_t {τ≤t}∈Ft​ ，即对于任意时间 $t$ ，任意在 $t$ 之前停止的事件 { τ ≤ t } \{\tau \leq t\} {τ≤t} 只依赖于 $t$ 之前的状态（$F_t$ 即为在 $t$ 之前发生的所有事件的集合，也就是所有 $t$ 之前发生的状态）。

用 $T$ 表示猴子得到目标字符串所需要的时间。

例如字符串一匹配完我们就停止，那么这个事件的停止时间只依赖于停止之前的所有状态（所打的字符），而不依赖于停止之后的所有状态（还没有打的字符），那么就说明这个停止时间 $\tau$ 是一个停时 ($\text{stopping time/optinal time}$) 。

停时具有很好的性质，利用可选停止定理来得到停时的期望，具体是构造一个公平赌博。

假设存在无数个赌徒，当猴子每打出一个字符前的一瞬间，一个赌徒进场并投注 $1$ 元给 $S_1$ ，假如中了就翻 26 倍，投给 $S_2$ … 直到字符串完全匹配为止或者出现失配情况。并且我们假设赌场在遇到目标字符串马上关闭赌场，这个时间为 $T$ ，显然 $T$ 是一个停时。

可以发现，$T$ 时刻赌徒们的带入赌资一共为 $T$ 元，带出的钱一共是 $26^8+26^5+26^2$ 。

为什么？因为一共只有三个人能赢钱出去，其中有一个人大赢，另外两个人赢到一半赌场就关闭了，（注意这个长字符串的后缀是特定字符串 $S$，所以只有特定字符串中前后缀相同的长度可以赢钱，其他人都是输光走人）

由于是公平赌场，当这个 $T$ 是停时的时候，可以用鞅的性质和可选停止定理来证明，带入赌资的期望和带出的钱的期望是相等的。也就是 $T$ 的期望是 $26^8+26^5+26^2$ 。具体可以参考 鞅 。

那么我们也很容易可以完成类似的题目，只要产生字符的概率是独立的，且产生相同字符的概率是相等的，就可以用所有 $\text{border}$ 的概率积的倒数之和来算出产生该字符串的期望。