Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
2  
X and Y are independent, right? –  Yemon Choi Feb 20 '10 at 20:29
1  
Do you want upper bounds when the probability is large, or upper bounds when the probability is small? The Berry-Esseen theorem tells you how rapidly the normal approximation works, but that might not help if you want tight estimates on the tails. –  Douglas Zare Feb 20 '10 at 21:03
    
Yes, X and Y are independent. As to the bounds, I apologize that I don't totally understand the question. What I want to do is find control the probability of the worse coin "beating" the better coin. (i.e. I want to upper bound $Pr(y>x)$ when $y\leftarrow B(n,q), x \leftarrow B(n,p)$ and $q<p$.) The specific application is in a randomized approximation algorithm-- I want to select $n$ to be as low as I can. Thank you for the pointer to the Berry-Esseen theorem. It looks like this can be used to convert Normal approximations into rigorous bounds? –  user4120 Feb 20 '10 at 21:31
2  
Yes, the Berry-Esseen theorem can be used to make the normal approximation effective. Whether that helps you a lot or not depends on the type of bound you want. If you can get the probability within 0.01, is that good? Or are you interested in the tails, where the probability might be 10^-6, and being off by a 0.01 is unacceptable? If the latter, then you may want something other than the Berry-Esseen theorem, and other bounds exist for that case. –  Douglas Zare Feb 20 '10 at 21:39
    
Thank you for the clarification. I am interested in the tails, in the sense that I would like a bound that becomes tight as $n$ becomes large. –  user4120 Feb 20 '10 at 22:37

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
I forgot to add the following: Please clarify whether the third point is a source of problems with the Hoeffding bound in your case. –  Douglas Zare Feb 21 '10 at 4:39
    
The third point is not the source of the problem. Or, at least, it isn't the immediate problem-- Hoeffding's bound is still frustratingly loose for $p$ and $q$ near $\frac{1}{2}$. (Still processing the rest of your post.) –  user4120 Feb 21 '10 at 5:17
1  
for this, even the simple Markov inequality is better than Hoeffding since one can carry out all the computations exactly. This gives something like: P[Y>X] < [ 2\sqrt{pq(1-p)(1-q)} + (1-p)(1-q) + pq ]^n –  Alekk Feb 21 '10 at 7:28
1  
@Alekk: Isn't the bound you obtain essentially tight? (i.e loosing at most a factor of 1/sqrt(n)) –  maks Feb 21 '10 at 23:12
    
Isn't there something wrong with your first formula: if you swap $p$ and $q$ (or $X$ and $Y$ if you want), you still have the same bound... –  CommuSoft 2 days ago

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).

share|improve this answer

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..

share|improve this answer
    
This gives an expression which is very accurate for large $n$, but isn't an upper bound $Pr(y>x)$. (Experimentally, it seems a lower bound.) –  user4120 Feb 20 '10 at 23:52
    
so what are you exactly looking for: normal approximation gives you the right rate of decay \lambda such that P(y>x) \approx C.exp(-\lambda n) while Hoeffding/Markov gives you another rate \lambda_2 which is 'slightly' weaker, but exact. –  Alekk Feb 21 '10 at 8:15
    
kooooooong, once you know that a variable Z has Gaussian tail decay, you're done. There is the elementary estimate (1/u-1/u^3) exp(-u^2) < P(X>u) < (1/u) exp(-u^2). This is well-known. For example, see Adler & Taylor "Random Fields and Geometry" for a quick proof. –  Tom LaGatta Feb 21 '10 at 9:52
    
Sure, the trouble is in bounding the difference of that Gaussian tail to the original distribution. There doesn't seem to be any obvious standard tool for establishing that. (Other than maybe Berry-Esseen, though it isn't clear how tight the bounds that yields are...) –  user4120 Feb 21 '10 at 14:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.