- Markov’s Inequality; Chebychev’s Inequality; Chernoff’s Bound.
- Bounds for the Poisson Distribution.
Throughout this section we assume that is a real valued random variable. The mean, variance and moment generating function of are, respectively, , and , when these exist.
Ex 1. [Markov’s Inequality] For positive random variable
Markov’s inequality can be thought of as an upper-bound on the probability or as a lower-bound on the expectation:
Ex 2. Let be the mode of , i.e. then
(Similar logic applies to other quartiles.)
Ex 3. [Chebychev’s Inequality] For with mean and variance
Ex 4. For a positive increasing function ,
Ex 5. [Chernoff’s Bound]
Let’s get some handy exponential and normal tail bounds for the Poisson distribution.
Ex 6. [Some Poisson Bounds] For , a Poisson random variable with parameter ,
Ex 7. [Continued]
Ex 8.[Continued] For ,
Ans 1. now take expectations.
Ans 2. Applying Markov’s inequality
Ans 3. Consider , square both sides and apply Markov .
Ans 4. Consider , apply to both sides and then .
Ans 5. Take apply , then minimize over theta.
Ans 6. First equality is straightforward. Second, implies which after substitution gives the bound.
Ans 7. First bound: The Chernoff bound  gives
By assumption , substituting this into the logorithm above gives the result. Second, by the same Chernoff bound and use that .
Ans 8. Similar to  with ; however now apply the bound .