D.6 Azuma 不等式

D.6 Azuma 不等式

本节介绍了一个比霍夫丁不等式更一般的集中不等式。其证明利用了针对随机游走差分的霍夫丁不等式。

定义 D.5 (随机游走差分) 一列随机变量 $V_1,V_2,\dots$ 是关于 $X_1,X_2,\dots$ 的随机游走差分序列，如果对于所有 $i>0$, $V_i$ 是 $X_1,\dots ,X_i$ 的函数且

$$\mathbb{E}\left[V_{i+1}\mid X_1,\dots ,X_i\right]=0.\text{\hspace{1em}(D.9)}$$

下面的结果与霍夫丁引理相似。

引理 D.6 设 $V$ 和 $Z$ 是满足 $\mathbb{E}\left[V\mid Z\right]=0$ 的随机变量，对于某个函数 $f$ 和常数 $c\ge 0$ ，不等式:

$$f\left(Z\right)\le V\le f\left(Z\right)+c.\text{\hspace{1em}(D.10)}$$

然后，对于所有 $t>0$ ，以下的上界成立:

$$\mathbb{E}\left[e^{tV}\mid Z\right]\le e^{t^2{c}^2/8}.\text{\hspace{1em}(D.11)}$$

证明:证明步骤与引理 D.1 相同，只是用条件期望代替期望:在 $Z,V$ 取值在 $\left[a,b\right]$ 且 $a=f\left(Z\right)$ 和 $b=f\left(Z\right)+c$ 的条件下，其期望消失。

该引理用于证明以下定理，该定理是本节的主要结果之一。

定理 D.7(Azuma 不等式) 设 $V_1,V_2,\dots$ 是关于随机变量 $X_1,X_2,\dots$ 的谱，并假设对于所有 $i>0$ 存在一个常数 $c_i\ge 0$ 以及随机变量 $Z_i$ ，它是 $X_1,\dots ,X_{i-1}$ 的函数，满足

$$Z_i\le V_i\le Z_i+c_i\text{\hspace{1em}(D.12)}$$

然后，对于所有 $ϵ>0$ 和 $m$ ，以下不等式成立:

$$\begin{array}{rl}\mathbb{P}\left[\sum _{i=1}^m{V}_i\ge ϵ\right]& \le \exp \left(\frac{-2{ϵ}^2}{\sum _{i=1}^m{c}_i^2}\right)\\ \mathbb{P}\left[\sum _{i=1}^m{V}_i\le -ϵ\right]& \le \exp \left(\frac{-2{ϵ}^2}{\sum _{i=1}^m{c}_i^2}\right).\end{array}\text{\hspace{1em}(D.13)(D.14)}$$

证明:对于任意 $k\in \left[m\right]$ ，设 $S_k=\sum _{i=1}^k{V}_k$ 。然后，使用 Chernoff 边界技术，对于任意 $t>0$ ，我们可以写出

$$\mathbb{P}\left[S_m\ge ϵ\right]\le e^{-tϵ}\mathbb{E}\left[e^{t{S}_m}\right]$$ $$=e^{-tϵ}\mathbb{E}\left[e^{t{S}_{m-1}}\mathbb{E}\left[e^{t{\mathbf{V}}_m}\mid X_1,\dots ,X_{m-1}\right]\right]$$ $$\le e^{-tϵ}\mathbb{E}\left[e^{t{S}_{m-1}}\right]e^{t^2{c}_m^2/8}\text{\hspace{1em}(lemma D.6)}$$ $$\le e^{-tϵ}{e}^{t^2\sum _{i=1}^m{c}_i^2/8}\text{\hspace{1em}(iterating previous argument)}$$ $$=e^{-2{ϵ}^2/\sum _{i=1}^m{c}_i^2},$$

其中我们选择 $t=4ϵ/\sum _{i=1}^m{c}_i^2$ 以最小化上界。这证明了定理的第一个陈述，第二个陈述以类似的方式证明。