Chebyshev's inequality

In probability theory, Chebyshev's inequality (also called the Bienaymé-Chebyshev inequality) provides an upper bound on the probability of deviation of a random variable (with finite variance) from its mean. More specifically, the probability that a random variable deviates from its mean by more than \(k\sigma\) is at most \(1/k^2\), where \(k\) is any positive constant and \(\sigma\) is the standard deviation (the square root of the variance).

The rule is often called Chebyshev's theorem, about the range of standard deviations around the mean, in statistics. The inequality has great utility because it can be applied to any probability distribution in which the mean and variance are defined. For example, it can be used to prove the weak law of large numbers.

Its practical usage is similar to the 68-95-99.7 rule, which applies only to normal distributions. Chebyshev's inequality is more general, stating that a minimum of just 75% of values must lie within two standard deviations of the mean and 88.88% within three standard deviations for a broad range of different probability distributions.

The term Chebyshev's inequality may also refer to Markov's inequality, especially in the context of analysis. They are closely related, and some authors refer to Markov's inequality as "Chebyshev's First Inequality," and the similar one referred to on this page as "Chebyshev's Second Inequality."

Chebyshev's inequality is tight in the sense that for each chosen positive constant, there exists a random variable such that the inequality is in fact an equality.

The theorem is named after Russian mathematician Pafnuty Chebyshev, although it was first formulated by his friend and colleague Irénée-Jules Bienaymé. The theorem was first proved by Bienaymé in 1853 and more generally proved by Chebyshev in 1867. His student Andrey Markov provided another proof in his 1884 Ph.D. thesis.

Let \(X\) (integrable) be a random variable with finite non-zero variance \(\sigma^2\) (and thus finite expected value \(\mu\)). Then for any real number \(k > 0\),

\(\Pr(|X-\mu|\geq k\sigma) \leq \frac{1}{k^2}.\)

Only the case \(k > 1\) is useful. When \(k \leq 1\) the right-hand side \(1/k^2 \geq 1\) and the inequality is trivial as all probabilities are at most 1.

As an example, using \(k = \sqrt{2}\) shows that the probability values lie outside the interval \((\mu - \sqrt{2}\sigma, \mu + \sqrt{2}\sigma)\) does not exceed \(1/2\). Equivalently, it implies that the probability of values lying within the interval (i.e. its "coverage") is at least \(1/2\).

For the general case, for any \(a > 0\),

\(\Pr(|X-\mu|\geq a) \leq \frac{\sigma^2}{a^2}.\)

Because it can be applied to completely arbitrary distributions provided they have a known finite mean and variance, the inequality generally gives a poor bound compared to what might be deduced if more aspects are known about the distribution involved.

Let \((X,\,\Sigma,\,\mu)\) be a measure space, and let \(f\) be an extended real-valued measurable function defined on \(X\). Then for any real number \(t > 0\) and \(0 < p < \infty\),

\(\mu(\{x\in X\,:\,\,|f(x)|\geq t\}) \leq {1\over t^p} \int_{X} |f|^p \, d\mu.\)

More generally, if \(g\) is an extended real-valued measurable function, nonnegative and nondecreasing, with \(g(t) \neq 0\) then:

\(\mu(\{x\in X\,:\,\,f(x)\geq t\}) \leq {1\over g(t)} \int_X g\circ f\, d\mu.\)

This statement follows from the Markov inequality, \(\mu(\{x\in X:|F(x)|\geq \varepsilon\}) \leq\frac1\varepsilon \int_X|F|d\mu\), with \(F=g\circ f\) and \(\varepsilon=g(t)\), since in this case \(\mu(\{x\in X\,:\,\,g\circ f(x)\geq g(t)\}) \geq \mu(\{x\in X\,:\,\,f(x)\geq t\})\). The previous statement then follows by defining \(g(x)\) as \(|x|^p\) if \(x\ge t\) and \(0\) otherwise.

Suppose we randomly select a journal article from a source with an average of 1000 words per article, with a standard deviation of 200 words. We can then infer that the probability that it has between 600 and 1400 words (i.e. within \(k=2\) standard deviations of the mean) must be at least 75%, because there is no more than \(1/k^2 = 1/4\) chance to be outside that range, by Chebyshev's inequality. But if we additionally know that the distribution is normal, we can say there is a 75% chance the word count is between 770 and 1230 (which is an even tighter bound).

As shown in the example above, the theorem typically provides rather loose bounds. However, these bounds cannot in general (remaining true for arbitrary distributions) be improved upon. The bounds are sharp for the following example: for any \(k \geq 1\),

\(X = \begin{cases} -1, & \text{with probability }\;\;\frac{1}{2k^2} \\ \phantom{-}0, & \text{with probability }1 - \frac{1}{k^2} \\ +1, & \text{with probability }\;\;\frac{1}{2k^2} \end{cases}\)

For this distribution, the mean is \(\mu = 0\) and the variance is \(\sigma^2 = \frac{(-1)^2}{2k^2} + 0 + \frac{1^2}{2k^2} = \frac{1}{k^2}\), so the standard deviation is \(\sigma = 1/k\) and

\(\Pr(|X-\mu| \ge k\sigma) = \Pr(|X| \ge 1) = \frac{1}{k^2}.\)

Chebyshev's inequality is an equality for precisely those distributions which are affine transformations of this example.

Markov's inequality states that for any non-negative real-valued random variable \(Y\) and any positive number \(a\), we have \(\Pr(|Y| \geq a) \leq \mathbb{E}[|Y|]/a\). One way to prove Chebyshev's inequality is to apply Markov's inequality to the random variable \(Y = (X - \mu)^2\) with \(a = (k \sigma)^2\):

\(\Pr(|X - \mu| \geq k\sigma) = \Pr((X - \mu)^2 \geq k^2\sigma^2) \leq \frac{\mathbb{E}[(X - \mu)^2]}{k^2\sigma^2} = \frac{\sigma^2}{k^2\sigma^2} = \frac{1}{k^2}.\)

It can also be proved directly using conditional expectation:

\(\begin{aligned} \sigma^2&=\mathbb{E}\bigl[ (X-\mu)^2 \bigr]\\[5pt] &=\mathbb{E}\Bigl[ (X-\mu)^2 \;\Big|\; k\sigma\leq |X-\mu| \Bigr] \Pr\bigl[ k\sigma\leq|X-\mu| \bigr] + \mathbb{E}\Bigl[ (X-\mu)^2 \;\Big|\; k\sigma>|X-\mu| \Bigr] \Pr\bigl[ k\sigma>|X-\mu| \bigr] \\[5pt] &\geq(k\sigma)^2 \Pr\bigl[ k\sigma\leq |X-\mu| \bigr] + 0\cdot\Pr\bigl[ k\sigma>|X-\mu| \bigr] \\[5pt] &=k^2\sigma^2 \Pr\bigl[ k\sigma\leq|X-\mu| \bigr] \end{aligned}\)

Chebyshev's inequality then follows by dividing by \(k^2 \sigma^2\). This proof also shows why the bounds are quite loose in typical cases: the conditional expectation on the event where \(|X - \mu| < k \sigma\) is thrown away, and the lower bound of \(k^2 \sigma^2\) on the event \(|X - \mu| \geq k \sigma\) can be quite poor.

Chebyshev's inequality can also be obtained directly from a simple comparison of areas, starting from the representation of an expected value as the difference of two improper Riemann integrals (at the drawing in the definition of expected value for arbitrary real-valued random variables).

Selberg derived a generalization to arbitrary intervals. Suppose \(X\) is a random variable with mean \(\mu\) and variance \(\sigma^2\). Selberg's inequality states that if \(\beta \geq \alpha \geq 0\),

\(\Pr( X \in [\mu - \alpha, \mu + \beta] ) \ge \begin{cases}\frac{ \alpha^2 }{\alpha^2 + \sigma^2} &\text{if } \alpha(\beta-\alpha) \geq 2\sigma^2 \\ \frac{4\alpha\beta - 4\sigma^2}{(\alpha + \beta)^2} &\text{if } 2\alpha\beta \geq 2\sigma^2 \geq \alpha(\beta - \alpha) \\ 0 & \sigma^2 \geq \alpha\beta\end{cases}\)

When \(\alpha = \beta\), this reduces to Chebyshev's inequality. These are known to be the best possible bounds.

Chebyshev's inequality naturally extends to the multivariate setting, where one has \(n\) random variables \(X_i\) with mean \(\mu_i\) and variance \(\sigma_i^2\). Then the following inequality holds.

\(\Pr\left(\sum_{i=1}^n (X_i - \mu_i)^2 \ge k^2 \sum_{i=1}^n \sigma_i^2 \right) \le \frac{1}{k^2}\)

This is known as the Birnbaum-Raymond-Zuckerman inequality after the authors who proved it for two dimensions. This result can be rewritten in terms of vectors \(X = (X_1, X_2, \ldots)\) with mean \(\mu = (\mu_1, \mu_2, \ldots)\), standard deviation \(\sigma = (\sigma_1, \sigma_2, \ldots)\), in the Euclidean norm \(|| \cdot ||\).

\(\Pr(\| X - \mu \| \ge k \| \sigma \|) \le \frac{ 1 } { k^2 }.\)

One can also get a similar infinite-dimensional Chebyshev's inequality. A second related inequality has also been derived by Chen. Let \(n\) be the dimension of the stochastic vector \(X\) and let \(\operatorname{E}(X)\) be the mean of \(X\). Let \(S\) be the covariance matrix and \(k > 0\). Then

\(\Pr \left( ( X - \operatorname{E}(X) )^T S^{-1} (X - \operatorname{E}(X)) < k \right) \ge 1 - \frac{n}{k}\)

where \(Y^T\) is the transpose of \(Y\). The inequality can be written in terms of the Mahalanobis distance as

\(\Pr \left( d^2_S(X,\operatorname{E}(X)) < k \right) \ge 1 - \frac{n}{k}\)

where the Mahalanobis distance based on \(S\) is defined by

\(d_S(x,y) =\sqrt{ (x -y)^T S^{-1} (x -y) }\)

Navarro proved that these bounds are sharp, that is, they are the best possible bounds for that regions when we just know the mean and the covariance matrix of \(X\).

Stellato et al. showed that this multivariate version of the Chebyshev inequality can be easily derived analytically as a special case of Vandenberghe et al. where the bound is computed by solving a semidefinite program (SDP).

Mitzenmacher and Upfal note that by applying Markov's inequality to the nonnegative variable \(| X - \operatorname{E}(X) |^n\), one can get a family of tail bounds

\(\Pr\left(| X - \operatorname{E}(X) | \ge k \operatorname{E}(|X - \operatorname{E}(X) |^n )^{ \frac{1}{n} }\right) \le \frac{1 } {k^n}, \qquad k >0,\ n \geq 2.\)

For \(n = 2\) we obtain Chebyshev's inequality. For \(k \geq 1,\ n > 4\) and assuming that the \(n\) moment exists, this bound is tighter than Chebyshev's inequality. This strategy, called the method of moments, is often used to prove tail bounds.

A related inequality sometimes known as the exponential Chebyshev's inequality is the inequality

\(\Pr(X \ge \varepsilon) \le e^{ -t \varepsilon }\operatorname{E}\left (e^{ t X } \right), \qquad t > 0.\)

Let \(K(t)\) be the cumulant generating function,

\(K( t ) = \log \left(\operatorname{E}\left( e^{ t x } \right) \right).\)

Taking the Legendre-Fenchel transformation of \(K(t)\) and using the exponential Chebyshev's inequality we have

\(-\log( \Pr (X \ge \varepsilon )) \ge \sup_t( t \varepsilon - K( t ) ).\)

This inequality may be used to obtain exponential inequalities for unbounded variables.

If \(\Pr(x)\) has finite support based on the interval \([a, b]\), let \(M = \max(|a|, |b|)\), where \(|x|\) is the absolute value of \(x\). If the mean of \(\Pr(x)\) is zero then for all \(k > 0\)

\(\frac{\operatorname{E}(|X|^r ) - k^r }{M^r} \le \Pr( | X | \ge k ) \le \frac{\operatorname{E}(| X |^r ) }{ k^r }.\)

The second of these inequalities with \(r = 2\) is the Chebyshev bound. The first provides a lower bound for the value of \(\Pr(x)\).

Saw et al extended Chebyshev's inequality to cases where the population mean and variance are not known and may not exist, but the sample mean and sample standard deviation from \(N\) samples are to be employed to bound the expected value of a new drawing from the same distribution. The following simpler version of this inequality is given by Kabán.

\(\Pr( | X - m | \ge ks ) \le \frac 1 {N + 1} \left\lfloor \frac {N+1} N \left(\frac{N - 1}{k^2} + 1 \right) \right\rfloor\)

where \(X\) is a random variable which we have sampled \(N\) times, \(m\) is the sample mean, \(k\) is a constant and \(s\) is the sample standard deviation.

This inequality holds even when the population moments do not exist, and when the sample is only weakly exchangeably distributed; this criterion is met for randomised sampling. A table of values for the Saw-Yang-Mo inequality for finite sample sizes (\(N < 100\)) has been determined by Konijn. The table allows the calculation of various confidence intervals for the mean, based on multiples, C, of the standard error of the mean as calculated from the sample. For example, Konijn shows that for \(N = 59\), the 95 percent confidence interval for the mean \(m\) is \((m - C s, m + C s)\), where \(C = 4.447 \cdot 1.006 = 4.47\) (this is 2.28 times larger than the value found on the assumption of normality showing the loss on precision resulting from ignorance of the precise nature of the distribution).

An equivalent inequality can be derived in terms of the sample mean instead,

\(\Pr( | X - m | \ge km ) \le \frac{N - 1} N \frac 1 {k^2} \frac{s^2}{m^2} + \frac 1 N.\)

A table of values for the Saw-Yang-Mo inequality for finite sample sizes (\(N < 100\)) has been determined by Konijn.

For fixed \(N\) and large \(m\) the Saw-Yang-Mo inequality is approximately

\(\Pr( | X - m | \ge ks ) \le \frac 1 {N + 1}.\)

Beasley et al have suggested a modification of this inequality

\(\Pr( | X - m | \ge ks ) \le \frac 1 {k^2( N + 1 )}.\)

Condensed: the full section is in Wikipedia.

Stellato et al. simplified the notation and extended the empirical Chebyshev inequality from Saw et al. to the multivariate case. Let \(\xi \in \mathbb{R}^{n_\xi}\) be a random variable and let \(N \in \mathbb{Z}_{\geq n_\xi}\). We draw \(N+1\) iid samples of \(\xi\) denoted as \(\xi^{(1)},\dots,\xi^{(N)},\xi^{(N+1)} \in \mathbb{R}^{n_\xi}\). Based on the first \(N\) samples, we define the empirical mean as \(\mu_N = \frac 1 N \sum_{i=1}^N \xi^{(i)}\) and the unbiased empirical covariance as \(\Sigma_N = \frac 1 N \sum_{i=1}^N (\xi^{(i)} - \mu_{N})(\xi^{(i)} - \mu_N)^\top\). If \(\Sigma_N\) is nonsingular, then for all \(\lambda \in \mathbb{R}_{\geq 0}\) then

\(\begin{aligned} & P^{N+1} \left((\xi^{(N+1)} - \mu_N)^\top \Sigma_N^{-1}(\xi^{(N+1)} - \mu_N) \geq \lambda^2\right) \\[8pt] \leq {} & \min\left\{1, \frac 1 {N+1} \left\lfloor \frac{n_\xi(N+1)(N^2 - 1 + N\lambda^2)}{N^2\lambda^2}\right\rfloor\right\}. \end{aligned}\)