简单介绍一下最近用到一些核函数的结果。

称$n\times n$阶对称方阵$A$半正定，如果对任意的$n$维向量$\alpha$，有$\alpha^T A\alpha\geq 0$。称定义在$\Omega\times\Omega\subset \mathbb{R}^d\times\mathbb{R}^d$上的二元函数$H(\cdot,\cdot)$对称半正定，如果$H$对称且对任意的$n\geq 1$以及$\{x_1,\ldots x_n\}\subset \Omega$，矩阵$K:=(H(x_j,x_k))_{jk}$是半正定的。

在很多情况下，我们希望二元函数$H$是由一个一元函数$\Phi$诱导产生的，具体来说$H(x_j,x_k)=\Phi(x_j-x_k)$，其中$\Phi$是定义在$\mathbb{R}^d$上的函数。我们称这样的$\Phi$为半正定核函数。这样的表示在随机过程中有很强的背景，其中$H$为一个随机过程的相关函数，如果$H$可以用$\Phi$表示，则这个随机过程是平稳的，并称$\Phi(\cdot)/\Phi(0)$为自相关函数。

反过来，如果先给定一个$\Phi$，我们也能定义$H(x_j,x_k)=\Phi(x_j-x_k)$，问题是在何种条件下，这样定义的$H$满足对称半正定性呢？

在此需要说明，此行以上的所有讨论中我们只在实数域上讨论。因为大多数具有实际意义的问题都发生在实数域上。从数学角度上讲，如果要考虑复数矩阵，则上面的对称矩阵需要改变为厄米特矩阵。

出于使用价值的考量，我们这里不去讨论最一般的$\Phi$，而是限定$\Phi$要满足一些良好的正则性条件。具体来说，我们要求$\Phi$可积，并且$\Phi$可以被它的傅里叶变换$\hat{\Phi}$通过反变换公式恢复。

直观上似乎很难想象正定性和傅里叶变换有什么联系，然而实际上它们的联系是非常紧密的。

首先由于二元函数$H$是对称的，因此$\Phi$必然是个偶函数，因此$\Phi$的傅里叶变换$\hat{\Phi}$是实函数。

为了研究矩阵$K$是否正定，我们考虑二次型$\alpha^T K\alpha$。使用求和的形式展开，它等于
$$\sum_{j=1}^n\sum_{k=1}^n \alpha_j\alpha_k \Phi(x_j-x_k). $$
现在我们使用傅里叶反变换公式
$$\Phi(x_j-x_k)=\int_{\mathbb{R}^d} \hat{\Phi}(\omega) e^{i (x_j-x_k)^T\omega} d\omega. $$
把上述两式组合在一起得到
\[\int_{\mathbb{R}^d} \sum_{j=1}^n\sum_{k=1}^n \alpha_j\alpha_k e^{i (x_j-x_k)^T \omega} \hat{\Phi}(\omega) d\omega=\int_{\mathbb{R}^d} \sum_{j=1}^n\sum_{k=1}^n \alpha_j\alpha_k e^{i x_j^T \omega}e^{-i x_j^T\omega} \hat{\Phi}(\omega) d\omega.\]
接下来就是见证奇迹的时刻了。利用共轭复数的定义，$e^{-i x_j^T\omega}=\overline{e^{i x_j^T\omega}}$，同时由于$\alpha_j$们都是实数，所以有$\alpha_j=\overline{\alpha_j}$。于是上面的式子可以改写成
\[\int_{\mathbb{R}^d} \sum_{j=1}^n\sum_{k=1}^n \alpha_j e^{i x_j^T \omega}\overline{\alpha_k e^{i x_j^T\omega}} \hat{\Phi}(\omega) d\omega=\int_{\mathbb{R}^d} \left|\sum_{j=1}^n \alpha_j e^{i x_j^T \omega}\right|^2 \hat{\Phi}(\omega) d\omega.\]
因为$\left|\sum_{j=1}^n \alpha_j e^{i x_j^T \omega}\right|^2$必然非负，所以只要$\hat{\Phi}(\omega)$非负，整个积分必然非负，这就说明矩阵$K$是半正定的。

反过来的结论也成立，如果$\Phi$半正定，说明所有的$K$都是半正定的，因为三角多项式$\sum_{j=1}^n \alpha_j e^{i x_j^T \omega}$可以在有限区域上逼近任何连续函数，通过一定的分析技巧可以证明，只要$\hat{\Phi}$在一个Lebesgue测度为正的集合上取负值，就可以得到矛盾。

上面的结果非常有名，称为Bochner定理。用这个定理可以非常容易的判定一个核函数是否正定，例如$e^{-x^2}$就是一个正定的核函数，用线性代数的记法则是
\[\sum_{j=1}^n\sum_{k=1}^n \alpha_j\alpha_k e^{-(x_j-x_k)^2}\geq 0.\]
这个结果如果要用初等数学的方法证明恐怕是非常困难的。

我最近反复用到的结论是一个类似的结果，假设有两个正定核函数，分别记为$\Phi$和$\Psi$，对固定的点$\{x_1,\ldots,x_n\}$，令$K_1=(\Phi(x_j-x_k))_{jk}, K_2=(\Psi(x_j-x_k))_{ij}$。如果对$c>0$有$\hat{\Phi}\leq c\hat{\Psi}$，则有$K_1\leq c K_2$，即$c K_2-K_1$半正定。这个结果用类似的方法很容易证明。

设$I_k$是$k$阶单位阵，$1_{kl}$是$k\times l$阶所有元素都为1的矩阵，求以下矩阵的行列式
\(\begin{pmatrix}
l I_k & 1_{k l}\\
1_{lk} & k I_l
\end{pmatrix}\)

四、最终结果

经过上面的准备，我们到达了最终成果的论述。

这里需要的一个重要的技术手段称为“链接”（chaining）。回顾一下，对于所有的$\epsilon>0$，我们都可以相应的覆盖数$N(\epsilon,\mathcal{F})$。在链接方法中，我们不止考虑某个特定的$\epsilon$，而是选取$\epsilon_n\downarrow 0$，并考虑相应的一族$N(\epsilon_n,\mathcal{F})$。

为了简便起见，我们先让$\epsilon_i$待定。根据覆盖数定义，存在中心$f_1,\ldots,f_N, N=N(\epsilon_i,\mathcal{F})$，使得对一切$f\in\mathcal{F}$，存在某个$f_j$使得$|f-f_j|_\infty<\epsilon_n$。我们记这个（由$f$确定的）$f_j$为$f^{(i)}(f)$，如果这样的$f_j$不唯一，我们可以任取其中一个。

我们用$D:=diam(\mathcal{F})$表示$\mathcal{F}$的$L_\infty$直径。显然$N(2D,\mathcal{F})=1$。为了方便起见，我们不妨假设$0\in\mathcal{F}$。此外，我们要求$\epsilon_0= 2D$，并且选取中心为0，即$f^{(0)}(f)=0$对一切$f\in\mathcal{F}$成立。

用上述方法定义出来的$f^{(n)}(f)$还缺乏一些层次结构。在链接方法中，我们希望得到一个像链条一样层次分明的结构，类似“区-市-省-中央”这样逐级往上并可以追溯的结构。为此，我们递归的定义
\[f_{(S)}:=f^{(S)}(f),\\
f_{(S-1)}:=f^{(S-1)}(f_{(S)}),\\
\cdots\\
f_{(1)}:=f^{(1)}(f_{(2)}),\\
f_{(0)}:=f^{(0)}(f_{(1)})=0,\]
其中$S$待定。值得注意的是，尽管我们没有采用显示的记号，实际上每一个$f_{(i)}$都依赖于$f$。

下面介绍链接方法的主要思想。一个重要步骤是使用下面的“伸缩和”来表示任意的$f$：
\[f=(f-f_{(S)})+(f_{(S)}-f_{(S-1)})+\cdots+(f_{(1)}-f_{(0)}).\]
此时我们得到
\[\sup_{f}|\langle e, f\rangle_n|\leq \sup_{f}|\langle e, f-f_{(S)}\rangle_n|+\sum_{i=1}^S\sup_{f}|\langle e,f_{(i)}-f_{(i-1)}\rangle_n|.\]
上述不等式尽管右侧出现了很多项，然而仔细观察后就可以发现其实每一项都可以被很好的控制住。

我们的目标是控制$\mathbb{P}(\sup_{f}\sqrt{n}|\langle e, f\rangle|_n>t)$。利用引理2.1，我们自然的希望将$t$拆分成
\[t\geq t_0+t_S+t_{S-1}+\cdots+t_1,\]
并把每个$t_i$分配给“伸缩和”中的对应项。当然，$t_i$具体的分配方法是一个微妙的部分，它将直接影响到我们上界估计的准确程度。和前面一样，我们先让$t_i$待定，在经过一些计算之后这些值的选择方案就会变得清晰起来。

我们先考虑余项$\mathbb{P}(\sup_{f}\sqrt{n}|\langle e, f-f_{(S)}\rangle_n|>t_0)$，它较简单。由Hölder不等式，
\[|\langle e, f-f_{(S)}\rangle_n|\leq \frac{1}{n}\sum_{i=1}^n |e_i| |f-f_{S}|_\infty\leq \epsilon_S \cdot \frac{1}{n}\sum_{i=1}^n |e_i|. \]
因此由引理1.4直接得到，对$t_0>\epsilon_S\sqrt{2nv}/c$，有
\begin{eqnarray}
\mathbb{P}(\sup_{f}\sqrt{n}|\langle e, f-f_{(S)}\rangle_n|>t_0)\leq 2 \exp\left\{-\frac{(t_0 -\epsilon_S\sqrt{n}v/c)^2}{2n^{-1/2}c\epsilon_S t_0}\right\}.
\end{eqnarray}

我们再来估计$\mathbb{P}(\sup_{f}\sqrt{n}|\langle e, f_{(i)}-f_{(i-1)}\rangle_n|>t_i)$。一个有意思的事实是：虽然$f$所在的函数空间$\mathcal{F}$一般都有无穷个元素，但是$f_{(i)}-f_{(i-1)}$的可能取值却是有限的。也就是说，在这一项中的$\sup_{f}$其实只需要遍历有限多种可能性。这使得我们可以运用引理2.2。

具体的说，根据定义，$f_{(i)}-f_{(i-1)}$的可能取值不超过$N(\epsilon_i,\mathcal{F})$种。此外，显然有
\[|f_{(i)}-f_{(i-1)}|_{\infty}<\epsilon_{i-1}.\]
在此处我们就可以看出递归定义的好处，它能使得两个相邻的层次之间的关系更加紧密，这对我们研究“伸缩和”的帮助很大。

由此，根据推论1.3，对每一个固定的$f$，我们有
\[\mathbb{P}(\sqrt{n}|\langle e, f_{(i)}-f_{(i-1)}\rangle_n|>t_i)\leq 2\exp\left\{-\frac{t_i^2}{4 \epsilon_{i-1}^2 v}\right\},\]
其中$t_i$需要满足
\[0<t_i\leq \sqrt{n} \epsilon_{i-1} v/ c.\]
至于最大值的不等式，我们利用推论2.3，得到
\[\mathbb{P}(\sup_{f}\sqrt{n}|\langle e, f_{(i)}-f_{(i-1)}\rangle_n|>t_i)\leq 2 \exp\left\{H(\epsilon_i,\mathcal{F})-\frac{t_i^2}{4 \epsilon_{i-1}^2 v}\right\}.\]

我们当然希望上述不等式右边大括号里的部分是负数，否则这个不等式就没有实际的意义。进一步说，按照引理2.1，我们需要做到两点：1）引理2左侧的求和$\sum_{i=1}^S t_i$能够被有效的控制；2）引理2右侧的概率求和$\sum_{i=1}^S \exp\{H(\epsilon_i,\mathcal{F})-t_i^2/(4 \epsilon_{i-1}^2 v)\}$要小。而这需要通过选择适当的$\epsilon_i$和$t_i$来实现。历经了一番艰苦的尝试之后，我做出如此的选择：
\[\epsilon_i=2^{-i} D,\\
t_i=\epsilon_{i-1}\sqrt{8vH(\epsilon_i,\mathcal{F})}+u_i,\\
u_i=\epsilon_{i-1}\sqrt{i } u v/c,\]
其中$u>0$是（一定程度上的）自由参数。下面就来验证一下这确实是一个好的选择，首先
\[\sum_{i=1}^S t_i=\sum_{i=1}^S \epsilon_{i-1}\sqrt{8vH(\epsilon_i,\mathcal{F})}+\sum_{i=1}^S \epsilon_{i-1}\sqrt{i } u v/c,\]
其中第一项可以通过面积原理被积分控制如下
\[\sum_{i=1}^S \epsilon_{i-1}\sqrt{8vH(\epsilon_i,\mathcal{F})}=2\sum_{i=1}^S (\epsilon_{i-1}-\epsilon_i)\sqrt{8vH(\epsilon_i,\mathcal{F})}\\
\leq 6\sqrt{v}\int_{\epsilon_S}^D \sqrt{H(\epsilon,\mathcal{F})}d \epsilon,\]
第二项则显然与$D v u/c$同阶，因为
\[\sum_{i=1}^S \epsilon_{i-1}\sqrt{i } u v/c\leq \sum_{i=1}^\infty 2^{-i+1}\sqrt{i } D u v/c\\
\leq 2\left(\sum_{i=1}^\infty 2^{-i}i\right)^{1/2} \left(\sum_{i=1}^\infty 2^{-i}\right)^{1/2}D u v/c<3D u v/c.\]
此外，我们要求$t_i$需要满足推论1中的约束条件，则有
\begin{eqnarray}
\mathbb{P}(\sup_{f}\sqrt{n}|\langle e, f_{(i)}-f_{(i-1)}\rangle_n|>t_i)\leq 2 \exp\left\{\frac{(t_i-u_i)^2-2t_i^2}{8 \epsilon_{i-1}^2 v}\right\}\leq 2 \exp\left\{-\frac{u_i^2}{4 \epsilon_{i-1}^2 v}\right\},
\end{eqnarray}
这里我们利用了不等式$(t_i-u_i)^2-2t_i^2=-t_i^2-2t_i u_i+u_i^2\leq -2 u_i^2$。带入$u_i$取值，得
\[\mathbb{P}(\sup_{f}\sqrt{n}|\langle e, f_{(i)}-f_{(i-1)}\rangle_n|>t_i)\leq 2 \exp\left\{-\frac{i v u^2}{4 c^2}\right\}.\]
对$i$求和以后上式右边不超过
\[2\exp\left\{-\frac{v u^2}{4 c^2}\right\}/\left(1-\exp\left\{-\frac{v u^2}{4 c^2}\right\}\right).\]

现在再回头考虑约束条件$t_i\leq \sqrt{n} \epsilon_{i-1} v/ c$，为了省去不必要的麻烦，我们干脆限定
\[\epsilon_{i-1}\sqrt{8vH(\epsilon_i,\mathcal{F})}\leq \epsilon_{i-1} v/ (2c),\\
\epsilon_{i-1}\sqrt{i } u v/c\leq \sqrt{n} \epsilon_{i-1} v/ (2c),\]
即
\[\sqrt{H(\epsilon_i,\mathcal{F})}\leq \sqrt{nv/32}/c, \sqrt{i} u\leq \sqrt{n} / 2.\]

这个条件意味着，$S$不能取得任意大。为此，我们取$S$满足
1）$\sqrt{H(\epsilon_S,\mathcal{F})}<\sqrt{nv/32}/c, S < \sqrt{n}$,
2）$\sqrt{H(\epsilon_{S+1},\mathcal{F})}\geq \sqrt{nv/32}/c$，或$S+1\geq \sqrt{n}$。
我们考虑$S$不超过$\sqrt{n}$（而不是$S$不超过$n$）的目的是希望留一些裕度给$u$（$u\leq \sqrt{n/S}/2$）。我们假定$n$充分大，具体地说$n\geq 2$且$n\geq H(D,\mathcal{F})\cdot \sqrt{32/v} c$，此时我们总有$S>0$。下面分两种情况进行讨论。

情形I，如果$\sqrt{H(\epsilon_{S+1},\mathcal{F})}\geq \sqrt{nv/32}/c$，根据第三节中$G^{-1}$的定义，我们有
\[\epsilon_{S+1}\leq G^{-1}(\sqrt{nv/32}/c)<\epsilon_S.\]
利用引理3.1，我们有
\[\frac{\sqrt{nv}\epsilon_{S}}{c}=\frac{2\sqrt{nv}\epsilon_{S+1}}{c}\leq \frac{2\sqrt{nv}}{c}G^{-1}(\sqrt{nv/32}/c)\\
\leq 2\sqrt{32}\int_0^{G^{-1}(\sqrt{nv/32}/c)} H^{1/2}(\epsilon,\mathcal{F})d \epsilon\leq 12\int_0^{\epsilon_n} H^{1/2}(\epsilon,\mathcal{F})d \epsilon.\]
此时取
\[t_0=\frac{\sqrt{n}v\epsilon_{S}}{c}+\epsilon_{S}\sqrt{S}v u/c.\]
带入(1)得到
\[\mathbb{P}(\sup_{f}\sqrt{n}|\langle e, f-f_{(S)}\rangle_n|>t_0)\leq 2 \exp\left\{-\frac{S v u^2}{ c^2}\right\},\]
其中我们用到了条件$u\leq \sqrt{n/S}/2$。

情形II，如果$S+1\geq \sqrt{n}$，则有$\epsilon_S\sqrt{n}\leq 2^{\sqrt{n}-1}\sqrt{n}D$，它不超过$2D$。因此我们直接取
\[t_0=u v D/c,\]
并令$u>2$。带入(1)，利用条件$u\leq \sqrt{n/S}/2$，可得
\[\mathbb{P}(\sup_{f}\sqrt{n}|\langle e, f-f_{(S)}\rangle_n|>t_0)\leq 2 \exp\left\{-\frac{(u-2)^2 v}{c^2}\right\}.\]

综合上述两情形，可知
\[\sum_{i=0}^S t_i\leq 12 \sqrt{v}\int_0^D H^{1/2}(\epsilon,\mathcal{F})d\epsilon +4 u v D /c.\]
所有概率之和也可以被$C_1\exp\{-C_2 (u-2)^2\}$控制，里面的常数较复杂就不具体写了。另外注意到$u$的范围是$u\leq \sqrt{n/S}/2$，一个充分条件是$u\leq n^{1/4}/2$。

在推论1.3中，$x$可以和$\sqrt{n}$同阶，而这里$u$最多只能达到$n^{1/4}$阶，这是不合理的。我们自然希望得到更广的结果，不过这样的结果需要考虑重新构造$t_i$。

定义
\[t_i=\epsilon_{i-1}\sqrt{8vH(\epsilon_i,\mathcal{F})}+u_i,\\
u_i=\epsilon_{i-1}u v/c.\]
和之前的定义相比，只有$u_i$的部分有差别。注意到此时$u$的约束条件就变成了
\[u\leq \sqrt{n} / 2,\]
也就是我们获得了至多$\sqrt{n}$的阶。

利用(2)式，得到此情况下的尾部概率不超过
\[2 \exp\left\{-\frac{v u^2}{4 c^2}\right\}.\]
该式对所有$i$求和是发散的，不过好在我们实际上只有$S$项，也就是总概率不超过
\[2 \exp\left\{\log S-\frac{v u^2}{4 c^2}\right\}.\]
换句话说，只要$(v u^2)/(4 c^2)>2\log S$，总概率就不超过
\[2 \exp\left\{-\frac{v u^2}{8 c^2}\right\}.\]
我们注意到，这种情况下$u$不能太小（至少需要$\sqrt{\log S}$的阶）。按照前面的$S$选取方法，$S$不超过$\sqrt{n}$，因此$\sqrt{\log S}$的阶远小于$n^{-1/4}$。所以只要$n$充分大的情况下，这种情况下的$u$的取值范围就可以覆盖$[O(n^{1/4}),O(n^{1/2}))]$之间的部分，其中具体操作不再赘述。

综合上述两种情况，我们得到了下面的主要定理。

定理. 假设$v=2\mathbb{E}(\exp\{|e_i|/c\})c^2<+\infty$，积分$\int_0^D H^{1/2}(\epsilon,\mathcal{F})d \epsilon$收敛，且$2<u<\sqrt{n} / 2$，则对于充分大（依赖于$v,c$）的$n$有
\[\mathbb{P}\left(\sup_{f\in\mathcal{F}}\sqrt{n}\langle e,f\rangle_n> 12 \sqrt{v}\int_0^D H^{1/2}(\epsilon,\mathcal{F})d\epsilon +4 u v D /c\right)\leq 6\exp\left\{-\frac{v (u-2)^2}{8c^2}\right\}.\]

注解：粗略的讲，对于很大的$u$，一个随机变量大于其均值加上u$\times$标准差的概率很小。在上述定理中，我们可以粗略的认为我们感兴趣的随机变量的均值~$\sqrt{v}\int_0^D H^{1/2}(\epsilon,\mathcal{F})d\epsilon$，标准差~$vD/c$。实际上，在很多情况下，事实就是如此。

三、覆盖数

由于$A:=\sup_{f\in\mathcal{F}}\langle e, f \rangle_n$，可以想象$A$的大小和函数空间$\mathcal{F}$的“大小”也有密切的关系。

如果$\mathcal{F}$太大，很容易导致$A=\infty$。所以我们会对$\mathcal{F}$提出一些最低的要求。首先我们要求$\mathcal{F}$是$L_\infty$空间的紧子集。在此条件下，我们要需要进一步量化函数空间的大小。为此，需要引入覆盖数的概念。

首先对$f\in L_\infty,\epsilon>0$，令$B(f,\epsilon)$为以$f$为圆心，$\epsilon$为半径的$L_\infty$（开）球。

定义. 对$\epsilon>0$，覆盖数$N(\epsilon,\mathcal{F})$为最小的自然数$N$，使得存在中心$f_1,\ldots,f_N\in L_\infty$，满足覆盖条件
\[\mathcal{F}\subset\bigcup_{i=1}^N B(f_i,\epsilon).\]

定义. 定义度量熵\(H(\epsilon,\mathcal{F})=\log N(\epsilon,\mathcal{F})\)。

注解：覆盖数的对数之所以叫“熵”，是因为它有来自信息论的渊源。最早Kolmogorov定义熵为$\lceil\log_2 N(\epsilon,\mathcal{F})\rceil$。其涵义为：为了（在一定精度意义下）近似一个函数空间，所需要的二进制编码的最小字节数。在概率论中我们借用了信息论中的名称，不过其信息论下的涵义在此处已经不复存在。

本文中不会对任何具体的函数空间计算覆盖数的上界，因为这些计算已经脱离了概率论的范畴。我们只需要知道对一切重要和常见的函数空间，覆盖数的上界计算已经有现成的结果了。

现在我们来看看$H(\epsilon,\mathcal{F})$有哪些性质。根据定义，$H(\cdot,\mathcal{F})$是非负减（阶梯）函数，满足$H(+\infty,\mathcal{F})=0$。

我们令$G(\epsilon)=H^{1/2}(\epsilon,\mathcal{F})$。仿照初等概率论中的分布函数，我们对$0<x<G(0+)$，定义
\[G^{-1}(x):=\sup\{y\geq 0: G(y)\geq x\}.\]

下面证明一个引理。

引理3.1. 对一切$0<t<G(0+)$有
\[G^{-1}(t)t\leq \int_0^{G^{-1}(t)} G(x) d x.\]

证明. 如果允许不够严格的证明会很容易，只需要换元+分部积分立刻得到答案。严格的证明则需要加入一些实分析的技巧。
如果$\liminf_{x\downarrow 0} G(x)x>0$，则有$\int_0^{G^{-1}(t)} G(x) d x$发散，此时没什么需要证明的。
下面假定$\liminf_{x\downarrow 0} G(x)x=0$。取序列$a_n\downarrow 0$，满足$G(a_n)a_n\rightarrow 0$。
构造满足如下条件的函数$G_n$：
1）$G_n(\cdot)$连续，且严格单调减。
2）对一切$0<x<G(0+)$及$n$，$G_n(x)>G(x)$且$G_n(x)\downarrow G(x)$。
3）若$\int_0^{G^{-1}(t)} G(x) d x$有限，则$\int_0^{G^{-1}_1(t)} G_1(x) d x\leq 2\int_0^{G^{-1}(t)} G(x) d x$。
这样的$G_n$显然是存在的，例如可以构造分段线性的$G_n$。综合上面的各种单调性，不难看出
\[G_n^{-1}(G(a_n))\geq a_n, G^{-1}(G_n(x))\leq x, G_n^{-1}(x)\downarrow G^{-1}(x)\]
考虑以下不等式序列，其中用到了换元法（测度变换）和分部积分公式：
\[0\leq \int_t^{G(a_n)} G^{-1}(x)d x\\
=\int_{G_n^{-1}(t)}^{G_n^{-1}(G(a_n))}G^{-1}(G_n(x)) d G_n(x)\\
\leq \int_{G_n^{-1}(t)}^{a_n}x d G_n(x)\\
=a_n G_n(a_n)-G_n^{-1}(t)t+\int_{a_n}^{G_n^{-1}(t)} G_n(x) d x.\]
整理得
\[G^{-1}_n(t)t\leq a_n G_n(a_n)+\int_{a_n}^{G_n^{-1}(t)} G_n(x) d x.\]
令$n\rightarrow\infty$，结合条件3）和控制收敛定理，即得结论。

二、两个概率结果

我们先从简单的步骤开始。下面的引理简单但实用。

引理2.1. 设$X_1,\ldots,X_n$是随机变量，$a_1,\ldots,a_n$是实数，$a>a_1+\cdots+a_n$则有
\[\mathbb{P}\left(\sum_{i=1}^n X_i>a\right)\leq \sum_{i=1}^n\mathbb{P}(X_i>a_i).\]

证明. 注意到$\{\sum_{i=1}^n X_i>a\}\subset\cup_{i=1}^n \{X_i>a_i\}$。所以
\[\mathbb{P}\left(\sum_{i=1}^n X_i>a\right)\leq \mathbb{P}\left(\bigcup_{i=1}^n \{X_i>a_i\}\right)\leq \sum_{i=1}^n\mathbb{P}(X_i>a_i).\]

第二个引理涉及到随机变量的最大值，也是显然的结论。

引理2.2. 设$X_1,\ldots,X_n$是随机变量，$t$是实数，则有
\[\mathbb{P}(\max_{i} X_i>t)\leq \sum_{i=1}^n \mathbb{P}(X_i>t).\]

证明. 只需注意到$\{\max_{i} X_i>t\}=\cup_{i=1}^n\{X_i>t\}$。剩余部分和引理2证明相同。

如果$\mathbb{P}(X_i>t)$很小，在适当的情况下可以让求和也较小。下面的推论是一种我们实际使用的情况，其中$\mathbb{P}(X_i>t)\leq C_1\exp(-C_2 t^2)$，如前一节推论1所示。

推论2.3. 如果$\mathbb{P}(X_i>t)\leq C_1\exp(-C_2 t^2)$，则有
\[\mathbb{P}(\max_{i}X_i>t)\leq C_1\exp(\log n-C_2 t^2).\]

推论2.3说明，只要$t>\sqrt{\log n/ C_2}$，$\mathbb{P}(\max_{i}X_i>t)$就能以很快的速度衰减。

一、 Bernstein不等式
Bernstein不等式是研究这个问题的基本出发点。其叙述如下：
定理1.1（Bernstein不等式）. 假设$e_1,\ldots,e_n$是零均值独立随机变量，且存在常数$v_0,M>0$满足
\[\mathbb{E}\left(\exp\{|e_i|/M\}-1-\frac{|e_i|}{M}\right)M^2\leq \frac{v_0}{2},\]
则有
\[\mathbb{P}(n^{-1/2}|e_1+\cdots+e_n|>x)\leq 2 \exp\left\{-\frac{x^2}{2(n^{-1/2}Mx+v_0)}\right\},\]
对一切$x>0$成立。

Bernstein不等式的证明是纯分析的，过程比较复杂就从略了，可以在很多书籍或讲义里找到。

我们用$|\cdot|_\infty$来表示$\mathcal{F}$上的$L_\infty$范数。首先我们有下面的引理成立。

引理1.2. 令$v=2\mathbb{E}(\exp\{|e_i|/c\})c^2$，$a\geq |f|_\infty$。则对一切$x>0$有
\[\mathbb{P}(\sqrt{n}|\langle e,f\rangle_n|>x)\leq 2 \exp\left(-\frac{x^2}{2(n^{-1/2}a c x+a^2 v)}\right).\]
证明. 由Bernstein不等式取$M=a c, v_0=a^2 v$即得。

Bernstein不等式的有用之处在于当$x$较小时，例如$n^{-1/2} a c x\leq a^2 v$时，等式右端项类似于$2\exp(-C x^2)$，如下述推论所示。

推论1.3. 在引理1.2的条件下，如果$x$满足
\[0<x\leq \sqrt{n} a v/c,\]
则有
\[\mathbb{P}(\sqrt{n}|\langle e,f\rangle_n|>x)\leq 2 \exp\left(-\frac{x^2}{4 a^2 v}\right).\]

很显然，如果随机变量$e_i$满足Bernstein不等式的条件，那么$|e_i|-\mathbb{E}|e_i|$也满足条件。
引理1.4在引理1.2的条件下，
\[\mathbb{P}\left(n^{-1/2}\sum_{i=1}^n\left(|e_i|-\mathbb{E}|e_i|\right)>x\right)\leq 2 \exp\left\{-\frac{x^2}{2(n^{-1/2}cx+v)}\right\},\]
对一切$x>0$成立。
证明. 首先
\[\mathbb{E}e^{||e_i|-\mathbb{E}|e_i||/c}=\mathbb{E}e^{(|e_i|-\mathbb{E}|e_i|)/c}I(|e_i|>\mathbb{E}|e_i|)+\mathbb{E}e^{(\mathbb{E}|e_i|-|e_i|)/c}I(|e_i|<\mathbb{E}|e_i|)\\
\leq \frac{v}{2 c^2e^{\mathbb{E}[|e_i|/c]}}+e^{\mathbb{E}[|e_i|/c]}.\]
由Jensen不等式可知$e^{\mathbb{E}[|e_i|/c]}\leq \mathbb{E}e^{|e_i|/c}=v/(2c^2)$，即$e^{\mathbb{E}[|e_i|/c]}\in[1,v/(2c^2)]$。而函数$v/(2c^2 x)+x$在$[1,v/(2c^2)]$上的最大值显然在端点处达到，所以
\[\mathbb{E}e^{||e_i|-\mathbb{E}|e_i||/c}\leq 1+\frac{v}{2c^2}.\]
从而
\[\mathbb{E}\left(\exp\{||e_i|-\mathbb{E}|e_i||/c\}-1-\frac{||e_i|-\mathbb{E}|e_i|}{c}\right)c^2\leq \frac{v}{2},\]
再结合Bernstein不等式即得。

我们再将$\mathbb{E}|e_i|$移到右边就得到推论1.5
推论1.5. 在引理1.4的条件下，
\[\mathbb{P}\left(n^{-1/2}\sum_{i=1}^n |e_i|>x\right)\leq 2 \exp\left\{-\frac{(x -\sqrt{n}v/c)^2}{2n^{-1/2}cx}\right\},\]
对一切$x>\sqrt{n}v/c$成立。

证明.利用
\[\mathbb{E}|e_i|\leq \frac{\mathbb{E}e^{c|e_i|}}{ c}=v/c.\]
及引理1.4即得。

假设$e_1,\ldots,e_n$是独立同分布，且均值为零的随机变量，$x_1,\ldots,x_n$为确定的点，$f$为确定的函数，我们引入（随机内积）记号
\[\langle e,f\rangle_n:=\frac{1}{n}\sum_{i=1}^n e_i f(x_i).\]

在（非参数）回归分析中的理论研究中，一个重要的量是
\[A:=\sup_{f\in\mathcal{F}}\langle e,f\rangle_n,\]
其中$\mathcal{F}$是某个函数空间，它和对应非参数回归的构造方法有关。这个量的大小和相应的回归分析方法的收敛速度有密切的关系。

在本文中，我们假定$e_i$满足$\mathbb{E}[\exp(|e_i|/c)]<+\infty$对某个$c>0$成立。我们来考虑如何有效的估计$A$的上界。

解决这个问题已经有标准方法，但是传统的推导方法过于复杂（我完全没有读完整证明的耐心），我最近做了些研究，得到了一个相对简单的推导过程，虽然最终结论比传统结果弱一些，但是在很多情况下已经足够了。

一个骰子扔出3的概率和两个骰子扔出6的概率不等，这很难理解么？

最近的研究用到了一个概率不等式。

设$X_1,\ldots,X_n$为独立的随机变量，记其部分和
\[S_k=\sum_{i=1}^k X_i.\]

定理（Ottaviani's inequality）. 对任意的$\lambda,\nu>0$，有
\[\mathbb{P}\left(\max_{k\leq n}|S_k|>\lambda+\mu\right)\leq \frac{\mathbb{P}(|S_n|>\lambda)}{1-\max_{k\leq n}\mathbb{P}(|S_n-S_k|>\mu)}.\]

Ottaviani's inequality是一个很强的极大值不等式。为了说明这一点，假设$X_i$的尾部概率衰减很快，例如正态分布，同时取$\lambda=\mu$足够大，这时会有
\[\mathbb{P}(|S_n|>\lambda+\mu)\ll\mathbb{P}(|S_n|>\mu)\ll 1.\]
从而不等式右侧可以非常小。下面给出不等式的证明。

证明. 定义事件$A_k=\{|S_k|>\lambda+\mu,|S_{k-1}|\leq \lambda+\mu,\cdots,|S_1|\leq \lambda+\mu\}$，即$S_k$在时刻$k$首次超过$\lambda+\mu$。显然，左式中的事件即为$A_1,\ldots,A_n$的不交并。
根据定义，$|S_n-S_k|$独立于$\{|S_1|,\ldots,|S_k|\}$，因而有
\[\mathbb{P}(A_k)\min_{j\leq n}\mathbb{P}(|S_n-S_j|\leq \mu)\\
\leq \mathbb{P}(A_k)\mathbb{P}(|S_n-S_k|\leq \mu)\\
= \mathbb{P}(A_k,|S_n-S_k|\leq \mu)\\
\leq \mathbb{P}(A_k,|S_n|>\lambda),\]
最后不等式来源于$A_k$隐含事件$\{|S_k|>\lambda+\mu\}$。最后对$k$求和即得原不等式。

第一个做出来的人肯定是有偶然性的，但问题的关键是在第一个人之后是否有人继承和发扬。这个就和社会认知，财富分配等问题有关了。