Basic Probability Bounds

  • Markov’s Inequality; Chebychev’s Inequality; Chernoff’s Bound.
  • Bounds for the Poisson Distribution.

Throughout this section we assume that X is a real valued random variable. The mean, variance and moment generating function of X are, respectively, \mu, \sigma and M_X(\theta), when these exist.

Ex 1. [Markov’s Inequality] For positive random variable X

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 m be the mode of X, i.e. {\mathbb P}( X\leq m) = \frac{1}{2} then

(Similar logic applies to other quartiles.)

Ex 3. [Chebychev’s Inequality] For X with mean \mu and variance \sigma

Ex 4. For a positive increasing function f,

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 Po(\mu), a Poisson random variable with parameter \mu,

and

Ex 7. [Continued]

 

Ex 8.[Continued] For z\geq 0,


Answers.

Ans 1. \mathbb{I} [X \geq x] \leq \frac{X}{x} now take expectations.

Ans 2. Applying Markov’s inequality

Ans 3. Consider |X-\mu| \geq x, square both sides and apply Markov [1].

Ans 4. Consider X \geq x, apply f to both sides and then [1].

Ans 5. Take f(x)=e^{\theta x} apply [4], then minimize over theta.

Ans 6. First equality is straightforward. Second, \frac{d}{d\theta} (\mu e^\theta -\theta x)=0 implies \theta= \log \left(\frac{x}{\mu} \right) which after substitution gives the bound.

Ans 7. First bound: The Chernoff bound [5] gives

By assumption \log \frac{x}{\mu}\geq 2, substituting this into the logorithm above gives the result. Second, by the same Chernoff bound and use that \frac{x}{\mu}\log \frac{x}{\mu} \leq 0.

Ans 8. Similar to [7] with x=\mu+z; however now apply the bound \log (1+z/\mu)\geq z/\mu +z^2/(2\mu^2).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s