鞅
一些定义：
随机过程：依赖于参数的一组随机变量的全体，参数通常是时间。即假设 TTT 是指标集，且对于任意 t∈Tt\in Tt∈T，XtX_tXt 都是一随机变量，那么我们就可以称 {Xt∣t∈T}\{X_t|t\in T\}{Xt∣t∈T} 为一随机过程。条件概率：P(A∣B)P(A|B)P(A∣B)，表示事件 AAA 在事件 BBB 发生的条件下发生的概率。独立同分布：对于随机变量 X1,⋯ ,XnX_1,\cdots,X_nX1,⋯,Xn，若它们服从同一分布，并且互相独立，就称这些变量独立同分布。Var(X)Var(X)Var(X)：为随机变量 XXX 的方差，等于 E((X−E(X))2)E((X-E(X))^2)E((X−E(X))2)，展开后也等于 E(X2)−E(X)2E(X^2)-E(X)^2E(X2)−E(X)2。
接下来介绍鞅的定义，一种最基础的鞅的定义是：
称离散随机过程 {X0,X1,⋯ }\{X_0,X_1,\cdots\}{X0,X1,⋯} 是鞅，若对于任意的 nnn 都满足：
E(∣Xn∣)<∞E(|X_n|)<\inftyE(∣Xn∣)<∞。
E(Xn+1∣Xn,⋯ ,X0)=XnE(X_{n+1}|X_n,\cdots,X_0)=X_nE(Xn+1∣Xn,⋯,X0)=Xn。
这里 Xn,⋯ ,X0X_n,\cdots,X_0Xn,⋯,X0 作为条件概率里的条件，意思是假设随机变量 Xn,⋯ ,X0X_n,\cdots,X_0Xn,⋯,X0 已经确定了。即其等价于：∀x0,x1,⋯ ,xn,E(Xn+1∣Xn=xn,⋯ ,X0=x0)=Xn\forall x_0,x_1,\cdots,x_n,E(X_{n+1}|X_n=x_{n},\cdots,X_0=x_0)=X_n∀x0,x1,⋯,xn,E(Xn+1∣Xn=xn,⋯,X0=x0)=Xn。
一个扩展一点的定义：
称离散随机过程 {Y0,Y1,⋯ }\{Y_0,Y_1,\cdots\}{Y0,Y1,⋯} 关于随机过程 {X0,X1,⋯ }\{X_0,X_1,\cdots\}{X0,X1,⋯} 是鞅，若对于任意的 nnn 都满足：
E(∣Yn∣)<∞E(|Y_n|)<\inftyE(∣Yn∣)<∞。E(Yn+1∣Xn,⋯ ,X0)=YnE(Y_{n+1}|X_n,\cdots,X_0)=Y_nE(Yn+1∣Xn,⋯,X0)=Yn。
注意，第二个条件意味着 YnY_nYn 仅可能与 Xn,⋯ ,X0X_n,\cdots,X_0Xn,⋯,X0 有关，即在 Xn,⋯ ,X0X_n,\cdots,X_0Xn,⋯,X0 确定的情况下，YnY_nYn 也是确定的。
观察鞅的定义，我们可以得到这么一个结论：假设 YnY_nYn 是关于 XnX_nXn 的鞅，那么 ∀t,E(Yt)=E(Y0)\forall t,E(Y_t)=E(Y_0)∀t,E(Yt)=E(Y0)。
但注意这个结论并不和鞅定义中第二个条件等价，鞅定义中的第二个条件会比这个结论更加严格。
除此之外还有上鞅和下鞅：如果鞅的第二个条件中的符号变为 $\leq $ 则称其为上鞅；如果变为 ≥\geq≥，则称其为下鞅。注意这和 “上”、“下” 的直觉相反。
一道例题：
考虑一个简单的随机游走过程，即 Sn=∑k=1nXkS_n=\sum_{k=1}^nX_kSn=∑k=1nXk，且 P(Xi=1)=P(Xi=−1)=12P(X_i=1)=P(X_i=-1)=\frac{1}{2}P(Xi=1)=P(Xi=−1)=21。
求证：SnS_nSn 是一个关于 XnX_nXn 的鞅。
证明：第一个条件：E(∣Sn∣)≤n<∞E(|S_n|)\leq n<\inftyE(∣Sn∣)≤n<∞。
第二个条件：E(Sn+1−Sn∣Xn,⋯ ,X0)=E(Xn+1∣Xn,⋯ ,X0)=E(Xn+1)=0E(S_{n+1}-S_n|X_n,\cdots,X_0)=E(X_{n+1}|X_n,\cdots,X_0)=E(X_{n+1})=0E(Sn+1−Sn∣Xn,⋯,X0)=E(Xn+1∣Xn,⋯,X0)=E(Xn+1)=0。
求证：Yn=Sn2−nY_n=S_n^2-nYn=Sn2−n 是一个关于 XnX_nXn 的鞅。
证明：第一个条件：E(∣Sn2−n∣)≤E(Sn2)≤n2<∞E(|S_n^2-n|)\leq E(S_n^2)\leq n^2<\inftyE(∣Sn2−n∣)≤E(Sn2)≤n2<∞。第二个条件：
E(Yn+1−Yn∣Xn,⋯ ,X0)=E((Sn+12−(n+1))−(Sn2−n)∣Xn,⋯ ,X0)=E(Sn+12−Sn2−1∣Xn,⋯ ,X0)=12((Sn+1)2+(Sn−1)2)−Sn2−1=0
\begin{aligned}
&E(Y_{n+1}-Y_{n}|X_n,\cdots,X_0)\\
=&E((S_{n+1}^2-(n+1))-(S_n^2-n)|X_n,\cdots,X_0)\\
=&E(S_{n+1}^2-S_n^2-1|X_n,\cdots,X_0)\\
=&\tfrac{1}{2}((S_n+1)^2+(S_n-1)^2)-S_n^2-1\\
=&0
\end{aligned}
====E(Yn+1−Yn∣Xn,⋯,X0)E((Sn+12−(n+1))−(Sn2−n)∣Xn,⋯,X0)E(Sn+12−Sn2−1∣Xn,⋯,X0)21((Sn+1)2+(Sn−1)2)−Sn2−10
鞅的停时定理
一些定义：
几乎一定：一个事件 AAA 几乎一定会发生当且仅当事件 AAA 发生的概率为 111。即 AAA 不发生的情况集合可能是非空的，但它们对应的概率为 000。在样本空间有限时，“几乎一定” 和 “一定” 通常没有区别。但在样本空间无限时，这种区别变得非常重要，因为无限集可以有出现概率为 000 的非空子集。
例子：在 [0,1][0,1][0,1] 中任选一个实数，选出的数几乎一定大于 000。
下面可能还要注意 “趋近于” 和 “等于” 的区别：比如 000 乘任何数一定是 000（注意 ∞\infty∞ 不是 “数”），但一个趋近于 000 的数乘上一个趋近于 ∞\infty∞ 的数我们不知道它是什么。
停时：关于随机过程 {X0,X1,⋯ }\{X_0,X_1,\cdots\}{X0,X1,⋯} 的停时是一个非负的随机变量 TTT（可能为 ∞\infty∞），满足对于任意的 nnn，[n=T][n=T][n=T] 的取值仅与 X0,⋯ ,XnX_0,\cdots,X_nX0,⋯,Xn 有关。直观地说，对于任意的时间 nnn，你可以仅通过 X0,⋯ ,XnX_0,\cdots,X_nX0,⋯,Xn 判断 T,nT,nT,n 的大小关系（当然若 T≤nT\leq nT≤n，你也可以得到 TTT 的具体取值）。
带停时的随机过程：对于随机过程 {X0,X1,⋯ ,}\{X_0,X_1,\cdots,\}{X0,X1,⋯,}，设其停时为 TTT，定义该随机过程所对应的带停时的随机过程 {Xˉ0,Xˉ1,⋯ }\{\bar X_0,\bar X_1,\cdots\}{Xˉ0,Xˉ1,⋯}：
Xˉn={Xn,n≤TXT,n>T
\bar X_n=
\begin{cases}
X_n,&n\leq T\\
X_T,&n>T
\end{cases}
Xˉn={Xn,XT,n≤Tn>T
当然，一些文章中可能会直接用 Xmin(n,T)X_{\min(n,T)}Xmin(n,T) 代替 Xˉn\bar X_nXˉn。
直观地说，{Xˉ0,Xˉ1,⋯ }\{\bar X_0,\bar X_1,\cdots\}{Xˉ0,Xˉ1,⋯} 就是把 {X0,X1,⋯ }\{X_0,X_1,\cdots\}{X0,X1,⋯} 改成在停时之后维持不变的结果。
注意停时 TTT 只是一个关于 {X0,X1,⋯ ,}\{X_0,X_1,\cdots,\}{X0,X1,⋯,} 的函数，并不是说一个随机过程有停时它就是带停时的。
我们可以证明某个鞅带停时后也是一个鞅：
引理 1：设 YnY_nYn 是一个关于 XnX_nXn 的鞅，那么 Yˉn\bar Y_nYˉn 也是一个关于 XnX_nXn 的鞅。
证明：我们只需要证明 E(Yˉn+1∣Xn,⋯ ,X0)=YˉnE(\bar Y_{n+1}|X_n,\cdots,X_0)=\bar Y_nE(Yˉn+1∣Xn,⋯,X0)=Yˉn 即可。
注意 Xn,⋯ ,X0X_n,\cdots,X_0Xn,⋯,X0 是已知的，所以我们可以得到 T,nT,nT,n 的大小关系：
若 T≤nT\leq nT≤n，则 Yˉn+1=Yˉn\bar Y_{n+1}=\bar Y_nYˉn+1=Yˉn。若 T>nT>nT>n，则 E(Yˉn+1∣Xn,⋯ ,X0)=E(Yn+1∣Xn,⋯ ,X0)=Yn=YˉnE(\bar Y_{n+1}|X_n,\cdots,X_0)=E(Y_{n+1}|X_n,\cdots,X_0)=Y_n=\bar Y_{n}E(Yˉn+1∣Xn,⋯,X0)=E(Yn+1∣Xn,⋯,X0)=Yn=Yˉn。
直观地说，对于那些未到停时的过程它们原来就是期望不变的，对于那些已经到停时的过程由于我们已经钦定它们不变了，所以它们也是期望不变的。
推论：⋯=E(Yˉ1)=E(Yˉ0)=E(Y0)=E(Y1)=⋯\cdots=E(\bar Y_1) =E(\bar Y_0)=E(Y_0)=E(Y_1)=\cdots⋯=E(Yˉ1)=E(Yˉ0)=E(Y0)=E(Y1)=⋯。直观上也很容易解释。
接下来介绍鞅的停时定理：
设 {Y0,Y1,⋯ }\{Y_0,Y_1,\cdots\}{Y0,Y1,⋯} 是一个鞅，TTT 是其停时，且 TTT 几乎一定有限（P(T<∞)=1P(T<\infty)=1P(T<∞)=1），若有下列条件之一成立，则有 E(YT)=E(Y0)E(Y_T)=E(Y_0)E(YT)=E(Y0)：
TTT 几乎一定有界，即存在一个常数 KKK 使得 P(T≤K)=1P(T\leq K)=1P(T≤K)=1。
证明：
E(YT)=P(T≤K)E(YT∣T≤K)+P(T>K)E(YT∣T>k)=E(YT∣T≤K)=E(YˉK)=E(Y0)：
\begin{aligned}
E(Y_T)&=P(T\leq K)E(Y_T|T\leq K)+P(T>K)E(Y_T|T>k)\\
&=E(Y_T|T\leq K)\\
&=E(\bar Y_K)\\
&=E(Y_0)
\end{aligned}：
E(YT)=P(T≤K)E(YT∣T≤K)+P(T>K)E(YT∣T>k)=E(YT∣T≤K)=E(YˉK)=E(Y0)：
一些帮助理解的例子：
数轴上从 000 开始向右游走，每次走长度 111 或长度 222，走到当前位置大于等于特定常数 SSS 为止。这个是 TTT 有界的例子。从 [0,1][0,1][0,1] 中每次随机选一个实数，直到选出非 000 数为止。这是 TTT 不有界但几乎一定有界的例子。每次抛一枚硬币，直到抛出反面位置。这是 TTT 不几乎一定有界的例子。因为对于任意的 KKK，P(T>K)=12KP(T>K)=\frac{1}{2^K}P(T>K)=2K1，而即使是 KKK 趋近于 ∞\infty∞ 时，P(T>K)P(T>K)P(T>K) 也只是趋近于 000，而不等于 000。
Yˉn\bar Y_nYˉn 几乎一定有界，即存在一个常数 KKK 使得 P(∣Yˉn∣≤K)=1P(|\bar Y_n|\leq K)=1P(∣Yˉn∣≤K)=1。
证明：
E(YT)=limn→∞P(T≤n)E(YT∣T≤n)+P(T>n)E(YT∣T>n)=limn→∞P(T≤n)E(Yˉn∣T≤n)+P(T>n)⋅O(1)=limn→∞P(T≤n)E(Yˉn∣T≤n)=limn→∞E(Yˉn)−P(T>n)E(Yˉn∣T>n)=limn→∞E(Yˉn)−P(T>n)⋅O(1)=limn→∞E(Yˉn)=E(Y0)
\begin{aligned}
E(Y_T)&=\lim_{n\to \infty}P(T\leq n)E(Y_T|T\leq n)+P(T>n)E(Y_T|T>n)\\
&=\lim_{n\to \infty}P(T\leq n)E(\bar Y_n|T\leq n)+P(T>n)\cdot O(1)\\
&=\lim_{n\to \infty}P(T\leq n)E(\bar Y_n|T\leq n)\\
&=\lim_{n\to \infty}E(\bar Y_n)-P(T>n)E(\bar Y_n|T>n)\\
&=\lim_{n\to \infty}E(\bar Y_n)-P(T>n)\cdot O(1)\\
&=\lim_{n\to \infty}E(\bar Y_n)\\
&=E(Y_0)
\end{aligned}
E(YT)=n→∞limP(T≤n)E(YT∣T≤n)+P(T>n)E(YT∣T>n)=n→∞limP(T≤n)E(Yˉn∣T≤n)+P(T>n)⋅O(1)=n→∞limP(T≤n)E(Yˉn∣T≤n)=n→∞limE(Yˉn)−P(T>n)E(Yˉn∣T>n)=n→∞limE(Yˉn)−P(T>n)⋅O(1)=n→∞limE(Yˉn)=E(Y0)
一些帮助理解的例子：
数轴上从 000 开始随机游走，每次等概率向左或向右移动 111，走到 −m-m−m 或 mmm 为止。那么第 nnn 步之后的位置 SnS_nSn 肯定有界 [−m,m][-m,m][−m,m]。
E(T)E(T)E(T) 有限。且 E(∣Yn+1−Yn∣)E(|Y_{n+1}-Y_n|)E(∣Yn+1−Yn∣) 几乎一定有界，即存在一个常数 KKK 使得 P(E(∣Yn+1−Yn∣)≤K)=1P(E(|Y_{n+1}-Y_n|)\leq K)=1P(E(∣Yn+1−Yn∣)≤K)=1。
证明：
limt→∞E(YT−Yt)=limt→∞P(T>t)E(YT−Yt∣T>t)=limt→∞∑i=t∞P(T>i)E(Yi+1−Yi∣T>i)≤limt→∞∑i=t∞P(T>i)K=Klimt→∞∑i=t∞P(T>i)=Klimt→∞∑i=t∞P(T=i)(i−t)≤Klimt→∞∑i=t∞P(T=i)i
\begin{aligned}
&\lim_{t\to \infty}E(Y_T-Y_t)\\
=&\lim_{t\to \infty}P(T>t)E(Y_T-Y_t|T>t)\\
=&\lim_{t\to \infty}\sum_{i=t}^{\infty}P(T>i)E(Y_{i+1}-Y_i|T>i)\\
\leq &\lim_{t\to \infty}\sum_{i=t}^{\infty}P(T>i)K\\
=&K\lim_{t\to\infty}\sum_{i=t}^{\infty}P(T>i)\\
=&K\lim_{t\to \infty}\sum_{i=t}^{\infty}P(T=i)(i-t)\\
\leq &K\lim_{t\to \infty}\sum_{i=t}^{\infty}P(T=i)i\\
\end{aligned}
==≤==≤t→∞limE(YT−Yt)t→∞limP(T>t)E(YT−Yt∣T>t)t→∞limi=t∑∞P(T>i)E(Yi+1−Yi∣T>i)t→∞limi=t∑∞P(T>i)KKt→∞limi=t∑∞P(T>i)Kt→∞limi=t∑∞P(T=i)(i−t)Kt→∞limi=t∑∞P(T=i)i
考虑设 Sn=∑i=0nP(T=i)iS_n=\sum_{i=0}^nP(T=i)iSn=∑i=0nP(T=i)i，显然数列 SnS_nSn 趋近于数 E(T)E(T)E(T)，那么 E(T)−SnE(T)-S_nE(T)−Sn 趋近于 000，所以上式等于 000。故：
E(YT)=limt→∞E(Yt)=E(Y0)
E(Y_T)=\lim_{t\to \infty}E(Y_t)=E(Y_0)
E(YT)=t→∞limE(Yt)=E(Y0)
一些帮助理解的例子：
首先注意前提条件中的 P(T<∞)=1P(T<\infty)=1P(T<∞)=1 并不代表着 E(T)<∞E(T)<\inftyE(T)<∞。比如我们这么构造停时为 iii 的概率：P(T=i)=pi=6π2⋅1i2P(T=i)=p_i=\frac{6}{\pi^2}\cdot \frac{1}{i^2}P(T=i)=pi=π26⋅i21，显然 ∑i≥0pi\sum_{i\geq 0}p_i∑i≥0pi 收敛于 111，所以 P(T<∞)=1P(T<\infty)=1P(T<∞)=1。但如果我们要求 E(T)=∑i≥0pii=6π2∑i≥01iE(T)=\sum_{i\geq 0}p_ii=\frac{6}{\pi^2}\sum_{i\geq 0}\frac{1}{i}E(T)=∑i≥0pii=π26∑i≥0i1，会发现它并不收敛，而是发散的。
讲一个应用的例子吧：
CF1349D Slime and Biscuits
题意：
有 nnn 个人，每个人拥有 AiA_iAi 块饼干。
每次随机将一块饼干等概率分给除了其所有者以外的人。
求第一次出现有一个人拥有所有饼干的所需的期望次数。
做法：
停时与 aaa 序列有关，我们考虑构造一个鞅，同时携带了 AAA 序列和时间这两个信息。
我们大胆地猜想，我们可以构造一个关于 AAA 序列的函数 F(A)F(A)F(A) 使得 Yt=F(At)+tY_t=F(A_t)+tYt=F(At)+t 为鞅。进一步的猜想是令 F(A)=∑i=1nf(ai)F(A)=\sum_{i=1}^nf(a_i)F(A)=∑i=1nf(ai)。
那么我们就需要满足：
E(Yt+1−Yt∣At)=0
E(Y_{t+1}-Y_t|A_t)=0
E(Yt+1−Yt∣At)=0
展开后得到：
1+∑i=1n(m−At,im⋅n−2n−1−1)f(At,i)+At,imf(At,i−1)+m−At,im⋅1n−1f(At,i+1)=0
1+\sum_{i=1}^n\left(\frac{m-A_{t,i}}{m}\cdot \frac{n-2}{n-1}-1\right)f(A_{t,i})+\frac{A_{t,i}}{m}f(A_{t,i}-1)+\frac{m-A_{t,i}}{m}\cdot \frac{1}{n-1}f(A_{t,i}+1)=0
1+i=1∑n(mm−At,i⋅n−1n−2−1)f(At,i)+mAt,if(At,i−1)+mm−At,i⋅n−11f(At,i+1)=0
一个技巧是把 111 拆到里面去：
∑i=1n(m−At,im⋅n−2n−1−1)f(At,i)+At,imf(At,i−1)+m−At,im⋅1n−1f(At,i+1)+At,im=0
\sum_{i=1}^n\left(\frac{m-A_{t,i}}{m}\cdot \frac{n-2}{n-1}-1\right)f(A_{t,i})+\frac{A_{t,i}}{m}f(A_{t,i}-1)+\frac{m-A_{t,i}}{m}\cdot \frac{1}{n-1}f(A_{t,i}+1)+\frac{A_{t,i}}{m}=0
i=1∑n(mm−At,i⋅n−1n−2−1)f(At,i)+mAt,if(At,i−1)+mm−At,i⋅n−11f(At,i+1)+mAt,i=0
注意到这个式子对于 AtA_tAt 为任意序列都成立，所以为了不失一般性，我们应该令：
(m−xm⋅n−2n−1−1)f(x)+xmf(x−1)+m−xm⋅1n−1f(x+1)+xm=0
\left(\frac{m-x}{m}\cdot \frac{n-2}{n-1}-1\right)f(x)+\frac{x}{m}f(x-1)+\frac{m-x}{m}\cdot \frac{1}{n-1}f(x+1)+\frac{x}{m}=0
(mm−x⋅n−1n−2−1)f(x)+mxf(x−1)+mm−x⋅n−11f(x+1)+mx=0
对于任意的 x∈[0,m]x\in[0,m]x∈[0,m]。
解出 fff 即可，可以做到 O(m)O(m)O(m)。那么 E(T)=E(F(AT)+T)−E(F(AT))=E(YT)−E(F(AT))=E(Y0)−E(F(AT))E(T)=E(F(A_T)+T)-E(F(A_T))=E(Y_T)-E(F(A_T))=E(Y_0)-E(F(A_T))E(T)=E(F(AT)+T)−E(F(AT))=E(YT)−E(F(AT))=E(Y0)−E(F(AT)).
至于为什么这个鞅能用鞅的停时定理，我们可以发现它满足 E(∣Yt+1−Yt∣)E(|Y_{t+1}-Y_t|)E(∣Yt+1−Yt∣) 有界，但 E(T)<∞E(T)<\inftyE(T)<∞ 这个我不会证。（但既然题目都让你求它了那它肯定就是有限的）