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.


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'}$$


$$\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]$$


$$\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]$$


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


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


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.