10 离散鞅与首达问题
抛一枚公平硬币，正面赢 1 元，反面输 1 元。现在你已经知道前 20 次结果，问第 21 次之后的资金平均会是多少。答案很简单：条件期望等于当前资金。但这句话不代表下一步不会输，也不代表你可以通过聪明地挑选停手时刻把公平游戏变成稳赚游戏。
离散鞅正好把这种“在当前信息下没有条件平均优势”的直觉写成数学语言。本章从信息逐步增加的过程出发，解释条件期望为什么是公平性的核心；然后用停止时间描述“什么时候停手”，在有限边界的首达问题中得到命中概率和平均耗时。涉及停止定理的地方只使用受控、有限的例子，并把一般结论的边界明确标出来。
公平性必须相对于信息来谈
令 F_n 表示时刻 n 已经知道的全部信息。最基本的要求是信息随时间增加：
F_0⊆F_1⊆F_2⊆...。
一个随机变量 M_n 如果在时刻 n 的信息下已经可以确定，就说它适应于这组信息；直观上，观察者在第 n 步不需要偷看未来就能知道 M_n。若每个 M_n 可积，即 E[|M_n|]<∞，并且
E[M_{n+1}|F_n]=M_n，
那么过程 (M_n) 称为离散时间鞅。
等式的左边不是把下一步结果直接算出来，而是在已知 F_n 的条件下，对未来不确定性取平均。右边是当前值，所以鞅说的是：知道现在以后，下一步的条件平均没有系统性上升或下降。
以公平游戏为例，设每步增量 ξ_{n+1} 取 +1 和 -1，概率均为 1/2，且与过去独立。资金过程
M_n=M_0+ξ_1+...+ξ_n
满足
E[M_{n+1}|F_n]=E[M_n+ξ_{n+1}|F_n]=M_n+E[ξ_{n+1}]=M_n。
相邻两步之间的关键只是一行：未来增量与过去独立，且平均为零。若游戏的赢面依赖过去，或每次下注金额由过去改变，就需要重新计算条件期望，不能只因为“每一步看起来公平”就下结论。
鞅不是“每条轨迹都不变”，也不是“不会出现连续亏损”。它只约束条件平均。公平游戏完全可能先连续输很多次；鞅性质表达的是，在这些结果已经发生之后，下一步的平均增量仍为零。
两个离散鞅例子
对称随机游走
令 S_0=i，并令每一步以相同概率向左或向右移动一个单位。取 F_n 为前 n 步的全部信息，则 S_n 是鞅，因为
E[S_{n+1}|F_n]=S_n+E[ξ_{n+1}|F_n]=S_n。
这里 S_n 本身可以是位置、库存差额或账户余额。换一个视角，若每一步增量 ξ_{n+1} 的条件平均为 d 而不是 0，那么
S_n-nd
才可能是鞅。减去的 nd 被称为补偿项：它拿走了可预测的平均漂移，只留下条件平均为零的部分。
补偿后的计数过程
每个时段是否有顾客到达，用独立指标变量 I_k 表示，P(I_k=1)=p。累计到达数为
N_n=I_1+...+I_n。
每一步平均增加 p，所以 N_n 不是鞅；但
M_n=N_n-np
是鞅。验证时只需写
E[M_{n+1}|F_n]=E[N_n+I_{n+1}-(n+1)p|F_n]
=N_n-np+E[I_{n+1}]-p=M_n。
这个形式很有用：观察到的累计数减去按模型预期的累计数，形成一个没有可预测偏差的过程。它不表示每个样本都接近 np，而是表示每一步新增的“意外部分”在条件平均上为零。
停止时间：只看已经发生的事
“等到资金第一次达到 10 元就停”是一个自然的停手规则。把停止时刻记作 τ，它必须满足：对每个 n，事件 {τ≤n} 可以由 F_n 判断。换句话说，到第 n 步时，只使用已经看到的信息，就能知道是否已经停了。这样的 τ 称为相对于 (F_n) 的停止时间。
首次到达某个状态是停止时间。例如
τ={n≥0:S_n∈{0,N}} 的最小值
表示第一次碰到上下边界的时刻。因为到时刻 n 只需检查前 n 步是否已经碰到边界，所以它符合定义。
相反，设硬币游走，规定“如果第 2 步是正面就第 1 步停，否则第 2 步停”。在第 1 步结束时，你还不知道第 2 步，所以“是否在第 1 步前已经决定停下”不能由当时信息判断。这不是停止时间。规则看起来只多看了一步，却已经把未来信息偷偷放进了停手决定。
为了在固定时刻使用鞅的条件期望，常把过程截断为
M_{n∧τ}，其中 n∧τ=min(n,τ)。
在每一步，如果还没有停，就按鞅规则走一步；如果已经停，就保持原值。对有界停止时间，或者对有限状态、有限边界中先截断再取极限的受控情形，可以得到
E[M_{n∧τ}]=E[M_0]。
这不是一句“任何时候随便停，平均值都不变”的通行证。它背后需要可积性、停止规则和极限交换等条件；一般停止定理的完整证明超出本章范围。我们只在有限边界的例子里逐项核对这些条件。
用鞅求首达概率
考虑对称随机游走 S_n，从 S_0=i 出发，其中 0<i<N。游走每步向左或向右移动一个单位，到达 0 或 N 就停止。令 τ 是首次到达 {0,N} 的时刻，记
p_i=P_i(S_τ=N)。
我们要找的是先到上边界的概率，而不是某一条路径会怎么走。选择 S_n 作为鞅，是因为在停止时它只剩两个可能值：0 或 N。这种“停下之后变量取很少几个值”的结构，正是方法选择的理由。
n 截断停止时间，写成 E_i[S_{n∧τ}]=i。在有限区间内，路径不会逃到边界之外，且截断变量有界，所以可以在这个受控范围使用鞅的公平性。τ 以概率 1 发生；让 n 增大后，S_{n∧τ} 走到停止时就是 S_τ。于是得到 E_i[S_τ]=i。这里使用的是有限状态边界带来的受控极限，不把它推广成任意停止时间的结论。S_τ=N 的概率是 p_i，S_τ=0 的概率是 1-p_i，所以 E_i[S_τ]=N p_i+0(1-p_i)=Np_i。i，得到 p_i=i/N。检查边界也合理：从 0 出发命中 N 的概率是 0，从 N 出发则是 1；初始位置越靠近 N，命中 N 的概率越大。例如 N=10,i=3 时，先到 10 的概率是 3/10。这不是说每条路径有 30% 的“中间状态”，而是许多次独立重复实验中，先触碰上边界的比例趋近于 0.3。
同一个问题还可以问平均停多久
概率 p_i 只告诉我们先碰哪一边。若想知道平均需要多少步，单独使用 S_n 不够，因为 S_τ 只记录终点，不记录路径长度。一个自然的候选是平方修正后的过程
Q_n=S_n^2-n。
验证它是鞅。因为下一步增量 ξ_{n+1} 取 ±1，有
S_{n+1}^2=(S_n+ξ_{n+1})^2=S_n^2+2S_nξ_{n+1}+1。
在 F_n 下取条件期望，E[ξ_{n+1}|F_n]=0，于是
E[S_{n+1}^2-(n+1)|F_n]=S_n^2-n。
在同一个有限边界首达问题中使用截断与受控极限，可得
E_i[S_τ^2-τ]=i^2。
停下时 S_τ 只有 0 和 N 两种值，所以 E_i[S_τ^2]=N^2p_i=N^2(i/N)=Ni。代回即得
E_i[τ]=Ni-i^2=i(N-i)。
例如 N=10,i=3，平均停止时间为 3×7=21 步。这个结果的形状也值得检查：从边界出发是 0 步；从中间出发通常要走得更久；关于中点 N/2 对称。对大的 N，中间位置的平均停留时间达到约 N^2/4，说明首达问题的时间尺度是平方级，而不是线性级。
有偏游走的一个方法提示
若向右概率为 p、向左概率为 q=1-p，且 p≠q，位置 S_n 不再是鞅，因为每步平均增量为 p-q。这时选择 r=q/p，考察
M_n=r^{S_n}。
给定当前位置 s，下一步的条件平均为
p r^{s+1}+q r^{s-1}=r^s(pr+q/r)=r^s(q+p)=r^s。
因此它是鞅。用同样的有限边界首达思路，可以得到
P_i(S_τ=N)=\frac{1-(q/p)^i}{1-(q/p)^N}。
这里的重点是方法选择：有漂移时，不要机械使用位置本身；寻找一个使“一步条件平均保持不变”的变换。令 p 趋近 1/2 时，这个表达式连续地回到 i/N 的对称情形，但极限化简需要单独处理，不能在 p=q 时直接代入分母为零的式子。
公平性的边界
鞅方法很有力量，也很容易被用过头。
其一，停止时间必须不偷看未来。根据完整路径挑一个“最有利”的时刻，往往已经不是停止时间。
其二，停止后的变量必须能控制。即使 τ 以概率 1 有限，M_τ 的期望也未必能从 M_0 直接推出。对称随机游走从 0 出发，令 τ 为第一次到达 +1 的时刻。这个 τ 确实几乎处处有限，且 S_τ=1，所以 E[S_τ]=1，并不等于 S_0=0。问题在于这个停止时间的期望是无穷，停止前的负向路径没有统一的可积控制；把固定时刻的等式直接推到这个无界停止时刻是不合法的。
其三，鞅只表达条件平均公平，不保证方差小、不保证路径稳定，也不保证一个有限样本会显示出接近 0 的收益。若过程有向下的条件漂移，则对应的是超鞅；若有向上的条件漂移，则对应的是次鞅。判断时应回到条件期望，而不是凭一两条样本路径贴标签。
“我可以等到有利时刻再停，所以公平游戏一定能赚钱”是典型误读。必须同时检查停手规则是否只依赖过去、停止后的变量是否可积，以及是否具备足够的有界性或一致控制。缺少这些条件时，E[M_τ]=E[M_0] 可能根本没有资格写出来。
这个交互位置适合让你同时看许多条公平随机游走路径，逐步增加观察步数，比较“每一步条件平均为零”和“单条路径上下波动”之间的区别。
第二个交互位置适合调整起点、上下边界和左右概率，观察首达概率及平均停留时间。改变参数后，先用 i/N 或 i(N-i) 做对称情形的预测，再判断有偏情形为什么需要换鞅。
练习
题 1（巩固）。 设 I_1,I_2,... 独立，P(I_k=1)=0.4，N_n=I_1+...+I_n。证明 N_n-0.4n 是鞅，并说明 N_n 本身为什么不是鞅。
题 2（变式）。 对称随机游走在 {0,8} 内从 i=2 出发，到达任一边界就停止。求先到 8 的概率和平均停止步数。
题 3（迁移）。 某计数过程每步独立以概率 p 增加 1，否则保持不变。写出一个自然的鞅，并解释它表示什么。
题 4（边界判断）。 对称随机游走从 0 出发，令 τ 为第一次到达 +1 的时刻。有人写下 E[S_τ]=E[S_0]=0。指出这一步的问题，不必证明 τ 几乎处处有限。
小结：把“公平”放回条件里
离散鞅的核心等式是 E[M_{n+1}|F_n]=M_n。它把当前信息固定下来，只平均未来尚未揭晓的部分。补偿项可以去掉可预测漂移，平方修正项可以把路径长度编码进过程；选对鞅后，有限边界的停止问题会变成对停止时取值的代数计算。
首达概率的计算依靠有限边界和可控停止。停止时间的直观边界同样重要：不能偷看未来，不能默认无界停止可以直接代入，不能把“每步平均公平”误说成“每条路径没有风险”。遇到新问题时，先写清 F_n 知道什么，再核对条件期望，最后才决定是否值得引入停止时间和鞅。