Timeline for Tail bound for Poisson random variable

8 events

when toggle format	what		by	license	comment
Aug 13, 2012 at 3:03	answer	added	cardinal		timeline score: 13
Aug 12, 2012 at 2:57	vote	accept	Bobby Kleinberg
Aug 11, 2012 at 15:22	answer	added	fedja		timeline score: 7
Aug 10, 2012 at 18:19	answer	added	irchans		timeline score: 1
Aug 10, 2012 at 17:33	answer	added	tergi		timeline score: 3
Aug 10, 2012 at 16:18	comment	added	Bobby Kleinberg		Maybe "tail bound" was a poor choice of words. I'm thinking of $\lambda$ as a fixed constant in (0,1), and I think the difficult case is actually when $\lambda$ is very close to 1, so $e^{-\lambda}$ should not be interpreted as inverse-exponential. The probability a Poisson equals its mode is inverse-square-root, this would enable a lower bound of $\Theta(1/\sqrt{k})$, but that doesn't exceed $e^{-\lambda}$ when $k$ is larger than $e^{c \lambda}$ for some $c$.
Aug 10, 2012 at 15:05	comment	added	Ryan O'Donnell		Any chance there's a typo in the question? What you wrote does not look like a tail bound to me. E.g., if $\lambda$ is $1/2$, you're asking about the probability a Poisson(k/2) is less than k (i.e., that it's less than twice its mean)? The probability a Poisson equals its mode should already be inverse-square-root, much bigger than inverse-exponential.
Aug 10, 2012 at 14:13	history	asked	Bobby Kleinberg	CC BY-SA 3.0