基本不等式
The Markov inequality
a nonnegative random variable Y, for every y > 0, $Pr(Y>=y)$ satisfies
$Pr(Y>=y)<=EY/y$
进一步，$\lim\limits_{y \to \infty}yP(Y>=y)=0$
切比雪夫不等式
（Chebyshev inequality）
切比雪夫不等式
X的均值是u,方差是$\sigma^2$,那么，$\forall t>0,Pr[\mid X-u \mid \geq t \sigma] \leq \dfrac{1}{t^2}$
等价表示：
$Pr[\mid X-u \mid \geq s] \leq \dfrac{\sigma^2}{s^2}$
证明提要：
$\sigma^2=\sum\limits_{x_i}(x_i-u)^2f(x_i) \geq \sum\limits_{\mid x_i -u \mid \geq s}(x_i-u)^2f(x_i)$
$ \geq \sum\limits_{\mid x_i -u\mid \geq s}s^2f(x_i)=s^2\sum\limits_{\mid x_i -u\mid \geq s}f(x_i)$
$=s^2 Pr[\mid X-u \mid \geq s]$
（其实根据Markov inequality，也容易证明，如下）
$P((X-EX)^2\geq y)\leq \dfrac{E(X-EX)^2}{y}$
然后得到结论。
切比雪夫不等式的推广
X的均值是u，n阶中心距$u_{\mid n \mid}=E[\mid X-u \mid ^n],(n \geq 1)$,有
$Pr[\mid X-u \mid \geq t]\leq \dfrac{u_{\mid n\mid}}{t^n}$
证明方法相同
切比雪夫单边不等式
X的均值是u,方差是$\sigma^2$,那么，$\forall s>0,Pr[ X-u \geq s] \leq \dfrac{\sigma^2}{s^2+\sigma^2}$
Cherno bounds
根据 the Markov inequality
$P(\exp(rZ)\geq y)\leq \dfrac{E\exp(rZ)}{y}$
我们把y换成$\exp(rb)$，然后这个不等式变换为：
$P(Z\geq b)\leq E\exp(rZ) \exp{(-rb)}$
这个不等式有个重要应用：随机过程中的加和问题$S_n=X_1+X_2+…+X_n$，有：
$P(S_n\geq na)\leq E\exp(rS_n) \exp{(-rna)}$
所以，$P(S_n\geq na)\leq (E\exp{(rX)})^n \exp{(-rna)}$
大数定律
弱大数定律
如果$X_i$独立同分布，$u=EX,\bar X=1/n \sum X_i $,
$\forall \epsilon >0,n\to \infty ,Pr[\mid \bar X-u \mid >\epsilon] \to 0$
辛钦大数定律
条件：$X_k$独立同分布
对任意$\varepsilon>0$
\(\lim\limits_{n\to \infty} P\{ \mid \dfrac{1}{n} \sum\limits_{k=1}^n X_k -u\mid < \varepsilon \}=1\)
（用切比雪夫不等式去证明）
伯努利大数定理
$f_A$是n次独立实验中，事件A发生的概率。
p是事件A在每次实验中发生的概率。
（用辛钦大数定律去证明）
中心极限定理
（Lindberg-Levy中心极限定理）
前提：$X_1,X_2,…$独立同分布，且$EX_i=u, DX_i=\sigma^2$，总有
也就是说，独立同分布的均值，服从$N(\mu,\sigma^2)$
De Moivre-Laplace 中心极限定理
其实就是 Levy 的特殊情况
$X_i$是0-1分布，那么
\(\lim\limits_{n\to \infty} P\{ \dfrac{\sum\limits_{i=1}^n X_i -n p}{\sqrt n p(1-p)} \leq x\} =\Phi(x)\)
二项分布趋近于正态分布。
（有时可以用来做一些近似计算之类的）
