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

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)$.