| |
| |
Preface | |
| |
| |
| |
Chernoff-Hoeffding Bounds | |
| |
| |
| |
What Is "Concentration of Measure"? | |
| |
| |
| |
The Binomial Distribution | |
| |
| |
| |
The Chernoff Bound | |
| |
| |
| |
Heterogeneous Variables | |
| |
| |
| |
The Hoeffding Extension | |
| |
| |
| |
Useful Forms of the Bound | |
| |
| |
| |
A Variance Bound | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
Applications of the Chernoff-Hoeffding Bounds | |
| |
| |
| |
Probabilistic Amplification | |
| |
| |
| |
Load Balancing | |
| |
| |
| |
Skip Lists | |
| |
| |
| |
Quicksort | |
| |
| |
| |
Low-Distortion Embeddings | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
Chernoff-Hoeffding Bounds in Dependent Settings | |
| |
| |
| |
Negative Dependence | |
| |
| |
| |
Local Dependence | |
| |
| |
| |
Janson's Inequality | |
| |
| |
| |
Limited Independence | |
| |
| |
| |
Markov Dependence | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
Interlude: Probabilistic Recurrences | |
| |
| |
| |
Problems | |
| |
| |
| |
Martingales and the Method of Bounded Differences | |
| |
| |
| |
Review of Conditional Probabilities and Expectations | |
| |
| |
| |
Martingales and Azuma's Inequality | |
| |
| |
| |
Generalising Martingales and Azuma's Inequality | |
| |
| |
| |
The Method of Bounded Differences | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
The Simple Method of Bounded Differences in Action | |
| |
| |
| |
Chernoff-Hoeffding Revisited | |
| |
| |
| |
Stochastic Optimisation: Bin Packing | |
| |
| |
| |
Balls and Bins | |
| |
| |
| |
Distributed Edge Colouring: Take 1 | |
| |
| |
| |
Models for the Web Graph | |
| |
| |
| |
Game Theory and Blackwell's Approachability Theorem | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
The Method of Averaged Bounded Differences | |
| |
| |
| |
Hypergeometric Distribution | |
| |
| |
| |
Occupancy in Balls and Bins | |
| |
| |
| |
Stochastic Optimisation: Travelling Salesman Problem | |
| |
| |
| |
Coupling | |
| |
| |
| |
Handling Rare Bad Events | |
| |
| |
| |
Quicksort | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
The Method of Bounded Variances | |
| |
| |
| |
A Variance Bound for Martingale Sequences | |
| |
| |
| |
Applications | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
Interlude: The Infamous Upper Tail | |
| |
| |
| |
Motivation: Non-Lipschitz Functions | |
| |
| |
| |
Concentration of Multivariate Polynomials | |
| |
| |
| |
The Deletion Method | |
| |
| |
| |
Problems | |
| |
| |
| |
Isoperimetric Inequalities and Concentration | |
| |
| |
| |
Isoperimetric Inequalities | |
| |
| |
| |
Isoperimetry and Concentration | |
| |
| |
| |
The Hamming Cube | |
| |
| |
| |
Martingales and Isoperimetric Inequalities | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
Talagrand's Isoperimetric Inequality | |
| |
| |
| |
Statement of the Inequality | |
| |
| |
| |
The Method of Non-Uniformly Bounded Differences | |
| |
| |
| |
Certifiable Functions | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
Isoperimetric Inequalities and Concentration via Transportation Cost Inequalities | |
| |
| |
| |
Distance between Probability Distributions | |
| |
| |
| |
Transportation Cost Inequalities Imply Isoperimetric Inequalities and Concentration | |
| |
| |
| |
Transportation Cost Inequality in Product Spaces with the Hamming Distance | |
| |
| |
| |
An Extension to Non-Product Measures | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
Quadratic Transportation Cost and Talagrand's Inequality | |
| |
| |
| |
Introduction | |
| |
| |
| |
Review and Road Map | |
| |
| |
| |
An L<sub>2</sub> (Pseudo)-Metric on Distributions | |
| |
| |
| |
Quadratic Transportation Cost | |
| |
| |
| |
Talagrand's Inequality via Quadratic Transportation Cost | |
| |
| |
| |
Extension to Dependent Processes | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
Log-Sobolev Inequalities and Concentration | |
| |
| |
| |
Introduction | |
| |
| |
| |
A Discrete Log-Sobolev Inequality on the Hamming Cube | |
| |
| |
| |
Tensorisation | |
| |
| |
| |
Modified Log-Sobolev Inequalities in Product Spaces | |
| |
| |
| |
The Method of Bounded Differences Revisited | |
| |
| |
| |
Self-Bounding Functions | |
| |
| |
| |
Talagrand's Inequality Revisited | |
| |
| |
| |
Pointers to the Literature | |
| |
| |
| |
Problems | |
| |
| |
| |
Summary of the Most Useful Bounds | |
| |
| |
| |
Chernoff-Hoeffding Bounds | |
| |
| |
| |
Bounds for Well-Behaved Functions | |
| |
| |
Bibliography | |
| |
| |
Index | |