Bounding the probability of one Binomial r.v. greater than another.

Question

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?

---

Update: see my answer below.

Answer 1

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). $$

Answer 2

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$