基于鞅与停时的概率问题：求解猴子随机打字先出现AB而非AA的概率
嘿，你的思路完全没问题！选T作为首次出现AA或AB的停时是正确的方向，核心就是构造一个合适的鞅来应用可选停时定理。我来一步步帮你捋清楚怎么操作：
首先，我们可以根据当前打字的最后一个字符状态来定义随机变量序列$X_n$：
- 定义两个状态：
- S₀：当前最后一个字符不是A（包括初始无字符的情况，或者最后一个是B/其他字母）
- S₁：当前最后一个字符是A
- 令$X_n$表示从第n步的状态出发，最终先打出AB的概率。
接下来验证$X_n$是鞅：对于任意n，给定前n步的信息$F_n$，$E[X_{n+1}|F_n] = X_n$——因为下一步的状态只依赖当前状态，且未来的期望概率等于当前状态的概率，完全符合鞅的无后效性要求。
然后我们用状态对应的概率来列方程：
- 设$p = X_0$（初始状态S₀下的目标概率，也就是我们要求的答案）
- 设$q$为状态S₁下先打出AB的概率
先分析状态S₁（最后一个字符是A）：
下一步打字有三种可能：
- 打出A（概率设为$a$）：直接出现AA，停时T触发，此时$X_T=0$
- 打出B（概率设为$b$）：直接出现AB，停时T触发，此时$X_T=1$
- 打出其他字母（概率$1-a-b$）：最后一个字符变成其他字母，回到状态S₀，此时$X_{n+1}=p$
根据鞅的性质，状态S₁的期望等于当前值，所以：
$$q = a \times 0 + b \times 1 + (1-a-b) \times p$$
再分析状态S₀（最后一个字符不是A）：
下一步打字的三种可能：
- 打出A（概率$a$）：进入状态S₁，此时$X_{n+1}=q$
- 打出B（概率$b$）：最后一个字符还是B，回到状态S₀，此时$X_{n+1}=p$
- 打出其他字母（概率$1-a-b$）：最后一个字符是其他字母，回到状态S₀，此时$X_{n+1}=p$
同样根据鞅的性质：
$$p = a \times q + (b + 1-a-b) \times p$$
化简这个式子会得到$p = q$（两边减去$(1-a)p$，剩下$a p = a q$，$a≠0$时可约掉）
把$p=q$代入状态S₁的方程：
$$p = b + (1-a-b)p$$
整理后得到：
$$p = \frac{b}{a + b}$$
如果我们假设猴子打每个字母的概率相等（比如26个字母，$a=b=\frac{1}{26}$），那$p=\frac{1}{2}$；如果只考虑A和B两个字母（$a=b=\frac{1}{2}$），结果也是$\frac{1}{2}$，这和直观推导的结果一致~
最后应用可选停时定理：因为停时T的期望是有限的（不管字母多少，总能在有限步内触发AA或AB的概率为1），所以$E[X_T] = E[X_0] = p$，而$X_T$就是我们要的指示变量（出现AB为1，AA为0），所以$E[X_T]$就是先出现AB的概率，也就是我们求的$p$。
备注：内容来源于stack exchange，提问作者Its me
