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

可选停时定理（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] 几乎必然发生。 (一般条件) 同时满足以下三个条件： [math]\displaystyle{ T\lt \infty }[/math] 几乎必然发生； [math]\displaystyle{ \mathbb{E}[|Y_T|]\lt \infty }[/math]; [math]\displaystyle{ \lim_{n\to\infty}\mathbb{E}\left[Y_n\cdot I[T\gt n]\right]=0 }[/math]。

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

可选停时定理的应用

模式匹配的平均等待时间

令 [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\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]

对于任意 [math]\displaystyle{ i\ge 1 }[/math]，定义如下的随机过程 [math]\displaystyle{ \{Y^{(i)}_t:t\ge 0\} }[/math]

• 当 [math]\displaystyle{ 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]，代表了一个赌徒（gambler），在关于“原随机串从第 [math]\displaystyle{ i }[/math] 位开始成功匹配模式 [math]\displaystyle{ \boldsymbol{x} }[/math]”这件事进行赌博，采用如下策略：

• （第一轮） 押注1元钱赌 [math]\displaystyle{ X_i=x_1 }[/math]。如果赌赢，则额外获得1元并进入第二轮；否则损失全部赌注（1元）资产变为-1，并停止赌博游戏，。
  • （第二轮）押注2元钱赌 [math]\displaystyle{ X_{i+1}=x_2 }[/math]。如果赌赢，则额外获得2元并进入第三轮；否则损失全部赌注（2元）资产变为-1，并停止赌博游戏。
    • （第三轮）押注4元钱赌 [math]\displaystyle{ X_{i+2}=x_3 }[/math]。如果赌赢，则额外获得4元并进入第四轮；否则损失全部赌注（4元）资产变为-1，并停止赌博游戏。
      • （第四轮）押注8元钱赌 [math]\displaystyle{ X_{i+3}=x_4 }[/math]。如果赌赢，则额外获得8元并进入第四轮；否则损失全部赌注（8元）资产变为-1，并停止赌博游戏。

.... ....

• • • • • （第 [math]\displaystyle{ k }[/math] 轮）押注 [math]\displaystyle{ 2^{k-1} }[/math] 元钱赌 [math]\displaystyle{ X_{i+k-1}=x_k }[/math]。如果赌赢，则额外获得 [math]\displaystyle{ 2^{k-1} }[/math] 元，总资产为 [math]\displaystyle{ 2^{k}-1 }[/math] 元；否则损失全部赌注（[math]\displaystyle{ 2^{k-1} }[/math]元）资产变为-1。无论输赢，都停止赌博游戏。

随机过程 [math]\displaystyle{ \{Y^{(i)}_t:t\ge 0\} }[/math] 记录了这个赌徒在每一时刻的资产。初始为 [math]\displaystyle{ Y_0=\cdots =Y_{i-1}=0 }[/math]，从 [math]\displaystyle{ i }[/math] 时刻开始，进入上述游戏的第一轮。

由于 [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{ Y^{(T-k+1)}_{t} }[/math]（即从 [math]\displaystyle{ T-k+1 }[/math] 时刻开始进入赌博游戏的那个赌徒）资产为 [math]\displaystyle{ Y^{(T-k+1)}_{T}=2^k-1 }[/math]；
• 而剩余的从 [math]\displaystyle{ T }[/math] 时刻之前的某个时刻 [math]\displaystyle{ i\lt T }[/math] 开始进入赌局的赌徒 [math]\displaystyle{ Y^{(i)}_{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{ Y^{(i)}_{t} }[/math] 从 [math]\displaystyle{ i=T-j+1 }[/math] 时刻开始进入赌博游戏，连续猜中至 [math]\displaystyle{ T }[/math] 时刻，其资产为 [math]\displaystyle{ Y^{(i)}_{T}=2^j-1 }[/math]；
• 所有其余的从 [math]\displaystyle{ i\lt T }[/math] 时刻开始进入赌局的赌徒 [math]\displaystyle{ Y^{(i)}_{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]