Probability of one binomial variable being greater than another. I need to calculate (or bound) the probability that one binomial variable is greater than other.  Specifically, if $x \leftarrow  B(n,p)$ and $y \leftarrow B(n,q)$, what is the probability that $y \geq x$?  Informally, I will flip two bent coins with known biases $n$ times each, and I would like a convenient expression/bound on the probability that one beats the other.  If it matters, I would specifically like upper bounds on $Pr(y \geq x)$ when $q < p$.
I've tried to following strategies:


*

*Consider $z=y-x$ to be a variable.  Bound $Pr(z\geq 0)$ using Hoeffding's inequality.  This works, but seems to give very weak bounds.

*Approximate $B(n,p)$ and $B(n,q)$ with normal distributions.  Call these $P(x)$ and $Q(y)$.  Then do the integral $\int_{x=0}^n \int_{y=x}^n Q(y) P(x) dy dx$.  This gets ugly pretty fast and, even if it succeeded, wouldn't give a tight bound, but only an approximation.


Seems like it would be a well-studied problem, but searching doesn't uncover much.  I appreciate any help!
 A: Edit: I've filled in a few more details.
The Hoeffding bound from expressing $Y-X$ as the sum of $n$ differences between Bernoulli random variables $B_q(i)-B_p(i)$ is 
$$Prob(Y-X \ge 0) = Prob(Y-X + n(p-q) \ge n(p-q)) \le \exp\bigg(-\frac{2n^2 (p-q)^2}{4n}\bigg)$$
$$Prob(Y-X \ge 0) \le \exp\bigg(-\frac{(p-q)^2}{2}n\bigg)$$
I see three reasons you might be unhappy with this.


*

*The Hoeffding bound just isn't sharp. It's based on a Markov bound, and that is generally far from sharp. 

*The Hoeffding bound is even worse than usual on this type of random variable. 

*The amount by which the Hoeffding bound is not sharp is worse when $p$ and $q$ are close to $0$ or $1$ than when they are close to $\frac12$. The bound depends on $p-q$ but not how extreme $p$ is. 


I think you might address some of these by going back to the proof of Hoeffding's estimate, or the Bernstein inequalities, to get another estimate which fits this family of variables better. 
For example, if $p=0.6$, $q=0.5$, or $p=0.9$, $q=0.8$, and you want to know when the probability is at most $10^{-6}$, the Hoeffding inequality tells you this is achieved with $n\ge 2764$.
For comparison, the actual minimal values of $n$ required are $1123$ and $569$, respectively, by brute force summation.  
One version of the Berry-Esseen theorem is that the Gaussian approximation to a cumulative distribution function is off by at most 
$$0.71 \frac {\rho}{\sigma^3 \sqrt n}$$
where $\rho/\sigma^3$ is an easily computed function of the distribution which is not far from 1 for the distributions of interest. This only drops as $n^{-1/2}$ which is unacceptably slow for the purpose of getting a sharp estimate on the tail. At $n=2764$, the error estimate from Berry-Esseen would be about $0.02$. While you get effective estimates for the rate of convergence, those estimates are not sharp near the tails, so the Berry-Esseen theorem gives you far worse estimates than the Hoeffding inequality. 
Instead of trying to fix Hoeffding's bound, another alternative would be to express $Y-X$ as a sum of a (binomial) random number of $\pm1$s by looking at the nonzero terms of $\sum (B_q(i)-B_p(i))$. You don't need a great lower bound on the number of nonzero terms, and then you can use a sharper estimate on the tail of a binomial distribution. 
The probability that $B_q(i)-B_p(i) \ne 0$ is $p(1-q) + q(1-p) = t$. For simplicity, let's assume for the moment that there are $nt$ nonzero terms and that this is odd. The conditional probability that 
$B_q(i)-B_p(i) = +1$ is $w=\frac{q(1-p)}{p(1-q)+q(1-p)}$.
The Chernoff bound on the probability that the sum is positive is $\exp(-2(w-\frac 12)^2tn)$.
$$ \exp(-2\bigg(\frac{q(1-p)}{p(1-q)+q(1-p)} - \frac 12\bigg)^2 \big(p(1-q) + q(1-p)\big) n)$$
is not rigorous, but we need to adjust $n$ by a factor of $1+o(1)$, and we can compute the adjustment with another Chernoff bound. 
For $p=0.6, q=0.5$, we get $n \ge 1382$. For $p=0.9, q=0.8$, we get $n \ge 719$.
The Chernoff bound isn't particularly sharp. Comparison with a geometric series with ratio $\frac{w}{1-w}$ gives that the probability that there are more $+1$s than $-1$s is at most
$${nt \choose nt/2} w^{nt/2} (1-w)^{nt/2} \frac {1-w}{1-2w}$$
This gives us nonrigorous bounds of $nt \gt 564.4, n \ge 1129$ for $p=0.6,q=0.5$ and 
$nt\gt 145.97, n\ge 562$ for $p=0.9,q=0.8$. Again, these need to be adjusted by a factor of $1+o(1)$ to get a rigorous estimate (determine $n$ so that there are at least $565$ or $146$ nonzero terms with high probability, respectively), so it's not a contradiction that the actual first acceptable $n$ was $569$, greater than the estimate of $562$. 
I haven't gone through all of the details, but this shows that the technique I described gets you much closer to the correct values of $n$ than the Hoeffding bound.
A: I think you are missing the point a little bit. Hoeffding's inequality being good or bad is in no way linked to Markov's inequality. It can be shown that in your situation it is optimal up to a factor like 1/sqrt(x), which is the factor before the exponent in the asymptotics of the poisson tail. 
The uniform Berry-Esseen bounds are worthless when dealing with concentration inequalities for independent random variables. Even the non-uniform versions will not bring you very far.
My suggestions. The Hoeffding bound you are using is not the best bound that can be obtained using exponential functions. The best possible such inequality is given in the paper of Hoeffding 1963. It has a nice analytic form (but not an exponent). Take it and use it, I do not believe you will bet much further than this (except, maybe, you can lose the factor I told you above).  
A: Normal approximation is the simple way to go.
P~N(p,p(1-p)/n)
Q~N(q,p(1-q)/n)
wlog, let p>q, to calculate the probability that P>Q, find the distribution of P-Q and find when it's 0.
P-Q~N(p-q, (p(1-p)+q(1-q))/n). Just integrate from there and all is well..
