Concentration of Measure for the Analysis of Randomized Algorithms

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.

隨機化演算法已成為演算法課程的核心部分，因為它們在現代應用中的廣泛使用越來越普遍。本書提供了一個統一且有條理的方法，用於獲得隨機化演算法性能的高概率估計的概率技巧。它涵蓋了從Chernoff-Hoeffding (CH)界限到更複雜的技巧，如馬丁格爾和等周不等式，以及一些最近的發展，如Talagrand的不等式，運輸成本不等式和log-Sobolev不等式的基本工具包。在此過程中，還對基本主題的變化進行了研究，例如在相依設置中的CH界限。作者強調對不同方法的比較研究，並在具體的應用實例中突出各自的優點和缺點。本書的撰寫適用於離散設置，足以分析演算法，避免了不必要的測度論細節，因此使得本書對計算機科學家、概率學家和離散數學家都易於理解。