An inequality for tail probabilities of martingales with bounded differences
type: Item
instance of: scholarly article
title: An inequality for tail probabilities of martingales with bounded differences
zbMATH Open document ID: 1016.60024
DOI: 10.1023/A:1020269808826
published in: Lithuanian Mathematical Journal
publication date: 2003-05-19T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 60E15
Mathematics Subject Classification ID: 60G42
zbMATH DE Number: 1912619
zbMATH Keywords: probabilities of large deviations
zbMATH Keywords: martingale
zbMATH Keywords: bounds for tail probabilities
zbMATH Keywords: inequalities
zbMATH Keywords: bounded differences and random variables
zbMATH Keywords: measure concentration phenomena
zbMATH Keywords: product spaces
zbMATH Keywords: Lipschitz functions
zbMATH Keywords: Hoeffding's inequalities
zbMATH Keywords: Azuma's inequality
author: Vidmantas Bentkus
reviewed by: B. L. S. Prakasa Rao
MaRDI profile type: Publication
full work available at URL: a:1020269808826
OpenAlex ID: W1508225606
description: scientific article; zbMATH DE number 1912619