Let $\epsilon > 0$. Let $(p_k),(q_k) , k \in \mathbb{N}$ be two sequences $ \in [1/2-\epsilon,1/2+\epsilon]$ s.t. $p_k>q_k$. For $k \in \mathbb{N}$, let $B_k(p_k)$ and $B_k(q_k)$ be two independent binomial random variables with parameters $(k,p_k)$ and $(k,q_k)$ respectively.
What I would like
I am looking for a non-trivial lower bound on $$ \mathbb{P}(B_k(p_k) > B_k(q_k)) + \frac{1}{2} \mathbb{P}(B_k(p_k) = B_k(q_k)) $$ as a function of $(p_k-q_k)$. By ``non-trivial'', I mean strictly greater than $1/2$ :)
You can see this as the probability to beat an opponent in a $k$-rounds coin toss game, when both coins are only close to perfectly balanced.
I only need this lower bound to hold asymptotically (i.e., for $k$ large enough), and specifically, I'm considering the case $(p_k-q_k) = o(1/k)$.
I am ready to assume that $(p_k-q_k) > 1/e^{k/2}$ (in case such assumption is useful...)
What I have tried already
Hoeffding's bound gives (see this post): $$ \mathbb{P}( B_k(p_k) > B_k(q_k) ) > 1 - \exp \left( -\frac{1}{2} k (p_k-q_k) \right), $$ which goes to $0$ in my case.
I've also tried to use the Berry-Esseen theorem, ending up with: $$ \mathbb{P}( B_k(p) > B_k(q) ) > \Phi \left( \frac{\sqrt{k}(p_k-q_k)}{\sigma_k} \right) - \frac{C}{\sigma_k \sqrt{k}} , $$ where $\sigma_k = \sqrt{p_k(1-p_k) + q_k(1-q_k)}$ and $C = 0.4748$ for instance. Again, the RHS is too small for my purpose, when $(p_k-q_k)$ is very small.