# Markov inequality example

If I have $x_1, x_2,\ldots, x_n$ independent NON-identically distributed Bernoulli random variables, how do I show that: $$\mathrm{Pr}\left(\sum_{i=1}^nx_i>\beta\mu\right)\le e^{-g(\beta)\mu}$$

where $$\beta>1$$$$\mu=E\left(\sum_{i=1}^nx_i\right)$$$$g(\beta)=\beta\times \ln(\beta)-\beta+1$$? I believe this can be accomplished using the Markov inequality (because that's what we've been covering), but I'm still not sure how to apply it.

-

In markov's inequality, Note that

$$P(\sum_{i=1}^n x_i > \beta \mu) = P(\beta^{\sum_{i=1}^n x_i} > \beta^{\beta \mu})$$

Now apply markov inequality to rhs to get

$$\leq \frac{E[\beta^{\sum_{i=1}^n x_i}]}{\beta^{\beta \mu}} = \frac{\prod_{i=1}^nE[\beta^{x_i}]}{\beta^{\beta \mu}}=\frac{\prod_{i=1}^nE[\beta^{x_i}]}{e^{(\beta \ln \beta) \mu}}$$

Now $E[\beta^{x_i}] = 1 + p_i(\beta-1)$ where $p_i$ is the mean of the i'th bernoulli random variable. Now you observe

$$\prod_{i=1}^nE[\beta^{x_i}] = \prod_{i=1}^n(1 + p_i(\beta-1)) \leq \prod_{i=1}^n e^{p_i(\beta-1)}$$ $$= e^{(\beta - 1)\sum_{i=1}^n p_i} = e^{(\beta - 1)\mu}$$

Putting it all together, we get $$P(\sum_{i=1}^n x_i > \beta \mu) \leq e^{(-\beta \ln \beta +\beta -1)\mu} = e^{-g(\beta)\mu}$$

QED

-