Timeline for Probability of one binomial variable being greater than another.
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 26, 2014 at 0:31 | comment | added | willeM_ Van Onsem |
No offense ;), it was merely from a programming perspective. And well one could simply branch over the two cases with an if I guess?
|
|
| Aug 26, 2014 at 0:21 | comment | added | Douglas Zare | @CommuSoft: I used the assumption that $p \gt q$. As far as I can see, this is a correct application of Hoeffding's inequality on random variables in $[-1,1]$. Perhaps what happens if you reverse that assumption indicates that Hoeffding's inequality can't be sharp. | |
| Aug 25, 2014 at 23:13 | comment | added | willeM_ Van Onsem | 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... | |
| Feb 24, 2010 at 13:45 | vote | accept | user4120 | ||
| Feb 24, 2010 at 3:30 | history | edited | Douglas Zare | CC BY-SA 2.5 |
Added more explicit estimates and numerical examples.
|
| Feb 21, 2010 at 23:12 | comment | added | maks | @Alekk: Isn't the bound you obtain essentially tight? (i.e loosing at most a factor of 1/sqrt(n)) | |
| Feb 21, 2010 at 7:28 | comment | added | Alekk | 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 | |
| Feb 21, 2010 at 5:17 | comment | added | user4120 | 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.) | |
| Feb 21, 2010 at 4:39 | comment | added | Douglas Zare | I forgot to add the following: Please clarify whether the third point is a source of problems with the Hoeffding bound in your case. | |
| Feb 21, 2010 at 4:31 | history | answered | Douglas Zare | CC BY-SA 2.5 |