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