Bounds for being very far from the mean If I toss $n$ coins each with probability $1/\sqrt{n}$ of getting a head, I would like to know bounds for the probability of getting $n/2$ or more heads. Clearly the mean number of heads is $\sqrt{n}$. It seems you could use the multiplicative form of the Chernoff bound but is it still valid when you are this far from the mean?  The definition in the wikipedia doesn't make this clear.
 A: This is also a possible application for Hoeffding's Inequality. But I must admit I don't know the Chernoff bound so well, perhaps it is sharper. (In fact, I looked it up only after writing my answer and it looks like a specialized version of Hoeffding's inequality and might thus be sharper.)
Let $X_1,\ldots,X_n$ denote independent random variables with a $\mathrm{Bi}(1,1/\sqrt{n})$ distribution. Every $X_i$ is bounded between zero and one. If we let $S_n=X_1+\ldots+X_n$, then by Hoeffding's Inequality, $$P(S_n-ES_n\geq t) \leq \exp\{-2t^2/n\}\, \text{for all }t>0\,.$$ 
Now $ES_n=\sqrt{n}$, so $S_n\geq n/2$ is equivalent to $S_n-\sqrt{n}\geq n/2-\sqrt{n}$. So it remains to plug in $t=n/2-\sqrt{n}$ into Hoeffding's Inequality. If I did not mess up, we end up with $$P(S_n\geq n/2)\leq \exp\{-n/2+2\sqrt{n}-2\}\, \text{for all } n>4\,, $$
the restriction on $n$ being due to the required positivity of $t$.
For small and not so small samples (I don't know whether a numerical result might also be interesting to you or whether you need a theoretical result), an exact computation using the binomial distribution is absolutely no problem. I will add numeric results as an edit.
Edit:
We may compare exact results with Hoeffding's Inequality as follows:
p.exact <- function(n) 1-pbinom(floor((n-1)/2),n,1/sqrt(n))
hoeffding <- function(n) exp(-n/2+2*sqrt(n)-2)
N <- 40
lst <- data.frame(cbind(n=1:N,exact=1:N,hoeffding=1:N))
for (i in 1:N) {
    lst[i,2] <- p.exact(i)
    lst[i,3] <- hoeffding(i)
}
lst

plot(exact~n,data=lst,type="l",ylab="probability")
lines(lst$n[5:N],lst$hoeffding[5:N],lty=3)
legend("topright",legend=c("Binomial","Hoeffding"),lty=c(1,3))

which gives the following plot:

It can be seen that for small sample sizes, it would be good to perform the exact computations. The differences for bigger values are not well visible anymore, one could for example plot the ratio of the two values if one is interested in these things.
