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.

1 Answer 1


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?

  • $\begingroup$ Thanks a lot for the fast reply! I didn't see that the sum could be written in such a closed, obviously non-negative form. This is quite helpful indeed. $\endgroup$
    – Permutant
    Nov 12, 2015 at 8:31
  • $\begingroup$ 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. $\endgroup$
    – Permutant
    Nov 13, 2015 at 12:59
  • 2
    $\begingroup$ @Permutant: I wish I tell you how clever I was, but actually I just put it into Maple and it gave the answer. I was surprised there was a closed form and checked a few cases numerically to be sure. $\endgroup$ Nov 13, 2015 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.