Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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)}. $$

share|cite|improve this answer

For integers $j$ with $0 \le j \le n$, $$Pr[X \ge j] = 2^{-n} {n \choose j} {\mbox{$_2$F$_1$}(1,-n+j;\,j+1;\,-1)}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.