一个tail bound定理

59 阅读 0 评论 39 点赞

我是靠谱客的博主繁荣红酒，最近开发中收集的这篇文章主要介绍一个tail bound定理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一些基础：

Markov不等式： $x$ 为非负随机变量， $p(x>a)leq e(x)/a$

Chebyshev不等式： $p(|x-e(x)|geq a)leq e((x-e(x))^{2})/a^{2}$

Markov不等式的推论：当r为偶数时，有 $p(|x|geq a)=p(x^{r}geq a^{r})leq e(x^{r})/a^{r}$

注记：

Markov不等式要求X是非负随机变量，给出的界随着a的增长，以 $1/a$ 的速率下降
Chebyshev不等式不要求X是非负随机变量，给出的界随着a的增长，以 $1/a^{2}$ 的速率下降
推论不等式在r为偶数的时候成立，给出的界随着a的增长，以 $1/a^{r}$ 的速率下降
如果 $e(x^{r})$ 相较于 $e(x)$ , $e(x^2)$ 等低阶矩增加的不是很多，被某种上界所限制，则推论效果会比较好，可以获得更紧的界（r越大，界越紧）；

定理的Intuition：

在机器学习中，我们将样本看作随机变量，并且经常研究 $x=x_{1}+x_{2}+...+x_{n}$ 的相关性质
Chernoff界只适用于取值范围有界的随机变量（例如0-1随机变量），而指数分布和高斯分布的取值范围是无界的。
可以证明如下结论：方差为1的指数分布和高斯分布的第s阶矩不超过s!（于是定理的复杂条件就比较合理了）

定理：

令 $x=x_{1}+x_{2}+...+x_{n}$ ， $x_{1},...,x_{n}$ 是n个相互独立的随机变量，均值为零，方差不超过 $sigma ^{2}$

且满足 $|e(x_{i}^{r})|leq sigma^{2}r!$ ，对于 $r=3, 4, ..., s$ 成立（其中正偶数 $sleq nsigma^{2}/2$ ）

（以上是对随机变量的性质的限制，要求随机变量的各阶矩有某一个上界）

若a $in$ [0, $sqrt2 n sigma^{2}$ ]，有 $pr(|x_{1}+x_{2}+...+x_{n}|geq a)leq left ( 2snsigma^{2}/a^{2})^{s/2}$

如果进一步有条件 $sgeq a^{2}/(4nsigma^{2})$ 成立，则有更紧的界 $pr(|x_{1}+x_{2}+...+x_{n}|geq a)leq 3e^{-a^2/(12nsigma^{2})}$

证明：

$e(x^{r})=e((x_{1}+x_{2}+...+x_{n})^{r})=sum r!/r_{1}!r_{2}!...r_{n}!e(x_{1}^{r_{1}})e(x_{2}^{r_{2}})...e(x_{n}^{r_{n}})$

下面考虑和式中的各项的值，可以分为如下两种情况：

情形1：若存在某个 $r_{i}=1$ ，由均值为0知该项必然为0

情形2：若所有非零的 $r_{i}>=2$ ，则该项 $leq r!sigma^{2(number: of: nonzero:r_{i}:in:set)}$

固定集合{ ${ r_{1},r_{2},...,r_{n} }$ }中非零元的个数，假设为t

则非零元一共有 $binom{n}{t}$ 种选择，不妨假设非零元为 $r_{1},r_{2},...,r_{t}$ ，

问题转化为求解方程 $r_{1}+r_{2}+...+r_{t}=r$ 满足 $r_{i}geq 2$ 的解的个数，易知一共有 $binom{r-t-1}{t-1}$ 个解。

相应的，和式中满足{ ${ r_{1},r_{2},...,r_{n} }$ }中一共有t个非零元并且非零元都不小于2的项一共有 $binom{n}{t}$ $binom{r-t-1}{t-1}$ 个，这样的项的上界为 $r!sigma^{2t}$

故和式 $e(x^{r})$ 的上界为 $r!sum_{t=1}^{r/2}f(t)$ ，其中 $f(t)=$ $binom{n}{t}$ $binom{r-t-1}{t-1}$ $sigma^{2t}$

而 $f(t)=$ $binom{n}{t}$ $binom{r-t-1}{t-1}$ $sigma^{2t}$ $leq h(t)=(nsigma^{2})^{t}/t!*2^{r-t-1}$

（利用 $binom{n}{t}=n*(n-1)*...*(n-t+1)/t!<=n^{t}/t!$ 和 $binom{r-t-1}{t-1}leq 2^{r-t-1}$ ）

由于 $tleq r/2leq nsigma^{2}/4$ ，得 $h(t)/h(t-1)=nsigma^{2}/2tgeq 2$ ，故

$e(x^{r})=r!sum_{t=1}^{r/2}f(t)leq r!h(r/2)(1+1/2+1/4+...)leq r!/(r/2)!*2^{r/2}*(nsigma^2)^{r/2}$

应用Markov不等式，我们可以得到：

$p(|x|>a)=p(|x|^{r}>a^{r})leq e(|x|^{r})/a^{r}$ （Markov不等式）

$leq r!(nsigma^{2})^{r/2}2^{r/2}/(r/2)!a^{r}$ $=g(r)$ （利用上面得出的对 $e(x^{r})$ 的估计）

$leq (2rnsigma^{2}/a^{2})^{r/2}$ （利用 $r/2+1leq r,...,r-1leq r,rleq r$ ）

不等式对所有的偶数 $rleq s$ 成立，令 $r=s$ ，即可得到第一个不等式

对于偶数r，有 $g(r)/g(r-2)=4(r-1)nsigma^{2}/a^{2}$ ，故当 $r-1leq a^{2}/(4nsigma^{2})$ 时， $g(r)$ 递减，之后 $g(r)$ 递增

令r为 $leq a^{2}/(6nsigma^{2})$ 的最大偶数（则 $r+2geq a^{2}/(6nsigma^{2})$ ），tail probability至多为 $e^{-r/2}$ $leq e^{1-a^2/(12nsigma^2)}leq 3*e^{-a^2/(12nsigma^2)}$ ，即可得到第二个不等式