A lower bound for the expectation of $\min\{X,n-X\}$ when $X$ follows a $\mathrm{Binomial}(n,p)$ distribution

Question

Let $X$ be a random variable following a $\mathrm{Binomial}(n,p)$ distribution, and let $$Y=\min\{X,n-X\}.$$ Ispired by the problem posed by C. Clement on https://math.stackexchange.com/questions/1696256/expectation-and-concentration-for-minx-n-x-when-x-is-a-binomial, I want to ask whether there exists some constant $c>0$ such that $\mathbb{E}(Y)\geq c\cdot\min\{p,1-p\}\cdot n$ for all $0<p<1$. If this is not true, can we find some $p_0$ with $\frac{1+\sqrt{5}}{4}\leq p_0<1$ such that if $X\sim \mathrm{Binomial}(n,p_0)$ then $\mathbb{E}(Y)\geq (1-p)[(1+4p)n-8(1+p)]$?

Answer 1

Since $\min(a,b)=(a+b-|a-b|)/2$, your question is really about upper bounding $E|2X-n|$, or, equivalently, $E|X-n/2|$:

$$E\min(X,n-X)=n/2-2E|X-n/2|.$$

You can upper bound $E|X-n/2|$ using Jensen's inequality: $E|X-n/2|\le\sqrt{E(X-n/2)^2}$.

The latter, if I'm not mistaken, evaluates to $$ n\sqrt{ p(1-p)/n+p^2-p+1/4 } =:nF(p).$$

For $n$ sufficiently large and $p$ sufficiently small (certainly, $p\le 0.65$; the exact value can be easily computed), we have $2F(p)\le c(1-p)$ for some universal $c>0$. That means that $n/2-2F(p)n\ge cnp$, so your conjecture holds for this range of $p$. [I'm confident that with a bit more care you can extend the result to all $p$, perhaps with a worse constant. Update: this "confidence" has proven misplaced, see Dmitry Krachun's answer below!]

Answer 2

Note that such a universal constant $c$ does not exist; by the law of large numbers ($\operatorname{Binomial}(n, p)$ being a sum of $n$ i.i.d $\operatorname{B}(p)$ r.v.), for any $p\in (0, 1)$ we have $\mathbb{E}[Y]/n\rightarrow \min\{p, 1-p\}$, so for $p$ close to $1$ constant $c$ must be taken to be at most $(1-p)/p$ to accommodate all large $n$; this tends to zero as $p\rightarrow 1$. To accommodate all $n$ you may need $c$ somewhat smaller than $\min\{p, 1-p\}/p$ but certainly you can always find some $c=c(p)$ which would work for all $n$.

For the second question the answer is no (assuming $p$ in the inequality should be read as $p_0$). Indeed, by the law of large numbers $\mathbb{E}[Y]/n\rightarrow 1-p_0$, whereas $\operatorname{RHS}/n\rightarrow (1-p_0)(1+4p_0)>1-p_0$.