集中不等式概要
最近在上的两门课都频繁地用到了集中不等式, 遂作文以总结之, 主要材料来自《Foundations of Machine Learning》
最经典的集中不等式当属 Markov’s Inequality, 其证明技巧被广泛应用于其他不等式. 考虑一个非负的随机变量 \(X\), 则对每一个 \(\varepsilon>0\), \(\varepsilon\mathbb{P}[X\geqslant \varepsilon] \leqslant \mathbb{E}X\), 这就是 Markov’s Inequality:
设随机变量 \(X\geqslant 0\), 则 \(\forall \varepsilon >0\),
\[\mathbb{P}[X\geqslant \varepsilon] \leqslant \frac{1}{\varepsilon} \mathbb{E}X.\]
注意到 \(e^{t\varepsilon}>0,\,\mathbb{P}[X\geqslant \varepsilon]=\mathbb{P}[e^{tX}\geqslant e^{t\varepsilon}]\), 于是
\[\mathbb{P}[X\geqslant \varepsilon]\leqslant e^{-t\varepsilon}\mathbb{P}[e^{tX}\geqslant e^{t\varepsilon}].\]我们可以通过对 \(\mathbb{P}[e^{tX}\geqslant e^{t\varepsilon}]\) 进行放缩, 得到关于 \(t\) 的函数, 再对 \(t\) 求最小值来给出 \(\mathbb{P}[X\geqslant \varepsilon]\) 的估计, 这种技巧称为 Chernoff Bounding Technique.
Hoeffding’s Inequality 的证明依赖于 Hoeffding’s Lemma.
设 \(X\) 是在区间 \([a,b]\) 中取值且 \(\mathbb{E}X=0\) 的随机变量, 则对每一个 \(t>0\), 有
\[\mathbb{E}\exp(tX) \leqslant \exp\left(\frac{t^2(b-a)^2}{8}\right).\]
证明: 将 \(\exp(tX)\) 视为 \(X\) 的函数, 利用凸性得到
\[\exp(tX)\leqslant \frac{X-a}{b-a}\exp\left(tb\right) + \frac{b-X}{b-a}\exp\left(ta\right).\]由于 \(\mathbb{E}X=0\), 于是
\[\mathbb{E}\exp(tX) \leqslant \frac{b}{b-a}\mathbb{E}\exp\left(ta\right) - \frac{a}{b-a}\mathbb{E}\exp\left(tb\right).\]定义
\[\varphi(t)=\log\left(\frac{b}{b-a}\exp\left(ta\right) - \frac{a}{b-a}\exp\left(tb\right)\right).\]则 \(\varphi(0)=0,\,\varphi'(0)=0,\) 而
\[\begin{aligned} \varphi''(\xi)&=\frac{ab(ae^{\xi a}-be^{\xi b})(be^{\xi a}-ae^{\xi b})-a^2b^2(e^{\xi a}-e^{\xi b})^2}{(be^{\xi a}-ae^{\xi b})^2}\\ &=\frac{-ab(b-a)^2}{-2ab+a^2e^{\xi (a-b)}+b^2e^{\xi (b-a)}}\\ &\leqslant \frac{(b-a)^2}{4}. \end{aligned}\]利用带 Lagrange 余项的展开得, 存在 \(\xi\in(0,t)\)
\[\varphi(t) = \varphi(0) + \varphi'(0)t + \frac{\varphi''(\xi)}{2} t^2\leqslant \frac{t^2(b-a)^2}{8}.\]故
\[\mathbb{E}\exp(tX) \leqslant \mathbb{E} e^{\varphi(t)} \leqslant \exp\left(\frac{t^2(b-a)^2}{8}\right).\]假设 \(X_i\in [a_i,b_i],\,i=1,2,\ldots,m\) 是一组相互独立的随机变量, 记 \(S=\sum_{i=1}^m X_i\), 则 \(\forall \varepsilon > 0\),
\[\begin{aligned} \mathbb{P}[S - \mathbb{E}S\geqslant \varepsilon]&\leqslant \exp\left(-\frac{2\varepsilon^2}{\sum_{i=1}^{m} (b_i-a_i)^{2}}\right),\\ \mathbb{P}[S - \mathbb{E}S\leqslant -\varepsilon]&\leqslant \exp\left(-\frac{2\varepsilon^2}{\sum_{i=1}^{m} (b_i-a_i)^{2}}\right). \end{aligned}\]
证明: 由 Markov’s Inequality 及 \(X_i\) 的独立性, 任取 \(t>0\)
\[\begin{aligned} \mathbb{P}[S - \mathbb{E}S\geqslant \varepsilon]&\leqslant e^{-t\varepsilon}\mathbb{E}\exp\left(t(S - \mathbb{E}S)\right)\\ &= e^{-t\varepsilon} \prod_{i=1}^m \mathbb{E}\exp\left(t(X_i-\mathbb{E}X_i)\right)\\ &\leqslant \exp\left(-t\varepsilon + \frac{t^2}{8}\sum_{i=1}^m(b_i-a_i)^2 \right). \end{aligned}\]取 \(t=\frac{4\varepsilon}{\sum_{i=1}^m(b_i-a_i)^2}\) 得
\[\mathbb{P}[S - \mathbb{E}S\geqslant \varepsilon]\leqslant \exp\left(-\frac{2\varepsilon^2}{\sum_{i=1}^{m} (b_i-a_i)^{2}}\right).\]对 \(-X_i\) 使用上述不等式即得
\[\mathbb{P}[S - \mathbb{E}S\leqslant -\varepsilon]\leqslant \exp\left(-\frac{2\varepsilon^2}{\sum_{i=1}^{m} (b_i-a_i)^{2}}\right).\]相比于粗糙的 Union Bound, 即 \(\mathbb{P}(\cup A_i)\leqslant \cup \mathbb{P}A_i\), Hoeffding’s Inequality 往往能给出精确地多的估计 (不等式右端以指数平方衰减), 但 Hoeffding’s Inequality 并没有考虑随机变量 \(X_i\) 在区间 \([a_i,b_i]\) 内的分布情况, 当 \(X_i\) 的期望 \(p_i\) 已知时, 我们希望得到更精确的估计, 这就是 Multiplicative Chernoff Bounds 要做的. 为导出 Multiplicative Chernoff Bounds, 我们先证明 Sanov’s Theorem.
假设 \(X_1,\ldots,X_m\) 是相互独立且服从分布 \(\mathcal{D}\) 的随机变量, 它们在区间 \([0,1]\) 内取值, 且均值为 \(p\). 则对每一个 \(q\in [p,1]\), 有
\[\mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\geqslant q\right] \leqslant \exp\big(-mD(q\parallel p)\big),\]其中
\[D(q\parallel p) = q \log \frac{q}{p}+(1-q) \log \frac{1-q}{1-p}\]称为 \(q\) 关于 \(p\) 的二元相对熵 (Binary Relative Entropy).
证明: 对每一个 \(t > 0\), 借助 Markov’s Inequality 证明中的技巧得
\[\begin{aligned} \mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\geqslant q\right] =& e^{-tmq}e^{tmq}\mathbb{P}\left[\exp\Big(t \sum_{i=1}^{m} X_{i}\Big)\geqslant e^{tmq}\right]\\ \leqslant& e^{-tmq}\mathbb{E}\left[\exp\Big(t \sum_{i=1}^{m} X_{i}\Big)\right]\\ =& e^{-tmq}\prod_{i=1}^{m}\mathbb{E}\left[\exp(t X_{i})\right]. \end{aligned}\]将 \(\exp(t X_{i})\) 视为关于 \(X_i\) 的凸函数, 由于 \(X_i\in [0,1]\), 则
\[\exp(t X_{i}) \leqslant (1-X_i) \exp(t \cdot 0)+X_i\exp(t\cdot 1)=(1-X_i)+X_i\exp(t).\]因此
\[\mathbb{E}\exp(t X_{i}) \leqslant 1-p + pe^{t}.\]故 \(\forall t>0\), 有
\[\mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\geqslant q\right] \leqslant e^{-tmq}(1-p + pe^{t})^m = \big( (1-p)e^{-tq}+pe^{(1-q)t}\big)^m.\]\((1-p)e^{-tq}+pe^{(1-q)t}\) 在 \(t=\log\frac{q(1-p)}{p(1-q)}\) 处取最小值. 在 \(p<q\) 时, 令 \(t=\log\frac{q(1-p)}{p(1-q)}>0\) 得
\[\begin{aligned} \mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\geqslant q\right] &\leqslant \left((1-p)\left(\frac{p(1-q)}{q(1-p)}\right)^q+p\left(\frac{q(1-p)}{p(1-q)}\right)^{1-q}\right)^m\\ &=\left(\left(\frac{p(1-q)}{q(1-p)}\right)^q \left(1-p+p\frac{q(1-p)}{p(1-q)}\right) \right)^m\\ &=\left(\left(\frac{p(1-q)}{q(1-p)}\right)^q \left(\frac{1-p}{1-q}\right) \right)^m\\ &=\exp(-mD(q\parallel p)). \end{aligned}\]在 \(q=p\) 时, \(D(q\parallel p)=0\), 此时欲证的概率不等式右端为 \(1\), 必然成立.
利用 Sanov’s Theorem 可以得到比 Hoeffding’s Inequality 更好的估计, 取 \(0<\varepsilon\leqslant 1-p\), 则 \(p+\varepsilon \in (p, 1]\), 于是
\[\mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\geqslant p+\varepsilon\right] \leqslant \exp(-mD(p+\varepsilon\parallel p)).\]考虑函数
\[f(p) = q \log \frac{q}{p}+(1-q) \log \frac{1-q}{1-p} - 2(p-q)^2,\quad p\in [0,1].\]其导数为
\[f'(p) = -\frac{q}{p} + \frac{1-q}{1-p} - 4(p-q) = (p-q)\left(\frac{1}{p(1-p)}-4\right).\]由 \(p(1-p)\leqslant 1/4\) 知 \(p=q\) 是 \(f(p)\) 的最小值点, 故 \(f(p)\geqslant f(q) = 0\), 因此
\[D(q\parallel p) = q \log \frac{q}{p}+(1-q) \log \frac{1-q}{1-p}\geqslant 2(p-q)^2,\]该不等式称为 Pinsker’s Inequality. 取 \(q=p+\varepsilon\) 得
\[D(p+\varepsilon\parallel p) \geqslant 2\varepsilon^2 \quad \Rightarrow \quad \exp(-mD(p+\varepsilon\parallel p))\leqslant \exp(-2m\varepsilon^2).\]这说明利用 Sanov’s Theorem 得到的估计不弱于利用 Hoeffding’s Inequality 得到的估计. 对另一方向的概率
\[\mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\leqslant p-\varepsilon\right]\]进行估计时, 仅需构造 \(Y_i = 1-X_i\), 则 \(Y_i\in [0,1],\,\mathbb{E}Y_i=1-p\), 于是
\[\mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\leqslant p-\varepsilon\right] = \mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} Y_{i}\geqslant 1-p+\varepsilon\right]\leqslant \exp(-mD(1-p+\varepsilon\parallel 1-p))=\exp(-mD(p-\varepsilon\parallel p)).\]最后一个等式利用了二元相对熵的性质: \(D(1-p+\varepsilon\parallel 1-p) = D(p-\varepsilon\parallel p)\).
假设 \(X_1,\ldots,X_m\) 是相互独立且服从分布 \(\mathcal{D}\) 的随机变量, 它们在区间 \([0,1]\) 内取值, 且均值为 \(p\). 则对每一个 \(\gamma \in [0,\frac{1}{p}-1]\), 有
\[\begin{aligned} \mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\geqslant (1+\gamma)p\right] &\leqslant \exp\big(-\frac{mp\gamma^2}{\gamma+2}\big),\\ \mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\leqslant (1-\gamma)p\right] &\leqslant \exp\big(-\frac{mp\gamma^2}{2}\big). \end{aligned}\]
证明: 上述结果的证明需要对二元相对熵 \(D(q\parallel p)\) 进行比 Pinsker’s Inequality 更加精确的估计, 首先要用到两个不等式:
\[\log(1+x) \geqslant \frac{x}{1+x/2},\quad \log(1+x)\leqslant x.\]由于 \(\mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\geqslant (1+\gamma)p\right]\leqslant \exp\big(-m D((1+\gamma)p\parallel p)\big)\), 仅需估计 \(D((1+\gamma)p\parallel p)\).
\[\begin{aligned} D((1+\gamma)p\parallel p)&=(1+\gamma) p \log \frac{(1+\gamma) p}{p}+(1-(1+\gamma) p) \log \left[\frac{1-(1+\gamma) p}{1-p}\right] \\ &=(1+\gamma) p \log (1+\gamma)+(1-p-\gamma p) \log \left[1-\frac{\gamma p}{1-p}\right] \\ &\geqslant(1+\gamma) p \frac{\gamma}{1+\frac{\gamma}{2}}-(1-p-\gamma p) \frac{\gamma p}{1-p}\\ &=\gamma^2p\left(\frac{1}{\gamma+2}+\frac{1}{1/p-1}\right)\\ &\geqslant \frac{\gamma^2p}{\gamma+2}. \end{aligned}\]故 \(\mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\geqslant (1+\gamma)p\right]\leqslant \exp\big(-\frac{m\gamma^2p}{\gamma+2}\big)\). 再对 \(D((1-\gamma)p\parallel p)\) 进行估计, 这需要用到
\[(1-x) \log (1-x) \geqslant -x+\frac{x^{2}}{2},\;x\in(0,1) ,\quad (1+x)\log(1+x)\geqslant x.\]由于
\[\begin{aligned} D((1-\gamma)p\parallel p) &= (1-\gamma)p\log \frac{(1-\gamma)p}{p} + (1-p+\gamma p)\log \frac{1-p+\gamma p}{1-p}\\ &\geqslant p(-\gamma + \frac{\gamma^2}{2})+(1-p)\left(1 + \frac{\gamma p}{1-p}\right)\log\left(1 + \frac{\gamma p}{1-p}\right)\\ &\geqslant p(-\gamma + \frac{\gamma^2}{2}) + (1-p)\frac{\gamma p}{1-p}\\ &=\frac{\gamma^2p}{2}. \end{aligned}\]故 \(\mathbb{P}\left[\frac{1}{m} \sum_{i=1}^{m} X_{i}\leqslant (1-\gamma)p\right]\leqslant \exp\big(-\frac{m\gamma^2p}{2}\big)\).
为证明 Azuma’s Inequality, 先定义鞅差序列 (Martingale Difference Sequence (MDS)):
称一组随机变量序列 \(V_1,V_2,\ldots\) 为关于 \(X_1,X_2,\ldots\) 的鞅差序列, 若对每一个 \(i>0\), \(V_i\) 是 \(X_1,X_2,\ldots,X_{i}\) 的函数, 并且满足
\[\mathbb{E}\left[V_{i+1} \mid X_{1}, \ldots, X_{i}\right]=0.\]
回顾鞅 (Martingale) 的定义:
称随机变量序列 \(Y_1,Y_2,\ldots\) 为关于 \(X_1,X_2,\ldots\) 的鞅, 若
\[\mathbb{E}|Y_i|<\infty,\quad \mathbb{E}\left[Y_{i+1} \mid X_{1}, \ldots, X_{i}\right]=Y_i.\]
鞅差序列的定义实际上是在说
\[\mathbb{E}\left[\sum_{k=1}^{i+1} V_{k}\mid X_{1}, \ldots, X_{i}\right]=\sum_{k=1}^{i} V_{k}.\]即以 \(V_k\) 为增量的随机变量序列 \(\sum_{k=1}^{i} V_{k}\) 是鞅.
与 Hoeffding’s Inequality 的证明类似, Azuma’s Inequality 的证明也依赖于对单变量情形的分析:
假设 \(V,Z\) 是满足 \(\mathbb{E}[V\mid Z]=0\) 的随机变量, 并且对某个函数 \(f(\cdot)\) 与非负常数 \(c\geqslant 0\) 有
\[f(Z) \leqslant V \leqslant f(Z)+c.\]则任取 \(t > 0\), 有如下估计:
\[\mathbb{E}\left[e^{t V} \mid Z\right] \leq e^{t^{2} c^{2} / 8}.\]
证明: 将 Hoeffding’s Lemma 中的概率全部替换为关于变量 \(Z\) 的条件概率即得.
结合鞅差序列的定义与上述推广的 Hoeffding’s Lemma, 我们可以将 Hoeffding’s Inequality 推广到更加一般的情形:
设 \(V_1,V_2,\ldots\) 是关于随机变量 \(X_1,X_2,\ldots\) 的鞅差序列. 且任取 \(i>0\), 存在常数 \(c_i\geqslant 0\) 与以 \(X_1,X_2,\ldots,X_{i-1}\) 为自变量的函数 \(Z_i\), 使得
\[Z_i\leqslant V_i \leqslant Z_i+c_i.\]则任取 \(\varepsilon > 0\) 与正整数 \(m\), 有下列不等式成立:
\[\begin{aligned}\mathbb{P}\left[\sum_{i=1}^{m} V_{i} \geqslant \varepsilon\right] \leqslant \exp \left(\frac{-2 \varepsilon^{2}}{\sum_{i=1}^{m} c_{i}^{2}}\right), \\\mathbb{P}\left[\sum_{i=1}^{m} V_{i}\leqslant-\varepsilon\right] \leqslant \exp \left(\frac{-2 \varepsilon^{2}}{\sum_{i=1}^{m} c_{i}^{2}}\right).\end{aligned}\]
证明: 记 \(S_{k}=\sum_{i=1}^{k} V_{k}\), 于是任取 \(t>0\), 有
\[\begin{aligned} \mathbb{P}\left[S_{m} \geqslant \varepsilon\right] & \leqslant e^{-t \varepsilon} \mathbb{E}\left[e^{t S_{m}}\right] \\ &=e^{-t \varepsilon} \mathbb{E}\left[e^{t S_{m-1}} \mathbb{E}\left[e^{t \mathbf{V}_{m}} \mid X_{1}, \ldots, X_{m-1}\right]\right] \\ & \leqslant e^{-t \varepsilon} \mathbb{E}\left[e^{t S_{m-1}}\right] e^{t^{2} c_{m}^{2} / 8} \\ & \leqslant e^{-t \varepsilon} e^{t^{2} \sum_{i=1}^{m} c_{i}^{2} / 8} \\ &=e^{-2 \varepsilon^{2} / \sum_{i=1}^{m} c_{i}^{2}}. \end{aligned}\]其中第二步用到了重期望公式
\[\mathbb{E}\left[e^{t S_{m}}\right] = \mathbb{E}\left[e^{t S_{m-1}} \mathbb{E}\left[e^{t \mathbf{V}_{m}} \mid X_{1}, \ldots, X_{m-1}\right]\right],\]最后一步是通过取 \(t = \frac{4\varepsilon}{\sum_{i=1}^{m} c_{i}^{2}}\) 得到的.
设 \(X_1,X_2,\ldots,X_m\) 是一组相互独立且在 \(\mathcal{X}\) 中取值的随机变量, 函数 \(f\colon\mathcal{X}^m\to \mathbb{R}\) 满足
\[\left|f\left(x_{1}, \ldots, x_{i}, \ldots, x_{m}\right)-f\left(x_{1}, \ldots, x_{i}^{\prime}, \ldots x_{m}\right)\right| \leq c_{i},\quad \forall x_k\in\mathcal{X},\;x_i'\in\mathcal{X},\;k=1,2,\ldots,m,\]其中 \(c_1,c_2,\ldots,c_m\) 是一组大于 \(0\) 的常数. 以 \(f(S)\) 表示 \(f(X_1,X_2,\ldots,X_m)\), 则任取 \(\varepsilon > 0\), 有
\[\begin{aligned} \mathbb{P}[f(S)-\mathbb{E}[f(S)] \geq \varepsilon] & \leq \exp \left(\frac{-2 \varepsilon^{2}}{\sum_{i=1}^{m} c_{i}^{2}}\right), \\ \mathbb{P}[f(S)-\mathbb{E}[f(S)] \leq-\varepsilon] & \leq \exp \left(\frac{-2 \varepsilon^{2}}{\sum_{i=1}^{m} c_{i}^{2}}\right). \end{aligned}\]
证明: 取
\[V_k = \mathbb{E}\left[f(S)\mid X_1,\ldots,X_{k-1}\right]-\mathbb{E}\left[f(S)\mid X_1,\ldots,X_{k}\right],\quad k=2,3,\ldots,m.\]并规定 \(V_1= f(S)-\mathbb{E}\left[f(S)\mid X_1\right]\). 可以验证这样定义的 \(V_1,V_2,\ldots,V_m\) 是关于随机变量序列 \(X_1,X_2,\ldots,X_m\) 的鞅差序列. 定义
\[\begin{aligned} U_{k} &=\mathbb{E}\left[f(S) \mid X_{1}, \ldots, X_{k-1}\right] - \inf_{x} \mathbb{E}\left[f(S) \mid X_{1}, \ldots, X_{k-1}, x\right],\\ L_{k} &=\mathbb{E}\left[f(S) \mid X_{1}, \ldots, X_{k-1}\right] - \sup_{x} \mathbb{E}\left[f(S) \mid X_{1}, \ldots, X_{k-1}, x\right]. \end{aligned}\]它们分别是 \(V_k\) 的上下确界, 利用条件
\[\left|f\left(x_{1}, \ldots, x_{i}, \ldots, x_{m}\right)-f\left(x_{1}, \ldots, x_{i}^{\prime}, \ldots x_{m}\right)\right| \leq c_{i},\quad \forall x_k\in\mathcal{X},\;x_i'\in\mathcal{X},\;k=1,2,\ldots,m,\]得 \(U_k\leqslant L_k + c_k\), 故
\[L_k \leqslant V_k \leqslant L_k+c_k.\]再由 Sanov’s Theorem 即得
\[\mathbb{P}[f(S)-\mathbb{E}[f(S)] \geq \varepsilon] = \mathbb{P}\left[\sum_{i=1}^{m} V_{i} \geqslant \varepsilon\right] \leq \exp \left(\frac{-2 \varepsilon^{2}}{\sum_{i=1}^{m} c_{i}^{2}}\right).\]同理可得
\[\mathbb{P}[f(S)-\mathbb{E}[f(S)] \leq-\varepsilon] \leq \exp \left(\frac{-2 \varepsilon^{2}}{\sum_{i=1}^{m} c_{i}^{2}}\right).\]该不等式表明当自变量给函数 \(f\) 带来的改变有界时, \(f(S)\) 对均值的偏离可以被指数函数控制. Hoeffding’s Inequality 可通过取
\[f(S)=f(X_1,X_2,\ldots,X_m)=\frac{1}{m}\sum_{i=1}^m X_i\]的 McDiarmid’s Inequality 得到.
作为本文的结尾, 我们最后给出次高斯随机变量的定义及 Maximal Inequality. 服从高斯分布的随机变量的一个重要性质是其尾部以指数平方的概率衰减, 例如当变量 \(X\sim \mathcal{N}(0,1)\), 对每个 \(t\geqslant 0\), 有
\[\mathbb{P}[|X|\geqslant t]\leqslant 2e^{-t^2/2}.\]这种形式的估计在实际推导中很有用, 是服从高斯分布的随机变量最重要的性质之一. 我们将这一性质推广, 并以此来定义次高斯随机变量.
对随机变量 \(X\), 若存在 \(K_1>0\), 使得
\[\mathbb{P}[|X|\geqslant t]\leqslant 2\exp\left(-t^2/K_1^2\right),\quad \forall t\geqslant 0.\]则称其为次高斯随机变量.
若 \(\mathbb{E}X=0\), 其还具有如下的等价定义 (此处留坑, 以后有心情再补证明):
存在 \(K_5>0\), 使得
\[\mathbb{E} \exp (\lambda X) \leq \exp \left(K_{5}^{2} \lambda^{2}\right), \quad \forall \lambda \in \mathbb{R}.\]
且在该不等式成立时, 必然有 \(\mathbb{E}X=0.\) (继续留坑)
借助这一等价定义, 可以对由有限个次高斯随机变量构成的集合的最大值进行估计.
假设 \(X_1,X_2,\ldots,X_n\) 是一组满足
\[\exp(tX_j)\leqslant \exp \left(\frac{r^2t^2}{2}\right),\quad j=1,2,\ldots,n\]的次高斯随机变量 (不要求独立), 其中 \(r>0\). 则
\[\mathbb{E}\left[\max _{1\leqslant j\leqslant n} X_{j}\right] \leqslant r \sqrt{2 \log n}.\]
证明: 任取 \(t>0\), 利用指数函数的凸性及 Jensen’s Inequality 得
\[\exp\left(t \mathbb{E}\left[\max _{1\leqslant j\leqslant n} X_{j}\right]\right) \leqslant \mathbb{E}\exp\left(t \max _{1\leqslant j\leqslant n} X_{j}\right)=\mathbb{E}\left[\max _{1\leqslant j\leqslant n} \exp(tX_j)\right] \leqslant \mathbb{E}\left[\sum_{1\leqslant j\leqslant n} \exp(tX_j)\right] \leqslant \mathbb{E}\ n e^{\frac{t^{2} r^{2}}{2}}.\]两边取对数并除以 \(t\) 得
\[\mathbb{E}\left[\max _{1\leqslant j\leqslant n} X_{j}\right] \leqslant \frac{\log n}{t}+\frac{t r^{2}}{2}.\]取 \(t=\sqrt{2\log n}/r\) 即得
\[\mathbb{E}\left[\max _{1\leqslant j\leqslant n} X_{j}\right] \leqslant r \sqrt{2 \log n}.\]该定理还有以下推论:
假设 \(X_1,\ldots,X_n\) 是满足 \(X_j=\sum_{i=1}^mY_{ij}\) 的随机变量, \(Y_{ij}\) 是相互独立的随机变量, 且 \(Y_{ij}\in [-r_i,+r_i],\,r_i>0,\,\mathbb{E}Y_{ij}=0\), 则
\[\mathbb{E}\left[\max _{1\leqslant j\leqslant n} X_{j}\right] \leqslant r \sqrt{2 \log n},\quad r=\sqrt{\sum_{i=1}^{m} r_{i}^{2}}.\]
证明: 只需证明 \(\mathbb{E}\exp\left(tX_j\right)\leqslant \exp\left(r^2t^2/2\right)\), 其中 \(r=\sqrt{\sum_{i=1}^{m} r_{i}^{2}}\). 利用 \(Y_{ij}\) 的独立性及 Hoeffding’s Inequality, 有
\[\mathbb{E}\left[e^{t X_{j}}\right]=\mathbb{E}\left[\prod_{i=1}^{m} e^{t Y_{i j}}\right]=\prod_{i=1}^{m} \mathbb{E}\left[e^{t Y_{i j}}\right] \leqslant \prod_{i=1}^{m} e^{\frac{t^{2} r_{j}^{2}}{2}}=e^{\frac{t^{2} r^{2}}{2}}.\]再由 Maximal Inequality 即得
\[\mathbb{E}\left[\max _{1\leqslant j\leqslant n} X_{j}\right] \leqslant r \sqrt{2 \log n},\quad r=\sqrt{\sum_{i=1}^{m} r_{i}^{2}}.\]