Suppose we have a random variable X with binomial distribution B(n, p). I'm interested in the probability P(X ≥ E[X]). In particular, is there some inequality for how this probability changes as n and p grow? Is there some lower and upper bound for this probability? I was not able to find any resource on this topic.
For context, I am using some probabilistic computational model and I'm trying to see how it behaves as n (the size of the input) grows.
On
The thing you are looking for is Large Deviation and the rate function.
Let $X_{i}$ be identical and independent (IID) random variables and X ~ $X_{1}$ with summation and moment generating function
$$ S_n={\sum_{i=1}^n}X_i $$
$$ M(\theta) = E[e^{\theta X}] < \infty, $$
$$ \theta ∈(-\gamma,\gamma), \gamma>0 $$ and if $a ≥E[X]$ and $\theta^*$>0 such that
$$ \lambda^*(a) = sup[{\theta}a-\lambda_{X}(\theta)|\theta>0]=\theta^*a-\lambda_{X}(\theta^*) $$ where $\lambda_X(\theta)=ln(M_X(\theta))$ is the logmoment.
Then, the probability $P(S_n>na)$ is bounded by upper and lower bounds tightly for every $n>n_{\delta}$ and $\delta$ by: $$ exp(-n(\lambda^*(a)+\delta))<P(S_n>na)<exp(-n(\lambda^*(a)-\delta)) $$
For your problem, we have ${X_i}$'s as Bernoulli(p) that are iid. Also, your binomial is: $S_n={\sum_{i=1}^n}X_i$. All conditions are satisfied and Large Deviation Limits can be applied now.
Finding the moment generating function of ${X_i}$.
$$ E[e^{{\theta}X}]=pe^{\theta}+(1-p) $$
$$ \lambda_X(\theta)=ln(M_X(\theta))=ln(pe^{\theta}+(1-p)) $$
$E[S_n]=np$ and we are asked to find bound for $P(Sn>np)$, which we now know the bounds for.
The rest is just plugging in $a=x$ in the explanation above and maximizing the rate function $\lambda^*(x)$ with respect to the $\theta$.
Hope this helps, sorry if I miswrote something, I am new here.
Since $E(X)=np$ for binomial, $P(X\gt np)=\sum\limits_{k=m}^n \binom{n}{k}p^k(1-p)^{n-k}$, where $m=\lfloor np\rfloor +1$.