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.

  • $\begingroup$ 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. $\endgroup$
    – mike
    Nov 25 at 15:17
  • $\begingroup$ @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? $\endgroup$ Nov 25 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.