离散鞅引论

4.1 鞅的定义与例子

4.1.1 定义与基本性质

约定

1. 用 a.e. (almost everywhere) 表示命题几乎处处成立, 即不成立的点的测度为 0

2. 用 a.s. (almost sure) 表示命题以概率 1 成立.

定义 随机过程 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是 鞅, 如果对于 $\mathrm{\forall }n\ge 0$$\forall n \ge 0$, 有

1. $E\left|X_n\right|<\mathrm{\infty }$$E\vqty{X_n} < \infty$.

2. $E(X_{n+1}\mid X_0,X_1,\cdots ,X_n)=X_n$$E\pqty{X_{n+1} \mid X_0, X_1, \cdots, X_n} = X_n$, a.s..

定义 设有二过程 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 和 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$, 称前者关于后者是鞅, 如果

1. $E\left|X_n\right|<\mathrm{\infty }$$E\vqty{X_n} < \infty$.

2. $E(X_{n+1}\mid Y_0,Y_1,\cdots ,Y_n)=X_n$$E(X_{n + 1} \mid Y_0, Y_1, \cdots, Y_n) = X_n$, a.s..

备注

1. $X_n=E(X_{n+1}\mid Y_0,\cdots ,Y_n)$$X_n = E(X_{n+1} \mid Y_0, \cdots, Y_n)$ 作为 $(Y_0,\cdots ,Y_n)$$(Y_0, \cdots, Y_n)$ 的函数, 在给定 $(Y_0,\cdots ,Y_n)$$(Y_0, \cdots, Y_n)$ 时是定值, 因此 $E(X_n\mid Y_0,\cdots ,Y_n)=X_n$$E(X_n \mid Y_0, \cdots, Y_n) = X_n$.

2. 于是有 $E(X_{n+1})=E[E(X_{n+1}\mid Y_0,\cdots ,Y_n)]=E(X_n)=E(X_0)$$E(X_{n+1}) = E[E(X_{n+1} \mid Y_0, \cdots, Y_n)] = E(X_n) = E(X_0)$.

4.1.2 鞅的典型例子

例 1 (i.i.d. r.v. 之和) 设 $Y_0=0,\{Y_n,n\ge 1\}$$Y_0 = 0, \Bqty{Y_n, n \ge 1}$ 独立同分布, $E{Y}_n=0,E\left|Y_n\right|<\mathrm{\infty }$$EY_n = 0, E\vqty{Y_n} < \infty$, 令 $X_0=0$$X_0 = 0$, 记 $X_n={\displaystyle \sum _{i=1}^n{Y}_i}$$X_n = \insum Y_i$, 则 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是鞅.

例 2 (和的方差) 设 $Y_0=0,\{Y_n,n\ge 1\}$$Y_0 = 0, \Bqty{Y_n, n \ge 1}$ 独立同分布, $E{Y}_n=0,E{Y}_n^2={\sigma }^2$$EY_n = 0, EY_n^2 = \sigma^2$, $X_0=0,X_n={\left({\displaystyle \sum _{k=1}^n{Y}_k}\right)}^2-n{\sigma }^2$$X_0 = 0, X_n = \pqty{\knsum Y_k}^2 - n\sigma^2$, 则 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是鞅.

例 3 (一般和) 设 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 为随机序列, $Z_i=g_i(Y_0,\cdots ,Y_i)$$Z_i = g_i(Y_0, \cdots, Y_i)$, 函数 $f$$f$ 满足 $E[f(Z_k)]<\mathrm{\infty }$$E[f(Z_k)] < \infty$, 有界实函数 $a_k(y_0,\cdots ,y_{k-1})$$a_k(y_0, \cdots, y_{k-1})$ 满足 $\left|a_k\right|\le A_k$$\vqty{a_k} \le A_k$, 约定 $E[f(Z_0)\mid Y_{-1}]=E[f(Z_0)]$$E[f(Z_0) \mid Y_{-1}] = E[f(Z_0)]$, 则

关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是鞅.

例 4 (马氏链导出的鞅)

例 5 (转移概率特征向量导出的鞅)

例 6 (分支过程构成的鞅)

例 7 (Wald 鞅)

例 8 (似然比构成的鞅)

例 9 (Doob 鞅过程)

例 10 (随机 Radon-Nikodym 导数构成的鞅)

4.2 上下鞅与分解定理

4.2.1 定义与例子

约定

1. $x^{-}=min(x,0)$$x^- = \min(x, 0)$.

2. $x^{+}=max(x,0)$$x^+ = \max(x, 0)$.

定义 若随机过程 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 和 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 满足

1. $E(X_n^{-})>-\mathrm{\infty }$$E(X_n^-) > -\infty$.

2. $E(X_{n+1}\mid Y_0,\cdots ,Y_n)\le X_n$$E(X_{n + 1} \mid Y_0, \cdots, Y_n) \le X_n$.

3. $X_n$$X_n$ 是 $Y_0,\cdots ,Y_n$$Y_0, \cdots, Y_n$ 的函数.

则称 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是 上鞅.

定义 若随机过程 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 和 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 满足

1. $E(X_n^{+})<+\mathrm{\infty }$$E(X_n^+) < +\infty$.

2. $E(X_{n+1}\mid Y_0,\cdots ,Y_n)\ge X_n$$E(X_{n + 1} \mid Y_0, \cdots, Y_n) \ge X_n$.

3. $X_n$$X_n$ 是 $Y_0,\cdots ,Y_n$$Y_0, \cdots, Y_n$ 的函数.

则称 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是 下鞅.

备注 由于 $X_n$$X_n$ 是 $Y_0,\cdots ,Y_n$$Y_0, \cdots, Y_n$ 的函数, 对于上下鞅均有 $X_n=E(X_n\mid Y_0,\cdots ,Y_n)$$X_n = E(X_n \mid Y_0, \cdots, Y_n)$.

例 1 设 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是马氏链, $\mathit{P}=(p_{ij})$$\bm P = (p_{ij})$, $f$$f$ 是 $\mathit{P}$$\bm P$ 的有界 右超正则函数, 即

1. ${\displaystyle \sum _{j\in S}{p}_{ij}f(j)\le f(i)}$$\d\sum_{j \in S} p_{ij} f(j) \le f(i)$.

2. $|f(i)|\le M$$\vqty{f(i)} \le M$.

则 $\{X_n=f(Y_n),n\ge 0\}$$\Bqty{X_n = f(Y_n), n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是上鞅.

4.2.2 上下鞅的性质

引理 1 (Jensen 不等式) 若 $\varphi$$\phi$ 是下凸函数, $X$$X$ 是随机变量, 则

引理 2 如果 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是鞅, $\varphi$$\phi$ 是下凸函数, 且 $\mathrm{\forall }n\in \mathbb{N}:E[\varphi (X_n{)}^{+}]<\mathrm{\infty }$$\forall n \in \N\colon E[\phi(X_n)^+] < \infty$, 则 $\{\varphi (X_n),n\ge 0\}$$\Bqty{\phi(X_n), n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是一个下鞅.

推论 若 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是鞅, 且 $E(X_n^2)<\mathrm{\infty }$$E(X_n^2) < \infty$, 则 $\{\left|X_n\right|,n\ge 0\}$$\Bqty{\vqty{X_n}, n \ge 0}$ 与 $\{X_n^2,n\ge 0\}$$\Bqty{X_n^2, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是下鞅.

性质 1 若 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是 (上) 鞅, 则

性质 2 若 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是 (上) 鞅, 则对 $0\le k\le n$$0 \le k \le n$ 有

性质 3 若 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是 (上) 鞅, $g=g(Y_0,\cdots ,Y_n)\ge 0$$g = g(Y_0, \cdots, Y_n) \ge 0$, 则

4.2.3 上下鞅分解定理

定理 4.2.1 若 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是下鞅, 则唯一存在过程 $\{M_n,n\ge 1\}$$\Bqty{M_n, n \ge 1}$ 与 $\{Z_n,n\ge 1\}$$\Bqty{Z_n, n \ge 1}$, 使得

1. $\{M_n,n\ge 1\}$$\Bqty{M_n, n \ge 1}$ 关于 $\{Y_n,n\ge 1\}$$\Bqty{Y_n, n \ge 1}$ 是鞅.

2. $Z_n=Z_n(Y_1,\cdots ,Y_{n-1})$$Z_n = Z_n(Y_1, \cdots, Y_{n-1})$, 且 $Z_1=0,Z_n\le Z_{n+1},E{Z}_n<+\mathrm{\infty }$$Z_1 = 0, Z_n \le Z_{n + 1}, EZ_n < +\infty$.

3. $\mathrm{\forall }n\in {\mathbb{N}}^{+}:X_n=M_n+Z_n$$\forall n \in \N^+\colon X_n = M_n + Z_n\ $.

推论 若 $\{X_n,n\ge 1\}$$\Bqty{X_n, n \ge 1}$ 关于 $\{Y_n,n\ge 1\}$$\Bqty{Y_n, n \ge 1}$ 是上鞅, 则唯一存在过程 $\{M_n,n\ge 1\}$$\Bqty{M_n, n \ge 1}$ 与 $\{Z_n,n\ge 1\}$$\Bqty{Z_n, n \ge 1}$, 使得

1. $\{M_n,n\ge 1\}$$\Bqty{M_n, n \ge 1}$ 关于 $\{Y_n,n\ge 1\}$$\Bqty{Y_n, n \ge 1}$ 是鞅.

2. $Z_n=Z_n(Y_1,\cdots ,Y_{n-1})$$Z_n = Z_n(Y_1, \cdots, Y_{n-1})$, 且 $Z_1=0,Z_n\le Z_{n+1},E{Z}_n<+\mathrm{\infty }$$Z_1 = 0, Z_n \le Z_{n + 1}, EZ_n < +\infty$.

3. $\mathrm{\forall }n\in {\mathbb{N}}^{+}:X_n=M_n-Z_n$$\forall n \in \N^+\colon X_n = M_n - Z_n\ $.

4.2.4 序贯决策模型

定义 记状态空间 $S=\{1,2,\cdots ,p\}$$S = \Bqty{1, 2, \cdots, p}$ 有限, 行动集 (或 决策空间) $A=\{a,b,\cdots ,l\}$$A = \Bqty{a, b, \cdots, l}$ 有限, 每经单位时间观察即使的系统状态 $i$$i$, 然后从 $A$$A$ 中选取一个行动 $a$$a$, 并

1. 得到一个报酬 (或能量) $r(i,a)$$r(i, a)$.

2. 在现时段状态为 $i$$i$ 且采取行动为 $a$$a$ 的条件下, 系统下一时刻转移到状态 $j$$j$ 的概率为 $q(j\mid i,a)$$q(j \mid i, a)$.

于是该可控随机动态系统称为 序贯决策模型.

定义

1. $Y_k$$Y_k$ 和 ${\mathrm{\Delta }}_k$$\Delta_k$ 分别表示 $k$$k$ 时段系统的状态和采取的行动.

2. $h_{n-1}=\{i_0,a_0,i_1,a_1,\cdots ,i_{n-1},a_{n-1}\}$$h_{n - 1} = \Bqty{i_0, a_0, i_1, a_1, \cdots, i_{n-1}, a_{n-1}}$ 称为 $n-1$$n-1$ 之前的 历史.

3. $a_n={\pi }_n(h_{n-1},i_n)$$a_n = \pi_n(h_{n-1}, i_n)$, 其中 ${\pi }_n$$\pi_n$ 称为 $n$$n$ 时刻的 决策函数.

4. 决策函数序列 $\pi =\{{\pi }_0,{\pi }_1,\cdots ,{\pi }_{N-1}\}$$\pi = \Bqty{\pi_0, \pi_1, \cdots, \pi_{N - 1}}$ 称为一个 决策.

5. 期望总报酬 $V(\pi ,i)=E_{\pi }\left\{{\displaystyle \sum _{k=0}^{N-1}r(Y_k,{\mathrm{\Delta }}_k)\mid Y_0=i}\right\}$$V(\pi, i) = E_\pi \Bqty{\dsum_{k=0}^{N-1} r(Y_k, \Delta_k) \mid Y_0 = i}$.

6. 最优策略 ${\pi }^{\ast }:\mathrm{\forall }i\in S:V({\pi }^{\ast },i)=\underset{\pi }{max}V(\pi ,i)$$\pi^*\colon \forall i \in S\colon V(\pi^*, i) = \max_\pi V(\pi, i)$.

7. $\begin{array}{c}{V}_k(i)=\{\begin{array}{ll}0,& k=N,i\in S,\\ \underset{a\in A}{max}\{r(i,a)+{\displaystyle \sum _{j\in S}q(j\mid i,a)V_{k+1}(j)}\},& 1\le k<N,i\in S.\end{array}\end{array}$$V_k(i) = \begin{cases} 0, & k = N, i \in S, \\ \max\limits_{a \in A} \Bqty{ r(i, a) + \dsum_{j \in S} q(j \mid i, a) V_{k + 1}(j) }, & 1 \le k < N, i \in S. \end{cases}$

8. $X_n={\displaystyle \sum _{k=1}^n\{V_k(Y_k)-E[V_k(Y_k)\mid Y_0,{\mathrm{\Delta }}_0,\cdots ,Y_{k-1},{\mathrm{\Delta }}_{k-1}]\}}$$X_n = \knsum \Bqty{ V_k(Y_k) - E\bqty{ V_k(Y_k) \mid Y_0, \Delta_0, \cdots, Y_{k - 1}, \Delta_{k - 1} } }$.

问题 序贯决策模型的最优决策.

解

由 4.1.2 例 3 (一般和) 知 $\{X_n,n\ge 1\}$$\Bqty{X_n, n \ge 1}$ 关于 $\{(Y_n,{\mathrm{\Delta }}_n),n\ge 0\}$$\Bqty{(Y_n, \Delta_n), n \ge 0}$ 是鞅, 于是

并且

从而由马氏性得

根据此不等式, 于是有

即

令 $Y_0=i$$Y_0 = i$, 则有

若选取 $a_{k-1}^{\ast }\in A$$a_{k-1}^* \in A$, 使得 $a_{k-1}^{\ast }(i)={\pi }_{k-1}^{\ast }(i_0,a_0^{\ast },\cdots ,i_{k-1})$$a_{k-1}^*(i) = \pi_{k-1}^*(i_0, a_0^*, \cdots, i_{k-1})$ 满足上述第 7 点定义, 即

则 ${\pi }^{\ast }=\{{\pi }_0^{\ast },{\pi }_1^{\ast },\cdots ,{\pi }_{N-1}^{\ast }\}$$\pi^* = \Bqty{\pi_0^*, \pi_1^*, \cdots, \pi_{N-1}^*}$ 是最优策略.

4.3 停时与停时定理

4.3.1 严谨定义与例子

记号

1. $\sigma (X)$$\sigma(X)$ 为由 $X$$X$ 生成的事件 σ 域.

2. ${\mathcal{F}}_n=\sigma (Y_k,0\le k\le n)$$\cal F_n = \sigma(Y_k, 0 \le k \le n)$.

定义 设随机变量 $T\in \mathbb{N}\cap \{+\mathrm{\infty }\}$$T \in \N \cap \Bqty{+\infty}$, 随机序列 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$, 且 ${\mathcal{F}}_n=\sigma (Y_k,0\le k\le n)$$\cal F_n = \sigma(Y_k, 0 \le k \le n)$, 若对 $\mathrm{\forall }n\ge 0$$\forall n \ge 0$, 有 $\{T=n\}\in {\mathcal{F}}_n$$\Bqty{T = n} \in \cal F_n$, 则称 $T$$T$ 是 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 的 停时 (stopping time) (或马氏时间).

例子

• 对于随机过程 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$, 首达时间 $T=min\{n:Y_n\in A\}$$T = \min\Bqty{n : Y_n \in A}$ 是停时.

• 对于时齐 Poisson 过程 $\{N(t),t\ge 0\}$$\Bqty{N(t), t \ge 0}$,

  • $N(t)$$N(t)$ 关于 $\{S_n,n\ge 0\}$$\Bqty{S_n, n \ge 0}$ 不是停时.

  • $N(t)+1$$N(t) + 1$ 关于 $\{S_n,n\ge 0\}$$\Bqty{S_n, n \ge 0}$ 是停时.

4.3.2 鞅的期望与停时

引理 1 若 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 的 (上) 鞅, $T$$T$ 是关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 的停时, 则

引理 2 若 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 的 (上) 鞅, $T$$T$ 是关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 的停时, 则

引理 3 设随机变量 $X$$X$ 满足 $E\left|X\right|<\mathrm{\infty }$$E\vqty{X} < \infty$, $T$$T$ 是关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 的停时, 且 $P(T<\mathrm{\infty })=1$$P(T < \infty) = 1$, 则

定理 4.3.1 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是鞅, $T$$T$ 是停时, 若 $P\{T<\mathrm{\infty }\}=1$$P\Bqty{T < \infty} = 1$, 且 $E(\underset{n\ge 0}{sup}\left|X_{T\wedge n}\right|)<\mathrm{\infty }$$E(\sup\limits_{n \ge 0} \vqty{X_{T \and n}}) < \infty$, 则 $E{X}_T=E{X}_0$$EX_T = EX_0$.

推论 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是鞅, $T$$T$ 是停时, 且 $ET<\mathrm{\infty }$$ET < \infty$. 若

则 $E{X}_0=E{X}_T$$EX_0 = EX_T$.

4.3.3 停时定理与推论

定理 4.3.2 (停时定理) 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是鞅, $T$$T$ 是停时, 若

1. $P(T<\mathrm{\infty })=1$$P(T < \infty) = 1$.

2. $E\left|X_T\right|<\mathrm{\infty }$$E\vqty{X_T} < \infty$.

3. $\underset{n\to \mathrm{\infty }}{lim}E\left|X_n{I}_{\{T>n\}}\right|=0$$\nlim E\vqty{X_n I_\Bqty{T > n}} = 0$.

则 $E{X}_T=E{X}_0$$EX_T = EX_0$.

推论 1 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是鞅, $T$$T$ 是停时, 若

1. $P\{T<\mathrm{\infty }\}=1$$P\Bqty{T < \infty} = 1$.

2. $\mathrm{\exists }k<\mathrm{\infty },\mathrm{\forall }n\ge 0:E(X_{T\wedge n}^2)\le k$$\exist k < \infty, \forall n \ge 0\colon E(X^2_{T \and n}) \le k$.

则 $E{X}_T=E{X}_0$$EX_T = EX_0$.

推论 2 若

1. $Y_0=0$$Y_0 = 0$, $\{Y_k,k\ge 1\}$$\Bqty{Y_k, k \ge 1}$ 独立同分布.

2. $E{Y}_k=\mu ,D{Y}_k={\sigma }^2<\mathrm{\infty }$$EY_k = \mu, DY_k = \sigma^2 < \infty$.

3. $S_0=0,S_n={\displaystyle \sum _{k=1}^n{Y}_k,X_n=S_n-n\mu }$$S_0 = 0, S_n = \knsum Y_k, X_n = S_n - n \mu$.

4. $T$$T$ 为停时, $ET<\mathrm{\infty }$$ET < \infty$.

则 $E\left|X_T\right|<\mathrm{\infty }$$E\vqty{X_T} < \infty$, 且 $E{X}_T=E{S}_T-\mu ET=0$$EX_T = ES_T - \mu ET = 0$.

4.3.4 停时与随机游动

记号

1. $Y_0=0,\{Y_k,k\ge 1\}$$Y_0 = 0, \Bqty{Y_k, k \ge 1}$ 独立同分布, 且

   $P\{Y_k=1\}=p\ge 0$$P\Bqty{Y_k = 1} = p \ge 0$, $P\{Y_k=-1\}=q=1-p\ge 0$$P\Bqty{Y_k = -1} = q = 1 - p \ge 0$.

2. $X_0=0,X_n={\displaystyle \sum _{k=1}^n{Y}_k}$$X_0 = 0, X_n = \knsum Y_k$.

3. $T_{0j}=min\{n:X_0=0,X_n=j\}$$T_{0j} = \min\Bqty{n\colon X_0 = 0, X_n = j}$.

4. $T=min\{n:(X_n=a)\vee (X_n=b)\},b\in {\mathbb{N}}^{+},a\in \mathbb{Z}\mathrm{\setminus }\mathbb{N}$$T = \min\Bqty{n\colon (X_n = a) \or (X_n = b)}, b \in \N^+, a \in \Z \backslash \N$.

5. ${}_{b}T_a=min\{n:X_0=0,X_l\ne b,1\le l\le n-1,X_n=a\}$$\sideset{_b}{_a}{T} = \min\Bqty{n \colon X_0 = 0, X_l \ne b, 1 \le l \le n - 1, X_n = a}$.

6. $V_a=P\{{}_{b}T_a<\mathrm{\infty }\mid X_0=0\}$$V_a = P\Bqty{\sideset{_b}{_a}{T} < \infty \mid X_0 = 0}$ 表示从 0 出发先到达 $a$$a$ 的概率.

   于是 $P\{{}_{a}T_b<\mathrm{\infty }\mid X_0=0\}=1-V_a$$P\Bqty{\sideset{_a}{_b}T < \infty \mid X_0 = 0} = 1 - V_a$.

实例 设甲乙两人赌博, $\left|a\right|$$\vqty{a}$ 表示甲原有的资金 (注意 $a$$a$ 为负数), $Y_n$$Y_n$ 表示甲第 $n$$n$ 次得到的钱, $b$$b$ 表示乙原有的资金, $V_a$$V_a$ 表示甲先输光的概率.

情况 1 当 $p=q={\displaystyle \frac{1}{2}}$$p = q = \dfrac{1}{2}$ 时, 即公平赌博时,

1. 甲先输光的概率为 $V_a={\displaystyle \frac{b}{\left|a\right|+b}}$$V_a = \dfrac{b}{\vqty{a} + b}$,

2. 任何一方输光的平均时间为 $ET=\left|a\right|b$$ET = \vqty{a} b$.

情况 2 当 $\mu =p-q>0$$\mu = p - q > 0$ 时, 即不公平赌博时,

1. 甲先输光的概率为 $V_a={\displaystyle \frac{1-{\left(\frac{q}{p}\right)}^b}{{\left(\frac{q}{p}\right)}^a-{\left(\frac{q}{p}\right)}^b}}$$V_a = \dfrac{ 1 - \pqty{\cfrac{q}{p}}^b }{ \pqty{\cfrac{q}{p}}^a - \pqty{\cfrac{q}{p}}^b }$.

2. 任何一方输光的平均时间为 $ET={\displaystyle \frac{a-b+b{\left(\frac{q}{p}\right)}^a-a{\left(\frac{q}{p}\right)}^b}{(p-q)[{\left(\frac{q}{p}\right)}^a-{\left(\frac{q}{p}\right)}^b]}}$$ET = \dfrac{ a - b + b\pqty{\cfrac{q}{p}}^a - a\pqty{\cfrac{q}{p}}^b }{ (p - q) \bqty{ \pqty{\cfrac{q}{p}}^a - \pqty{\cfrac{q}{p}}^b } }$.

4.4 鞅收敛定理

4.4.1 上穿不等式

引理 1 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是下鞅, $S$$S$, $T$$T$ 关于 $\left\{Y_n\right\}$$\Bqty{Y_n}$ 是停时, 且 $0\le S\le T\le N$$0 \le S \le T \le N$, 则

定义 设 $\left\{X_n\right\}$$\Bqty{X_n}$ 是随机序列, 令

1. $V^{(n)}(a,b)(\omega )$$V^{(n)}(a, b)(\omega)$ 是 $\{X_0(\omega ),X_1(\omega ),\cdots ,X_n(\omega )\}$$\Bqty{X_0(\omega), X_1(\omega), \cdots, X_n(\omega)}$ 向上穿越 $(a,b)$$(a, b)$ 的次数.

2. 若干次首达 $(-\mathrm{\infty },a]$$\pbqty{-\infty, a}$ 和 $[b,+\mathrm{\infty })$$\bpqty{b, +\infty}$ 的时间为

3. $a^{+}\equiv a\vee 0\equiv max(a,0)$$a^+ \equiv a \or 0 \equiv \max(a, 0)$.

备注 $V^{(n)}(a,b)(\omega )=k\iff \mathrm{\exists }k\in {\mathbb{N}}^{+}:{\alpha }_{2k}\le n<{\alpha }_{2k+2}$$V^{(n)}(a, b)(\omega) = k \RLA \exist k \in \N^+ \colon \alpha_{2k} \le n < \alpha_{2k + 2}$.

引理 2 (上穿不等式) 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是下鞅, 则

推论 若 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 关于 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 是上鞅, ${\bar{V}}^{(n)}(a,b)$$\overline V^{(n)}(a, b)$ 是 $X_n$$X_n$ 下穿 $(a,b)$$(a, b)$ 的次数, 则

如果 $X_n\ge 0,0\le a<b$$X_n \ge 0, 0 \le a < b$, 则

4.4.2 鞅收敛定理

定理 4.4.1 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是一个下鞅, 且 $\underset{n}{sup}E\left|X_n\right|<\mathrm{\infty }$$\sup_n E\vqty{X_n} < \infty$, 则存在一随机变量 $X_{\mathrm{\infty }}$$X_\infty$, 使得 $\left\{X_n\right\}$$\Bqty{X_n}$ 以概率 1 收敛于 $X_{\mathrm{\infty }}$$X_\infty$, 即

且 $E\left|X_{\mathrm{\infty }}\right|<\mathrm{\infty }$$E\vqty{X_\infty} < \infty$.

4.4.3 最大值不等式

引理 1 (Kolmogorov 不等式) 设 $\left\{X_n\right\}$$\Bqty{X_n}$ 独立且 $\mathrm{\forall }i\in \mathbb{N}:E\left|X_i\right|<+\mathrm{\infty }$$\forall i \in \N \colon E\vqty{X_i} < +\infty$, 令 $S_n={\displaystyle \sum _{i=1}^n{X}_i}$$S_n = \insum X_i$, 则

证明

推论 1 (Chebyshev 不等式) 设 $E{X}^2<+\mathrm{\infty }$$EX^2 < +\infty$, 则

推论 2 (最大值不等式) 设 $\{Y_n,n\ge 0\}$$\Bqty{Y_n, n \ge 0}$ 独立同分布, 且 $E{Y}_i=0,E{Y}_i^2={\sigma }^2(i\ge 0)$$EY_i = 0, EY_i^2 = \sigma^2\ (i \ge 0)$, $X_0=0,X_n={\displaystyle \sum _{i=1}^n{Y}_i}$$X_0 = 0, X_n = \insum Y_i$, 则

4.4.4 另一收敛定理

引理 2 设 $\{X_n\ge 0,n\ge 0\}$$\Bqty{X_n \ge 0, n \ge 0}$ 是下鞅, 则

推论 1 (Markov 不等式) 设 $Y\ge 0$$Y \ge 0$, 则

推论 2 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是鞅, 则

定理 4.4.2 设 $\left\{X_n\right\}$$\Bqty{X_n}$ 关于 $\left\{Y_n\right\}$$\Bqty{Y_n}$ 是鞅, 且 $\mathrm{\exists }k,\mathrm{\forall }n\in \mathbb{N}:E{X}_n^2\le k<\mathrm{\infty }$$\exist k, \forall n \in \N\colon EX_n^2 \le k < \infty$, 则存在一有限随机变量 $X_{\mathrm{\infty }}$$X_\infty$, 使得

1. $P\{\underset{n\to \mathrm{\infty }}{lim}{X}_n=X_{\mathrm{\infty }}\}=1$$P\Bqty{ \nlim X_n = X_\infty } = 1$.

2. $\underset{n\to \mathrm{\infty }}{lim}E{|X_n-X_{\mathrm{\infty }}|}^2=0$$\nlim E\vqty{X_n - X_\infty}^2 = 0$.

3. $\mathrm{\forall }n\in \mathbb{N}:E{X}_n=E{X}_{\mathrm{\infty }}$$\forall n \in \N \colon EX_n = EX_\infty$.

证明 略.

4.5 连续参数鞅

定义 设 $\{X(t),t\ge 0\}$$\Bqty{X(t), t \ge 0}$ 是一随机过程, 记 ${\mathcal{F}}_t=\sigma (X(s),0\le s\le t)$$\cal F_t = \sigma(X(s), 0 \le s \le t)$, 若满足下述条件

1. $\mathrm{\forall }t\ge 0:E|X(t)|<\mathrm{\infty }$$\forall t \ge 0 \colon E\vqty{X(t)} < \infty$.

2. $\mathrm{\forall }s,t\ge 0:E[X(t+s)\mid {\mathcal{F}}_t]=X(t)$$\forall s, t \ge 0 \colon E\bqty{X(t + s) \mid \cal F_t} = X(t)$, a.s..

3. $\mathrm{\forall }t\ge 0:X(t)$$\forall t \ge 0 \colon X(t)$ 关于 $\mathcal{F}$$\cal F$ 是可测的. (参考笔记).

则过程 $\{X(t),t\ge 0\}$$\Bqty{X(t), t \ge 0}$ 称为 鞅.

定义 (离散化等价定义) 随机过程 $\{X(t),t\ge 0\}$$\Bqty{X(t), t \ge 0}$ 称为 鞅, 如果满足

1. $\mathrm{\forall }t\ge 0:E|X(t)|<\mathrm{\infty }$$\forall t \ge 0 \colon E\vqty{X(t)} < \infty$.

2. $\mathrm{\forall }0\le t_0<\cdots <t_{n+1}:E[X(t_{n+1})\mid X(t_1),\cdots ,X(t_n)]=X(t_n)$$\forall 0 \le t_0 < \cdots < t_{n + 1} \colon E\bqty{X(t_{n + 1}) \mid X(t_1), \cdots, X(t_n)} = X(t_n)$, a.s..

备注 连续参数的上下鞅类似定义.

定义 设随机序列 $\{X(t),t\ge 0\}$$\Bqty{X(t), t \ge 0}$ 和非负随机变量 $T$$T$, 记 ${\mathcal{F}}_t=\sigma (X(s),0\le s\le t)$$\cal F_t = \sigma(X(s), 0 \le s \le t)$, 若

则称 $T$$T$ 是 $\{X(t),t\ge 0\}$$\Bqty{X(t), t \ge 0}$ 的 停时.

定理 4.5.1 (停时定理) 设 $\{X(t),t\ge 0\}$$\Bqty{X(t), t \ge 0}$ 是鞅, $T$$T$ 是停时, 若

1. $P\{T<\mathrm{\infty }\}=1$$P\Bqty{T < \infty} = 1$.

2. $E\left(\underset{t\ge 0}{sup}\left|X(T\wedge t)\right|\right)<\mathrm{\infty }$$E\pqty{\sup_{t \ge 0} \vqty{X\pqty{T \and t}}} < \infty$.

则 $EX(T)=EX(0)$$EX(T) = EX(0)$.