Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 6 down vote accepted

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}$$

These both have the correct distributions.

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.

share|cite|improve this answer
Oh yes, coupling! Unfortunately I only came across this once in my studies and forgot about it again, but here it is exactly what you need. (+1) – TMM Sep 10 '11 at 15:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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