Timeline for Probability Theory, Chernoff Bounds, Sum of Independent (but not identically distributed) r.v
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 6, 2010 at 21:22 | vote | accept | Michael | ||
| Nov 7, 2010 at 10:28 | |||||
| Nov 6, 2010 at 21:19 | comment | added | Michael | Maybe I should write this in the question: Yes, my $E[X]=\Theta(n)$. As I commented in the another answer, I think there is no such bound for this case (linear expectation and exponential bound). | |
| Nov 6, 2010 at 21:07 | comment | added | Warren Schudy | Can't you pick $t=\Theta(\sqrt{n})$? Do you know that $E[X] = \Omega(n)$? If $E[X]$ can be arbitrarily small then you can't get better than Markov. | |
| Nov 6, 2010 at 18:41 | vote | accept | Michael | ||
| Nov 6, 2010 at 20:40 | |||||
| Nov 6, 2010 at 18:03 | vote | accept | Michael | ||
| Nov 6, 2010 at 18:41 | |||||
| Nov 6, 2010 at 18:02 | comment | added | Michael | But is seems that Bernstein inequality (for geometric r.v. we can use ineq. #2 from the link) can't give exponential tail in the case t=constant. If t is not constant, then we don't get $\Pr(X > \alpha\cdot E[X])$, where $\alpha=const$. | |
| Nov 6, 2010 at 15:55 | history | answered | Warren Schudy | CC BY-SA 2.5 |