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

From TCS Wiki
Jump to navigation Jump to search

可选停时定理

可选停时定理 (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] 的一个细化，且 [math]\displaystyle{ \Sigma_n }[/math] 是令随机向量 [math]\displaystyle{ (X_0,X_1,\ldots,X_n) }[/math] [math]\displaystyle{ \Sigma_n }[/math]-可测的最小 [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{ \{X_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]。

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

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=概率论与数理统计_(Spring_2023)/OST_and_applications&oldid=11422"