Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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 at 12:56
    
@BenBarber Thank you! I think it can work like that, I will fix the details –  user118866 Jun 10 at 14:18
1  
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 at 15:38
    
Thank you for the reference! –  user118866 Jun 12 at 12:50

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
2  
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 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 at 13:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.