×

Concentration inequalities for sums and martingales. (English) Zbl 1337.60002

SpringerBriefs in Mathematics. Cham: Springer (ISBN 978-3-319-22098-7/pbk; 978-3-319-22099-4/ebook). x, 120 p. (2015).
This is a short book on concentration inequalities for sums and martingales divided in four chapters. The first chapter describes some classical results such as the strong law of large numbers, the cental limit theorem (CLT) for sums, large deviations, and an application of the CLT and some inequalities for the construction of confidence intervals for the binomial probability \(p\). This chapter also introduces martingales, Doob’s convergence theorem, the associated strong law of large numbers for martingales, and the CLT for martingales.
Chapter 2 deals with concentration inequalities for sums. It is divided into many subsections covering various inequalities. The chapter begins with Bernstein’s one-sided and two-sided inequalities, Hoeffding’s inequality, Bennett’s inequality, and sub-Gaussian inequalities under different conditions. It is interesting to quote at least one such inequality.
Let \(X_1,\dots,X_n\) be independent random variables, and assume that \(a_k\leq X_k\leq b_k\), a.s., where \(a_k < b_k\) for \(k=1,2,\dots,n\). Let \(c_k=b_k-a_k\), \(\| c\|_p=(\sum^n_{k=1}c^p_k)^{1/p}\). Also, let \(S_n=X_1+\dots+X_n\). Then for any \(p\in (1,2]\) and for any positive \(x\), \[ \operatorname{P} (|S_n - \operatorname{E}S_n | \geq c_p x) \leq 2\exp(-2x^q ), \] where \(q = p/(p - 1)\).
A little discussion is given about weighted sums. Sums of gamma random variables are also treated. The chapter is concluded with some complements and exercises.
Chapter 3 continues with concentration inequalities for martingales. The chapter begins with Azuma-Hoeffding inequalities and covers Freedman and Fan-Grama-Liu inequalities, Bernstein’s inequality, and de la Peña’s inequalities under various assumptions. For example, the Azuma-Hoeffding inequality is an extension of Hoeffding’s inequality from independent random variables to martingales \(\{M_n \}\) when the martingale differences \(\Delta M_n\) are in \((a_n , b_n )\). With \(D_n =\sum^n_{ k=1} (b_k - a_k )^2\), this inequality states that \[ \operatorname{P}(M_n \geq x) \leq \exp(-2x^2 /D_n ) , x > 0. \] Various other exponential inequalities (and their variations) are given for martingales under various conditions on the martingale differences. For example, the Freedman inequality and de la Peña inequalities are nicely described. The chapter is concluded with some complements and exercises involving linear regression processes, and Galton-Watson processes, etc.
Finally, the last Chapter 4 is devoted to a few applications in probability and statistics. The chapter begins with an application to autoregressive processes \(X_n = \theta X_{n-1} + \epsilon_n\), where \(X_n\) and \(\epsilon_n\) are the observation and the noise, respectively. Let \(\hat{\theta}_n\) be the least squares estimator of \(\theta\). In the stable case of \(|\theta| < 1\), asymptotic normality and the rate of convergence are given for \(\hat{\theta}_n\). Other applications include random permutations, empirical periodograms, and random matrices, etc. A typographical error in the displayed equation at the bottom of page 38 should be noted, and Jensen’s inequality deserves mention in connection with Lemma 2.6. Despite a few shortcomings, this short book is a collection of useful concentration inequalities with a lot of information for interested readers.

MSC:

60-02 Research exposition (monographs, survey articles) pertaining to probability theory
60G42 Martingales with discrete parameter
60F05 Central limit and other weak theorems
60F15 Strong limit theorems
60G46 Martingales and classical analysis
PDFBibTeX XMLCite
Full Text: DOI