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 language | English (US) |
---|---|
Title of host publication | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
Publisher | Publ by ACM |
Pages | 331-340 |
Number of pages | 10 |
State | Published - 1993 |
Event | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA Duration: Jan 25 1993 → Jan 27 1993 |
Other
Other | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
City | Austin, TX, USA |
Period | 1/25/93 → 1/27/93 |
ASJC Scopus subject areas
- General Engineering