D.10 最大不等式

下面给出了有限集合的随机变量的最大值的期望的一个上界，这在几个上下文中很有用。

定理 D.10(最大不等式)设 $X_1\dots X_n$ 是 $n\ge 1$ 实值随机变量，使得对于所有 $j\in \left[n\right]$ 和 $t>0,\mathbb{E}\left[e^{t{X}_j}\right]\le e^{\frac{t^2{r}^2}{2}}$ 对于某个 $r>0$ 。那么，以下不等式

成立:

$$\mathbb{E}\left[\underset{j\in \left[n\right]}{\max }{X}_j\right]\le r\sqrt{2\log n}$$

证明:对于任意的 $t>0$ ，由于指数函数的凸性和Jensen不等式，以下成立:

$$e^{t\mathbb{E}\left[\underset{j\in \left[n\right]}{\max }{X}_j\right]}\le \mathbb{E}\left[e^{t\underset{j\in \left[n\right]}{\max }{X}_j}\right]=\mathbb{E}\left[\underset{j\in \left[n\right]}{\max }{e}^{t{X}_j}\right]\le \mathbb{E}\left[\sum _{j\in \left[n\right]}{e}^{t{X}_j}\right]\le n{e}^{\frac{t^2{r}^2}{2}}.$$

对两边取对数得到

$$\mathbb{E}\left[\underset{j\in \left[n\right]}{\max }{X}_j\right]\le \frac{\log n}{t}+\frac{t{r}^2}{2}\text{\hspace{1em}(D.25)}$$

选择 $t=\frac{\sqrt{2\log n}}{r}$ ，它最小化了右边，给出了上界 $r\sqrt{2\log n}$ 。注意，考虑到它们的矩生成函数的表达式(方程(C.24))，对于标准高斯随机变量 $X_j$ ，定理的假设成立且为等式:$\mathbb{E}\left[e^{t{X}_j}\right]=e^{\frac{t^2}{2}}$

推论 D.11(最大不等式)设 $X_1\dots X_n$ 为 $n\ge 1$ 实值随机变量，满足对于所有 $j\in \left[n\right],X_j=\sum _{i=1}^m{Y}_{ij}$ ，其中，对于每个固定的 $j\in \left[n\right],Y_{ij}$ 是独立的均值为零的随机变量，取值在 $\left[-r_i,+r_i\right]$ 中，对于某个 $r_i>0$ 。那么，以下不等式成立:

$$\mathbb{E}\left[\underset{j\in \left[n\right]}{\max }{X}_j\right]\le r\sqrt{2\log n}$$

其中 $r=\sqrt{\sum _{i=1}^m{r}_i^2}$ 。

证明:由于 $Y_{ij}$ 对于固定的 $j$ 是独立的，以及根据Hoeffding引理(引理D.1)，以下不等式对于所有 $j\in \left[n\right]$ 成立:

$$\mathbb{E}\left[e^{t{X}_j}\right]=\mathbb{E}\left[\prod _{i=1}^m{e}^{t{Y}_{ij}}\right]=\prod _{i=1}^m\mathbb{E}\left[e^{t{Y}_{ij}}\right]\le \prod _{i=1}^m{e}^{\frac{t^2{r}_j^2}{2}}=e^{\frac{t^2{r}^2}{2}},\text{\hspace{1em}(D.26)}$$

其中 $r^2=\sum _{i=1}^m{r}_i^2$ 。然后，结果立即由定理D.10得出。