# Proving an inequation based on binomial distributions

Problem statement

Let $c \in \mathbb{N}$, $n_1 \in \mathbb{N}_0$, and $n_2 \in \mathbb{N}_0$ be integers and $p$ a probability. Furthermore, let $b(m,j,p) = \binom{m}{j}p^j(1-p)^{m-j}$ denote the probability mass function of the binomial distribution and let $B(m,j,p) = \sum_{i=0}^j b(m,i,p) = \sum_{i=0}^j \binom{m}{i}p^i(1-p)^{m-i}$ denote the cumulative binomial distribution function.

I want to prove that

$\forall k \in \mathbb{N}, k \leq c: \sum_{j=0}^{k-1} b\left(c,j,p\right) B_{j,k} \leq \sum_{j=0}^{k-1} b\left(c-1,j,p\right) B_{j,k}$

holds when $B_{j,k}$ is defined as

$B_{j,k} = B\left(n_1,k-1-j,p\right) \cdot B\left(n_2,k-1-j,p\right)$

What I have done so far

For an arbitrary $k \in \mathbb{N}$ satisfying $k \leq c$, we have \begin{align} &\sum_{j=0}^{k-1} b\left(c,j,p\right) B_{j,k} \leq\sum_{j=0}^{k-1} b\left(c-1,j,p\right) B_{j,k}\\ \iff \; &\sum_{j=0}^{k-1} \binom{c}{j}p^j(1-p)^{c-j} B_{j,k} \leq \sum_{j=0}^{k-1} \binom{c-1}{j}p^j(1-p)^{c-j-1} B_{j,k}\\ \iff \; &\sum_{j=0}^{k-1} \binom{c}{j}p^j(1-p)^{c-j} B_{j,k} \leq \frac{\sum_{j=0}^{k-1} \binom{c-1}{j}p^j(1-p)^{c-j} B_{j,k}}{1-p}\\ \iff \; &\sum_{j=0}^{k-1} (1-p)\binom{c}{j}p^j(1-p)^{c-j} B_{j,k} \leq \sum_{j=0}^{k-1} \binom{c-1}{j}p^j(1-p)^{c-j} B_{j,k}\nonumber\\ \iff \; &\sum_{j=0}^{k-1} \left[\binom{c-1}{j}-(1-p)\binom{c}{j}\right] p^j(1-p)^{c-j} B_{j,k} \geq 0\nonumber\\ \iff \; &\sum_{j=0}^{k-1} \left[\frac{c-j}{c}\binom{c}{j}-(1-p)\binom{c}{j}\right] p^j(1-p)^{c-j} B_{j,k} \geq 0\nonumber\\ \iff \; &\sum_{j=0}^{k-1} \frac{cp-j}{c} \binom{c}{j} p^j(1-p)^{c-j} B_{j,k} \geq 0\nonumber\\ \iff \; &\sum_{j=0}^{k-1} (cp-j) \binom{c}{j} p^j(1-p)^{c-j} B_{j,k} \geq 0 \end{align}

Unfortunately, at this point, I'm unsure how to continue, and would greatly appreciate any help!

Here are a few observations which might be useful:

• Because of the factor $cp-j$, every summand in in the last inequation with $j \leq \lfloor cp \rfloor$ is non-negative, while every summand with $j > \lfloor cp \rfloor$ is negative.
• The factors $B_{j,k}$ are monotonically decreasing with increasing $j$ and thus reduce the effect of the "harmful" negative summands. However, experimental evaluation suggests that the last inequation could be satisfied even in the absence of the $B_{j,k}$ factors. Maybe this could be exploited.

Without the $B_{j,k}$, the last sum can be evaluated: $$\sum_{j=0}^{k-1} (cp-j) \binom cj p^j (1-p)^{c-j} = k\binom ck p^k(1-p)^{c-k+1}.$$ Together with your observation that $B_{j,k}$ is decreasing, that does it, no?
• Led by the closed form of the sum, I was able to complete the proof with an induction that includes the $B_{j,k}$ and exploits their monotonicity. So the problem is solved, thanks again for the help :) However, I have to say I still don't see how to arrive at the closed form of the sum directly. I'd appreciate it if you could give me some hint how you did that, out of interest, and because it might be helpful with some related formulas I'm dealing with in my current research. Nov 13, 2015 at 12:59