2009年2月21日星期六

Chernoff bound

Chernoff bound

《概率与计算》一书中介绍了一个叫作“切尔诺夫界”的不等式,在概率论中,可以用来估计随机变量尾分布的性质,也就是随机变量在远离其期望值的某区域中取值的概率。切尔诺夫界可以用于分析算法的概率意义下的性能,具体来说,能给出算法运行时间超过某一阈值的概率的上界,或者解的相对误差超过某一阈值的概率的上界。

Wikipedia上有切尔诺夫界的若干中形式的公式。我在这里不加证明地引用其中一个比较简单的公式,然后给出一个它在算法分析上应用。

切尔懦夫定理:X1,...,Xn是独立随机变量,Xi服从0-1分布,,则对任意的ε,0<ε<1,有:

考虑这样一个判定问题:G=(V,E)为无向图,D={(si,ti),i=1,...,n,}为一个顶点对的集合,问是否存在{pi,i=1,...,n},其中pi为连接si到ti的路,使得任何一条边e属于E都没有被两条路pi、pj覆盖。
对应解一个优化问题:给一组路{pi,i=1,...,n},对于任一e属于E,定义cong(e)=|{pi|e属于pi,i=1,...,n}|,即通过e的路的条数。求{pi,i=1,...,n}使得C=max{cong(e),e属于E}达到最小,即让被通过次数最多的边,通过次数最少。

这个问题是NP难的,不过我们可以设计这样一个算法:线性规划松弛,然后随机近似。通过切尔诺夫界能够给出这个算法的近似率的一个估计。

令Pi为从si到ti的所有路的集合,记f(p,i)=1{p属于Pi},也就是表示p是否是一条从si到ti的路。优化目标是min C。约束条件有下面两个:
首先任何一对点si,ti恰有一条路p通过,
,对于任意i,
其次每一条边的冲突数不超过C,
,对任意e属于E。
我们把f(p,i)松弛到[0,1],用线性规划的方式求解。然后对每个i=1,...,n,用轮盘赌的方式以概率f(pi,i)选pi属于Pi。

上面就是线性规划松弛加随机近似的算法,下面用概率的方法分析这个算法。

定义随机变量表示路选中的路pi是否通过边e,i=1,...,n,e属于E。则:

定义,表示边e的被通过的次数。则:

由切尔诺夫界定理,立得:

没有评论: