# Proving inequalities similar to Chernoff Bounds

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)$?

## 1 Answer

\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.