# lower bound on sum of Bernoulli trials

Suppose that $X$ is the sum of $n$ Bernoulli random variables with $p=1/2$. I'm wondering whether there a way to get a function $f(n,k)$ such that, for $k\ge 0$, $$Pr[X \ge E[X] + k ] \ge f(n,k).$$ I've looked at Markov's Inequality, but this works the opposite way as it gives me a lower bound of being close to the mean.

-

Exact formulas for $\mathbb P(X\geqslant \mathbb E(X)+k)$ involve sums of binomial coefficients which, except in the regime $\frac{n}2-k$ bounded, may not be very illuminating. On the other hand, the exact asymptotics of $\mathbb P(X\geqslant \mathbb E(X)+k)$ when $n\to\infty$ and $k=\Theta(n)$ are known to correspond to the optimal exponential inequality. Let us explain this in the present case. For every $s\geqslant1$, $$\mathbb P(X\geqslant \mathbb E(X)+k)\leqslant\mathbb E(s^X)s^{-\mathbb E(X)-k}.$$ One knows that $\mathbb E(s^X)=[\frac12(1+s)]^n$ and $\mathbb E(X)=\frac12n$, hence the task is to minimize the quantity $(1+s)^ns^{-(n/2)-k}$ over $s\geqslant1$. The logarithmic derivative is $\frac{n}{1+s}-\frac{(n/2)+k}{s}$, hence one chooses $s=\frac{(n/2)+k}{(n/2)-k}$, which yields $\mathbb P(X\geqslant \mathbb E(X)+k)\leqslant f(n,k)$ with $$f(n,k)=\left(1-\tfrac{2k}n\right)^{-\frac{n}2+k}\left(1+\tfrac{2k}n\right)^{-\frac{n}2-k}.$$ As said above, if $n\to\infty$ and $k/n\to\alpha$, then it happens that this upper bound also indicates the correct logarithmic behaviour of the probability considered, since $$\lim\limits_{n\to\infty}n^{-1}\log\mathbb P(X\geqslant \mathbb E(X)+k)=\lim\limits_{n\to\infty}n^{-1}\log f(n,\alpha n).$$ For example, $$f(n,\tfrac{n}4)=\left(\tfrac{16}{27}\right)^{\tfrac{n}4},$$ hence $$\mathbb P(X\geqslant\tfrac{3n}4+o(n))=\left(\tfrac{16}{27}\right)^{\tfrac{n}4+o(n)}.$$
For integers $j$ with $0 \le j \le n$, $$Pr[X \ge j] = 2^{-n} {n \choose j} {\mbox{_2F_1}(1,-n+j;\,j+1;\,-1)}$$