CHERNOFF-HOEFFDING BOUNDS FOR APPLICATIONS WITH LIMITED INDEPENDENCE

作     者：SCHMIDT, JP SIEGEL, A SRINIVASAN, A 

作者机构：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.