# Extension of the Azuma-Hoeffding inequality (when the differences are bounded with large probability)

Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is $$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$ for suitable constants $(c_i)$ and $\epsilon>0$. I read in Dubhashi-Panconesi book that for all $t>0$ $$\mathbb{P}(X_n>X_0+t) \,\leq\, \exp\left(-\frac{t^2}{2\,\sum_{i=1}^nc_i^2}\right) +\,\epsilon\;.$$

How can I prove this result? I already know that it holds for $\epsilon=0$ (it is the so called Azuma-Hoeffding inequality). But I don't manage to deduce this corollary. My first idea was to split and bound the probability as follows: $$\mathbb{P}(|X_n-X_0|<t) \,\leq\, \mathbb{P}(|X_n-X_0|<t \ \big|\ \forall\,i=1,\dots,n\,|X_i-X_{i-1}|\leq c_i) \,+\, \epsilon$$ but then I don't know how to bound the first term on the r.h.s. because I don't know if $(X_i)$ is still a super-martingale with respect to the conditional probability.

• The very rough idea for how inequalities similar to this one can be proved is this: follow your martingale until it's about to go off the rails, then force it to be constant. It remains a martingale, and now has bounded differences, so is concentrated. Finally, increase the error probability by the probability that something went wrong and the variable which is concentrated is not the variable you were interested in. – Ben Barber Jun 10 '14 at 12:56
• @BenBarber Thank you! I think it can work like that, I will fix the details – user118866 Jun 10 '14 at 14:18
• Van Vu and I wrote up essentially this inequality (proven the way Ben suggests) as Proposition 34 of arxiv.org/abs/1206.1893 . – Terry Tao Jun 10 '14 at 15:38

The general idea behind such inequalities is to follow the martingale $X$ until you lose control over the differences, then force it to be constant. This defines a new martingale $Y$ with bounded differences, which is therefore concentrated. You then add to your probability of error the probability that the differences of $X$ are too large, so that $Y \neq X$.