most recent 30 from http://mathoverflow.net 2013-05-18T19:17:02Z http://mathoverflow.net/feeds/question/115444 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115444/a-multiplicative-version-of-mcdiarmids-inequality-like-the-one-of-chernoff-hoef Steven Wu 2012-12-04T21:23:13Z 2012-12-04T21:23:13Z

<p>McDiarmid's Inequality basically says the following:<br> 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 &lt; 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.<br> 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]] &lt; \exp(-\epsilon^2E[X]/3).$$</p> <p>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?</p>