# An inequality about binomial distribution

The question is:

Consider $n$ Bernoulli trials, where for $i = 1, 2,..., n$, the $i$th trial has probability $p_i$ of success, and let $X$ be the random variable denoting the total number of successes. Let $p \ge p_i$ for all $i = 1, 2, \ldots , n$. Prove that for $1 \le k \le n$,

$$\Pr \{ X < k \} \ge \sum_{i=0}^{k-1}b(i; n, p)$$

I tried to use induction on $k$ but obviously it doesn't work.

-
Would it be too simple to argue that if every single trial in process $A$ has a lower success probability than in process $B$, then the probability of getting less than some fixed number of successes $k$ in $A$ is higher than in $B$? Or do you want a "mathematical" proof? –  TMM Sep 10 '11 at 14:53
@George, it does work with p = 1 –  ablmf Sep 10 '11 at 14:56
@Thijs's comment indicates the exact reason why the result holds. Relying on coupling, one can turn this into a full fledged proof--if necessary... :-) –  Did Sep 10 '11 at 15:14

You're trying to show that for $0\leq k\leq n$, $\mathbb{P}[X\leq k]\geq \mathbb{P}[\text{Bin}(n,p)\leq k]$.
We can prove this by coupling; the idea is to work on a probability space over which these variables are related in a useful way. Let $(U_i:1\leq i\leq n)$ be a sequence of IID uniform random variables on $[0,1]$ and write:
$$X=\sum\limits_{i=1}^n \mathbf{1}_{U_i<p_i}\quad\text{and}\quad \text{Bin}(n,p) = \sum\limits_{i=1}^n \mathbf{1}_{U_i<p}$$
Now $X\leq \text{Bin}(n,p)$ with full probability. In particular, on this probability space, $\{\text{Bin}(n,p)\leq k\}\subset \{X\leq k\}$, so taking probabilities gives the result.