Timeline for Lowerbounding expectation value of binomial tail
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 22, 2020 at 7:07 | answer | added | ofer zeitouni | timeline score: 0 | |
| Jun 21, 2020 at 10:36 | comment | added | Mateus Araújo | I still don't see how that helps. For example, I can directly apply the Chernoff bound to $P(B\ge 0)$, which gives me the upper bound $f(q,p,n) \le (\sqrt{pq}+\sqrt{(1-p)(1-q)})^{2n}$, but this is exactly the same bound I got via generating functions. And the difficult is anyway finding a lower bound. Do you have any specific anti-concentration inequality in mind that would work? Also, the variance of $W_i$ is $p(1-p)+q(1-q)$. | |
| Jun 20, 2020 at 19:17 | comment | added | ofer zeitouni | As to the actual question you asked - asymptotics then become very easy, it is a large deviations question, since the means are different. Exact computations I will leave to others, although I note that you are asking for $P(B\geq 0)$ where $B=\sum_{i=1}^N W_i$, $W_i$ iid, and $EW_i=p-q$ and variance of $W_i$ equal $2q(1-p)$. Asymptotics now follow... | |
| Jun 20, 2020 at 19:12 | comment | added | ofer zeitouni | By symmetry. You have two identically distributed variables $A,B$ and you ask for $P(A\geq B)$, which equals $1/2+P(A=B)$. The local CLT tells you that the probability that $A=B$ is of order $1/\sqrt{n}$ | |
| Jun 20, 2020 at 13:54 | comment | added | Mateus Araújo | Yes, it is. I don't see how that helps, though (I'm a physicist, not a mathematician). For example, the exact expression for $f(\frac12,\frac12,n)$ is $\frac12 + 4^{-n}\binom{2n}{n}/2$. How can one get that without doing work? | |
| Jun 20, 2020 at 12:02 | comment | added | ofer zeitouni | Isn't it just the probability that a Binomial(p,n) is greater than or equal to an independent binomial(q,n)? This gives immediately the cases you wrote (no need for limits or work...), and a bit of work should give you a decent bound (with actually the correct exponential rate). | |
| Jun 20, 2020 at 10:02 | history | asked | Mateus Araújo | CC BY-SA 4.0 |