Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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
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.