尾概率不等式及其应用
1. 引入
很多时候精确求概率是困难的，可以利用不等式求一个概率的上界。
问题：多少次试验能以95%的概率保证频率和概率的差距小于某个阈值呢？
2. Markov不等式
令X为样本空间上的非负随机变量，对任意一个正实数a，有
\[P(X \geq a) \leq \frac{E(X)}{a}\]这个上界比较松
3. Chebyshev不等式
令X为样本空间上的非负随机变量，对任意一个正实数r，有
\[P(|X-E(X)| \geq r) \leq \frac{\operatorname{Var}(X)}{r^{2}}\]该不等式的证明需要用到Markov不等式和
\[E\left((X-E(X))^{2}\right)=\operatorname{Var}(X)\]Chebyshev不等式更合理，这是因为X/n的方差与n有关
4. Chernoff不等式
假设X为定义在样本空间上的n个独立伯努利变量的和，则对任意小的delta，有：
\[P(X<(1-\delta) \mu)<\exp \left(-\mu \delta^{2} / 2\right)\] \[P(X>(1+\delta) \mu)<\exp \left(-\mu \delta^{2} / 4\right)\]5. 尾概率不等式的应用——Morris算法
处理海量数据的方式有（1）使用近似算法得到近似结果。（2）使用抽样方法减少数据集。这两种方式的计算结果都不一定准确，可以用尾概率不等式推断这些算法的精度。
5.1 Morris算法
Morris算法用于近似表示大整数，通常表示一个大数n需要log2n位（取上界）。
算法结构包括：
- 事件流计数 1 1 1 1 1 1 1 1 1 1
- 计数真实值 1 2 3 4 5 6 7 8 9 10
- 计数器X值 1 1 2 2 2 2 3 3 3 3
- 抽样概率 1/2 两次后 1/4 四次后 1/8
- 计数估计值 1 1 3 3 3 3 7 7 7 7
X实际上是在估计存储N需要的位数
虽然真实值和估计值的误差可能到两倍，但这是一个无偏估计
5.2 Morris+算法
上面提到Morris算法是一个无偏估计，但它的方差会随着N的增大而增大，减小方差可以采取的方式有多次计算求平均。因此Morris+算法维护多个计数器。
近似估计：估计值N1偏离真实值N大于σN的概率小于δ，称N1为N的（σ, δ）近似估计。
5.3 Morris++算法
对于多次Morris+算法，求中位数。由于Morris+算法减小了方差，多次的Morris+算法会越来越接近真实值。
该算法的近似估计的证明需要构造指示变量Yi和运用Chernoff不等式
\[Y_{i}=\left\{\begin{array}{ll} 1, & \text { if }\left|\frac{1}{n} \sum_{j=1}^{n} \widehat{N_{i j}}-N\right|>\epsilon N ; \\ 0, & \text { otherwise } \end{array}\right\]
