Concentration of Measure for the Analysis of Randomized Algorithms

by Devdatt P. Dubhashi , Alessandro Panconesi

• ISBN13: 9780521884273
• ISBN10: 0521884276
• Edition: 1st
• Format: Hardcover
• Copyright: 2009-06-15
• Publisher: Cambridge University Press

Summary

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.

Author Biography

Devdatt P. Dubhashi is Professor in the Department of Computer Science and Engineering at Chalmers University, Sweden. He earned a Ph.D. in computer science from Cornell University and held positions at the Max-Planck-Institute for Computer Science in Saarbruecken, BRICS, the University of Aarhus, and IIT Delhi. Dubhashi has published widely at international conferences and in journals, including many special issues dedicated to best contributions. His research interests span the range from combinatorics, to probabilistic analysis of algorithms and, more recently, to computational systems biology and distributed information systems such as the Web. Alessandro Panconesi is Professor of Computer Science at Sapienza University of Rome. He earned a Ph.D. in computer science from Cornell University and is the recipient of the 1992 ACM Danny Lewin Award. Panconesi has published more than 50 papers in international journals and selective conference proceedings, and he is the associate editor of the journal of Discrete Algorithms and the director of BiCi, the Bertinoro International Center of Informatics. His research spans areas of algorithmic research as diverse as randomised algorithms, distributed computing, complexity theory, experimental algorithmics, wireless networking and web information retrieval.

Table of Contents

Preface	p. xi
Chernoff-Hoeffding Bounds	p. 1
What Is "Concentration of Measure"?	p. 1
The Binomial Distribution	p. 2
The Chernoff Bound	p. 3
Heterogeneous Variables	p. 5
The Hoeffding Extension	p. 6
Useful Forms of the Bound	p. 6
A Variance Bound	p. 8
Pointers to the Literature	p. 10
Problems	p. 10
Applications of the Chernoff-Hoeffding Bounds	p. 16
Probabilistic Amplification	p. 16
Load Balancing	p. 17
Skip Lists	p. 18
Quicksort	p. 22
Low-Distortion Embeddings	p. 23
Pointers to the Literature	p. 29
Problems	p. 29
Chernoff-Hoeffding Bounds in Dependent Settings	p. 34
Negative Dependence	p. 34
Local Dependence	p. 38
Janson's Inequality	p. 39
Limited Independence	p. 43
Markov Dependence	p. 45
Pointers to the Literature	p. 49
Problems	p. 49
Interlude: Probabilistic Recurrences	p. 51
Problems	p. 56
Martingales and the Method of Bounded Differences	p. 58
Review of Conditional Probabilities and Expectations	p. 59
Martingales and Azuma's Inequality	p. 61
Generalising Martingales and Azuma's Inequality	p. 65
The Method of Bounded Differences	p. 67
Pointers to the Literature	p. 71
Problems	p. 72
The Simple Method of Bounded Differences in Action	p. 74
Chernoff-Hoeffding Revisited	p. 74
Stochastic Optimisation: Bin Packing	p. 74
Balls and Bins	p. 75
Distributed Edge Colouring: Take 1	p. 76
Models for the Web Graph	p. 78
Game Theory and Blackwell's Approachability Theorem	p. 80
Pointers to the Literature	p. 82
Problems	p. 82
The Method of Averaged Bounded Differences	p. 85
Hypergeometric Distribution	p. 85
Occupancy in Balls and Bins	p. 86
Stochastic Optimisation: Travelling Salesman Problem	p. 88
Coupling	p. 90
Handling Rare Bad Events	p. 99
Quicksort	p. 101
Pointers to the Literature	p. 103
Problems	p. 103
The Method of Bounded Variances	p. 106
A Variance Bound for Martingale Sequences	p. 107
Applications	p. 110
Pointers to the Literature	p. 117
Problems	p. 118
Interlude: The Infamous Upper Tail	p. 121
Motivation: Non-Lipschitz Functions	p. 121
Concentration of Multivariate Polynomials	p. 121
The Deletion Method	p. 123
Problems	p. 124
Isoperimetric Inequalities and Concentration	p. 126
Isoperimetric Inequalities	p. 126
Isoperimetry and Concentration	p. 127
The Hamming Cube	p. 130
Martingales and Isoperimetric Inequalities	p. 131
Pointers to the Literature	p. 132
Problems	p. 133
Talagrand's Isoperimetric Inequality	p. 136
Statement of the Inequality	p. 136
The Method of Non-Uniformly Bounded Differences	p. 139
Certifiable Functions	p. 144
Pointers to the Literature	p. 148
Problems	p. 148
Isoperimetric Inequalities and Concentration via Transportation Cost Inequalities	p. 151
Distance between Probability Distributions	p. 151
Transportation Cost Inequalities Imply Isoperimetric Inequalities and Concentration	p. 153
Transportation Cost Inequality in Product Spaces with the Hamming Distance	p. 154
An Extension to Non-Product Measures	p. 158
Pointers to the Literature	p. 159
Problems	p. 159
Quadratic Transportation Cost and Talagrand's Inequality	p. 161
Introduction	p. 161
Review and Road Map	p. 161
An L2 (Pseudo)-Metric on Distributions	p. 163
Quadratic Transportation Cost	p. 165
Talagrand's Inequality via Quadratic Transportation Cost	p. 167
Extension to Dependent Processes	p. 168
Pointers to the Literature	p. 169
Problems	p. 169
Log-Sobolev Inequalities and Concentration	p. 171
Introduction	p. 171
A Discrete Log-Sobolev Inequality on the Hamming Cube	p. 172
Tensorisation	p. 174
Modified Log-Sobolev Inequalities in Product Spaces	p. 175
The Method of Bounded Differences Revisited	p. 177
Self-Bounding Functions	p. 179
Talagrand's Inequality Revisited	p. 179
Pointers to the Literature	p. 181
Problems	p. 181
Summary of the Most Useful Bounds	p. 185
Chernoff-Hoeffding Bounds	p. 185
Bounds for Well-Behaved Functions	p. 185
Bibliography	p. 189
Index	p. 195
Table of Contents provided by Ingram. All Rights Reserved.