Markov and Chebyshev Inequalities

Definition An upper bound for the probability of an event $A$ is a number $b$ with $P(A) \le b$ that is proved from partial information about the model, such as the possible values, the mean or the variance, and therefore holds for every distribution with that information. A lower bound $P(A) \ge b$ is defined the same way. A tail probability is the probability of an event such as $\{X \ge a\}$ or $\{\lvert X - \mu \rvert \ge d\}$, in which a variable is large or far from its mean. Every probability is at most $1$, so an upper bound $b \ge 1$ is true but carries no information, and the useful statement is $P(A) \le \min(1, b)$.

Definition Let $X$ be a random variable with $P(X \ge 0) = 1$ and finite expectation, and let $a > 0$. Then

To prove it, let $I$ be the indicator of the event $\{X \ge a\}$. With probability $1$ the inequality $X \ge aI$ holds, because $X \ge a$ where $I = 1$ and $X \ge 0$ where $I = 0$. Taking expectations gives $E[X] \ge a\,E[I] = a\,P(X \ge a)$, and dividing by $a > 0$ finishes the proof. For a discrete $X$ the same argument reads

The first inequality drops the terms with $x < a$, which are nonnegative because $X \ge 0$, and the second replaces each remaining value by the smaller or equal number $a$. Since $\{X > a\}$ is contained in $\{X \ge a\}$, the same bound holds for $P(X > a)$.

Definition Let $Y$ have finite mean $\mu$ and let $d > 0$. The two-sided deviation event at distance $d$ is $\{\lvert Y - \mu \rvert \ge d\}$. It is the union of the lower tail $\{Y \le \mu - d\}$ and the upper tail $\{Y \ge \mu + d\}$, and both boundary points $\mu - d$ and $\mu + d$ belong to it. Its complement is the event $\{\lvert Y - \mu \rvert < d\}$, which is $\{\mu - d < Y < \mu + d\}$ with strict inequalities. The strict event $\{\lvert Y - \mu \rvert > d\}$ is contained in the two-sided event and has smaller probability when the boundary points carry probability. Because both sides are nonnegative, $\lvert Y - \mu \rvert \ge d$ holds exactly when $(Y - \mu)^2 \ge d^2$. A one-sided event such as $\{Y \ge \mu + d\}$ is contained in the two-sided event, so its probability is no larger.

Definition Let $Y$ have finite mean $\mu$ and finite variance $\sigma^2$, and let $d > 0$. Then

and taking complements,

To prove it, note that $(Y - \mu)^2$ is nonnegative with expectation $\sigma^2$, that $d^2 > 0$, and that $\{\lvert Y - \mu \rvert \ge d\} = \{(Y - \mu)^2 \ge d^2\}$. Markov’s inequality applied to $(Y - \mu)^2$ with threshold $d^2$ gives the bound.

Definition Let $Y$ have finite mean $\mu$ and finite standard deviation $\sigma > 0$, and let $k > 0$. Taking $d = k\sigma$ in Chebyshev’s inequality gives

Equivalently, at least $1 - 1/k^2$ of the probability lies strictly within $k$ standard deviations of the mean. The bound is below $1$ exactly when $k > 1$, and for $k \le 1$ it says nothing. If $\sigma = 0$, then $P(Y = \mu) = 1$ and the deviation event has probability $0$ for every $d > 0$.

Definition An inequality that holds for every distribution in a class is sharp for that class if some distribution in the class attains it with equality. No smaller number can then serve as a bound based on the same information. Markov’s inequality is sharp. For a mean $m \ge 0$ and a threshold $a > 0$ with $a \ge m$, the variable equal to $a$ with probability $m/a$ and to $0$ otherwise is nonnegative, has mean $m$ and has $P(X \ge a) = m/a$. Chebyshev’s inequality is sharp too. For any $\mu$, any $\sigma \ge 0$ and any $d > 0$ with $d \ge \sigma$, put probability $\sigma^2/(2d^2)$ at each of $\mu - d$ and $\mu + d$ and the remaining $1 - \sigma^2/d^2$ at $\mu$. This distribution has mean $\mu$, variance $\sigma^2$ and

When $a < m$ or $d < \sigma$ the ratio exceeds $1$, and the capped value $1$ is attained by the constant $m$ or by the values $\mu \pm \sigma$ with probability $\tfrac12$ each.