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

From TCS Wiki
Jump to navigation Jump to search
No edit summary
 
(39 intermediate revisions by the same user not shown)
Line 24: Line 24:
:* (''有限时间'') 存在有穷的 <math>n</math> 使得 <math>T<n</math> 几乎必然 (a.s.) 发生。  
:* (''有限时间'') 存在有穷的 <math>n</math> 使得 <math>T<n</math> 几乎必然 (a.s.) 发生。  
:* (''有限值域'') <math>T<\infty</math> 几乎必然发生,且存在有穷的 <math>c</math> 使得对于所有 <math>t\le T</math> 都有 <math>|Y_t|<c</math> 几乎必然发生。
:* (''有限值域'') <math>T<\infty</math> 几乎必然发生,且存在有穷的 <math>c</math> 使得对于所有 <math>t\le T</math> 都有 <math>|Y_t|<c</math> 几乎必然发生。
:* (''有穷期望时间'' + ''有限差'') <math>\mathbb{E}[T]<\infty</math>,且存在有穷的 <math>c</math> 使得对于所有 <math>t\ge 0</math> 都有 <math>\mathbb{E}[|Y_{t+1}-Y_t|\mid X_0,X_1,\ldots,X_t]<c</math> 几乎必然发生。
:* (''有穷期望时间'' + ''有限差'') <math>\mathbb{E}[T]<\infty</math>,且存在有穷的 <math>c</math> 使得对于所有 <math>t\le T</math> 都有 <math>\mathbb{E}[|Y_{t+1}-Y_t|\mid X_0,\ldots,X_t]<c</math> 几乎必然发生。
:* (''一般条件'') 同时满足以下三个条件:
:* (''一般条件'') 同时满足以下三个条件:
:*# <math>T<\infty</math> 几乎必然发生;
:*# <math>T<\infty</math> 几乎必然发生;
Line 33: Line 33:
前三个条件都更强:它们中任何一个都可以推出最后一个一般条件。这使得最后一个一般条件的可选停时定理是最普世的。然而,在具体的问题场景下,往往前三个充分条件更容易保证。
前三个条件都更强:它们中任何一个都可以推出最后一个一般条件。这使得最后一个一般条件的可选停时定理是最普世的。然而,在具体的问题场景下,往往前三个充分条件更容易保证。


==可选停时定理的证明==
=可选停时定理的应用=
 
== 一维随机游走 (1D random walk)==
考虑从0开始的无偏随机游走 (unbiased random walk):令 <math>X_1,X_2,\ldots\in</math> 为 <math>\{-1,+1\}</math> 上独立同分布的均匀随机变量,令 <math>Y_t=\sum_{i=1}^tX_i</math>。则 <math>\{Y_t:t\ge 0\}</math> 为随机游走过程。
 
众所周知该随机游走是一个关于 <math>\{X_i:i\ge 1\}</math> 的鞅:
:<math>\mathbb{E}[Y_{t+1}\mid X_1,\ldots,X_t]=\mathbb{E}[Y_{t}+X_{t+1}\mid X_1,\ldots,X_t]=\mathbb{E}[Y_{t}\mid X_1,\ldots,X_t]+\mathbb{E}[X_{t+1}\mid X_1,\ldots,X_t]=Y_t+\mathbb{E}[X_{t+1}]=Y_t</math>


=可选停时定理的应用=
假设这一随机游走在初次到达 <math>-a</math> 或者 <math>b</math> 时会停下,此处 <math>a,b\in\mathbb{Z}^+</math> 为两个正整数。
 
;吸收 (absorbing) 概率
我们计算随机游走停下时取值 <math>b</math> (或者取值 <math>-a</math>) 的概率。由于 <math>-a</math> 和 <math>b</math> 有时被称为随机游走的吸收态 (absorbing states) 或者吸收壁 (absorbing barriers),因此这一概率也被称为吸收概率。
 
令 <math>T</math> 为该随机游走停下的时刻,即:
:<math>T=\left\{t\ge 0\mid Y_t=-a\lor Y_t=b\right\}=\left\{t\ge 0\mid \sum_{i=1}^tX_i=-a\lor \sum_{i=1}^tX_i=b\right\}</math>
显然 <math>T</math> 为一个关于 <math>\{X_i:i\ge 1\}</math> 的良定义的停时。
 
易验证 <math>T<\infty</math> 几乎必然发生(这是因为假如有 <math>a+b</math> 个连续的 <math>X_i</math> 同号,则随机游走必然停止,而这一事件在有穷时间内几乎必然发生),
而且对于任意 <math>t\le T</math> 都有 <math>|Y_t|\le \max\{a,b\}</math>。
 
因此,根据可选停时定理(''有限值域'' 条件)有:
:<math>\mathbb{E}[Y_T]=\mathbb{E}[Y_0]=0</math>
 
另一方面,由于随机变量 <math>Y_T\in\{-a,b\}</math>,所以有:
:<math>0=\mathbb{E}[Y_T]=-a\cdot \Pr(Y_T=-a)+b\cdot \Pr(Y_T=b)=-a\cdot (1-\Pr(Y_T=b))+b\cdot \Pr(Y_T=b)</math>
因此可解出
:<math>\Pr(\text{随机游走停止时取值为}b)=\Pr(Y_T=b)=\frac{a}{a+b}</math>
 
;期望停时
接下来,我们希望计算随机游走的期望停时 <math>\mathbb{E}[T]</math>。
 
我们构造如下的随机过程:
:<math>Z_t=Y_t^2-t=\left(\sum_{i=1}^tX_i\right)^2-t</math>
易验证
:<math>Z_{t+1}=Y_{t+1}^2-t-1=(Y_t+X_{t+1})^2-t-1=Y_t^2+2X_{t+1}Y_t+X_{t+1}^2-t-1=Z_t+2X_{t+1}Y_t</math>
因此
:<math>\mathbb{E}[Z_{t+1}\mid X_1,\ldots,X_t]=\mathbb{E}[Z_t+2X_{t+1}Y_t\mid X_1,\ldots,X_t]=Z_t+2\mathbb{E}[X_{t+1}]\cdot \mathbb{E}[Y_t\mid X_1,\ldots,X_t]=Z_t</math>
因此,<math>\{Z_t:t\ge 0\}</math> 是关于 <math>\{X_i:i\ge 1\}</math> 的鞅。
 
易验证 <math>\mathbb{E}[T]<\infty</math> (只需意识到假如有 <math>a+b</math> 个连续的 <math>X_i</math> 同号,则随机游走必然停止,而这一事件发生的期望时间不大于 <math>(a+b)2^{a+b-1}</math>),
同时对于任意 <math>t\le T</math> 都有:
:<math>|Z_{t+1}-Z_t|=|2X_{t+1}Y_t|=2|Y_t|\le 2\max\{a,b\}</math>。


== 赌徒破产 (Gambler's ruin)==
根据可选停时定理(''有穷期望时间''+''有限差'' 条件)有:
:<math>\mathbb{E}[Z_T]=\mathbb{E}[Z_0]=\mathbb{E}[Y_0^2-0]=0</math>


==投票问题 (Ballot problem)==
另一方面,根据 <math>Z_t = Y_t^2-t</math> 的定义:
:<math>0=\mathbb{E}[Z_T]=\mathbb{E}[Y_T^2-T]=\mathbb{E}[Y_T^2]-\mathbb{E}[T]</math>
因此 <math>\mathbb{E}[T]=\mathbb{E}[Y_T^2]</math>。由于随机变量 <math>Y_T\in\{-a,b\}</math>,所以期望值 <math>\mathbb{E}[Y_T^2]</math> 可被计算如下:
:<math>\mathbb{E}[Y_T^2]=a^2\cdot \Pr(Y_T=-a)+b^2\cdot \Pr(Y_T=b)=a^2\cdot \frac{b}{a+b} + b^2\cdot \frac{a}{a+b}=\frac{a^2b+b^2a}{a+b}=ab</math>


== 模式匹配时间==
== 模式匹配时间==
令 <math>X_1,X_2,\ldots</math> 为均匀分布的随机比特串,即每个 <math>X_i\in\{0,1\}</math> 是独立的均匀分布的伯努利变量。令 <math>\boldsymbol{x}=x_1x_2\cdots x_k\in\{0,1\}^k</math> 表示一个长为 <math>k</math> 比特的'''模式''' (''pattern'')。令 <math>T\ge k</math> 表示在随机串中初次成功匹配该模式为其子串的时刻,即:
令 <math>X_1,X_2,\ldots</math> 为均匀分布的随机比特串,即每个 <math>X_i\in\{0,1\}</math> 是独立的均匀分布的伯努利变量。令 <math>\boldsymbol{x}=x_1x_2\cdots x_k\in\{0,1\}^k</math> 表示一个长为 <math>k</math> 比特的'''模式''' (''pattern'')。令 <math>T\ge k</math> 表示在随机串中初次成功匹配该模式为其子串的时刻,即:
:<math>T=\min\left\{t\mid (X_{t-k+1},\ldots, X_{t})=x_1\cdots x_k\right\}</math>
:<math>T=\min\left\{t\ge k\mid (X_{t-k+1},\ldots, X_{t})=x_1\cdots x_k\right\}</math>
显然 <math>T</math> 是关于随机过程 <math>\{X_i:i\ge 1\}</math> 的一个良定义的停时。
显然 <math>T</math> 是关于随机过程 <math>\{X_i:i\ge 1\}</math> 的一个良定义的停时。


该停时 <math>T</math> 也被称为模式 <math>\boldsymbol{x}</math> 的'''等待时间''' (waiting time)。它的期望有如下的闭合形式的公式。
如此定义的 <math>T</math> 也被称为模式 <math>\boldsymbol{x}</math> 的'''等待时间''' (waiting time)。它的期望有如下的闭合形式的公式。
{{Theorem|定理|
{{Theorem|定理|
:对于模式 <math>\boldsymbol{x}=x_1x_2\cdots x_k\in\{0,1\}^k</math> 的等待时间 <math>T</math>,有:
:对于模式 <math>\boldsymbol{x}=x_1x_2\cdots x_k\in\{0,1\}^k</math> 的等待时间 <math>T</math>,有:
Line 55: Line 98:
}}
}}


对于任意 <math>i\ge 1</math>,定义如下的随机过程 <math>\{Y^{(i)}_t:t\ge 0\}</math>
我们将采用可选停时定理 (OST) 来证明这一公式。为此,我们将 <math>X_1,X_2,\ldots</math> 解读为公平抛硬币的结果,并关于它构造公平赌博游戏 (fair gambling games),从而定义鞅。
* 当 <math>t<i</math>:
 
对于每一个整数 <math>i\ge 1</math>,我们想象有一个赌徒 (gambler) <math>i</math>,关于 <math>X_iX_{i+1}\cdots X_{i+k-1}=x_1\cdots x_k</math> 这件事进行赌博。采用如下的策略:
* 赌徒 <math>i</math> 的起始资产数为 0。
*(第一轮)赌徒 <math>i</math> 押注1元钱赌 <math>X_i=x_1</math>。
* (第二轮)如果前一轮赌赢,赌徒 <math>i</math> 押注2元钱赌 <math>X_{i+1}=x_2</math>。
* (第三轮)如果前两轮都赌赢,赌徒 <math>i</math> 押注4元钱赌 <math>X_{i+2}=x_3</math>。
:: .... ....
* (第 <math>k</math> 轮)如果前  <math>k-1</math> 轮全都赌赢,赌徒 <math>i</math> 押注 <math>2^{k-1}</math> 元钱赌 <math>X_{i+k-1}=x_k</math>。
* 在上述任何一轮中,如果赌赢,则赌徒会额外获得与所押注数额相等的钱数,并进入下一轮;如果在某一轮中赌输,则失去当前所押的赌注,因此使得总资产变为-1,并停止游戏。
 
无论输赢与否,赌博游戏在 <math>k</math> 轮之后都将终止。此时,假如赌徒 <math>i</math> 从头赢到尾,即事件 <math>X_iX_{i+1}\cdots X_{i+k-1}=x_1\cdots x_k</math> 发生,则游戏结束时其资产为 <math>2^{k1}</math> 元;否则,假如中间某一轮赌输,则从输的那一刻起,该赌徒的资产都将一直为-1。
 
对于每一个赌徒 <math>i\ge 1</math>,令随机过程 <math>\{Y^{(i)}_t:t\ge 0\}</math> 表示该赌徒在 <math>t</math> 时刻的资产数额。注意这里的时间 <math>t</math> 对应于随机过程 <math>X_1,X_2,\ldots</math> 的时间。因此,<math>\{Y^{(i)}_t:t\ge 0\}</math> 严格定义如下:
* 当 <math>0\le t<i</math>:
::<math>Y^{(i)}_t=0</math>
::<math>Y^{(i)}_t=0</math>
* 当 <math>i\le t\le i+k-1</math>:
* 当 <math>i\le t\le i+k-1</math>:
Line 65: Line 121:
::<math>Y^{(i)}_t=2^k-1</math>,否则 <math>Y^{(i)}_t=-1</math>
::<math>Y^{(i)}_t=2^k-1</math>,否则 <math>Y^{(i)}_t=-1</math>


其实,<math>Y^{(i)}_t</math> 的通项可表示为
事实上,<math>Y^{(i)}_t</math> 的通项可表示为
: <math>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>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>[x]^k_0=\max\{0,\min\{x,k\}\}</math> 表示 <math>x</math> 的上界为 <math>k</math> 下界为 0 的截断函数。
: 其中 <math>[x]^k_0=\max\{0,\min\{x,k\}\}</math> 表示 <math>x</math> 的上界为 <math>k</math> 下界为 0 的截断函数。


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


由于 <math>\{Y^{(i)}_t:t\ge 0\}</math> 是关于 <math>X_1,X_2,\ldots</math> 这个公平抛硬币过程进行公平赌博产生的净资产,因此容易验证对于任意 <math>i\ge 1</math>,随机过程 <math>\{Y^{(i)}_t:t\ge 0\}</math> 都是关于 <math>X_1,X_2,\ldots</math> 的鞅(此处省略严格验证过程)。
由于 <math>\{Y^{(i)}_t:t\ge 0\}</math> 是关于 <math>X_1,X_2,\ldots</math> 这个公平抛硬币过程进行公平赌博产生的净资产,因此容易验证对于任意赌徒 <math>i\ge 1</math>,随机过程 <math>\{Y^{(i)}_t:t\ge 0\}</math> 都是关于 <math>X_1,X_2,\ldots</math> 的鞅(此处省略严格验证过程)。


同时,容易验证(此处省略具体证明):相对于同一随机过程定义的一系列鞅之和,仍然是关于该过程的鞅。因此,
同时,容易验证(此处省略具体证明):相对于同一随机过程定义的一系列鞅之和,仍然是关于该过程的鞅。因此,
Line 95: Line 142:


注意到:在时间 <math>T</math>,即随机串首次成功匹配模式 <math>\boldsymbol{x}</math> 的时刻,根据上述赌博游戏的定义
注意到:在时间 <math>T</math>,即随机串首次成功匹配模式 <math>\boldsymbol{x}</math> 的时刻,根据上述赌博游戏的定义
* 此时刻有唯一一位赌徒 <math>Y^{(T-k+1)}_{t}</math>(即从 <math>T-k+1</math> 时刻开始进入赌博游戏的那个赌徒)资产为 <math>Y^{(T-k+1)}_{T}=2^k-1</math>;
* 此时刻有唯一一位赢者赌徒 <math>i=T-k+1</math>(即打赌 <math>X_{T-k+1}\cdots X_T=x_1\cdots x_k</math> 这件事发生的那个赌徒)在 <math>T</math> 时刻的资产为 <math>Y^{(T-k+1)}_{T}=2^k-1</math>;
* 而剩余的从 <math>T</math> 时刻之前的某个时刻 <math>i<T</math> 开始进入赌局的赌徒 <math>Y^{(i)}_{t}</math> 中,仅有一种情况可能在 <math>T</math> 时刻的资产不为-1,就是在 <math>T</math> 时刻尚在连续猜中的过程之中,而这种情况的赌徒皆一一对应于满足 <math>x_1\cdots x_j=x_{k-j+1}\cdots x_{k}</math> (即<math>\chi_j=1</math>)的 <math>1\le j<k</math> ——对于每个这样的<math>1\le j<k</math>,都有一位对应的赌徒 <math>Y^{(i)}_{t}</math> 从 <math>i=T-j+1</math> 时刻开始进入赌博游戏,连续猜中至 <math>T</math> 时刻,其资产为 <math>Y^{(i)}_{T}=2^j-1</math>;
* 所有赌徒 <math>i>T</math>,<math>T</math> 时刻都尚未进入 <math>k</math> 轮的赌博游戏,因此在 <math>T</math> 时刻的资产均为0;
* 所有其余的从 <math>i<T</math> 时刻开始进入赌局的赌徒  <math>Y^{(i)}_{t}</math>,在 <math>T</math> 时刻都已确定赌输,资产都为-1。
* 而所有剩余赌徒 <math>i<T</math> 中,仅有一种情况可能在 <math>T</math> 时刻的资产不为-1,就是在 <math>T</math> 时刻尚在连续猜中的过程之中,而这种情况的赌徒皆一一对应于满足 <math>x_1\cdots x_j=x_{k-j+1}\cdots x_{k}</math> (即<math>\chi_j=1</math>)的 <math>1\le j<k</math> ——对于每个这样的<math>1\le j<k</math>,都有一位对应的赌徒 <math>i=T-j+1</math> 从 <math>i=T-j+1</math> 这一时刻开始进入赌博游戏,连续猜中至 <math>T</math> 时刻,其在 <math>T</math> 时刻的资产为 <math>Y^{(i)}_{T}=2^j-1</math>;
* 所有其余的赌徒 <math>i<T</math>,在 <math>T</math> 时刻都已确定赌输,资产都为-1。


不难看出,在 <math>T</math> 时刻已确定为输的赌徒总数刚好为 <math>T-\sum_{j=1}^k\chi_j</math>,即到 <math>T</math> 时刻为止已经开始进入赌博游戏的赌徒总数,减去那些截止到 <math>T</math> 时刻为止尚在连续赢的过程中的赌徒。
不难看出,在 <math>T</math> 时刻已确定为输的赌徒总数刚好为 <math>T-\sum_{j=1}^k\chi_j</math>,即到 <math>T</math> 时刻为止已经开始进入赌博游戏的赌徒总数,减去那些截止到 <math>T</math> 时刻为止尚在连续赢的过程中的赌徒。
Line 115: Line 163:


==极大不等式 (Maximal inequality)==
==极大不等式 (Maximal inequality)==
如下定理给出了一个对于鞅的极大不等式。
{{Theorem|鞅极大不等式|
:令 <math>\{Y_t:t\ge 0\}</math> 是关于 <math>\{X_t:t\ge 0\}</math> 的鞅。如果对于所有 <math>t\ge 0</math> 都有 <math>Y_t\ge 0</math> 几乎必然 (a.s.) 发生,则对于任意 <math>n\ge 0</math> 与 <math>a> 0</math>,都有
::<math>\Pr\left(\max_{t\le n}Y_t \ge a\right)\le\frac{\mathbb{E}[Y_0]}{a}</math>
}}
该不等式实为'''杜布鞅不等式''' ([https://en.wikipedia.org/wiki/Doob%27s_martingale_inequality '''Doob's martingale inequality''']) 的一个特例,后者对于取值非负的下鞅 (submartingales) 都成立。
证明的关键想法是构造一个停时 <math>T</math> 使得事件 <math>\max_{t\le n}Y_t \ge a</math> 发生当且仅当 <math>Y_T \ge a</math>。
令 <math>T</math> 为初次满足 <math>Y_T \ge a</math> 或 <math>T \le n</math> 的时间,即:
:<math>T=\min{t\mid Y_t\ge a}\cup\{n\}</math>
易验证 <math>T</math> 是关于 <math>\{Y_t:t\ge 0\}</math> 的一个停时,因为 <math>T=t</math> 发生与否仅取决于 <math>Y_0,Y_1,\ldots, Y_t</math> 的取值。
因此, <math>T</math> 也必然是关于 <math>\{X_t:t\ge 0\}</math> 的一个停时,因为 <math>Y_t</math> 是 <math>X_0,X_1,\ldots, X_t</math> 的函数。
另外,对于如上构造的停时 <math>T</math> 容易验证:
* <math>\max_{t\le n}Y_t \ge a</math> 当且仅当 <math>Y_T \ge a</math>
这是因为:如果 <math>Y_T \ge a</math> 则存在 <math>t\le n</math> 使得 <math>Y_t \ge a</math>;反之如果存在 <math>t^*\le n</math> 使得 <math>Y_{t^*}=\max_{t\le n}Y_t \ge a</math>,则 <math>T</math> 就是最小的这样的 <math>t^*\le n</math>。
因为 <math>T\le n</math> 总是成立,因此根据可选时停定理(''有限时间'' 条件):
:<math>\mathbb{E}[Y_T]=\mathbb{E}[Y_0]</math>
因此,根据马尔可夫不等式:
:<math>\Pr\left(\max_{t\le n}Y_t \ge a\right)=\Pr\left(Y_T \ge a\right)\le\frac{\mathbb{E}[Y_T]}{a}=\frac{\mathbb{E}[Y_0]}{a}</math>


== Wald's equation==
== Wald's equation==
Wald's equation(瓦尔德方程?)可以看成是随机个随机变量之和版本的线性期望等式。
{{Theorem| Wald's equation|
:令 <math>X_1,X_2,\ldots</math> 为独立同分布的非负随机变量,且具有有穷期望 <math>\mu=\mathbb{E}[X_i]<\infty</math>。如果随机变量 <math>N</math> 是关于 <math>X_1,X_2,\ldots</math> 的停时,且满足 <math>\mathbb{E}[N]<\infty</math>,则
::<math>\mathbb{E}\left[\sum_{i=1}^NX_i\right]= \mathbb{E}[N]\cdot\mu</math>
}}
该等式的证明,可采用可选停时定理 (OST)。因此我们构造如下的随机过程:
:<math>Y_t=\sum_{i=1}^t(X_i-\mu)</math>
容易验证 <math>\{Y_t:t\ge 1\}</math> 是关于随机过程 <math>X_1,X_2,\ldots</math> 的鞅,因为:
:<math>\mathbb{E}[Y_{t+1}\mid X_1,\ldots,X_{t}]=\mathbb{E}[Y_{t}+(X_{t+1}-\mu)\mid X_1,\ldots,X_{t}]=\mathbb{E}[Y_{t}\mid X_1,\ldots,X_{t}]+\mathbb{E}[X_{t+1}-\mu\mid X_1,\ldots,X_{t}]=Y_{t}+\mathbb{E}[X_{t+1}-\mu]=Y_t</math>
由于 <math>\mathbb{E}[N]<\infty</math>,而且 <math>X_i</math> 作为非负变量,有:
:<math>\mathbb{E}[|Y_{t+1}-Y_t|\mid X_1,\ldots,X_t]=\mathbb{E}[|X_{t+1}-\mu|]\le \mathbb{E}[X_{t+1}+\mu]= 2\mu</math>
因此,根据可选停时定理(''有穷期望时间'' + ''有限差'' 条件),我们有
:<math>\mathbb{E}[Y_N]=\mathbb{E}[Y_1]=\mathbb{E}[X_1-\mu]=0</math>
另一方面,容易验证:
:<math>\mathbb{E}[Y_N]=\mathbb{E}\left[\sum_{i=1}^N(X_i-\mu)\right]=\mathbb{E}\left[\sum_{i=1}^NX_i\right]-\mathbb{E}[N]\cdot\mu</math>
因此,有:
:<math>\mathbb{E}\left[\sum_{i=1}^NX_i\right]= \mathbb{E}[N]\cdot\mu</math>

Latest revision as of 08:07, 5 June 2023

可选停时定理 (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\le T }[/math] 都有 [math]\displaystyle{ \mathbb{E}[|Y_{t+1}-Y_t|\mid X_0,\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]

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

可选停时定理的应用

一维随机游走 (1D random walk)

考虑从0开始的无偏随机游走 (unbiased random walk):令 [math]\displaystyle{ X_1,X_2,\ldots\in }[/math][math]\displaystyle{ \{-1,+1\} }[/math] 上独立同分布的均匀随机变量,令 [math]\displaystyle{ Y_t=\sum_{i=1}^tX_i }[/math]。则 [math]\displaystyle{ \{Y_t:t\ge 0\} }[/math] 为随机游走过程。

众所周知该随机游走是一个关于 [math]\displaystyle{ \{X_i:i\ge 1\} }[/math] 的鞅:

[math]\displaystyle{ \mathbb{E}[Y_{t+1}\mid X_1,\ldots,X_t]=\mathbb{E}[Y_{t}+X_{t+1}\mid X_1,\ldots,X_t]=\mathbb{E}[Y_{t}\mid X_1,\ldots,X_t]+\mathbb{E}[X_{t+1}\mid X_1,\ldots,X_t]=Y_t+\mathbb{E}[X_{t+1}]=Y_t }[/math]

假设这一随机游走在初次到达 [math]\displaystyle{ -a }[/math] 或者 [math]\displaystyle{ b }[/math] 时会停下,此处 [math]\displaystyle{ a,b\in\mathbb{Z}^+ }[/math] 为两个正整数。

吸收 (absorbing) 概率

我们计算随机游走停下时取值 [math]\displaystyle{ b }[/math] (或者取值 [math]\displaystyle{ -a }[/math]) 的概率。由于 [math]\displaystyle{ -a }[/math][math]\displaystyle{ b }[/math] 有时被称为随机游走的吸收态 (absorbing states) 或者吸收壁 (absorbing barriers),因此这一概率也被称为吸收概率。

[math]\displaystyle{ T }[/math] 为该随机游走停下的时刻,即:

[math]\displaystyle{ T=\left\{t\ge 0\mid Y_t=-a\lor Y_t=b\right\}=\left\{t\ge 0\mid \sum_{i=1}^tX_i=-a\lor \sum_{i=1}^tX_i=b\right\} }[/math]

显然 [math]\displaystyle{ T }[/math] 为一个关于 [math]\displaystyle{ \{X_i:i\ge 1\} }[/math] 的良定义的停时。

易验证 [math]\displaystyle{ T\lt \infty }[/math] 几乎必然发生(这是因为假如有 [math]\displaystyle{ a+b }[/math] 个连续的 [math]\displaystyle{ X_i }[/math] 同号,则随机游走必然停止,而这一事件在有穷时间内几乎必然发生), 而且对于任意 [math]\displaystyle{ t\le T }[/math] 都有 [math]\displaystyle{ |Y_t|\le \max\{a,b\} }[/math]

因此,根据可选停时定理(有限值域 条件)有:

[math]\displaystyle{ \mathbb{E}[Y_T]=\mathbb{E}[Y_0]=0 }[/math]

另一方面,由于随机变量 [math]\displaystyle{ Y_T\in\{-a,b\} }[/math],所以有:

[math]\displaystyle{ 0=\mathbb{E}[Y_T]=-a\cdot \Pr(Y_T=-a)+b\cdot \Pr(Y_T=b)=-a\cdot (1-\Pr(Y_T=b))+b\cdot \Pr(Y_T=b) }[/math]

因此可解出

[math]\displaystyle{ \Pr(\text{随机游走停止时取值为}b)=\Pr(Y_T=b)=\frac{a}{a+b} }[/math]
期望停时

接下来,我们希望计算随机游走的期望停时 [math]\displaystyle{ \mathbb{E}[T] }[/math]

我们构造如下的随机过程:

[math]\displaystyle{ Z_t=Y_t^2-t=\left(\sum_{i=1}^tX_i\right)^2-t }[/math]

易验证

[math]\displaystyle{ Z_{t+1}=Y_{t+1}^2-t-1=(Y_t+X_{t+1})^2-t-1=Y_t^2+2X_{t+1}Y_t+X_{t+1}^2-t-1=Z_t+2X_{t+1}Y_t }[/math]

因此

[math]\displaystyle{ \mathbb{E}[Z_{t+1}\mid X_1,\ldots,X_t]=\mathbb{E}[Z_t+2X_{t+1}Y_t\mid X_1,\ldots,X_t]=Z_t+2\mathbb{E}[X_{t+1}]\cdot \mathbb{E}[Y_t\mid X_1,\ldots,X_t]=Z_t }[/math]

因此,[math]\displaystyle{ \{Z_t:t\ge 0\} }[/math] 是关于 [math]\displaystyle{ \{X_i:i\ge 1\} }[/math] 的鞅。

易验证 [math]\displaystyle{ \mathbb{E}[T]\lt \infty }[/math] (只需意识到假如有 [math]\displaystyle{ a+b }[/math] 个连续的 [math]\displaystyle{ X_i }[/math] 同号,则随机游走必然停止,而这一事件发生的期望时间不大于 [math]\displaystyle{ (a+b)2^{a+b-1} }[/math]), 同时对于任意 [math]\displaystyle{ t\le T }[/math] 都有:

[math]\displaystyle{ |Z_{t+1}-Z_t|=|2X_{t+1}Y_t|=2|Y_t|\le 2\max\{a,b\} }[/math]

根据可选停时定理(有穷期望时间+有限差 条件)有:

[math]\displaystyle{ \mathbb{E}[Z_T]=\mathbb{E}[Z_0]=\mathbb{E}[Y_0^2-0]=0 }[/math]

另一方面,根据 [math]\displaystyle{ Z_t = Y_t^2-t }[/math] 的定义:

[math]\displaystyle{ 0=\mathbb{E}[Z_T]=\mathbb{E}[Y_T^2-T]=\mathbb{E}[Y_T^2]-\mathbb{E}[T] }[/math]

因此 [math]\displaystyle{ \mathbb{E}[T]=\mathbb{E}[Y_T^2] }[/math]。由于随机变量 [math]\displaystyle{ Y_T\in\{-a,b\} }[/math],所以期望值 [math]\displaystyle{ \mathbb{E}[Y_T^2] }[/math] 可被计算如下:

[math]\displaystyle{ \mathbb{E}[Y_T^2]=a^2\cdot \Pr(Y_T=-a)+b^2\cdot \Pr(Y_T=b)=a^2\cdot \frac{b}{a+b} + b^2\cdot \frac{a}{a+b}=\frac{a^2b+b^2a}{a+b}=ab }[/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\ge k\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]

我们将采用可选停时定理 (OST) 来证明这一公式。为此,我们将 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 解读为公平抛硬币的结果,并关于它构造公平赌博游戏 (fair gambling games),从而定义鞅。

对于每一个整数 [math]\displaystyle{ i\ge 1 }[/math],我们想象有一个赌徒 (gambler) [math]\displaystyle{ i }[/math],关于 [math]\displaystyle{ X_iX_{i+1}\cdots X_{i+k-1}=x_1\cdots x_k }[/math] 这件事进行赌博。采用如下的策略:

  • 赌徒 [math]\displaystyle{ i }[/math] 的起始资产数为 0。
  • (第一轮)赌徒 [math]\displaystyle{ i }[/math] 押注1元钱赌 [math]\displaystyle{ X_i=x_1 }[/math]
  • (第二轮)如果前一轮赌赢,赌徒 [math]\displaystyle{ i }[/math] 押注2元钱赌 [math]\displaystyle{ X_{i+1}=x_2 }[/math]
  • (第三轮)如果前两轮都赌赢,赌徒 [math]\displaystyle{ i }[/math] 押注4元钱赌 [math]\displaystyle{ X_{i+2}=x_3 }[/math]
.... ....
  • (第 [math]\displaystyle{ k }[/math] 轮)如果前 [math]\displaystyle{ k-1 }[/math] 轮全都赌赢,赌徒 [math]\displaystyle{ i }[/math] 押注 [math]\displaystyle{ 2^{k-1} }[/math] 元钱赌 [math]\displaystyle{ X_{i+k-1}=x_k }[/math]
  • 在上述任何一轮中,如果赌赢,则赌徒会额外获得与所押注数额相等的钱数,并进入下一轮;如果在某一轮中赌输,则失去当前所押的赌注,因此使得总资产变为-1,并停止游戏。

无论输赢与否,赌博游戏在 [math]\displaystyle{ k }[/math] 轮之后都将终止。此时,假如赌徒 [math]\displaystyle{ i }[/math] 从头赢到尾,即事件 [math]\displaystyle{ X_iX_{i+1}\cdots X_{i+k-1}=x_1\cdots x_k }[/math] 发生,则游戏结束时其资产为 [math]\displaystyle{ 2^{k1} }[/math] 元;否则,假如中间某一轮赌输,则从输的那一刻起,该赌徒的资产都将一直为-1。

对于每一个赌徒 [math]\displaystyle{ i\ge 1 }[/math],令随机过程 [math]\displaystyle{ \{Y^{(i)}_t:t\ge 0\} }[/math] 表示该赌徒在 [math]\displaystyle{ t }[/math] 时刻的资产数额。注意这里的时间 [math]\displaystyle{ t }[/math] 对应于随机过程 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 的时间。因此,[math]\displaystyle{ \{Y^{(i)}_t:t\ge 0\} }[/math] 严格定义如下:

  • [math]\displaystyle{ 0\le 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] 是关于 [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{ i=T-k+1 }[/math](即打赌 [math]\displaystyle{ X_{T-k+1}\cdots X_T=x_1\cdots x_k }[/math] 这件事发生的那个赌徒)在 [math]\displaystyle{ T }[/math] 时刻的资产为 [math]\displaystyle{ Y^{(T-k+1)}_{T}=2^k-1 }[/math]
  • 所有赌徒 [math]\displaystyle{ i\gt T }[/math][math]\displaystyle{ T }[/math] 时刻都尚未进入 [math]\displaystyle{ k }[/math] 轮的赌博游戏,因此在 [math]\displaystyle{ T }[/math] 时刻的资产均为0;
  • 而所有剩余赌徒 [math]\displaystyle{ i\lt 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{ i=T-j+1 }[/math][math]\displaystyle{ i=T-j+1 }[/math] 这一时刻开始进入赌博游戏,连续猜中至 [math]\displaystyle{ T }[/math] 时刻,其在 [math]\displaystyle{ T }[/math] 时刻的资产为 [math]\displaystyle{ Y^{(i)}_{T}=2^j-1 }[/math]
  • 所有其余的赌徒 [math]\displaystyle{ i\lt 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]

极大不等式 (Maximal inequality)

如下定理给出了一个对于鞅的极大不等式。

鞅极大不等式
[math]\displaystyle{ \{Y_t:t\ge 0\} }[/math] 是关于 [math]\displaystyle{ \{X_t:t\ge 0\} }[/math] 的鞅。如果对于所有 [math]\displaystyle{ t\ge 0 }[/math] 都有 [math]\displaystyle{ Y_t\ge 0 }[/math] 几乎必然 (a.s.) 发生,则对于任意 [math]\displaystyle{ n\ge 0 }[/math][math]\displaystyle{ a\gt 0 }[/math],都有
[math]\displaystyle{ \Pr\left(\max_{t\le n}Y_t \ge a\right)\le\frac{\mathbb{E}[Y_0]}{a} }[/math]

该不等式实为杜布鞅不等式 (Doob's martingale inequality) 的一个特例,后者对于取值非负的下鞅 (submartingales) 都成立。

证明的关键想法是构造一个停时 [math]\displaystyle{ T }[/math] 使得事件 [math]\displaystyle{ \max_{t\le n}Y_t \ge a }[/math] 发生当且仅当 [math]\displaystyle{ Y_T \ge a }[/math]

[math]\displaystyle{ T }[/math] 为初次满足 [math]\displaystyle{ Y_T \ge a }[/math][math]\displaystyle{ T \le n }[/math] 的时间,即:

[math]\displaystyle{ T=\min{t\mid Y_t\ge a}\cup\{n\} }[/math]

易验证 [math]\displaystyle{ T }[/math] 是关于 [math]\displaystyle{ \{Y_t:t\ge 0\} }[/math] 的一个停时,因为 [math]\displaystyle{ T=t }[/math] 发生与否仅取决于 [math]\displaystyle{ Y_0,Y_1,\ldots, Y_t }[/math] 的取值。 因此, [math]\displaystyle{ T }[/math] 也必然是关于 [math]\displaystyle{ \{X_t:t\ge 0\} }[/math] 的一个停时,因为 [math]\displaystyle{ Y_t }[/math][math]\displaystyle{ X_0,X_1,\ldots, X_t }[/math] 的函数。

另外,对于如上构造的停时 [math]\displaystyle{ T }[/math] 容易验证:

  • [math]\displaystyle{ \max_{t\le n}Y_t \ge a }[/math] 当且仅当 [math]\displaystyle{ Y_T \ge a }[/math]

这是因为:如果 [math]\displaystyle{ Y_T \ge a }[/math] 则存在 [math]\displaystyle{ t\le n }[/math] 使得 [math]\displaystyle{ Y_t \ge a }[/math];反之如果存在 [math]\displaystyle{ t^*\le n }[/math] 使得 [math]\displaystyle{ Y_{t^*}=\max_{t\le n}Y_t \ge a }[/math],则 [math]\displaystyle{ T }[/math] 就是最小的这样的 [math]\displaystyle{ t^*\le n }[/math]

因为 [math]\displaystyle{ T\le n }[/math] 总是成立,因此根据可选时停定理(有限时间 条件):

[math]\displaystyle{ \mathbb{E}[Y_T]=\mathbb{E}[Y_0] }[/math]

因此,根据马尔可夫不等式:

[math]\displaystyle{ \Pr\left(\max_{t\le n}Y_t \ge a\right)=\Pr\left(Y_T \ge a\right)\le\frac{\mathbb{E}[Y_T]}{a}=\frac{\mathbb{E}[Y_0]}{a} }[/math]

Wald's equation

Wald's equation(瓦尔德方程?)可以看成是随机个随机变量之和版本的线性期望等式。

Wald's equation
[math]\displaystyle{ X_1,X_2,\ldots }[/math] 为独立同分布的非负随机变量,且具有有穷期望 [math]\displaystyle{ \mu=\mathbb{E}[X_i]\lt \infty }[/math]。如果随机变量 [math]\displaystyle{ N }[/math] 是关于 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 的停时,且满足 [math]\displaystyle{ \mathbb{E}[N]\lt \infty }[/math],则
[math]\displaystyle{ \mathbb{E}\left[\sum_{i=1}^NX_i\right]= \mathbb{E}[N]\cdot\mu }[/math]

该等式的证明,可采用可选停时定理 (OST)。因此我们构造如下的随机过程:

[math]\displaystyle{ Y_t=\sum_{i=1}^t(X_i-\mu) }[/math]

容易验证 [math]\displaystyle{ \{Y_t:t\ge 1\} }[/math] 是关于随机过程 [math]\displaystyle{ X_1,X_2,\ldots }[/math] 的鞅,因为:

[math]\displaystyle{ \mathbb{E}[Y_{t+1}\mid X_1,\ldots,X_{t}]=\mathbb{E}[Y_{t}+(X_{t+1}-\mu)\mid X_1,\ldots,X_{t}]=\mathbb{E}[Y_{t}\mid X_1,\ldots,X_{t}]+\mathbb{E}[X_{t+1}-\mu\mid X_1,\ldots,X_{t}]=Y_{t}+\mathbb{E}[X_{t+1}-\mu]=Y_t }[/math]

由于 [math]\displaystyle{ \mathbb{E}[N]\lt \infty }[/math],而且 [math]\displaystyle{ X_i }[/math] 作为非负变量,有:

[math]\displaystyle{ \mathbb{E}[|Y_{t+1}-Y_t|\mid X_1,\ldots,X_t]=\mathbb{E}[|X_{t+1}-\mu|]\le \mathbb{E}[X_{t+1}+\mu]= 2\mu }[/math]

因此,根据可选停时定理(有穷期望时间 + 有限差 条件),我们有

[math]\displaystyle{ \mathbb{E}[Y_N]=\mathbb{E}[Y_1]=\mathbb{E}[X_1-\mu]=0 }[/math]

另一方面,容易验证:

[math]\displaystyle{ \mathbb{E}[Y_N]=\mathbb{E}\left[\sum_{i=1}^N(X_i-\mu)\right]=\mathbb{E}\left[\sum_{i=1}^NX_i\right]-\mathbb{E}[N]\cdot\mu }[/math]

因此,有:

[math]\displaystyle{ \mathbb{E}\left[\sum_{i=1}^NX_i\right]= \mathbb{E}[N]\cdot\mu }[/math]