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

McDiarmid's Inequality basically says the following:
Let $X_1, X_2, X_3, \ldots, X_n$ denote independent random variables and $f$ is a function of $n$ real arguments. If changing the value of the $i$-th variable changes the value of $f$ by at most $c_i$, then $$\Pr(f > E[f]+t), \Pr(f < E[f] -t) \leq \exp\left(\frac{-2t^2}{\sum_i c_i^2}\right)$$ Is there a known multiplicative version of this inequality, i.e. we have $\Pr(f > (1+\epsilon)E[f])$ on the left hand side.
The Chernoff-Hoeffding Bounds actually have the corresponding two versions: $$\Pr[X > E[X] +t] \leq \exp(-2t^2/n)$$ $$\Pr[X > (1+\epsilon)E[X]] < \exp(-\epsilon^2E[X]/3).$$

I am wondering anyone has thought about it for McDiarmid's Inequality. Is it possible to derive the same multiplicative version just by going though the proofs of both of them?

share|improve this question
    
I don't get it. The difference seems to be just a change of notation using $t=\epsilon E[X]$. Also, the second C-H bound you give looks suspicious without extra conditions. Maybe there's a non-negativity requirement? –  Brendan McKay Dec 4 '12 at 22:26
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.