You are previewing Concentration of Measure for the Analysis of Randomized Algorithms.
O'Reilly logo
Concentration of Measure for the Analysis of Randomized Algorithms

Book Description

Randomized algorithms have become a central part of the algorithms curriculum based on their increasingly widespread use in modern applications. This book presents a coherent and unified treatment of probabilistic techniques for obtaining high-probability estimates on the performance of randomized algorithms. It covers the basic tool kit from the Chernoff-Hoeffding (CH) bounds to more sophisticated techniques like Martingales and isoperimetric inequalities, as well as some recent developments like Talagrand's inequality, transportation cost inequalities, and log-Sobolev inequalities. Along the way, variations on the basic theme are examined, such as CH bounds in dependent settings. The authors emphasize comparative study of the different methods, highlighting respective strengths and weaknesses in concrete example applications. The exposition is tailored to discrete settings sufficient for the analysis of algorithms, avoiding unnecessary measure-theoretic details, thus making the book accessible to computer scientists as well as probabilists and discrete mathematicians.

Table of Contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright
  5. Dedication
  6. Contents
  7. Preface
  8. 1. Chernoff–Hoeffding Bounds
    1. 1.1 What Is “Concentration of Measure”?
    2. 1.2 The Binomial Distribution
    3. 1.3 The Chernoff Bound
    4. 1.4 Heterogeneous Variables
    5. 1.5 The Hoeffding Extension
    6. 1.6 Useful Forms of the Bound
    7. 1.7 A Variance Bound
    8. 1.8 Pointers to the Literature
    9. 1.9 Problems
  9. 2. Applications of the Chernoff–Hoeffding Bounds
    1. 2.1 Probabilistic Amplification
    2. 2.2 Load Balancing
    3. 2.3 Skip Lists
    4. 2.4 Quicksort
    5. 2.5 Low-Distortion Embeddings
    6. 2.6 Pointers to the Literature
    7. 2.7 Problems
  10. 3. Chernoff–Hoeffding Bounds in Dependent Settings
    1. 3.1 Negative Dependence
    2. 3.2 Local Dependence
    3. 3.3 Janson’s Inequality
    4. 3.4 Limited Independence
    5. 3.5 Markov Dependence
    6. 3.6 Pointers to the Literature
    7. 3.7 Problems
  11. 4. Interlude: Probabilistic Recurrences
    1. 4.1 Problems
  12. 5. Martingales and the Method of Bounded Differences
    1. 5.1 Review of Conditional Probabilities and Expectations
    2. 5.2 Martingales and Azuma’s Inequality
    3. 5.3 Generalising Martingales and Azuma’s Inequality
    4. 5.4 The Method of Bounded Differences
    5. 5.5 Pointers to the Literature
    6. 5.6 Problems
  13. 6. The Simple Method of Bounded Differences in Action
    1. 6.1 Chernoff–Hoeffding Revisited
    2. 6.2 Stochastic Optimisation: Bin Packing
    3. 6.3 Balls and Bins
    4. 6.4 Distributed Edge Colouring: Take 1
    5. 6.5 Models for the Web Graph
    6. 6.6 Game Theory and Blackwell’s Approachability Theorem
    7. 6.7 Pointers to the Literature
    8. 6.8 Problems
  14. 7. The Method of Averaged Bounded Differences
    1. 7.1 Hypergeometric Distribution
    2. 7.2 Occupancy in Balls and Bins
    3. 7.3 Stochastic Optimisation: Travelling Salesman Problem
    4. 7.4 Coupling
    5. 7.5 Handling Rare Bad Events
    6. 7.6 Quicksort
    7. 7.7 Pointers to the Literature
    8. 7.8 Problems
  15. 8. The Method of Bounded Variances
    1. 8.1 A Variance Bound for Martingale Sequences
    2. 8.2 Applications
    3. 8.3 Pointers to the Literature
    4. 8.4 Problems
  16. 9. Interlude: The Infamous Upper Tail
    1. 9.1 Motivation: Non-Lipschitz Functions
    2. 9.2 Concentration of Multivariate Polynomials
    3. 9.3 The Deletion Method
    4. 9.4 Problems
  17. 10. Isoperimetric Inequalities and Concentration
    1. 10.1 Isoperimetric Inequalities
    2. 10.2 Isoperimetry and Concentration
    3. 10.3 The Hamming Cube
    4. 10.4 Martingales and Isoperimetric Inequalities
    5. 10.5 Pointers to the Literature
    6. 10.6 Problems
  18. 11. Talagrand’s Isoperimetric Inequality
    1. 11.1 Statement of the Inequality
    2. 11.2 The Method of Non-Uniformly Bounded Differences
    3. 11.3 Certifiable Functions
    4. 11.4 Pointers to the Literature
    5. 11.5 Problems
  19. 12. Isoperimetric Inequalities and Concentration via Transportation Cost Inequalities
    1. 12.1 Distance between Probability Distributions
    2. 12.2 Transportation Cost Inequalities Imply Isoperimetric Inequalities and Concentration
    3. 12.3 Transportation Cost Inequality in Product Spaces with the Hamming Distance
    4. 12.4 An Extension to Non-Product Measures
    5. 12.5 Pointers to the Literature
    6. 12.6 Problems
  20. 13. Quadratic Transportation Cost and Talagrand’s Inequality
    1. 13.1 Introduction
    2. 13.2 Review and Road Map
    3. 13.3 An L2 (Pseudo)-Metric on Distributions
    4. 13.4 Quadratic Transportation Cost
    5. 13.5 Talagrand’s Inequality via Quadratic Transportation Cost
    6. 13.6 Extension to Dependent Processes
    7. 13.7 Pointers to the Literature
    8. 13.8 Problems
  21. 14. Log-Sobolev Inequalities and Concentration
    1. 14.1 Introduction
    2. 14.2 A Discrete Log-Sobolev Inequality on the Hamming Cube
    3. 14.3 Tensorisation
    4. 14.4 Modified Log-Sobolev Inequalities in Product Spaces
    5. 14.5 The Method of Bounded Differences Revisited
    6. 14.6 Self-Bounding Functions
    7. 14.7 Talagrand’s Inequality Revisited
    8. 14.8 Pointers to the Literature
    9. 14.9 Problems
  22. Appendix A
    1. A.1 Chernoff–Hoeffding Bounds
    2. A.2 Bounds for Well-Behaved Functions
  23. Bibliography
  24. Index