zbMATH — the first resource for mathematics

Concentration. (English) Zbl 0927.60027
Habib, Michael (ed.) et al., Probabilistic methods for algorithmic discrete mathematics. Berlin: Springer. Algorithms Comb. 16, 195-248 (1998).
This is an excellent chapter on concentration based on and/or referring to 72 papers and books, a few of them belonging to the author. In this chapter the author introduces and gives several applications of the two main approaches for proving concentration results, namely the bounded differences or martingale method and the recent method of M. Talagrand [Invent. Math. 126, No. 3, 505-563 (1996; Zbl 0893.60001)]. He starts with the classical bound of H. Chernoff [Ann. Math. Stat. 23, 493-509 (1952; Zbl 0048.11804)] and then presents the “independent bounded differences inequality” and applications of it to bin packing, coloring random graphs, and isoperimetric inequalities involving Hamming distances. The author introduces and proves more general concentration results regarding martingales before he proceeds to introduce and prove the following inequality, which he calls Talagrand’s inequality. Let \(\mathbf X=(X_1, \dots,X_n)\) be a family of independent random variables and let \(A\) be a subset of the product space and denote by \(d_T({\mathbf X},A)\) Talagrand’s convex function. Then for any \(t\geq 0\), \(\text{Pr} (\mathbf X\in A) \text{Pr} (d_T(\mathbf X,A) \geq t)\leq \exp(-t^2/4)\). This inequality is considered by the author as the most important of Talagrand’s many inequalities.
For the entire collection see [Zbl 0898.00019].

60E15 Inequalities; stochastic orderings
60G42 Martingales with discrete parameter