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.



Extension of the Azuma-Hoeffding inequality (when the differences are bounded with large probability)
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](http://www.math.ucsd.edu/~fan/wp/concen.pdf).


