Monotonicity of a partial binomial sum

Question

I'm wondering when does the following partial sum monotonically increase or decrease in $n$: $$f_x(n)=\sum^{\lfloor\frac{n}{2}\rfloor}_{k=0}{n \choose k}x^k(1-x)^{n-k}.$$

In theory, if $x<\frac{1}{2}$, the probability converges to 1. On the other hand, if $x>\frac{1}{2}$, it converges to zero. And when $x=\frac{1}{2}$, it converges to $\frac{1}{2}$.

I initially tried to show that the convergence is monotonically made, meaning that $f_x(n)$ is monotone in $n$. However, I tried several numbers for $x$ and found that it is actually not.

For example, when $x=0.49$, we have $f_{0.49}(2)\simeq0.7599$, $f_{0.49}(20)\simeq0.6229$, $f_{0.49}(10000)\simeq0.9778$. A similar example can be found for $x>\frac{1}{2}$.

Is there any intuition behind this non-monotonicity? or is there any increment in $n$ that the monotonicity is guaranteed?

Answer 1

I believe this is due to the fact that you're using even $n$. That includes the central coefficient $\binom n{n/2}$ and is thus half a value more than half of the sum. The effect of this “rounding error” is greater at smaller $n$, since half an additional value makes more of a difference when the distribution is spread over fewer values, and you're seeing the combined effect of this and the fact that the distribution gets more fully concentrated in the first half with increasing $n$. This effect doesn't occur for odd $n$, where you do get exactly half of the sum. For instance, $f_{0.49}(3)\approx0.5150$, $f_{0.49}(21)\approx0.5370$ and $f_{0.49}(10001)\approx0.9773$.

Answer 2

I think that this is a very complex problem.

Condering the case where $n$ is even, we have $$f_x(2m)=\sum^{m}_{k=0}{{2m} \choose k}x^k(1-x)^{2m-k}$$ Assuming $0 < x <1$, this is $$f_x(2m)=1-\binom{2 m}{m+1} (1-x)^{m-1} x^{m+1}\, _2F_1\left(1,1-m;m+2;-\frac{x}{1-x}\right)$$ Considering $m$ as a continuous variable and looking for the minimum value of $f_x(2m)$ for $m > 0$ there is always a minimum; however, assuming that I am not mistaken, it seems that this true only for $x < 0.5$ (I did not check for odd values of $n$).

Consider the case of $x=0.49$, the numerical values are given in the following table $$\left( \begin{array}{cc} m & \text{value} \\ 20 & 0.612207 \\ 21 & 0.611946 \\ 22 & 0.611757 \\ 23 & 0.611631 \\ 24 & 0.611560 \\ 25 & \color{red} {0.611537} \\ 26 & 0.611558 \\ 27 & 0.611618 \\ 28 & 0.611711 \\ 29 & 0.611835 \\ 30 & 0.611987 \end{array} \right)$$

Answer 3

After I saw the answer from joriki, I only focused on odd $n$ cases and could show the monotonicity. I'll leave my reasoning here for a future reference. Thanks for your comment, joriki.

Let $n=2m+1$, $m\geq 0$. I will show the sign of $f_p(2m+3)-f_p(2m+1)$ depends on whether $p>\frac{1}{2}$ or $p<\frac{1}{2}$.

Let $X_{n,p}\sim Binomial(n,p)$. The associated cdf is given by $$F_p(n,k)=P[X_{n,p}\leq k]=\sum_{i=0}^{k}{n\choose i}p^i(1-p)^{n-i}.$$

Before begin, note that $f_p(2m+1)=F_p(2m+1,m)$. From the cdf, we have \begin{align}F_p(2m+3,m+1)=&P[X_{2m+3,p}\leq m+1]\\=&P[X_{2m+3,p}\leq m+1|X_{2m+1,p}<m]P[X_{2m+1,p}<m]\\&+P[X_{2m+3,p}\leq m+1|X_{2m+1,p}=m]P[X_{2m+1,p}=m]\\&+P[X_{2m+3,p}\leq m+1|X_{2m+1,p}=m+1]P[X_{2m+1,p}=m+1]\\ =&1\cdot F_{p}(2m+1,m-1)+(2p(1-p)+(1-p)^2){2m+1\choose m}p^m(1-p)^{m+1}\\ &+(1-p)^2{2m+1\choose m+1}p^{m+1}(1-p)^m. \end{align} Here, note that $F_p(2m+1,m-1)=F_p(2m+1,m)-{2m+1\choose m}p^m(1-p)^{m+1}$. Plugging this in, the expression after the last equality is the same as $$F_p(2m+1,m)+(1-2p){2m+1\choose m}p^{m+1}(1-p)^{m+1}.$$ Thus, we have $$F_p(2m+3,m+1)=F_p(2m+1,m)+(1-2p){2m+1\choose m}p^{m+1}(1-p)^{m+1}$$ in which the sign of the last term is determined by whether it is $p>\frac{1}{2}$ or $p<\frac{1}{2}.$