Relation between cumulative distribution of binomials $\Pr[\operatorname{Bin}(n,p)\geq t]\leq \Pr[\operatorname{Bin}(n,q)\geq t]$

Question

Let $p<q$ be probabilities, $n\in\mathbb{N}$, and $t\geq 2n\max\{p,q\}$. I am struggling to prove that

$$\Pr[\operatorname{Bin}(n,p)\geq t]\leq \Pr[\operatorname{Bin}(n,q)\geq t]$$

but I think it should be true. I tried to use induction on $n$ but it didn't work out.

Answer 1

In fact the inequality is true for all $t \in \mathbb{R}$. In other words, $\operatorname{Bin}(n,q)$ first-order stochastically dominates $\operatorname{Bin}(n,p)$. One technique of proving this inequality is to construct a coupling between two distributions.

Indeed, consider independent random variables $X_1, X_2, \dots, X_n, Y_1, Y_2, \dots, Y_n$ such taht

• $X_1, X_2, \dots, X_n$ have $\operatorname{Ber}(q)$ distribution, and

• $Y_1, Y_2, \dots, Y_n$ have $\operatorname{Ber}(p/q)$ distribution.

Then we find that

• $S_q = X_1 + X_2 + \cdots + X_n$ has $\operatorname{Bin}(n,q)$ distribution, and
• $S_p = X_1Y_1 + X_2Y_2 + \cdots + X_nY_n$ has $\operatorname{Bin}(n,p)$ distribution, since $X_iY_i$'s are independent and have $\operatorname{Ber}(p)$ distribution.

Now since $X_iY_i \leq X_i$ always holds, it follows that $S_p \leq S_q$, and hence

$$ \mathbb{P}(\operatorname{Bin}(n,p) \geq t) = \mathbb{P}(S_p \geq t) \leq \mathbb{P}(S_q \geq t) = \mathbb{P}(\operatorname{Bin}(n,q) \geq t). $$

Answer 2

You can use a coupling with $(0,1)$-uniform random variable $U_i \sim_\text{i.i.d} \mathcal{U}(0,1)$, $i = 1, \ldots, n$.

Set $X_i = \mathbf{1}_{U_i < p}$ and $Y_i = \mathbf{1}_{U_i < q}$. Since $p < q$, $X_i \leqslant Y_i$.

Now, $A := X_1 + \cdots + X_n \sim \textrm{Ber}(n,p)$ and $B := Y_1 + \cdots + Y_n \sim \textrm{Ber}(n,q)$. One has $A \leqslant B$, wherefrom you can conclude.