在统计学习理论中有一个很基础的不等式：Hoeffding不等式，这个不等式是大数定律的一种形式。大数定律中最简单的不等式应该就是Chebyshev不等式了。我们今天来证明一下它，以及给出线性bound的几个推论：

Chebyshev不等式：假设t是非负随机变量，对于任意的$\alpha>0$，我们都有：$P[t\geq \alpha]\leq \frac{E \left(t\right)}{\alpha}$

证明如下：
我们定义一个集合$A\subset \Omega:A=\{t\in \Omega | t\geq a\}$,因此：

$$E\left(t\right)=\sum_{t\in \Omega}P\left(t\right)t=\sum_{t\in A}P\left(t\right)t+\sum_{t\notin A}P\left(t\right)t\leq \sum_{t\in A}P\left(t\right)t\\
\leq\sum_{t\in A}P\left(t\right)a = a P\left(A\right)$$
得证！
下面是俩推论：
1.随机变量$u$的均值是$\mu$，方差是$\sigma ^2$，因此可得，对任意$\alpha$，$P[\left(u-\mu\right)^2\geq \alpha]\leq \frac{\sigma^2}{\alpha}$
2.$u_1,u_2,…,u_N$是独立同分布的一组随机变量，每一个变量的均值都是$\mu$，方差是$\sigma^2$，定义新的随机变量$u=\frac{1}{N}\sum_{n=1}^{N}u_n$，对任意的$\alpha>0$，都有：$P[\left(u-\mu\right)^2\geq \alpha]\leq \frac{\sigma^2}{N\alpha}$