- 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 ,

and

**Ex 7. **[Continued]

**Ex 8.**[Continued] For ,

# Answers.

**Ans 1.** now take expectations.

**Ans 2.** Applying Markov’s inequality

**Ans 3.** Consider , square both sides and apply Markov [1].

**Ans 4.** Consider , apply to both sides and then [1].

**Ans 5.** Take apply [4], 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 [5] 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 [7] with ; however now apply the bound .