Return to Answer

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.

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!]

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-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-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.

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.

Not a complete answer (for lack of time, will try to add later). 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-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 } =:F(p).$$

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-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-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.