概率论与数理统计 (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] 的一个细化 (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]。

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

可选停时定理的证明

可选停时定理的应用

赌徒破产

投票问题

模式匹配的平均等待时间

令 [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]\lt \infty }[/math]。
可以仅考虑被 [math]\displaystyle{ k }[/math] 整除的位置开始的匹配，因此初次匹配的起始时刻 [math]\displaystyle{ T' }[/math] 整除以 [math]\displaystyle{ k }[/math] 后符合几何分布，且容易验证该 [math]\displaystyle{ T' }[/math] 随机支配 [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]

极大不等式

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