What is the probability for a Binomial to be greater than other? Let $X = B(n, p)$ and $Y = B(k, q)$ be two random variables with binomial distribution and, let $s$ be a positive integer. Assume that $n > k+s$ and $np \geq kq+s$.
What is the probability for $X$ to be greater than $Y+s$, i.e. $\Pr[X-Y > s]$? (A good lower-bound might be helpful)
 A: $\newcommand{\R}{\mathbb{R}} 
\renewcommand{\P}{\operatorname{\mathsf P}}
\newcommand{\de}{\delta}
\newcommand{\be}{\beta}$
I think the best bet here is to use the Berry--Esseen inequality for the binomial distribution. 
Let $X_1:=X$, $X_2:=Y$, $p_1:=p$, $q_1:=1-p_1$, $p_2:=q$, $q_2:=1-q_1$, $n_1:=n$, $n_2:=k$. Let $U_1$ and $U_2$ be independent normal random variables (r.v.'s) with the first two moments matching those of $X_1$ and $X_2$, 
respectively. By Theorem 1.4, 
\begin{equation}
 \sup_{x\in\R}|\P(X_j\le x)-\P(U_j\le x)|\le c\be_3(p_j)/\sqrt{n_j}=:\de(n_j,p_j), 
\end{equation}
where
\begin{equation}
 c:=0.4215,\quad\be_3(p_j):=\frac{p_j^2+q_j^2}{\sqrt{p_jq_j}};
\end{equation}
everywhere here $j=1,2$. Hence, 
\begin{align*}
 \P(X-Y>s)&=\int_\R\P(X-y> s)\P(Y\in dy) \\ 
 &\ge\int_\R\P(U_1-y> s)\P(Y\in dy)-\de(n_1,p_1) \\ 
 &=\P(U_1-Y> s)-\de(n_1,p_1) \\ 
& =\int_\R\P(u-Y> s)\P(U_1\in du)-\de(n_1,p_1) \\ 
& \ge\int_\R\P(u-U_2> s)\P(U_1\in du)-\de(n_2,p_2)-\de(n_1,p_1) \\ 
& =\P(U_1-U_2> s)-\de(n_2,p_2)-\de(n_1,p_1)=:L. 
\end{align*}
Note here also that $U_1-U_2$ is a normal r.v. with mean $np-kq\ge s$ and variance $np(1-p)+kq(1-q)$. So, $\P(U_1-U_2\ge s)\ge1/2$ and the lower bound $L$ on $\P(X-Y>s)$ should work well if $np(1-p)$ and $kq(1-q)$ are large enough. 
Quite similarly, one can also obtain an upper bound on $\P(X-Y>s)$: 
\begin{equation}
 \P(X-Y>s)=\P(X-Y\ge s+1)\le\P(U_1-U_2\ge s+1)+\de(n_2,p_2)+\de(n_1,p_1).
\end{equation}
