概率论与数理统计 (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{ 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]。

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

可选停时定理的证明

可选停时定理的应用

赌徒破产

投票问题

模式匹配的平均等待时间

令 [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 1 }[/math] 表示在随机串中初次成功匹配该模式为其子串的时间，即：

[math]\displaystyle{ T=\min\left\{t\mid (X_{T},X_{T+1},\ldots, X_{T+k-1})=x_1x_2\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^{\max\{0,\min\{t-i+1,k\}\}\cdot I[X_i\cdots X_{\min\{t,i+k-1\}}=x_1\cdots x_{\min\{t-i+1,k\}}]} }[/math]

如此定义的随机过程 [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] 时刻开始，进入上述游戏的第一轮。

极大不等式

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