# Upper bounds for independent random variables using Chernoff bounds

I've been reading through a stats book, in particular the section on Chernoff bounds and am struggling to solve this problem:

Consider any positive integer $\lambda$. Let $X = \sum_{i=1}^{n} X_{i}$, where $X_{i} \in \lbrace 0,\lambda \rbrace, \forall i \in \lbrace 1, \ldots , n \rbrace$ and the $X_{i}$ are mutually independent random variables. Let $\mu = \mathbb{E}[X]$. Using the Chernoff bounds, derive upper bounds on the following two probabilities:

$$\mathbb{P}[X≥(1+\delta)·\mu]$$ and $$\mathbb{P}[X≤(1−\delta)·\mu].$$

I can see that $X_{i} \in \lbrace 0,\lambda \rbrace$ is crucial here, but have no idea how to proceed.

## 1 Answer

Because: $X_i \in \{0,\lambda\}$, we can think of $X_i' = \frac{X_i}{\lambda}$ as a Bernoulli random variable with parameter $p = \mu'$.

We can then rewrite $X$ as $\lambda X'$ and $\mu$ as $\lambda\mu'$.

Following the derivations here or here, we get to the result.

Being (very) explicit:

$$\mathbb P[X' \geq (1+ \delta)\mu'] \leq \left[\frac{e^{\delta}}{(1 + \delta)^{1+\delta}}\right]^{\mu'}$$

and

$$\mathbb P[X' \leq (1 - \delta)\mu'] \leq \left[\frac{e^{-\delta}}{(1 - \delta)^{1-\delta}}\right]^{\mu'}$$

Notice that:

$$\mathbb P[X' \geq (1+ \delta)\mu'] = \mathbb P\left[\frac{X}{\lambda} \geq (1+ \delta)\frac{\mu}{\lambda}\right] = \mathbb P[X \geq (1+ \delta)\mu]$$

and

$$\mathbb P[X' \leq (1- \delta)\mu'] = \mathbb P\left[\frac{X}{\lambda} \leq (1 - \delta)\frac{\mu}{\lambda}\right] = \mathbb P[X \leq (1 - \delta)\mu]$$

Therefore:

$$\mathbb P[X \geq (1+ \delta)\mu] \leq \left[\frac{e^{\delta}}{(1 + \delta)^{1+\delta}}\right]^{\frac{\mu}{\lambda}}$$

and

$$\mathbb P[X \leq (1 - \delta)\mu] \leq \left[\frac{e^{-\delta}}{(1 - \delta)^{1-\delta}}\right]^{\frac{\mu}{\lambda}}$$