尝试学习应用鞅

对称简单随机游走，满足 \(E[S_n] = E[S_0]\)。

举例：站在数轴上，每个时刻有 1/2 的概率往左走 1 步，1/2 的概率往右走一步。设在 t 时刻位置是 \(S_t\)，那么 \(E[S_t] = \frac12 (E[S_{t-1}] + 1) + \frac12(E[S_{t-1}]-1) = E[S_{t-1}]\)

此时还有一个性质就是 \(S_n^2 - n\) 是鞅：\(E[S_n^2 - n] =\frac12 (E[S_{n-1}] + 1) ^2 + \frac12 (E[S_{n-1}] - 1)^2 - n = E[S_{n-1}^2 - (n-1)]\)

这东西能帮着算停时。\(E[S_0^2 - 0] = E[S_T^2 - T] \Rightarrow E[T] = E[S_T^2]\)

如果能刻画终态，就能得到停时的期望。

也有一些题目你刻画不了终态：

在数轴上，有 1/2 概率往左走 1 单位，有 1/2 概率往右走一单位。初始在 0，走 \(L\) 步。过程中走到 0 就重开，求期望走几步，能连续走 L 步都没有重开过。

这是对称简单随机游走。但是 E[S_n^2] 特别难刻画。就算使用卡特兰数计算出来最后落在绝对值为 \(k\) 的位置的概率，仍然需要计算组合式。被计算 \(P(\tau\ge x)\) 并对 x 求和的方法碾碎了