# 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
Thank you for the reference! – user118866 Jun 12 '14 at 12:50

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$.

This is worked out carefully for a wide range of various of various desirable properties that might fail with some small probability in Section 8 of Fan Chung and Linyuan Lu's Concentration inequalities and martingale inequalities — a survey.

-

Take a look at the Kutin-Niyogi extension of McDiarmid's inequality: "Almost-Everywhere Algorithmic Stability and Generalization Error", UAI 2002 people.cs.uchicago.edu/~niyogi/papersps/uai-stability.ps

or the more recent paper, https://dl.dropboxusercontent.com/u/3198145/mcdiarmid-unbounded.pdf "Concentration in unbounded metric spaces and algorithmic stability", ICML 2014 The latter has a lot of additional references.

-
I would also recommend the new book of Boucheron, Lugosi and Massart. In particular, their "exponential Efron-Stein" inequality gives a way of strongly bounding fluctuations when one does not have an absolute Lipschitz bound like in McDiarmid's inequality. – user5678 Jun 10 '14 at 10:23
Thank you! I found your references very interesting and I will read them carefully. But I Dubhashi-Panconesi book my question is left as an exercise, so I think there should be an easy way to prove it.. – user118866 Jun 10 '14 at 13:59