Given $X_{1},X_{2},…,X_{n}$ independent random Bernoulli variables having expected value $\mu$.
Then Chernoff bound is $P((1/n)*(X_{1}+X_{2}+…+X_{n}) \le \mu-\epsilon) \le e^{-2*\epsilon^{2}*n}$.
We have $D = 4 * (X_{1}+X_{2}+…+X_{n})$ and each variable i.e. $X_{i}$ has expected value $\frac{1}{2}$ . Using the above inequality and the given values, the upper bound on the probability of $D<=n$ has to be obtained.
I am unable to find a suitable approach to find the upper bound on the probability of $D<=n$. I plugged the values in the inequality and got it as probability of $D/(4n)≤E[D/(4n)]−ϵ$ but not able to proceed post it. Any hints on how to approach the same?
Best Answer
First, we rewrite the event of interest to conform to the Chernoff bound:
\begin{align} P(D \le n) &= P\left(4\sum X_i \le n\right) \\ &= P\left( \frac{1}{n} \sum X_i \le 1/4\right). \\ \end{align}
Now, if we set $1/4$ equal to $\mu - \epsilon = \frac{n}{2} - \epsilon$, then $\epsilon = \frac{n}{2} - \frac{1}{4}$. Hence,
\begin{align} P(D \le n) &= P\left( \frac{1}{n} \sum X_i \le \mu - \left[ \frac{n}{2} - \frac{1}{4} \right] \right) \\ & \le \exp \left(-2\left[\frac{n}{2} - \frac{1}{4} \right]^2 n \right). \end{align}