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

From TCS Wiki
Jump to navigation Jump to search
Line 54: Line 54:
0 &\text{否则}\end{cases}</math>
0 &\text{否则}\end{cases}</math>
}}
}}
对于任意 <math>i\ge 1</math>,定义如下的随机过程 <math>\{Y^{(i)}_t:t\ge 0\}</math>
* 当 <math>t<i</math>:
::<math>Y^{(i)}_t=0</math>
* 当 <math>i\le t\le i+k-1</math>:
:如果从原随机串第 <math>i</math> 位至今为止对模式 <math>\boldsymbol{x}</math> 的匹配都是成功的,即 <math>X_{i}\cdots X_{t}=x_1\cdots x_{t-i+1}</math>,则令
::<math>Y^{(i)}_t=2^{t-i+1}-1</math>,否则 <math>Y^{(i)}_t=-1</math>
* 当 <math>t\ge i+k</math>:
:如果从原随机串第 <math>i</math> 位开始成功匹配模式 <math>\boldsymbol{x}</math>,即 <math>X_{i}X_{i+1}\cdots X_{i+k-1}=x_1\cdots x_{k}</math>,则令
::<math>Y^{(i)}_t=2^k-1</math>,否则 <math>Y^{(i)}_t=-1</math>
其实,<math>Y^{(i)}_t</math> 的通项可表示为
: <math>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>\{Y^{(i)}_t:t\ge 0\}</math>,代表了一个赌徒(gambler),她是关于“原随机串从第 <math>i</math> 位开始成功匹配模式 <math>\boldsymbol{x}</math>”这件事进行赌博,采用如下策略:
*(第一轮) 押注1元钱赌 <math>X_i=x_1</math>。如果赌赢,则额外获得1元并进入第二轮;否则损失全部赌注(1元)资产变为-1,并停止赌博游戏,。
** (第二轮)押注2元钱赌 <math>X_{i+1}=x_2</math>。如果赌赢,则额外获得2元并进入第三轮;否则损失全部赌注(2元)资产变为-1,并停止赌博游戏。
*** (第三轮)押注4元钱赌 <math>X_{i+2}=x_3</math>。如果赌赢,则额外获得4元并进入第四轮;否则损失全部赌注(4元)资产变为-1,并停止赌博游戏。
**** (第四轮)押注8元钱赌 <math>X_{i+3}=x_4</math>。如果赌赢,则额外获得8元并进入第四轮;否则损失全部赌注(8元)资产变为-1,并停止赌博游戏。
::::: .... ....
***** (第 <math>k</math> 轮)押注 <math>2^{k-1}</math> 元钱赌 <math>X_{i+k-1}=x_k</math>。如果赌赢,则额外获得 <math>2^{k-1}</math> 元,总资产为 <math>2^{k}-1</math> 元;否则损失全部赌注(<math>2^{k-1}</math>元)资产变为-1。无论输赢,都停止赌博游戏。
随机过程 <math>\{Y^{(i)}_t:t\ge 0\}</math> 记录了这个赌徒在每一时刻的资产。初始为 <math>Y_0=\cdots =Y_{i-1}=0</math>,从 <math>i</math> 时刻开始,进入上述游戏的第一轮。


==极大不等式==
==极大不等式==

Revision as of 15:42, 3 June 2023

可选停时定理

可选停时定理 (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] 时刻开始,进入上述游戏的第一轮。

极大不等式