小当

数学版主

最新动态 2天前

  1. 5周前
    2019-01-16 11:27:33
    小当 发表了帖子 一个核函数的结果

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

    称$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$半正定。这个结果用类似的方法很容易证明。

  2. 4月前
    2018-10-18 12:13:15
    小当 发表了帖子 行列式计算

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

  3. 9月前
    2018-04-27 13:39:41
    小当 更新于 随机内积研究

    四、最终结果

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

    这里需要的一个重要的技术手段称为“链接”(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$。实际上,在很多情况下,事实就是如此。

  4. 10月前
    2018-04-24 11:14:30
    小当 更新于 随机内积研究

    三、覆盖数

    由于$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)和控制收敛定理,即得结论。

  5. 2018-04-24 03:18:13
    小当 更新于 随机内积研究

    二、两个概率结果

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

    引理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)$就能以很快的速度衰减。

  6. 2018-04-24 02:31:51
    小当 更新于 随机内积研究

    一、 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即得。

  7. 2018-04-24 02:31:36
    小当 发表了帖子 随机内积研究

    假设$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$的上界。

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

  8. 2018-03-30 09:22:33

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

  9. 11月前
    2018-03-16 04:55:43
    小当 发表了帖子 Ottaviani's inequality

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

    设$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$求和即得原不等式。

  10. 2018-03-03 03:53:09

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

查看更多