Let $p,q \in [0,1]$ with $p>q$. I denote by $B_k(p), B_k(q)$ two independent random variables following the binomial distribution, with parameters $(k,p)$ and $(k,q)$ respectively.
Informal Question
I would like to estimate the advantage granted by having the better "$p$" coin, in a $k$-rounds "coin tossing" contest, in the case that $p$ and $q$ are very close to each other.
Formal question
Is there a lower bound on \begin{equation} \label{eq} \mathbb{P}(B_k(q) < B_k(p)) - \mathbb{P}(B_k(p) < B_k(q)) \end{equation} which would be a function of $\epsilon = (p-q)$, and greater than $0$ even when $\epsilon \ll 1/k$?
More precisely, I consider the case that $k$ tends to $+\infty$ (but don't forget that $\epsilon$ shrinks faster than $1/k$...). Moreover, I may assume $p$ and $q$ as close to $1/2$ as I want.
My ideas so far
I tried to write Hoeffding bound, and got $$ \mathbb{P}(B_k(p) < B_k(q)) < \exp \left( -\frac{1}{2}k\epsilon^2 \right), $$ which is not good enough for $\epsilon \ll 1/k$.
I also tried to approximate the binomial distribution by the normal distribution using the Berry-Esseen theorem -- but it turns out to be too coarse. Specifically, I can obtain $$ \left| \mathbb{P}(B_k(q) < B_k(p)) - \Phi \left( \frac{\sqrt{k}\epsilon}{\sigma} \right) \right| < \frac{C}{\sigma \sqrt{k}}$$ and $$ \left| \mathbb{P}(B_k(p) < B_k(q)) - \Phi \left( -\frac{\sqrt{k}\epsilon}{\sigma} \right) \right| < \frac{C}{\sigma \sqrt{k}},$$ where $\sigma = \sqrt{p(1-p)+q(1-q)}$ and, e.g., $C = 0.4748$; but the RHS in both equations is too big to lead to the desired result.
My next step is to write the exact expression and derive w.r.t. $\epsilon$, but I'm not confident that it will lead to a good result (I'd be happy to hear your thoughts about it in the comments).
I originally asked this question on Mathematics Stack Exchange, but then I realized it could suit MathOverflow better.
