Chernoff-Hoeffding bounds for applications with limited independence

Jeanette P. Schmidt, Alan Siegel, Aravind Srinivasan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Chernoff-Hoeffding bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables. We present a simple technique which gives slightly better bounds than these, and which 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. They also yield improved bounds for various tail probability distributions and enable improved approximation algorithms for job-shop scheduling. The `limited independence' result implies that a reduced amount of randomness and weaker sources of randomness are sufficient for randomized algorithms whose analyses use the Chernoff-Hoeffding bounds, e.g., the analysis of randomized algorithms for random sampling and oblivious packet routing.

Original languageEnglish (US)
Title of host publicationProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Pages331-340
Number of pages10
StatePublished - 1993
EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
Duration: Jan 25 1993Jan 27 1993

Other

OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
CityAustin, TX, USA
Period1/25/931/27/93

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Chernoff-Hoeffding bounds for applications with limited independence'. Together they form a unique fingerprint.

Cite this