!!!!!!!!! Probability And Computing Randomized Algorithms And Probabilistic Analysis.pdf

文档介绍：Concentration of Measure for the Analysis of
Randomised Algorithms
Devdatt P. Dubhashi Alessandro Panconesi
October 21, 2005
DRAFT
2
DRAFT
Contents
1 Chernoff–Hoeffding Bounds 17
What is “Concentration of Measure”? . . . . . . . . . . . . . . . . 17
The Binomial Distribution . . . . . . . . . . . . . . . . . . . . . . 19
The Chernoff Bound . . . . . . . . . . . . . . . . . . . . . . . . . 19
Heterogeneous Variables . . . . . . . . . . . . . . . . . . . . . . . 21
The Hoeffding Extension . . . . . . . . . . . . . . . . . . . . . . . 22
Useful Forms of the Bound . . . . . . . . . . . . . . . . . . . . . . 22
A Variance Bound . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2 Interlude: Probabilistic Recurrences 33
3 Applying the CH-bounds 39
Probabilistic Amplification . . . . . . . . . . . . . . . . . . . . . . 39
Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Data Structures: Skip Lists . . . . . . . . . . . . . . . . . . . . . 41
Skip Lists: The Data Structure . . . . . . . . . . . . . . . 41
Skip Lists: Randomization makes it easy . . . . . . . . . . 42
3
DRAFT
4 CONTENTS
Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Packet Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Randomized Rounding . . . . . . . . . . . . . . . . . . . . . . . . 49
Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4 Chernoff-Hoeffding Bounds in Dependent Settings 55
Negative Dependence . . . . . . . . . . . . . . . . . . . . . . . . . 55
Local Dependence . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Janson’s I