Reviewing for exam: Chernoff bounds for a series of random variables I have a series of random variables, where the expected value is $\frac{n}{4}$.  I want to prove, with Chernoff bounds, that the probability that the actual value is less than $(1 - \epsilon)\frac{n}{8}$ is very small.  
I am unsure as to how to approach this problem.  It is immediately obvious that n/8 is half of n/4.  I don't believe solving for epsilon is the right approach for this, however.  How do I approach this?
 A: The Chernoff bound you need is given by
$$ Pr(X < (1-\delta)Ex[X]) \le \left( \frac{e^\delta}{(1-\delta)^{1-\delta}} \right)^{Ex[X]}. $$
In your case, $Ex[X] = n/4$.  Therefore,
$$ Pr(X < (1-\epsilon)n/8) \le Pr(X < n/8) \le Pr(X < (1/2)n/4) = Pr(X < (1 - 1/2)n/4), $$
so $\delta = 1/2$.
This leads to
$$ Pr(X < (1-\epsilon)n/8) \le \left( \frac{e^{1/2}}{(1/2)^{1/2}} \right)^{n/4}. $$
The expression on the right is easily reduced by algebraic manipulation.  After this, you need to find an $n$ such that this expression is polynomially small.
This shows some of the power of Chernoff bounds, that is, that once you know $Ex[X]$, you can pick $\delta$ easily, and then the bound itself is given by a simple closed expression raised to $Ex[X]$.  Let me repeat: all you need to know (if you have 0/1 independent Poisson Trials), is the expected value!
If you would like help with the algebraic manipulation, please comment as such.
NB + spoiler: Another formulation to memorize (cf. deathbed formulae :-) of the lower Chernoff bound is
$$ Pr(X < (1-\delta)Ex[X]) \le e^{-Ex[X]\delta^2/2}. $$
In your case, this would become
$$ Pr(X < (1-\epsilon)n/8) \le e^{-(n/4)(1/2)^2/2} = e^{-n/32}. $$
Solving for $n$ such that this expression is less than $N^{-c}$ gives $n \ge 64\log N$ (to get the bound with high probability with respect to $N$), as this equation shows:
$$ e^{-64\log(N)/32} = \left( e^{\log N} \right)^{-2} = N^{-2}. $$
Thus, with at least $n = \Theta(\log N)$ flips (or whatever your variables denote) means that $X \ge (1-\epsilon)n/8$ with high probability with respect to $N$.
