# Probability of winning a $k$-rounds coin toss game

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.

• View the smaller prob. as being obtained by first flipping a p coin and then a q/p coin and calling it a head if both coins are heads. In the regime you are interested in, you will likely get 1 or 0 extra p-heads, and therefore the probability that there are more p's is about the difference in expectations.
– mike
Nov 25 at 15:17
• @mike But that's a different joint distribution than the one the question asks about, right? The question asks about the case where $B_k(p)$ and $B_k(q)$ are independent. Or is there some reason why $\mathbb{P}(B_k(q) < B_k(p)) - \mathbb{P}(B_k(p) < B_k(q))$ is the same for the independent case and for your coupling? Nov 25 at 16:51