介绍
随机游走感觉其实就是markov process。它的数学定义是 $X_i$ 是IID的rv， $S_n = X_1 + X_2 +...+X_n$ 。将integer-time process $S_n$ 成为随机游走，或者说是基于 $X_i$ 的一维随机游走。
随机游走有2个重要的应用领域：queue delay和detection problem。
queue delay
还是考虑一个G/G/1 queue如下图：
令 $U_n = Y_{n-1}-X_n$ 。则
$$\begin{aligned}
W_n &= max[W_{n-1}+Y_{n-1}-X_n, 0]\\
&= max[W_{n-1}+U_n, 0]\\
&= max[max[W_{n-2}+U_{n-1}, 0] + U_n, 0]\\
&= max[(W_{n-2}+U_{n-1}+U_n), U_n, 0]\\
&= max[(W_{n-3}+U_{n-2}+U_{n-1}), (U_n+U_{n-1}), U_n,0]\\
&= ...\\
&= max[(U_1+U_2+..+U_n),(U_2+..+U_n),...,U_n]
\end{aligned}$$
令 $Z_i^n = U_n+U_{n-1}+...+U_{n-i+1}$ ，则
$$W_n = max[0,Z_1^n, Z_2^n,...,Z_n^n]\\
Pr\left\{W_n \ge \alpha\right\} = Pr\left\{max[0,Z_1^n, Z_2^n,...,Z_n^n] \ge \alpha\right\}$$
根据随机游走的定义，可知 $Z_i^n$ 就是一种随机游走。而 $W_n \ge \alpha$ 即 随机游走在第n次trial之前大于thresold $\alpha$
detection problem
和ml里面的贝叶斯判别差别不大，只不过是在随机过程中换了个名字，叫hypothesis testing。我们在这里只考虑H有2种取值。对于每一个假说H都有2种可能的取值，0和1，其PMF分别为 $p_H(0) = p_0, p_H(1) = p_1 = 1-p_0$
令 $Y=(Y_1, Y_2, ... Y_n)$ 表示n个观测，都是基于 $H=0\text{或}1$ 产生的并且其联合概率分布$f_{Y|H}(y|0),f_{Y|H}(y|1)$ 均大于0. 联合概率分布的定义为 $f_{Y|H}(y|l) = \prod_{i=1}^n f_{Y|H}(y_i|l)$
所以根据贝爷的定律，有：
$$Pr\left\{H=0|y\right\} = \dfrac{p_0f_{Y|H}(y|0)}{p_1f_{Y|H}(y|0) + p_0f_{Y|H}(y|0)}\\
\dfrac{Pr\left\{H=0|y\right\}}{Pr\left\{H=1|y\right\}} = \dfrac{p_0f_{Y|H}(y|0)}{p_1f_{Y|H}(y|1)}$$
当上面的比值大于1时，我们认为 $\hat{h} = 0$ ；小于1时认为 $\hat{h} = 1$ ；等于1时就都一样了。这种选法被称为MAP(Maximum a posteriori probability)
定义 $\Lambda(y) = \dfrac{f_{Y|H}(y|0)}{f_{Y|H}(y|1)}$ ，则我们可以将MAP表示为：
$$\Lambda(y) =
\begin{cases}
>p_1/p_0& \text{select}\hat{h} = 0\\
\le p_1/p_0& \text{select}\hat{h} = 1
\end{cases}$$
令 $z_i = \ln\dfrac{f_{Y|H}(y_i|0)}{f_{Y|H}(y_i|1)}$ ，MAP可以表示为：
$$\sum_{i=1}^n z_i =
\begin{cases}
>p_1/p_0& \text{select}\hat{h} = 0\\
\le p_1/p_0& \text{select}\hat{h} = 1
\end{cases}$$
如果我们令 $\eta = p_1/p_0$ ，则MAP就是一个threshold test。
当然，我们也可以根据错误进行。我们可以让 $Pr\left\{e|H=1\right\}$ 和 $Pr\left\{e|H=0\right\}$ 低于某个上界 $\alpha$ 。这被称为Neyman-Pearson rule。
对于一个test，我们定义 A 为由hypothesis 1产生的观测，则错误率为：
$q_0(A) = Pr\left\{Y\in A|H=0\right\};q_1(A) = Pr\left\{Y\in A^c|H=1\right\}$
所以错误的概率 $Pr\left\{e(A)\right\} = p_0q_0(A) + p_1q_1(A)$
如果test是threshold test，则 $A = \left\{y:\dfrac{f_{Y|H}(y|0)}{f_{Y|H}(y|1)}\le\eta\right\}$ 。对于一个threshold test来说， $\eta$ 至关重要。所以我们用 $\eta$ 表示threshold test。
对于任意一个test A和threshold test $0<\eta<\infty$ ， $(q_1(A), q_0(A))$ 必在直线 $y = -\eta x + q_0(\eta)+\eta q_1(\eta)$ 上方(如下图所示)
令 $u(\alpha) = \sup_{0\le \eta < \infty} q_0(\eta)+\eta(q_1(\eta)-\alpha)$ ，则如下图所示：
Neyman-Pearson test是在 $q_0(A)$ 的一些限制下，选择A以最小化 $q_1(A)$ 。这也是一个threshold test。
一个小例子
最简单的例子：只有观测只有一个维度的数据，不同hypothesis产生观测的概率为：
$p_{Y|H}(0|0)=p_{Y|H}(1|1) = \frac{2}{3}; p_{Y|H}(1|0)=p_{Y|H}(1|0) = \frac{1}{3}$
根据MAP的判断条件，可知： 当 $p_1 < 1/3$ 时，必有 $\hat{h} = 0$ ；当 $p_1 \ge 2/3$ 时，必有 $\hat{h} = 1$ 。只有在两者之间时，才需要进行判断；对于 $\eta$ 来说，是一样的。所以对于这种情况，图就变成了：
随机游走中的threshold crossing问题
令 $X_i$ 表示IID的rv，$S_n=X_1+X_2+...+X_n$ 表示随机游走， $g_X(r) = E[e^{rX}]$ 为MGF， $r_-, r_+$ 表示 $g_X(r)$ finite的下界和上界。threshold crossing考虑的问题为 $Pr\left\{\bigcup_{n=1}^\infty S_n\ge \alpha\right\}$
即随机游走的值大于threshold $\alpha$ 的概率。
我们在这里假设 $\bar{X} < 0$ ，但是$X$ 取正取负的概率均大于0
Chernoff bound
在前面曾经讨论过Chernoff bound：
$Pr\left\{S_n \ge na\right\}\le \exp(n[\gamma_X(r)-ra])$
其中 $\gamma_X(r) = \ln g_X(r)$
tightest bound为
$Pr\left\{S_n \ge na\right\}\le \exp(n\mu_X(a))\quad \mu_X(a) = \inf_{r\in(0, r_+)} \gamma_X(r)-ra$
可以发现 $\gamma_X''(r)>0$ ，故可将图像表示为：
所以 $Pr\left\{S_n \ge na\right\}\le \exp(n[\gamma(r_0)-r_0\gamma'(r_0)]), \gamma'(r_0)=a$
作进一步的替换可以得到
$$\begin{equation}
\label{eq:basic1}
Pr\left\{S_n \ge n\gamma'(r)\right\}\le \exp(n[\gamma(r)-r\gamma'(r)])
\end{equation}$$
Tilted probabilities
和上面一样， $X_n$ 为IID的rv， $g_X(r)$ 在 $(r_-,r_+)$ 范围内finite。在 $r\in(r_-,r_+)$ ，定义 $X$ 的tilted PMF为
$q_{X,r(x)} = p_X(x)\exp[rx-\gamma(r)]$
易知： $q_{X,r(x)} \ge 0$ 且 $\sum_x q_{X,r(x)} = \sum_x p_X(x)e^{rx}/E[e^{rx}] = 1$ ，这是满足定义的。
所以有
$q_{X^n,r(x_1,...,x_n)} = p_{X^n}(x_1,...,x_n)\exp(\sum_{i=1}^n[rx_i-\gamma(r)])$
而 $S_n = \sum_{i=1}^n x_n$ ，故
$q_{S_n, r(S_n)} = p_{S_n}(S_n)\exp[rs_n-n\gamma(r)]$
将tilted PMF下的期望记为 $E_r[X]$ 。则
$$\begin{aligned}
E_r[X] &= \sum_x xq_{X,r(x)} = \sum_x xp_X(x)\exp[rx-\gamma(r)]\\
&= \frac{1}{g_X(r)}\sum_x\frac{d}{dr} p_X(x)\exp[rx]\\
&= \frac{g_X'(r)}{g_X(r)} = \gamma'(r)
\end{aligned}$$
根据WLLN( $\lim_{n\to\infty}Pr\left\{|\frac{S_n}{n}-\bar{X}|>\epsilon\right\} = 0$ )，有
$$\begin{aligned}
1-\delta &\le \sum_{(\gamma'(r)-\epsilon)n \le s_n \le (\gamma'(r)-\epsilon)n} q_{S_n, r(s_n)}\\
& = \sum_{(\gamma'(r)-\epsilon)n \le s_n \le (\gamma'(r)-\epsilon)n} p_{S_n}(s_n) \exp[rs_n-n\gamma(r)]\\
& \le \sum_{(\gamma'(r)-\epsilon)n \le s_n \le (\gamma'(r)-\epsilon)n} p_{S_n}(s_n) \exp[n(r\gamma'(r)+r\epsilon-\gamma(r))]\\
& \le \sum_{(\gamma'(r)-\epsilon)n \le s_n} p_{S_n}(s_n)\exp[n(r\gamma'(r)+r\epsilon-\gamma(r))]\\
& = \exp[n(r\gamma'(r)+r\epsilon-\gamma(r))]Pr\left\{S_n \ge n(\gamma'(r)-\epsilon)\right\}
\end{aligned}$$
故
$Pr\left\{S_n \ge n(\gamma'(r)-\epsilon)\right\}\ge(1-\delta)\exp[n(\gamma(r) - r\gamma'(r) - r\epsilon)]$
回到threshold crossing
我们取 $r_0$ 使得 $\gamma'(r_o) = \alpha/n$ 。在此情况下，有：
$$\begin{equation}
\label{eq:basic2}
Pr\left\{S_n\ge \alpha\right\}\le \exp\left\{\alpha \Bigg[\frac{\gamma(r_o)}{\gamma'(r_o)}-r_o\Bigg]\right\}
\end{equation}$$
下图给出了其几何解释：
我们可以看到当 $n$ 很大时，slope很小，所以 $r_o$ 很小，水平的截断很大；当 $n$ 开始减小时， $r_o$ 开始增加，水平截断开始减小直到 $r_o = r^*$ ；在这之后， $r_o$ 继续增加，但是水平截断此时也开始增加。
从上面的描述可以发现：$r^*$ 是水平截断最小时 $r$ 的取值。所以有
$Pr\left\{S_n\ge \alpha\right\} \le \exp(-r^* \alpha) \quad \text{for }\alpha > 0, n\ge 1$
现在我们讨论 $r_+<\infty$ 的情况。这时我们需要考虑2种情况： $\gamma(r_+)$ 是否为 finite。对于 $\gamma(r_+)=\infty$ 的情况，当 $r\to r_+$ 时， $\gamma(r)\to\infty$ 。故 $r^*$ 必然存在；对于 $\gamma(r_+)<\infty$ ，如下图所示，如果 $r_o<r_+$，则 \ref{eq:basic1} 和 \ref{eq:basic2} 仍然成立。如果对于所有的 $r<r_+$ 都有 $\alpha/n > \gamma'(r)$ ，则我们可以进一步优化不等式为：
$Pr\left\{S_n \ge \alpha\right\}\le\exp\left\{n[\gamma(r_+)-r_+\alpha/n]\right\} = \exp\left\{\alpha[\gamma(r_+)n/\alpha-r_+]\right\}$
如果我们将 $r^*$ 的定义修改为 $\sup_{r>0}\gamma(r)<0$ ，这样两个式子就得到了统一。这样的情况下就可以计算 thresold crossing的问题了。不过这么算很麻烦，不够优雅(°д°) 接下来介绍一种优雅的方法
Wald’s identity
我们在这里定义2个 thresold $\alpha>0, \beta<0$ , thresold crossing问题在这里变成了 crossing其中任意一个 thresold 的问题(如下图)。
令 $X_i$ 为 IID 的 rv ，但是不全为0(不太能理解不全为0不就不是 IID 了么(・・))，$S_n = X_1+X_2+...+X_n$ ，$\alpha>0,\beta <0$ ，$J$ 是最小的使得 $S_n\ge\alpha$ 或 $S_n\le\beta$ 的 $n$ .则 $J$ 是 rv (即 $\lim_{m\to\infty}Pr\left\{J \ge m\right\} = 0$),且各阶矩均为 finite.
这个的证明比较 trike.由于 $X$ 不全为0,故必存在一些 $n$ 使得 $Pr\left\{S_n \le -\alpha+\beta\right\} > 0,\ Pr\left\{S_n \le \alpha-\beta\right\} > 0$ .在这种情况下,我们定义 $\epsilon = \max[Pr\left\{S_n \le -\alpha+\beta\right\}, Pr\left\{S_n \le \alpha-\beta\right\}]$
对于任何一个 $k\ge 1$, 假设 $J>n(k-1),\ S_{n(k-1)}\in(\beta, \alpha)$ ,则有:
$$Pr\left\{J>nk|J>n(k-1)\right\} \le 1-\epsilon\\
\Rightarrow Pr\left\{J>nk\right\}\le (1-\epsilon)^k$$
故 $J$ 为 rv,且 $g_J(r)$ 在 $r=0$ 时连续,故各阶矩均存在
Wald’s identity
有了前面的定义后,我们在来谈本节的主角:Wald’s identity.定理表述如下:
令 $X_i$ 为 IID 的 rv, $\gamma(r)=\ln\left\{E[e^{rX}]\right\}$ ,且在 $r_-<0<r_+$ 范围内 finite. 令 $S_n = X_1+X_2+...+X_n, \ \alpha>0,\ \beta<0,\ J$ 为最小的令 $S_n\ge\alpha$ 或 $S_n\le\beta$ 的 $n$ .对于所有的 $r \in (r_-,r_+)$, 都有
$E[\exp(rS_J-J\gamma(r))]=1$
证明:我们使用前面提到过的 tilted PMF, 令 $X^n = (X_1, X_2,...,X_n)，\ s_n = \sum_{i=1}^n x_i$ .则：
$q_{X^n, r(x^n)} = p_{X^n}(x^n)\exp[rs_n-n\gamma(r)]$
令 $\mathcal{T}_n$ 表示 $X_1,X_2,...,X_n$ 满足情况 $\beta<S_i<\alpha \text{ for }1\le i<n$ 且 $S_n\ge\alpha$ 或 $S_n\le\beta$ 。所以 stopping trial $J$ 的 tilted PMF 为
$$\begin{aligned}
q_{J,r(n)} &= \sum_{x^n\in\mathcal{T}_n} q_{X^n,r(x^n)} = \sum_{x^n\in\mathcal{T}_n} p_{X^n}(x^n)\exp[rs_n-n\gamma(r)]\\
&= E[\exp[rS_n-n\gamma(r)|J=n]]Pr\left\{J=n\right\}
\end{aligned}$$
等式两边对 $n$ 求和即可
与 Wald’s equality 的关系
我们在 renewal process 中提到了Wald’s equality( $E[S_J] = \bar{X}E[J]$ ).我们对 Wald’s identity 两边求导，可得：
$E[S_J - J\gamma'(r)]\exp \left\{rS_J-J\gamma(r)\right\}= 0$
令 $r=0$ ，即可得到 Wald’s equality。如果我们取2阶导，可得：
$E[(S_J-J\gamma'(r))^2-J\gamma''(r)]\exp \left\{rS_J-J\gamma(r)\right\}= 0$
同样令 $r=0$ ，可得：
$E[S_J^2 - 2JS_J\bar{X} + J^2\bar{X}^2] = \sigma^2_XE[J]\\$
当 $\bar{X}=0$ 时，原式可以简化为 $E[S^2_J] = \sigma^2_XE[J]$
来考虑一个特殊情况
上面我们为了简化结果，假设 $\bar{X}=0$ 。对于随机游走，我们也考虑这种情况，假设 $Pr\left\{X=1\right\}=1/2,\ Pr\left\{X=-1\right\}=1/2$ 且 thresold $\alpha,\ \beta$ 均为整数。故 $S_n$ 在 crossing thresold之前，必然先是 thresold 。因此我们可以将 stopping trial 定义为 $S_J = \alpha$ 或 $S_J = \beta$ 。令 $q_\alpha = Pr\left\{S_J=\alpha\right\}$ ，则 $S_J$ 的期望为 $\alpha q_\alpha + \beta(1-q_\alpha)$ 。根据 Wald’sequality, $E[S_J] = 0$ 。故有：
$$q_\alpha = \dfrac{-\beta}{\alpha-\beta}\quad 1-q_\alpha = \dfrac{\alpha}{\alpha-\beta}\\
\Rightarrow \sigma^2_XE[J] = E[S_J^2] = \alpha^2q_\alpha + \beta^2(1-q_\alpha)\\
\Rightarrow E[J] = -\beta\alpha/\delta^2_X = -\beta\alpha$$
thresold crossing 的指数边界
在满足 Wald’s identity 的基础上，如果 $\bar{X}<0$ 且对于 $r^* > 0$ 有 $\gamma(r^* ) = 0$ ，则有：
$Pr\left\{S_J\ge\alpha\right\}\le\exp(-r^* \alpha)$
证明：既然要满足 Wald’s identity，那么自然是要用的。我们令 $r = r^*$ ，则Wald’s identity可以化为 $E[\exp(r^* S_J)]=1$ 。而该式可以被表示为：
$$Pr\left\{S_J\ge\alpha\right\}E[\exp(r^* S_J)|S_J\ge\alpha] + Pr\left\{S_J\le\beta\right\}E[\exp(r^* S_J)|S_J\le\beta] = 1\\
\Rightarrow Pr\left\{S_J\ge\alpha\right\}E[\exp(r^* S_J)|S_J\ge\alpha]\le 1\\
\Rightarrow Pr\left\{S_J\ge\alpha\right\}\exp(r^* \alpha)\le 1$$
我们同样可以推导得到 $\beta$ 的不等式
将上面的理论运用到 G/G/1 queue中，我们可以得到Kingman Bound：
令 $X_i, Y_i$ 分别表示到达间隔和服务时间，队列初始为空，用户在0时刻到达。令 $U_i = Y_{i-1}-X_i, \gamma(r) = \ln\left\{E[e^{Ur}]\right\}$ 。假设存在 $r^* >0$ 使得 $\gamma(r) = 0$ 。令 $W_n$ 表示第 n 个顾客达到时队列的 queue delay。则：
$Pr\left\{W_n\ge \alpha\right\}\le Pr\left\{W\ge \alpha\right\}\le\exp(-r^* \alpha)$
对于 $\bar{X}>0$ 我们可以通过交换符号的方式来处理 $S_J<\beta$ 的情况。但是 $\bar{X}=0$ 就不好做了。考虑 $Pr\left\{S_J\le \beta\right\} = 1-Pr\left\{S_J\ge \alpha\right\}$ 。则可以解出
$Pr\left\{S_J\ge \alpha\right\} = \dfrac{1-E[\exp(r^* S_J)|S_J\le\beta] }{E[\exp(r^* S_J)|S_J\ge\alpha] -E[\exp(r^* S_J)|S_J\le\beta] }$
由于 $\alpha,\beta$ 均为整数，故有 $E[\exp(r^* S_J)| S_J\le\beta] = \exp(r^* \beta),\ E[\exp(r^* S_J)| S_J\ge\alpha] = \exp(r^* \alpha)$ 。故
$Pr\left\{S_J\ge \alpha\right\} = \dfrac{\exp(-r^* \alpha)[1-\exp(r^* \beta)] }{1 -\exp[-r^* (\alpha-\beta)] }$
binary hypothesis test
我们在前面讨论过 hypothesis test ，在这里主要讨论如何基于已有观测进行决策以及什么时间应该停止观测。首先回忆一下我们前面的定义：
$p_H(0) = p_0,\ p_H(1) = p_1$ 。给定 $n$ 个观测 $y_1, y_2, ...,y_n$ ，有 likelihood ratio
$\Lambda_n(y) = \prod_{i=1}^n \dfrac{f_{Y|H}(y_n|0)}{f_{Y|H}(y_n|1)}$
在此基础上，我们定义 log-likelihood-ratio:
$s_n = \sum_{i=1}^n z_n;\quad z_n =\ln\dfrac{f_{Y|H}(y_n|0)}{f_{Y|H}(y_n|1)}$
我们给出选择标准：
$$s_n
\begin{cases}
> \ln(p_1/p_0) & \hat{h} = 0\\
\le \ln(p_1/p_0) & \hat{h} = 1
\end{cases}$$
这就又成了 thresold crossing 的问题。即， $Pr\left\{e|H=1\right\} = Pr\left\{S_n \ge \ln(p_1/p_0)|H=1\right\}$ 。在此情况下，$\gamma_1(r)\text{ of } Z \text{ given }H=1$ 可以表示为：
$$\begin{aligned}
\gamma_1(r) &= \ln\int_y f_{Y|H}(y|1)\exp\left\{r\Bigg[\ln \dfrac{f_{Y|H}(y|0)}{f_{Y|H}(y|1)}\Bigg]\right\}dy\\
&= \ln\int_y [f_{Y|H}(y|1)]^{1-r}[f_{Y|H}(y|0)]^r dy
\end{aligned}$$
可以发现 $\gamma_1(1) \ln\int_yf_{Y|H}(y|0)dy=0$ ，即 $r^* = 1$ 。用Chernoff bound可得：
$Pr\left\{e|H=1\right\}\le\exp\left\{n(\min_r\gamma_1(r)-ra)\right\}\quad a = \dfrac{1}{n}\ln(p_1/p_0)$
上面不等式可以用下图表示：
同样的，我们可以找到 $Pr\left\{e|H=0\right\}$ 。首先
$\gamma_0(r)= \ln\int_y [f_{Y|H}(y|1)]^{-r}[f_{Y|H}(y|0)]^{1+r} dy$
可以发现 $\gamma_0(r)=\gamma_1(r-1)$ 。故
$Pr\left\{e|H=0\right\}\le\exp\left\{n[\min_r\gamma_1(r)+(1-r)a]\right\}$
再一次观测结束之后，我们可以有3种选择：接受 hypothesis 1, 接受 hypothesis 2或者继续实验。我们在前面研究了前两个选项，我们在这里研究第三个选项。这显然是一个 stopping trial。
我们假设当 stopping 发生时， $\hat{h} = 0 \text{ if } S_J>\alpha$ ，$\hat{h} = 1 \text{ if } S_J<\beta$ 。则错误判断的概率分别为：
$$Pr\left\{e|H=1\right\} = Pr\left\{S_J\ge \alpha|H=1\right\} \le \exp-\alpha\\
Pr\left\{e|H=0\right\} = Pr\left\{S_J\le \beta|H=0\right\} \le \exp\beta$$
随着我们增加 $\alpha,\beta$ ，错误率会越来越低。
根据 Wald’s equality ，有：
$E[J|H=0] = \dfrac{E[S_J|H=0]}{E[Z|H=0]} \approx\dfrac{\alpha + E[overshoot]}{E[Z|H=0]}$
上式种我们忽视了 crossing thresold $\beta$ 的概率，因为 $\alpha$ 和 $\beta$ 很大的情况下，这种概率很小。
crossing time 以及 barrier 的联合分布
最后我们考察 $Pr\left\{J\ge n, S_J \ge \alpha\right\}$ 。同样假设 $\bar{X}<0$ ，对于部分 $r^* > 0$ ，有 $\gamma(r)\le 0$ 。对于 $0\le r\le r^* ,J
\ge n$，有$-J\gamma(r)\ge -n\gamma(r)$ 根据 Wald identity，有
$$\begin{aligned}
1 &\ge E[\exp[rS_J-J\gamma(r)]|J\ge n, S_J \ge \alpha] Pr\left\{J\ge n, S_J \ge \alpha\right\}
&\ge \exp[r\alpha-n \gamma(r)]Pr\left\{J\ge n, S_J \ge \alpha\right\}
\end{aligned}$$
$\Rightarrow Pr\left\{J\ge n, S_J \ge \alpha\right\} \le \exp[n \gamma(r) - r\alpha]$
因为 $r\in(0, r^* ]$ ，我们可以获得上式的 tightest bound。 定义 $n^* = \alpha/\gamma'(r^* )$ ，则：
$$Pr\left\{J\ge n, S_J \ge \alpha\right\} \le
\begin{cases}
\exp[n\gamma(r_o) -r_o\alpha] & \text{for }n> n^* , \alpha/n = \gamma'(r_o)\\
\exp[-r^* \alpha] & n \le n^*
\end{cases}$$
Martingales
Martingales 是一种 integer-time 随机过程，定义为 $Z_n$ ，满足 $E[|Z_n|] < \infty$ 且
$E[Z_n|Z_{n-1},Z_{n-2},...,Z_1] = Z_{n-1}$
对于上面的定义，一般有两种解读的视角：第一种就是直接来看， $E[Z_n|Z_{n-1}=z_{n-1},Z_{n-2}=z_{n-2},...,Z_1=z_1] = z_{n-1}$ ；第二种将 $E[Z_n|Z_{n-1},Z_{n-2},...,Z_1]$ 看做一个函数。第二种看法更加复杂，必然也更加强大。
Martingales 和 markov 很像，不过前者是期望，后者是概率。
一些例子
Martingales 可能是我目前看到的随机过程里面最抽象的一个了。所以举几个例子加深一下印象
Random walk
martingale 的例子之一就是0期望的随机游走。这一点很容易看到：
$$\begin{aligned}
E[Z_n|Z_{n-1}, Z_{n-2},...,Z_1] &= E[X_n+Z_{n-1}|Z_{n-1}, Z_{n-2},...,Z_1]
&= E[X_n]+Z_{n-1} = Z_{n-1}
\end{aligned}$$
当然，对于任意的 rv $X$ 来说，令 $Z_n = S_n-n\bar{X}$ 也可以做到这一点。
Sums of dependent zero-mean variables
令 $X_i$ 为相关的 rv 且满足 $E[X_i|X_{i-1},...,X_1] = 0$ ，$Z_n = X_1+X_2+...+X_n$ 。则：
$$\begin{aligned}
E[Z_n|Z_{n-1},...,Z_1] &= E[X_n+Z_{n-1}|Z_{n-1},...,Z_1]\\
&= E[X_n|Z_{n-1},...,Z_1] + E[Z_{n-1}|Z_{n-1},...,Z_1]
&= Z_{n-1}
\end{aligned}$$
Product-form martingales
和上面的差不多，不过是把加法换成了乘法，即 $Z_n=X_1X_2...X_n$ 如果 $X_i$ 的均值为1，则：
$$\begin{aligned}
E[Z_n|Z_{n-1},...,Z_1] &= E[X_nZ_{n-1}|Z_{n-1},...,Z_1]\\
&=E[X_n]E[Z_{n-1}|Z_{n-1},...,Z_1] = Z_{n-1}
\end{aligned}$$
乘法的 martingale 有一个很重要应用。 我们假设 $X_i$ 为 IID ，$S_n = X_1+X_2+...+X_n$ 为随机游走， $\gamma(r) = \ln\left\{E[\exp(rX)]\right\}$ 。定义 $Z_n$ 为
$$\begin{aligned}
Z_n &= \exp\left\{rS_n-n\gamma(r)\right\}\\
&= \exp\left\{rX_n-\gamma(r)\right\}\exp\left\{rS_{n-1}-(n-1)\gamma(r)\right\}\\
&=\exp\left\{rX_n-\gamma(r)\right\} Z_{n-1}
\end{aligned}$$
故
$E[Z_n|Z_{n-1},...,Z_1] = E[\exp\left\{rX_n-\gamma(r)\right\}]E[Z_{n-1}|Z_{n-1},...,Z_1] = Z_{n-1}$
branching process
我们之前曾经讨论过branching process。branching process可以抽象为两个变量，其中 $Y_{i,n}$ 为 IID， $X_{n+1} = \sum_{i=1}^{X_n}Y_{i,n}$ 。
令 $\bar{Y}=E[Y_{i,n}]$ ，则 $E[X_n|X_{n-1}]=\bar{Y}X_{n-1}$ 。我们定义 $Z_n=X_n/\bar{Y}^n$ ，则：
$E[Z_n|Z_{n-1},...,Z_1] = E[\dfrac{X_n}{\bar{Y}^n}|X_{n-1},...,X_1]= \dfrac{\bar{Y}X_{n-1}}{\bar{Y}^n} = Z_{n-1}$
可以看到，$Z_n$ 也是 martingale
过去和未来的 partial isolation
令 $Z_n$ 为 martingale 对于任意的 $1\le i <n$ ，有
$E[Z_n|Z_i, Z_{i-1},...,Z_1] = Z_i$
证明：对于 $n=i+1$ ，有 $E[Z_{i+1}|Z_i,...,Z_1] = Z_i$ 。我们可以用下面的方法计算 $E[Z_{i+2}|Z_i,...,Z_1]$ :
$$\begin{aligned}
E[Z_{i+2}|Z_i,...,Z_1] &= E[E[Z_{i+2}|Z_{i+1},...,Z_1]|Z_i,...,Z_1] \\
&= E[Z_{i+1}|Z_i,...,Z_1] = Z_i
\end{aligned}$$
同样的方法可以用来计算 $E[Z_{i+3}|Z_i,...,Z_1]$ 等等。当然最后我们有：
$E[Z_n] = E[Z_1]$
用在前面乘法的例子种，可以得到：
$$\begin{aligned}
E[\exp(rS_n-n\gamma(r))] &= E[\exp(rX-\gamma(r))]\\
&= E[\exp(rX)]/g(r) = 1
\end{aligned}$$
submartingale 以及 supermartingale
submartingale 和 supermartingale都是martingale最简单的泛化。具体的定义如下：
同样对于integer-time随机过程 $Z_n$ 满足 $E[|Z_n|]<\infty$ ，如果满足 $E[Z_n|Z_{n-1}, Z_{n-2},...,Z_1] \ge Z_{n-1}$ ，则是submartingale；如果满足 $E[Z_n|Z_{n-1}, Z_{n-2},...,Z_1] \le Z_{n-1}$ ，则是supermartingale。
注意到martingale同时满足两个定义，所以它既是 submartingale ，也是 supermartingale 。如果 $Z_n$ 为submartingale ，则 $-Z_n$ 为 supermartingale。
对于partial isolation，修改如下：
令 $1\le i < n$ ，对于submartingale有 $E[Z_n|Z_i,...Z_1]\ge Z_i$ ；对于supermartingale有 $E[Z_n|Z_i,...Z_1]\le Z_i$ 。
随机游走 S_n 是 submartingale, martingale, supermartingale 分别对应 $\bar{X}\ge 0, \bar{X}= 0, \bar{X}\le 0$ ；同样如果存在semi- invariant moment generating function $\gamma(r)$ ，定义 $Z_n = \exp(rS_n)$ ，$Z_n$ 为 submartingale, martingale, supermartingale 分别对应 $\gamma(r) \ge 0,\gamma(r) = 0 ,\gamma(r) \le 0$
如果 $h(x)$ 为凸函数，对于 submartingale 或者 martingale $Z_n$ ，$h(Z_n)$ 也是 submartingale 。证明很简单，直接用Jensen不等式就行了。
stopped processes and stopping trials
在 renewal process 中我们讨论过 stopping trial 。如果 $J$ 是一个defective rv，那么将 $J$ 称为defective stopping trial(即该过程必然终止)。如果没有说明，我们将 $J$ 称为possibly-defective stopping trial 。
对于 possibly-defective stopping trial $J$ 我们定义 stopped process $Z_n^* = Z_n$ 如果 $J\ge n$ 否则 $Z_n^* = Z_J$ 。
对于 $Z_n^*$ 和 $Z_n$ 来说，如果 $Z_n$ 为 submartingale，$Z_n^*$ 也是 submartingale 。对于其他两种情况也一样。
给定一个随机过程 $Z_n$, possibly-defective stopping trial $J$ ，则我们可以找到对应的 $Z_n^*$ 。其与 $Z_n$ 的关系如下：
$$E[Z_1] \le E[Z_n^*] \le E[Z_n] \quad \text{(submartingale)} \\
E[Z_1] = E[Z_n^*] = E[Z_n] \quad \text{(martingale)} \\
E[Z_1] \ge E[Z_n^*] \ge E[Z_n] \quad \text{(supermartingale)} \\$$
令 $J$ 为 martingale $Z_n$ 的 stopping trial ，则 $E[Z_n] = E[Z_1]$ 当且仅当
$\lim_{n\to\infty}E[Z_n|J>n]Pr\left\{J>n\right\} = 0,\ E[|Z_J|] < \infty$
The Kolmogorov inequalities
Kolmogorov’s submartingale inequalities 表述如下：
$Z_n$ 为非负的 submartingale，对于所有的正整数 $m$ 以及正数 $a$ ,都有$Pr\left\{\max_{1\le i \le m} Z_i\ge a\right\} \le \dfrac{E[Z_m]}{a}$
证明： 对于一个非负的 martingale $Z_n$ ，给定正数 $a$ 和正整数 $m$ ，我们定义 stopping trial $J$ 为 最早的 $n\le m$ 满足 $Z_n\ge a$ 。如果对于所有的 $n\le m,\ Z_n<a$ 则 $n=m$ 。所以 $J$ 必然会在 $m$ 停止。故：
$Pr\left\{\max_{1\le i \le m}Z_i\ge a\right\} = Pr{Z_J\ge a}\le \dfrac{E[Z_J]}{a}$
由于 $J$ 必在 $m$ 停止，故 $Z_J = Z_m^*$ 。而 $E[Z_m^*]\le E[Z_m]$ 带入原式即得证。
从这个不等式出发，我们可以推导出一系列不等式。
一些衍生的不等式
Nonnegative martingale inequality
令 $Z_n$ 为非负的martingale， $a>0$ 则：
$Pr\left\{\sup_{n \ge 1} Z_n\ge a\right\} \le \dfrac{E[Z_1]}{a}$
Kolmogorov’s martingale inequality
令 $Z_n$ 为 martingale 满足 $E[Z_n^2]<\infty$， $b>0,m >1$ 故
$Pr\left\{\max_{1\le n \le m} |Z_n|\ge b\right\} \le \dfrac{E[Z_m^2]}{b^2}$
Kolmogorov’s random walk inequality
$X_i$ 为 IID 的 rv，均值为 $\bar{X}$ ，方差为 $\sigma^2$ ，$S_n=X_1+X_2+...+X_n$ 。对于任意正整数 $m$ 和正数 $\epsilon$ ，有：$Pr\left\{\max_{1\le n \le m} |S_n-n\bar{X}|\ge m\epsilon\right\}\le \dfrac{\sigma^2}{m\epsilon^2}$
还有2个没名字的
$S_n=X_1+X_2+...+X_n$ 为随机游走， $X_i$ 有均值 $\bar{X}$ 和 semi-invariant moment generating function $\gamma(x)$ 。对于任意一个 $r>0$ 满足 $0<\gamma(r)<\infty$ ， $a>0$ ，有：$Pr\left\{\max_{1\le n \le m}S_i\ge\alpha\right\}\le \exp\left\{-r\alpha + n\gamma(r)\right\}$
令 $Z_n$ 为非负的 submartingale，对于任意的正整数 $m$ 和 $a>0$ ，都有
$Pr\left\{\bigcup_{i\ge m}\left\{Z_i\ge a\right\}\right\}\le \dfrac{E[Z_m]}{a}$
SLLN
之前曾经证明过4阶矩存在时的SLLN，这里我们们削弱一下条件，证明二阶矩存在即可。
首先还是说明下SLLN。令 $X_i$ 为 IID 的 rv，均值为 $\bar{X}$ ，方差为 $\sigma^2<\infty$ ，令 $S_n = X_1+X_2+...+X_n$ 。则对于任意的 $\epsilon > 0$ 都有
$$Pr\left\{\lim_{n\to\infty}\dfrac{S_n}{n}=\bar{X}\right\} = 1\\
\lim_{n\to\infty}Pr\left\{\bigcup_{m > n}\bigg|\dfrac{S_m}{m}-\bar{X}\bigg|>\epsilon\right\} = 0$$
当然了，这两个式子是等价的，所以我们只要证明后一个就好了
$$\begin{aligned}
Pr\left\{\bigcup_{m > 2^k}\bigg|\dfrac{S_m}{m}-\bar{X}\bigg|>\epsilon\right\} &= Pr\left\{\bigcup_{j=k}^\infty\bigcup_{m=2^j+1}^{2^{j+1}}\bigg|\dfrac{S_m}{m}-\bar{X}\bigg|>\epsilon\right\}\\
&\le \sum_{j=k}^\infty Pr\left\{\bigcup_{m=2^j+1}^{2^{j+1}}\bigg|\dfrac{S_m}{m}-\bar{X}\bigg|>\epsilon\right\}\\
&= \sum_{j=k}^\infty Pr\left\{\bigcup_{m=2^j+1}^{2^{j+1}}|S_m-m\bar{X}|>\epsilon m\right\}\\
&\le \sum_{j=k}^\infty Pr\left\{\bigcup_{m=2^j+1}^{2^{j+1}}|S_m-m\bar{X}|>\epsilon 2^j\right\}\\
&= \sum_{j=k}^\infty Pr\left\{\max_{2^j+1\le m \le 2^{j+1}}|S_m-m\bar{X}|>\epsilon 2^j\right\}\\
&\le \sum_{j=k}^\infty Pr\left\{\max_{1\le m \le 2^{j+1}}|S_m-m\bar{X}|>\epsilon 2^j\right\}\\
&\le \sum_{j=k}^\infty \dfrac{2^{j+1}\sigma^2}{\epsilon^22^{2j}} = \dfrac{2^{-k+2}\sigma^2}{\epsilon^2}
\end{aligned}$$
martingale convergence theorem
由Kolmogorov submartingale inequalit可以推出的非常重要的结论，表述如下：
$Z_i$ 为 martingale 且存在 $M<\infty$ 使得 $E[Z_n^2]\ge M$ 。则存在一个 rv $Z$ 使得 $\lim_{n\to\infty}Z_n=Z$证明：易知，$Z_i$ 也是 submartingale 。因此 $E[Z_n^2]$ 在 $n$ 上递增。由于 $E[Z_n^2]\ge M$ 故必有 $\lim_{n\to\infty}E[Z_n^2] = M'$ 。由于对于任意正整数$k$ $Y_n = Z_{k+n}-Z_k$ 是均值为0的martingale，因此
$Pr\left\{\max_{1\le n \le m}|Z_{k+n}-Z_k|\ge b\right\}\le \dfrac{E[(Z_{k+m}-Z_k)^2]}{b^2}$
由 $E[Z_{k+m}Z_k|Z_k = z_k, Z_{k-1}=z_{k-1},...,Z_1=z_1] = z_k^2$ 故 $E[(Z_{k+m}-Z_k)^2] = E[Z_{k+m}^2]-E[Z_{k}^2]\le M'-E[Z_{k}^2]$ 。故
$Pr\left\{\sup_{n \ge 1}|Z_{k+n}-Z_k|\ge b\right\}\le \dfrac{M'-E[Z_k^2]}{b^2} = 0$
故
$Pr\left\{\sup_{n \ge 1}|Z_{k+n}-Z_k|\ge b\right\} = 0$