概率论初步
期望的线性性
随机变量的方差
推论:若随机变量 互相独立,则有:
(互相独立的定义:)
马尔科夫不等式
设 为非负随机变量,则 : 证明: (离散形式,连续形式的证明方法类似)
其中第一个 依赖于 非负的特性,因此非负是必须的!
马尔科夫不等式让我们可以在只知道随机变量期望的情况下对于其分布概率进行粗略定界。
切比雪夫不等式
设 为随机变量,则 : 证明: 注意到 且 非负,因此我们可以在第二步使用马尔科夫不等式。
如果我们不仅知道随机变量的期望(一阶矩),还知道其方差(二阶矩),那么切比雪夫不等式可以给出比马尔科夫不等式更为精确的上界。
切尔诺夫上界(Chernoff Bound)
设随机变量 ,其中 为 上互相独立的随机变量,则 : 且 :
三个不等式给出上界的比较
考虑如下问题:投
马尔科夫不等式:
显然,
切比雪夫不等式:
设随机二元变量
显然,取
看来这个例子里面还是切比雪夫不等式给出的上界最好 —— 是不是切尔诺夫上界我学到的形式本身太 loose 了?
近似算法初步
定义
若算法
是多项式时间的。- 对于所有输入,
的输出 ,其中 是该输入的最优解。
对于最大化问题,第二个条件为
(继续假设是最小化问题)
显然,为了精确计算
例:最小顶点覆盖问题
输入:
目标:最小化点集
这是一个知名的 NP Complete 问题。在这里我们设计一个简单的
思路:考虑
同时注意到,任意无向图极大匹配的大小必定是其点覆盖集大小的下界,因为点覆盖必须取极大匹配当中每一条边的至少一个端点才能完成覆盖!
算法:
- 计算
的一个极大匹配 。 - 取极大匹配所有边的所有端点为
。
为什么正确?考虑反证:若
近似比证明: