An inequality for tail probabilities of martingales with bounded differences (Q1873256)

Let \(M_n=X_1+\dots+X_n\) be a martingale within bounded differences \(X_m\) with \(|X_m|\leq\sigma_m\). Define \(\sigma^2= \sigma^2_1+ \dots+ \sigma^2_n\). The author proves that \(P(M_n\geq x)\leq c(1-\Phi (x/ \sigma))\) and \(P(M_n> x)\geq 1-c(1-\Phi(-x/ \sigma))\) where \(c\leq 25\) and \(\Phi (\cdot)\) is the standard normal distribution function. As an application of these results, the following result on concentration of measure is proved: Let \(\mathbb{Z}_1,\dots, \mathbb{Z}_n\) be independent random variables such that \(P(|\mathbb{Z}_j|\leq 1)=1\), \(1\leq j\leq n\). Let \(f:[-1,1]^n \to{\mathcal R}\) satisfy the Lipschitz condition in each variable \(z_j\) with Lipschitzian constant \(\sigma_j\). Define \(\sigma^2= \sigma^2_1+ \dots+\sigma^2_n\). Then \[ P\bigl[f(\mathbb{Z}_1, \dots,\mathbb{Z}_n) \geq Ef(\mathbb{Z}_1,\dots,\mathbb{Z}_n)+x\bigr] \leq D(x/2\sigma) \] and \[ P \bigl[f(\mathbb{Z}_1, \dots,\mathbb{Z}_n)\leq Ef(\mathbb{Z}_1, \dots,\mathbb{Z}_n)-x\bigr] \leq D(x/2 \sigma) \] where \(D(x)=\min \{e^{-x^2/2}, c(1-\Phi(x))\}\) and \(c\) is an absolute constant such that \(2\leq c\leq(1-\Phi (\sqrt 3))^{-1} \leq 25\). Reviewer's remark: For related results, see \textit{G. Van Der Geer} [in: Empirical process techniques for dependent data, 161-169 (Boston, 2002)].