Concentration inequalities using the entropy method (Q1431503): Difference between revisions

In the 90-ties of the last century concentration inequalities became a very active field of research, with various application, from ``classical'' probability, empirical processes to random graphs. For the background see e.g. \textit{M. Talagrand} [Ann. Probab. 24, 1--34 (1996; Zbl 0858.60019)], \textit{M. Ledoux} [ESAIM, Probab. Stat. 1, 63--87 (1997; Zbl 0869.60013)], \textit{S. G. Bobkov} and \textit{M. Ledoux} [J. Funct. Anal. 156, No. 2, 347--365 (1998; Zbl 0920.60002)] and \textit{P. Massart} [Ann. Probab, 28, No. 2, 863--884 (2000; Zbl 1140.60310)]. Following previous investigations by the authors [Random Struct. Algorithms 16, 277--292 (2000; Zbl 0954.60008)], the authors prove several concentration inequalities in the following setup: Let \((X_i)\) be independent random variables taking values in a measurable space \(\mathcal{X}\). Put \(X_1^{(n)} := (X_1 \dots X_n)\), let \(f: \mathcal{X}^n \to R\) be a measurable real function and put \( Z:=f(X_1, \dots X_n)\). For independent copies \((X_i')\) define \(Z^{(i)} := f(X_1, \dots, X_{i-1},X_i',X_{i+1}, \dots, X_n)\) and put \(V_+:= \mathbb{E}(\sum (Z-Z^{(i)}) 1_{\{Z>Z^{(i)}\}}| X_1^{(n)})\). \(V_-\) is defined analogously. Under technical assumptions -- e.g. boundedness of \(V_+\) or \(V_-\) and existence of moment generating functions -- the authors obtain exponential bounds. For example, Corollary 3: \ \(V_+ \leq c\) a.s. \( \Rightarrow P(Z>\mathbb{E}(Z)+t) \leq e^{-t^2/4c}\) for \(t>0\), and an analogous inequality if a.s. \(V_-\leq c\). The proofs rely on a version of a logarithmic Sobolev inequality proved in the above-mentioned paper of P. Massart. The paper contains several new applications of these inequalities, also a new approach to the ``Rademacher chaos'' providing a new proof of \textit{M. Talagrand}'s inequality [Invent. Math. 126, No. 3, 505--563 (1996; Zbl 0893.60001)].