版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:NYUCOURANT INST MATH SCIDEPT COMP SCINEW YORKNY 10012 CORNELL UNIVDEPT COMP SCIITHACANY 14853
出 版 物:《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)
年 卷 期:1995年第8卷第2期
页 面:223-250页
核心收录:
学科分类:07[理学] 0701[理学-数学] 070101[理学-基础数学]
主 题:CHERNOFF-HOEFFDING BOUNDS LARGE DEVIATIONS RANDOMIZED ALGORITHMS DERANDOMIZATION LIMITED INDEPENDENCE CORRELATION INEQUALITIES DETERMINISTIC SIMULATION
摘 要:Chernoff-Hoeffding (CH) bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables (r.v. s). We present a simple technique that gives slightly better bounds than these and that more importantly requires only limited independence among the random variables, thereby importing a variety of standard results to the case of limited independence for free. Additional methods are also presented, and the aggregate results are sharp and provide a better understanding of the proof techniques behind these bounds. These results also yield improved bounds for various tail probability distributions and enable improved approximation algorithms for jobshop scheduling. The limited independence result implies that a reduced amount and weaker sources of randomness are sufficient for randomized algorithms whose analyses use the CH bounds, e.g., the analysis of randomized algorithms for random sampling and oblivious packet routing.