Let $X = \sum_{i=0}^{n} Xn$, where $X_i \in \{0,1\}$ for all $i \in \{1,\ldots,n\}$ and the $X_i$’s are mutually independent random variables. Let $ = E[X]$. Furthermore, consider two parameters $μL$ and $μH$ such that $0 \le \mu_L \le \mu \le \mu_H$. Then for any $0 < \delta < 1$, prove the following two inequalities:

(1) $ Pr[X \ge(1+\delta)·\mu_H] \le \big(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\big)^{\mu_H}$

(2) $ Pr[X \le (1−\delta)·\mu_L] \le \big(\frac{e^{\delta}}{(1-\delta)^{(1-\delta)}}\big)^{\mu_L}$

Clearly I can see that these inequalities are very similar to the Chernoff Bounds, but how would my proof be any different? Here's what I have so far for (1):

Applying Markov's inequality (for any $t>0$): $$ Pr[X ≥(1+\delta)\mu] ≤ Pr[e^{tX} ≥e^{t(1+\delta)\mu}] $$ $$ \le \frac{\mathbb{E}(e^{tX})}{e^{t(1+\delta) \mu}}$$ $$ \le \frac{e^{(e^{t}-1) \mu}}{e^{t(1+\delta) \mu}}$$ Then for any $0 < \delta < 1$ set $t = \ln(1+\delta) < 0$ to get: $$ = \bigg(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\bigg)^{\mu}$$ $$ \le \bigg(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\bigg)^{\mu_H}$$

Is this anywhere near correct? And if so would something similar hold for $(2)$?


\begin{align} Pr(X > (1+\delta) \mu_H) &= Pr( e^{tX} > e^{(1+\delta)t\mu_H}), \text{let } t=\ln(1+\delta) \\&\le \frac{E[e^{tX}]}{e^{(1+\delta)t\mu_H}}, \text{By Markov's inequality} \\&= \frac{\prod_{i=1}^n(1+p_i(e^t-1))}{e^{(1+\delta)t\mu_H}} \\&\le \frac{\prod_{i=1}^ne^{p_i(e^t-1)}}{e^{(1+\delta)t\mu_H}}, \text{since} 1+x \le e^x \\&= \frac{e^{\mu(e^t-1)}}{e^{(1+\delta)t\mu_H}} \\&\le\left( \frac{e^{e^t-1}}{e^{t(1+\delta)}}\right)^{\mu_H} \\&= \left( \frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu_H} \end{align}

Similar trick for the second bound.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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