Timeline for Probability of one binomial variable being greater than another.
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 21, 2010 at 14:46 | comment | added | user4120 | 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...) | |
| Feb 21, 2010 at 9:52 | comment | added | Tom LaGatta | 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. | |
| Feb 21, 2010 at 8:15 | comment | added | Alekk | 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. | |
| Feb 20, 2010 at 23:52 | comment | added | user4120 | 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.) | |
| Feb 20, 2010 at 20:25 | history | answered | David Shor | CC BY-SA 2.5 |