概率论与数理统计 (Spring 2023)/OST and applications

From TCS Wiki
Jump to navigation Jump to search

可选停时定理 (OST)

可选停时定理 (Optional Stopping Theorem, OST),有事也被称为鞅停时定理 (Martingale Stopping Theorem)、可选抽样定理 (Optional Sampling Theorem) 等,是约瑟夫·杜布 (Joseph Doob) 发现的关于鞅的停时的刻画定理。

首先定义鞅 (martingale)。这是一类由公平赌博定义的随机过程。

定义(鞅)
[math]\displaystyle{ \{X_n:n\ge 0\} }[/math][math]\displaystyle{ \{Y_n:n\ge 0\} }[/math] 为离散时间随机过程(即随机变量序列)。若对于任意 [math]\displaystyle{ n\ge 0 }[/math] 都满足
  • [math]\displaystyle{ \mathbb{E}[|Y_n|]\lt \infty }[/math]
  • [math]\displaystyle{ \mathbb{E}\left[\,Y_{n+1}\mid X_0,X_1,\ldots,X_{n}\,\right]=Y_{n} }[/math]
则称随机过程 [math]\displaystyle{ \{Y_n:n\ge 0\} }[/math] 是关于 [math]\displaystyle{ \{X_n:n\ge 0\} }[/math] (martingale)。

停时 (stopping time) 的概念如下定义。

定义(停时)
非负整数值随机变量 [math]\displaystyle{ T }[/math] 是一个关于离散时间随机过程 [math]\displaystyle{ \{X_n:n\ge 0\} }[/math]停时 (stopping time),若对于任意 [math]\displaystyle{ n\ge 0 }[/math],事件 [math]\displaystyle{ T=n }[/math] 发生与否都取决于 [math]\displaystyle{ X_0,X_1,\ldots,X_n }[/math] 的取值。

更加严格地讲,随机过程 [math]\displaystyle{ \{X_n:n\ge 0\} }[/math] 可以唯一确定一个 [math]\displaystyle{ \sigma }[/math]域流 (filtration of [math]\displaystyle{ \sigma }[/math]-fields) [math]\displaystyle{ \Sigma_0\subseteq \Sigma_0 \subseteq \cdots }[/math],使得对于任意 [math]\displaystyle{ n\ge 0 }[/math][math]\displaystyle{ \sigma }[/math][math]\displaystyle{ \Sigma_{n+1} }[/math] 都是 [math]\displaystyle{ \Sigma_{n} }[/math] 的一个细化 (refinement),且 [math]\displaystyle{ \Sigma_n }[/math] 是令随机向量 [math]\displaystyle{ (X_0,X_1,\ldots,X_n) }[/math][math]\displaystyle{ \Sigma_n }[/math]-可测 ([math]\displaystyle{ \Sigma_n }[/math]-measurable) 的最小 [math]\displaystyle{ \sigma }[/math]代数。则 [math]\displaystyle{ T }[/math] 是一个关于 [math]\displaystyle{ \{X_n:n\ge 0\} }[/math] 的一个合法的停时,当且仅当对于任意 [math]\displaystyle{ n\ge 0 }[/math],都有事件 [math]\displaystyle{ \{T=n\}\in\Sigma_n }[/math],即 [math]\displaystyle{ T=n }[/math] 的发生与否,可以被 [math]\displaystyle{ X_0,X_1,\ldots,X_n }[/math] 的取值所确定。

可选停时定理 (Optional Stopping Theorem, OST)
一个鞅 [math]\displaystyle{ \{Y_n:n\ge 0\} }[/math] 在停时 [math]\displaystyle{ T }[/math](鞅和停时都是关于同一个离散时间随机过程 [math]\displaystyle{ \{X_n:n\ge 0\} }[/math] 定义的),总是满足:
[math]\displaystyle{ \mathbb{E}[Y_T]=\mathbb{E}[Y_0] }[/math],
如果有下列任何条件之一成立:
  • (有限时间) 存在有穷的 [math]\displaystyle{ n }[/math] 使得 [math]\displaystyle{ T\lt n }[/math] 几乎必然 (a.s.) 发生。
  • (有限值域) [math]\displaystyle{ T\lt \infty }[/math] 几乎必然发生,且存在有穷的 [math]\displaystyle{ c }[/math] 使得对于所有 [math]\displaystyle{ t\le T }[/math] 都有 [math]\displaystyle{ |Y_t|\lt c }[/math] 几乎必然发生。
  • (有穷期望时间 + 有限差) [math]\displaystyle{ \mathbb{E}[T]\lt \infty }[/math],且存在有穷的 [math]\displaystyle{ c }[/math] 使得对于所有 [math]\displaystyle{ t\ge 0 }[/math] 都有 [math]\displaystyle{ \mathbb{E}[|Y_{t+1}-Y_t|\mid X_0,X_1,\ldots,X_t]\lt c }[/math] 几乎必然发生。
  • (一般条件) 同时满足以下三个条件:
    1. [math]\displaystyle{ T\lt \infty }[/math] 几乎必然发生;
    2. [math]\displaystyle{ \mathbb{E}[|Y_T|]\lt \infty }[/math];
    3. [math]\displaystyle{ \lim_{n\to\infty}\mathbb{E}\left[Y_n\cdot I[T\gt n]\right]=0 }[/math]

前三个条件都更强:它们中任何一个都可以推出最后一个一般条件。这使得最后一个一般条件的可选停时定理是最普世的。然而,在具体的问题场景下,往往前三个充分条件更容易保证。

可选停时定理的证明

可选停时定理的应用

一维随机游走 (1D random walk)

考虑从0开始的无偏随机游走 (unbiased random walk):令 [math]\displaystyle{ X_1,X_2,\ldots\in }[/math][math]\displaystyle{ \{-1,+1\} }[/math] 上独立同分布的均匀随机变量,令 [math]\displaystyle{ Y_t=\sum_{i=1}^tX_i }[/math]。则 [math]\displaystyle{ \{Y_t:t\ge 0\} }[/math] 为随机游走过程。

假设这一随机游走在初次到达 [math]\displaystyle{ -a }[/math] 或者 [math]\displaystyle{ b }[/math] 时会停下,此处 [math]\displaystyle{ a,b\in\mathbb{Z}^+ }[/math] 为两个正整数。我们计算随机游走停下时取值 [math]\displaystyle{ b }[/math] 的概率。

众所周知该随机游走是一个关于 [math]\displaystyle{ \{X_i:i\ge 1\} }[/math] 的鞅:

[math]\displaystyle{ \mathbb{E}[Y_{t+1}\mid X_1,\ldots,X_t]=\mathbb{E}[Y_{t}+X_{t+1}\mid X_1,\ldots,X_t]=\mathbb{E}[Y_{t}\mid X_1,\ldots,X_t]+\mathbb{E}[X_{t+1}\mid X_1,\ldots,X_t]=Y_t+\mathbb{E}[X_{t+1}]=Y_t }[/math]

[math]\displaystyle{ T }[/math] 为该随机游走停下的时刻,即:

[math]\displaystyle{ T=\left\{t\ge 0\mid Y_t=-a\lor Y_t=b\right\}=\left\{t\ge 0\mid \sum_{i=1}^tX_i=-a\lor \sum_{i=1}^tX_i=b\right\} }[/math]

显然 [math]\displaystyle{ T }[/math] 为一个关于 [math]\displaystyle{ \{X_i:i\ge 1\} }[/math] 的良定义的停时。

易验证 [math]\displaystyle{ T\lt \infty }[/math] 几乎必然发生(这是因为假如有 [math]\displaystyle{ a+b }[/math] 个连续的 [math]\displaystyle{ X_i }[/math] 同号,则随机游走必然停止,而这一事件在有穷时间内几乎必然发生), 而且对于任意 [math]\displaystyle{ t\le T }[/math] 都有 [math]\displaystyle{ |Y_t|\le \max\{a,b\} }[/math]

因此,根据可选停时定理(有限值域 条件)有:

[math]\displaystyle{ \mathbb{E}[Y_T]=\mathbb{E}[Y_0]=0 }[/math]

另一方面,由于随机变量 [math]\displaystyle{ Y_T\in\{-a,b\} }[/math],所以有:

[math]\displaystyle{ 0=\mathbb{E}[Y_T]=-a\cdot \Pr(Y_T=-a)+b\cdot \Pr(Y_T=b)=-a\cdot (1-\Pr(Y_T=b))+b\cdot \Pr(Y_T=b) }[/math]

因此可解出

[math]\displaystyle{ \Pr(\text{随机游走停止时取值为}b)=\Pr(Y_T=b)=\frac{a}{a+b} }[/math]

投票问题 (Ballot problem)

模式匹配时间

[math]\displaystyle{ X_1,X_2,\ldots }[/math] 为均匀分布的随机比特串,即每个 [math]\displaystyle{ X_i\in\{0,1\} }[/math] 是独立的均匀分布的伯努利变量。令 [math]\displaystyle{ \boldsymbol{x}=x_1x_2\cdots x_k\in\{0,1\}^k }[/math] 表示一个长为 [math]\displaystyle{ k }[/math] 比特的模式 (pattern)。令 [math]\displaystyle{ T\ge k }[/math] 表示在随机串中初次成功匹配该模式为其子串的时刻,即:

[math]\displaystyle{ T=\min\left\{t\ge k\mid (X_{t-k+1},\ldots, X_{t})=x_1\cdots x_k\right\} }[/math]

显然 [math]\displaystyle{ T }[/math] 是关于随机过程 [math]\displaystyle{ \{X_i:i\ge 1\} }[/math] 的一个良定义的停时。

如此定义的 [math]\displaystyle{ T }[/math] 也被称为模式 [math]\displaystyle{ \boldsymbol{x} }[/math]等待时间 (waiting time)。它的期望有如下的闭合形式的公式。

定理
对于模式 [math]\displaystyle{ \boldsymbol{x}=x_1x_2\cdots x_k\in\{0,1\}^k }[/math] 的等待时间 [math]\displaystyle{ T }[/math],有:
[math]\displaystyle{ \mathbb{E}[T]=\sum_{j=1}^k\chi_j 2^j }[/math]
此处 [math]\displaystyle{ \chi_j }[/math] 指示了模式 [math]\displaystyle{ \boldsymbol{x}=(x_1,x_2,\ldots,x_k)\in\{0,1\}^k }[/math][math]\displaystyle{ j }[/math]-前缀与 [math]\displaystyle{ j }[/math]-后缀的一致性,即:
[math]\displaystyle{ \chi_j=\begin{cases}1 & \text{如果 }x_1\cdots x_j=x_{k-j+1}\cdots x_{k}\\ 0 &\text{否则}\end{cases} }[/math]

我们将采用可选停时定理 (OST) 来证明这一公式。为此,我们将 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 解读为公平抛硬币的结果,并关于它构造公平赌博游戏 (fair gambling games),从而定义鞅。

对于每一个整数 [math]\displaystyle{ i\ge 1 }[/math],我们想象有一个赌徒 (gambler) [math]\displaystyle{ i }[/math],关于 [math]\displaystyle{ X_iX_{i+1}\cdots X_{i+k-1}=x_1\cdots x_k }[/math] 这件事进行赌博。采用如下的策略:

  • 赌徒 [math]\displaystyle{ i }[/math] 的起始资产数为 0。
  • (第一轮)赌徒 [math]\displaystyle{ i }[/math] 押注1元钱赌 [math]\displaystyle{ X_i=x_1 }[/math]
  • (第二轮)如果前一轮赌赢,赌徒 [math]\displaystyle{ i }[/math] 押注2元钱赌 [math]\displaystyle{ X_{i+1}=x_2 }[/math]
  • (第三轮)如果前两轮都赌赢,赌徒 [math]\displaystyle{ i }[/math] 押注4元钱赌 [math]\displaystyle{ X_{i+2}=x_3 }[/math]
.... ....
  • (第 [math]\displaystyle{ k }[/math] 轮)如果前 [math]\displaystyle{ k-1 }[/math] 轮全都赌赢,赌徒 [math]\displaystyle{ i }[/math] 押注 [math]\displaystyle{ 2^{k-1} }[/math] 元钱赌 [math]\displaystyle{ X_{i+k-1}=x_k }[/math]
  • 在上述任何一轮中,如果赌赢,则赌徒会额外获得与所押注数额相等的钱数,并进入下一轮;如果在某一轮中赌输,则失去当前所押的赌注,因此使得总资产变为-1,并停止游戏。

无论输赢与否,赌博游戏在 [math]\displaystyle{ k }[/math] 轮之后都将终止。此时,假如赌徒 [math]\displaystyle{ i }[/math] 从头赢到尾,即事件 [math]\displaystyle{ X_iX_{i+1}\cdots X_{i+k-1}=x_1\cdots x_k }[/math] 发生,则游戏结束时其资产为 [math]\displaystyle{ 2^{k1} }[/math] 元;否则,假如中间某一轮赌输,则从输的那一刻起,该赌徒的资产都将一直为-1。

对于每一个赌徒 [math]\displaystyle{ i\ge 1 }[/math],令随机过程 [math]\displaystyle{ \{Y^{(i)}_t:t\ge 0\} }[/math] 表示该赌徒在 [math]\displaystyle{ t }[/math] 时刻的资产数额。注意这里的时间 [math]\displaystyle{ t }[/math] 对应于随机过程 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 的时间。因此,[math]\displaystyle{ \{Y^{(i)}_t:t\ge 0\} }[/math] 严格定义如下:

  • [math]\displaystyle{ 0\le t\lt i }[/math]
[math]\displaystyle{ Y^{(i)}_t=0 }[/math]
  • [math]\displaystyle{ i\le t\le i+k-1 }[/math]
如果从原随机串第 [math]\displaystyle{ i }[/math] 位至今为止对模式 [math]\displaystyle{ \boldsymbol{x} }[/math] 的匹配都是成功的,即 [math]\displaystyle{ X_{i}\cdots X_{t}=x_1\cdots x_{t-i+1} }[/math],则令
[math]\displaystyle{ Y^{(i)}_t=2^{t-i+1}-1 }[/math],否则 [math]\displaystyle{ Y^{(i)}_t=-1 }[/math]
  • [math]\displaystyle{ t\ge i+k }[/math]
如果从原随机串第 [math]\displaystyle{ i }[/math] 位开始成功匹配模式 [math]\displaystyle{ \boldsymbol{x} }[/math],即 [math]\displaystyle{ X_{i}X_{i+1}\cdots X_{i+k-1}=x_1\cdots x_{k} }[/math],则令
[math]\displaystyle{ Y^{(i)}_t=2^k-1 }[/math],否则 [math]\displaystyle{ Y^{(i)}_t=-1 }[/math]

事实上,[math]\displaystyle{ Y^{(i)}_t }[/math] 的通项可表示为

[math]\displaystyle{ Y^{(i)}_t=-1+2^{[t-i+1]^k_0}\cdot I[X_i\cdots X_{\min\{t,i+k-1\}}=x_1\cdots x_{\min\{t-i+1,k\}}] }[/math]
其中 [math]\displaystyle{ [x]^k_0=\max\{0,\min\{x,k\}\} }[/math] 表示 [math]\displaystyle{ x }[/math] 的上界为 [math]\displaystyle{ k }[/math] 下界为 0 的截断函数。


由于 [math]\displaystyle{ \{Y^{(i)}_t:t\ge 0\} }[/math] 是关于 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 这个公平抛硬币过程进行公平赌博产生的净资产,因此容易验证对于任意赌徒 [math]\displaystyle{ i\ge 1 }[/math],随机过程 [math]\displaystyle{ \{Y^{(i)}_t:t\ge 0\} }[/math] 都是关于 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 的鞅(此处省略严格验证过程)。

同时,容易验证(此处省略具体证明):相对于同一随机过程定义的一系列鞅之和,仍然是关于该过程的鞅。因此,

[math]\displaystyle{ Y_t=\sum_{i=1}^\infty Y^{(i)}_t }[/math]

是关于随机过程 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 的鞅。

还记得停时 [math]\displaystyle{ T }[/math] 是模式 [math]\displaystyle{ \boldsymbol{x} }[/math] 首次匹配成功的时刻。

  • 容易验证 [math]\displaystyle{ \mathbb{E}[T]\le k2^k\lt \infty }[/math]
可以仅考虑被 [math]\displaystyle{ k }[/math] 整除的位置开始的匹配,因此初次匹配的起始时刻 [math]\displaystyle{ T' }[/math] 整除以 [math]\displaystyle{ k }[/math] 后符合参数为 [math]\displaystyle{ 2^{-k} }[/math] 的几何分布,且容易验证该 [math]\displaystyle{ T' }[/math] 随机支配 (stochastically dominates) [math]\displaystyle{ T }[/math]
  • 同时,容易验证如下的有限差性质:对于任意时刻 [math]\displaystyle{ t\ge 0 }[/math],几乎必然地 [math]\displaystyle{ |Y_{t+1}-Y_t|\le k2^{k-1} }[/math]
注意到尽管 [math]\displaystyle{ Y_t }[/math] 是无穷多个 [math]\displaystyle{ Y^{(i)}_t }[/math] 之和,然而在任意时刻 [math]\displaystyle{ t\ge 0 }[/math],至多只有不超过 [math]\displaystyle{ k }[/math] 个不同的 [math]\displaystyle{ Y^{(i)}_t }[/math] 处于改变之中——即正在为期 [math]\displaystyle{ k }[/math] 轮的赌博游戏中,而每轮赌博游戏过后资产改变不超过 [math]\displaystyle{ 2^{k-1} }[/math]

因此,我们可以应用可选停时定理(有穷期望时间 + 有限差 条件),得到

[math]\displaystyle{ \mathbb{E}[Y_T]=\mathbb{E}[Y_0]=\mathbb{E}\left[\sum_{i=1}^\infty Y^{(i)}_0\right]=0 }[/math]

注意到:在时间 [math]\displaystyle{ T }[/math],即随机串首次成功匹配模式 [math]\displaystyle{ \boldsymbol{x} }[/math] 的时刻,根据上述赌博游戏的定义

  • 此时刻有唯一一位赢者赌徒 [math]\displaystyle{ i=T-k+1 }[/math](即打赌 [math]\displaystyle{ X_{T-k+1}\cdots X_T=x_1\cdots x_k }[/math] 这件事发生的那个赌徒)在 [math]\displaystyle{ T }[/math] 时刻的资产为 [math]\displaystyle{ Y^{(T-k+1)}_{T}=2^k-1 }[/math]
  • 所有赌徒 [math]\displaystyle{ i\gt T }[/math][math]\displaystyle{ T }[/math] 时刻都尚未进入 [math]\displaystyle{ k }[/math] 轮的赌博游戏,因此在 [math]\displaystyle{ T }[/math] 时刻的资产均为0;
  • 而所有剩余赌徒 [math]\displaystyle{ i\lt T }[/math] 中,仅有一种情况可能在 [math]\displaystyle{ T }[/math] 时刻的资产不为-1,就是在 [math]\displaystyle{ T }[/math] 时刻尚在连续猜中的过程之中,而这种情况的赌徒皆一一对应于满足 [math]\displaystyle{ x_1\cdots x_j=x_{k-j+1}\cdots x_{k} }[/math] (即[math]\displaystyle{ \chi_j=1 }[/math])的 [math]\displaystyle{ 1\le j\lt k }[/math] ——对于每个这样的[math]\displaystyle{ 1\le j\lt k }[/math],都有一位对应的赌徒 [math]\displaystyle{ i=T-j+1 }[/math][math]\displaystyle{ i=T-j+1 }[/math] 这一时刻开始进入赌博游戏,连续猜中至 [math]\displaystyle{ T }[/math] 时刻,其在 [math]\displaystyle{ T }[/math] 时刻的资产为 [math]\displaystyle{ Y^{(i)}_{T}=2^j-1 }[/math]
  • 所有其余的赌徒 [math]\displaystyle{ i\lt T }[/math],在 [math]\displaystyle{ T }[/math] 时刻都已确定赌输,资产都为-1。

不难看出,在 [math]\displaystyle{ T }[/math] 时刻已确定为输的赌徒总数刚好为 [math]\displaystyle{ T-\sum_{j=1}^k\chi_j }[/math],即到 [math]\displaystyle{ T }[/math] 时刻为止已经开始进入赌博游戏的赌徒总数,减去那些截止到 [math]\displaystyle{ T }[/math] 时刻为止尚在连续赢的过程中的赌徒。

因此,[math]\displaystyle{ T }[/math] 时刻所有赌徒的总资产 [math]\displaystyle{ Y_T }[/math] 可以被如下计算

[math]\displaystyle{ Y_T =T\text{时刻赢家的总资产}-1\cdot(T\text{时刻输家的数量})= \sum_{j=1}^k\chi_j(2^j-1) -\left(T-\sum_{j=1}^k\chi_j\right) }[/math]

根据之前可选停时定理保证的 [math]\displaystyle{ \mathbb{E}[Y_T]=0 }[/math],我们有

[math]\displaystyle{ \begin{align} 0=\mathbb{E}[Y_T] &= \mathbb{E}\left[\sum_{j=1}^k\chi_j(2^j-1) -\left(T-\sum_{j=1}^k\chi_j\right)\right]\\ &= \mathbb{E}\left[\sum_{j=1}^k\chi_j\cdot 2^j -T\right]\\ &= \sum_{j=1}^k\chi_j\cdot 2^j -\mathbb{E}\left[T\right] \end{align} }[/math]

这证明了:

[math]\displaystyle{ \mathbb{E}\left[T\right] = \sum_{j=1}^k\chi_j\cdot 2^j }[/math]

极大不等式 (Maximal inequality)

如下定理给出了一个对于鞅的极大不等式。

鞅极大不等式
[math]\displaystyle{ \{Y_t:t\ge 0\} }[/math] 是关于 [math]\displaystyle{ \{X_t:t\ge 0\} }[/math] 的鞅。如果对于所有 [math]\displaystyle{ t\ge 0 }[/math] 都有 [math]\displaystyle{ Y_t\ge 0 }[/math] 几乎必然 (a.s.) 发生,则对于任意 [math]\displaystyle{ n\ge 0 }[/math][math]\displaystyle{ a\gt 0 }[/math],都有
[math]\displaystyle{ \Pr\left(\max_{t\le n}Y_t \ge a\right)\le\frac{\mathbb{E}[Y_0]}{a} }[/math]

该不等式实为杜布鞅不等式 (Doob's martingale inequality) 的一个特例,后者对于取值非负的下鞅 (submartingales) 都成立。

证明的关键想法是构造一个停时 [math]\displaystyle{ T }[/math] 使得事件 [math]\displaystyle{ \max_{t\le n}Y_t \ge a }[/math] 发生当且仅当 [math]\displaystyle{ Y_T \ge a }[/math]

[math]\displaystyle{ T }[/math] 为初次满足 [math]\displaystyle{ Y_T \ge a }[/math][math]\displaystyle{ T \le n }[/math] 的时间,即:

[math]\displaystyle{ T=\min{t\mid Y_t\ge a}\cup\{n\} }[/math]

易验证 [math]\displaystyle{ T }[/math] 是关于 [math]\displaystyle{ \{Y_t:t\ge 0\} }[/math] 的一个停时,因为 [math]\displaystyle{ T=t }[/math] 发生与否仅取决于 [math]\displaystyle{ Y_0,Y_1,\ldots, Y_t }[/math] 的取值。 因此, [math]\displaystyle{ T }[/math] 也必然是关于 [math]\displaystyle{ \{X_t:t\ge 0\} }[/math] 的一个停时,因为 [math]\displaystyle{ Y_t }[/math][math]\displaystyle{ X_0,X_1,\ldots, X_t }[/math] 的函数。

另外,对于如上构造的停时 [math]\displaystyle{ T }[/math] 容易验证:

  • [math]\displaystyle{ \max_{t\le n}Y_t \ge a }[/math] 当且仅当 [math]\displaystyle{ Y_T \ge a }[/math]

这是因为:如果 [math]\displaystyle{ Y_T \ge a }[/math] 则存在 [math]\displaystyle{ t\le n }[/math] 使得 [math]\displaystyle{ Y_t \ge a }[/math];反之如果存在 [math]\displaystyle{ t^*\le n }[/math] 使得 [math]\displaystyle{ Y_{t^*}=\max_{t\le n}Y_t \ge a }[/math],则 [math]\displaystyle{ T }[/math] 就是最小的这样的 [math]\displaystyle{ t^*\le n }[/math]

因为 [math]\displaystyle{ T\le n }[/math] 总是成立,因此根据可选时停定理(有限时间 条件):

[math]\displaystyle{ \mathbb{E}[Y_T]=\mathbb{E}[Y_0] }[/math]

因此,根据马尔可夫不等式:

[math]\displaystyle{ \Pr\left(\max_{t\le n}Y_t \ge a\right)=\Pr\left(Y_T \ge a\right)\le\frac{\mathbb{E}[Y_T]}{a}=\frac{\mathbb{E}[Y_0]}{a} }[/math]

Wald's equation

Wald's equation(瓦尔德方程?)可以看成是随机个随机变量之和版本的线性期望等式。

Wald's equation
[math]\displaystyle{ X_1,X_2,\ldots }[/math] 为独立同分布的非负随机变量,且具有有穷期望 [math]\displaystyle{ \mu=\mathbb{E}[X_i]\lt \infty }[/math]。如果随机变量 [math]\displaystyle{ N }[/math] 是关于 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 的停时,且满足 [math]\displaystyle{ \mathbb{E}[N]\lt \infty }[/math],则
[math]\displaystyle{ \mathbb{E}\left[\sum_{i=1}^NX_i\right]= \mathbb{E}[N]\cdot\mu }[/math]

该等式的证明,可采用可选停时定理 (OST)。因此我们构造如下的随机过程:

[math]\displaystyle{ Y_t=\sum_{i=1}^t(X_i-\mu) }[/math]

容易验证 [math]\displaystyle{ \{Y_t:t\ge 1\} }[/math] 是关于随机过程 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 的鞅,因为:

[math]\displaystyle{ \mathbb{E}[Y_{t+1}\mid X_1,\ldots,X_{t}]=\mathbb{E}[Y_{t}+(X_{t+1}-\mu)\mid X_1,\ldots,X_{t}]=\mathbb{E}[Y_{t}\mid X_1,\ldots,X_{t}]+\mathbb{E}[X_{t+1}-\mu\mid X_1,\ldots,X_{t}]=Y_{t}+\mathbb{E}[X_{t+1}-\mu]=Y_t }[/math]

由于 [math]\displaystyle{ \mathbb{E}[N]\lt \infty }[/math],而且 [math]\displaystyle{ X_i }[/math] 作为非负变量,有:

[math]\displaystyle{ \mathbb{E}[|Y_{t+1}-Y_t|\mid X_1,\ldots,X_t]=\mathbb{E}[|X_{t+1}-\mu|]\le \mathbb{E}[X_{t+1}+\mu]= 2\mu }[/math]

因此,根据可选停时定理(有穷期望时间 + 有限差 条件),我们有

[math]\displaystyle{ \mathbb{E}[Y_N]=\mathbb{E}[Y_1]=\mathbb{E}[X_1-\mu]=0 }[/math]

另一方面,容易验证:

[math]\displaystyle{ \mathbb{E}[Y_N]=\mathbb{E}\left[\sum_{i=1}^N(X_i-\mu)\right]=\mathbb{E}\left[\sum_{i=1}^NX_i\right]-\mathbb{E}[N]\cdot\mu }[/math]

因此,有:

[math]\displaystyle{ \mathbb{E}\left[\sum_{i=1}^NX_i\right]= \mathbb{E}[N]\cdot\mu }[/math]