# Bounding the probability of one Binomial r.v. greater than another. [closed]

Let $X_1\sim Bin(k,p_1)$ and $X_2\sim Bin(k,p_2)$ be independent r.v. such that $p_1\neq p_2$, and w.l.o.g. let $p_1>p_2$. I wish to upper bound $\Pr(X_2 \geq X_1)$, i.e. finding as tight as possible $B=B(k,p_1,p_2)$ such that $$\Pr(X_2 \geq X_1)\leq B.$$ According to Total Probability we have $$\Pr(X_2 \geq X_1) = \sum_{i=0}^k\Pr(X_1=i)\Pr(X_2\geq i)=\sum_{i=0}^k{k \choose i}p_1^i(1-p_1)^{k-i}\Pr(X_2\geq i).$$ Expending the cdf did not produce anything interesting, therefore I tried using this bound on the cdf, but did not get anywhere.

Ideas?

• why does the $k$ suddenly turn into an $m$ in the second $=$ ? Mar 2 '18 at 16:08
• You could try to use Tschebyscheffs inequality for the expression $\Pr(X_2 \geq i)$. Mar 2 '18 at 16:34
• Are you assuming independence?
– Did
Mar 3 '18 at 20:21
• @Joker123 Thank, it was a typo. I wrote an answer below using Hoeffding's inequality, inspired by your answer. Thanks! Mar 4 '18 at 8:27

Too long for a comment:

You could get an approximation (at least for reasonable $k$ and probabilities not close to $0$ and $1$) with $$\Phi\left(\dfrac{k(p_2-p_1)+\frac12}{\sqrt{k (p_1(1-p_1)+p_2(1-p_2))}}\right)$$

As an example, with $k=10$, $p_1=0.4$ and $p_2=0.2$, you have $P(X_2 \ge X_1) \approx 0.2244$ while the approximation gives about $0.2266$

You be even more likely to exceed the true probability by changing the $\frac12$ in the approximation to $1$. The example would then suggest $0.3085$

• Thanks for your suggestion! Normal approximation is indeed valuable. I ended up using concentration inequalities, see my answer below. Mar 4 '18 at 8:40

Inspired by Joker123's comment above:

Define a series of i.i.d. r.v. $B_1,\dots,B_k$ such that $$B_i= \begin{cases} 1 & \text{w.p. } (1-p_1)p_2\\ 0 & \text{w.p. } p_1p_2 + (1-p_1)(1-p_2)\\ -1 & \text{w.p. } p_1(1-p_2)\\ \end{cases}.$$ Thus, \begin{align} \Pr(X_2 \geq X_1)&=\Pr(X_2-X_1\geq 0)=\Pr\left(\sum_{i=1}^k B_i \geq 0 \right) \\ & = \Pr\left(\frac{1}{k}\sum_{i=1}^k B_i - (p_2-p_1) \geq (p_1-p_2) \right). \end{align} Notice that $\mathbb E(B_i)=p_2-p_1$ for all $i\in\{1,\dots,k\}$, and that $B_i$ is bounded in the interval $[-1,1]$. Finally, using Hoeffding's Inequality we obtain $$\leq \exp\left( -\frac{2k^2(p_1-p_2)^2}{4k} \right).$$

• Do you really intend to have a $\frac{2k^2}{4k}$ term rather than $\frac{k}{2}$ or is there an typo? Mar 4 '18 at 11:02
• @Henry In favor of those who are not familiar with Hoeffding's Inequality, I presented it as appears in here - en.wikipedia.org/wiki/Hoeffding%27s_inequality . If you think it confuses readers, I'll change it. Mar 4 '18 at 11:14
• Very nice idea! Mar 4 '18 at 14:32