Timeline for Expected maximum inner product
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 28, 2014 at 20:20 | vote | accept | Simd | ||
| Jan 28, 2014 at 11:17 | comment | added | Ben Barber | The binomial distribution is fairly flat in a strip of width $\sqrt m$ near its mean, so I certainly expect to see values of size $\sqrt m$. Lower bounds for the probability of large deviations are not as common as upper bounds, and I don't know any nice statements offhand, but something precise is said in the appendix of Alon and Spencer, for example. Often the guiding principle is that the binomial distribution is well approximated by a normal distribution in the centre. | |
| Jan 28, 2014 at 11:01 | comment | added | Simd | Thank you. Is there a matching lower bound which tells me that it is exponentially unlikely to take values smaller than anything just a tiny bit smaller than $\sqrt{m}$ too? | |
| Jan 28, 2014 at 10:53 | history | answered | Ben Barber | CC BY-SA 3.0 |