
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
1/k2
k
\sigma
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.[1] [2]
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.[3]
The theorem is named after Russian mathematician Pafnuty Chebyshev, although it was first formulated by his friend and colleague Irénée-Jules Bienaymé.[4] The theorem was first proved by Bienaymé in 1853[5] and more generally proved by Chebyshev in 1867.[6] [7] His student Andrey Markov provided another proof in his 1884 Ph.D. thesis.[8]
Chebyshev's inequality is usually stated for random variables, but can be generalized to a statement about measure spaces.
Let
X
\sigma2
\mu
k>0
\Pr(|X-\mu|\geqk\sigma)\leq
| 1 | |
| k2 |
.
Only the case
k>1
k\leq1
1/k2\geq1
As an example, using
k=\sqrt{2}
(\mu-\sqrt{2}\sigma,\mu+\sqrt{2}\sigma)
1/2
1/2
For the general case, for any
a>0
\Pr(|X-\mu|\geqa)\leq
| \sigma2 | |
| a2 |
.
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.
k | Min. % within k deviations of mean | Max. % beyond k deviations from mean | |
|---|---|---|---|
| 1 | 0% | 100% | |
| 50% | 50% | ||
| 1.5 | 55.55% | 44.44% | |
| 2 | 75% | 25% | |
| 2 | 87.5% | 12.5% | |
| 3 | 88.8888% | 11.1111% | |
| 4 | 93.75% | 6.25% | |
| 5 | 96% | 4% | |
| 6 | 97.2222% | 2.7778% | |
| 7 | 97.9592% | 2.0408% | |
| 8 | 98.4375% | 1.5625% | |
| 9 | 98.7654% | 1.2346% | |
| 10 | 99% | 1% |
Let
(X,\Sigma,\mu)
f
X
t>0
0<p<infty
\mu(\{x\inX:|f(x)|\geqt\})\leq{1\overtp}\intX|f|pd\mu.
More generally, if
g
g(t) ≠ 0
\mu(\{x\inX:f(x)\geqt\})\leq{1\overg(t)}\intXg\circfd\mu.
This statement follows from the Markov inequality,
\mu(\{x\inX:|F(x)|\geq\varepsilon\})\leq
| 1\varepsilon | |
| \int |
X|F|d\mu
F=g\circf
\varepsilon=g(t)
\mu(\{x\inX:g\circf(x)\geqg(t)\})\geq\mu(\{x\inX:f(x)\geqt\})
g(x)
|x|p
x\get
0
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
1/k2=1/4
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\geq1
X=\begin{cases} -1,&with
| 1 | |
| 2k2 |
\\ \phantom{-}0,&withprobability1-
| 1 | |
| k2 |
\\ +1,&with
| 1 | |
| 2k2 |
\end{cases}
For this distribution, the mean is
\mu=0
\sigma2=
| (-1)2 | |
| 2k2 |
+0+
| 12 | |
| 2k2 |
=
| 1 | |
| k2 |
\sigma=1/k
\Pr(|X-\mu|\gek\sigma)=\Pr(|X|\ge1)=
| 1 | |
| k2 |
.
Markov's inequality states that for any non-negative real-valued random variable
Y
a
\Pr(|Y|\geqa)\leqE[|Y|]/a
Y=(X-\mu)2
a=(k\sigma)2
\Pr(|X-\mu|\geqk\sigma)=\Pr((X-\mu)2\geqk2\sigma2)\leq
| E[(X-\mu)2] | |
| k2\sigma2 |
=
| \sigma2 | |
| k2\sigma2 |
=
| 1 | |
| k2 |
.
It can also be proved directly using conditional expectation:
\begin{align} \sigma2&=El[(X-\mu)2r]\\[5pt] &=El[(X-\mu)2 | k\sigma\leq|X-\mu|r]\Prl[k\sigma\leq|X-\mu|r] +El[(X-\mu)2 | k\sigma>|X-\mu|r]\Prl[k\sigma>|X-\mu|r]\\[5pt] &\geq(k\sigma)2\Prl[k\sigma\leq|X-\mu|r]+0 ⋅ \Prl[k\sigma>|X-\mu|r]\\[5pt] &=k2\sigma2\Prl[k\sigma\leq|X-\mu|r] \end{align}
k2\sigma2
|X-\mu|<k\sigma
k2\sigma2
|X-\mu|\geqk\sigma
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).[10]
Several extensions of Chebyshev's inequality have been developed.
Selberg derived a generalization to arbitrary intervals.[11] Suppose
X
\mu
\sigma2
\beta\geq\alpha\geq0
\Pr(X\in[\mu-\alpha,\mu+\beta])\ge\begin{cases}
| \alpha2 | |
| \alpha2+\sigma2 |
&if\alpha(\beta-\alpha)\geq2\sigma2\
| 4\alpha\beta-4\sigma2 | |
| (\alpha+\beta)2 |
&if2\alpha\beta\geq2\sigma2\geq\alpha(\beta-\alpha)\ 0&\sigma2\geq\alpha\beta\end{cases}
When
\alpha=\beta
See main article: Multidimensional Chebyshev's inequality.
Chebyshev's inequality naturally extends to the multivariate setting, where one has
n
Xi
\mui
| 2 | |
| \sigma | |
| i |
| n | |
| \Pr\left(\sum | |
| i=1 |
(Xi-
| 2 | |
| \mu | |
| i) |
\gek2
| n | |
| \sum | |
| i=1 |
| 2 | |
| \sigma | |
| i |
\right)\le
| 1 | |
| k2 |
X=(X1,X2,\ldots)
\mu=(\mu1,\mu2,\ldots)
\sigma=(\sigma1,\sigma2,\ldots)
|| ⋅ ||
\Pr(\|X-\mu\|\gek\|\sigma\|)\le
| 1 | |
| k2 |
.
One can also get a similar infinite-dimensional Chebyshev's inequality. A second related inequality has also been derived by Chen.[16] Let
n
X
\operatorname{E}(X)
X
S
k>0
\Pr\left((X-\operatorname{E}(X))TS-1(X-\operatorname{E}(X))<k\right)\ge1-
| n | |
| k |
where
YT
Y
\Pr\left(
| 2 | |
| d | |
| S(X,\operatorname{E}(X)) |
<k\right)\ge1-
| n | |
| k |
where the Mahalanobis distance based on
S
dS(x,y)=\sqrt{(x-y)TS-1(x-y)}
Navarro[17] 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.[18] showed that this multivariate version of the Chebyshev inequality can be easily derived analytically as a special case of Vandenberghe et al.[19] where the bound is computed by solving a semidefinite program (SDP).
If the variables are independent this inequality can be sharpened.[20]
\Pr\left
| n | |
| (cap | |
| i=1 |
| |Xi-\mui| | |
| \sigmai |
\leki\right)\ge
| n | |
| \prod | |
| i=1 |
\left(1-
| 1 | ||||||
|
\right)
Berge derived an inequality for two correlated variables
X1,X2
\rho
X1
X2
| 2 | |
| \sigma | |
| i |
Xi
\Pr\left(
| 2 | |
| cap | |
| i=1 |
\left[
| |Xi-\mui| | |
| \sigmai |
<k\right]\right)\ge1-
| 1+\sqrt{1-\rho2 | |
| } |
{k2}.
This result can be sharpened to having different bounds for the two random variables[22] and having asymmetric bounds, as in Selberg's inequality.[23]
Olkin and Pratt derived an inequality for
n
| n | |
| \Pr\left(cap | |
| i=1 |
| |Xi-\mui| | |
| \sigmai |
<ki\right)\ge1-
| 1 | |
| n2 |
\left(\sqrt{u}+\sqrt{n-1}\sqrt{n\sumi
| 1 | ||||||||
|
-u}\right)2
where the sum is taken over the
n
u=
| n | |
| \sum | |
| i=1 |
| 1 | ||||||||
|
+
| n | |
| 2\sum | |
| i=1 |
\sumj<i
| \rhoij | |
| kikj |
where
\rhoij
Xi
Xj
Olkin and Pratt's inequality was subsequently generalised by Godwin.[25]
Mitzenmacher and Upfal[26] note that by applying Markov's inequality to the nonnegative variable
|X-\operatorname{E}(X)|n
\Pr\left(|X-\operatorname{E}(X)|\gek\operatorname{E}(|X-\operatorname{E}(X)|n
| ||||||
| ) |
\right)\le
| 1 | |
| kn |
, k>0, n\geq2.
For
n=2
k\geq1, n>4
n
A related inequality sometimes known as the exponential Chebyshev's inequality[27] is the inequality
\Pr(X\ge\varepsilon)\lee\operatorname{E}\left(e\right), t>0.
Let
K(t)
K(t)=log\left(\operatorname{E}\left(e\right)\right).
Taking the LegendreâFenchel transformation of
K(t)
-log(\Pr(X\ge\varepsilon))\ge\supt(t\varepsilon-K(t)).
This inequality may be used to obtain exponential inequalities for unbounded variables.[28]
If
\Pr(x)
[a,b]
M=max(|a|,|b|)
|x|
x
\Pr(x)
k>0
| \operatorname{E | |
| (|X| |
r)-kr}{Mr}\le\Pr(|X|\gek)\le
| \operatorname{E | |
| (| |
X|r)}{kr}.
The second of these inequalities with
r=2
\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
\Pr(|X-m|\geks)\le
| 1 | |
| N+1 |
\left\lfloor
| N+1 | \left( | |
| N |
| N-1 | |
| k2 |
+1\right)\right\rfloor
where
X
N
m
k
s
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
N=59
m
(m-Cs,m+Cs)
C=4.447 ⋅ 1.006=4.47
An equivalent inequality can be derived in terms of the sample mean instead,
\Pr(|X-m|\gekm)\le
| N-1 | |
| N |
| 1 | |
| k2 |
| s2 | |
| m2 |
+
| 1 | |
| N. |
A table of values for the SawâYangâMo inequality for finite sample sizes (
N<100
For fixed
N
m
\Pr(|X-m|\geks)\le
| 1 | |
| N+1 |
.
Beasley et al have suggested a modification of this inequality
\Pr(|X-m|\geks)\le
| 1 | |
| k2(N+1) |
.
In empirical testing this modification is conservative but appears to have low statistical power. Its theoretical basis currently remains unexplored.
The bounds these inequalities give on a finite sample are less tight than those the Chebyshev inequality gives for a distribution. To illustrate this let the sample size
N=100
k=3
For
N=10
For
N=100
For
N=500
For
N=1000
The Chebyshev inequality for the distribution gives 95% and 99% confidence intervals of approximately ±4.472 standard deviations and ±10 standard deviations respectively.
See main article: Samuelson's inequality.
Although Chebyshev's inequality is the best possible bound for an arbitrary distribution, this is not necessarily true for finite samples. Samuelson's inequality states that all values of a sample must lie within
\sqrt{N-1}
By comparison, Chebyshev's inequality states that all but a
1/N
\sqrt{N}
N
\sqrt{N}
An alternative method of obtaining sharper bounds is through the use of semivariances (partial variances). The upper (
| 2 | |
| \sigma | |
| + |
| 2 | |
| \sigma | |
| - |
| 2 | |
| \sigma | |
| + |
=
| \sumx>m(x-m)2 | |
| n-1 |
,
| 2 | |
| \sigma | |
| - |
=
| \sumx<m(m-x)2 | |
| n-1 |
,
where
m
n
The variance of the sample is the sum of the two semivariances:
\sigma2=
| 2 | |
| \sigma | |
| + |
+
| 2. | |
| \sigma | |
| - |
In terms of the lower semivariance Chebyshev's inequality can be written[34]
\Pr(x\lem-a\sigma-)\le
| 1 | |
| a2 |
.
Putting
a=
| k\sigma | |
| \sigma- |
.
Chebyshev's inequality can now be written
\Pr(x\lem-k\sigma)\le
| 1 | |
| k2 |
| |||||||||
| \sigma2 |
.
A similar result can also be derived for the upper semivariance.
If we put
| 2 | |
| \sigma | |
| u |
=
| 2, | |
| max(\sigma | |
| - |
| 2) | |
| \sigma | |
| + |
,
Chebyshev's inequality can be written
\Pr(|x\lem-k\sigma|)\le
| 1 | |
| k2 |
| |||||||||
| \sigma2 |
.
Because
| 2 | |
| \sigma | |
| u |
\leq\sigma2
If the distribution is known to be symmetric, then
| 2 | |
| \sigma | |
| + |
=
| 2 | |
| \sigma | |
| - |
=
| 1 | |
| 2 |
\sigma2
and
\Pr(x\lem-k\sigma)\le
| 1 | |
| 2k2 |
.
This result agrees with that derived using standardised variables.
Stellato et al. simplified the notation and extended the empirical Chebyshev inequality from Saw et al. to the multivariate case. Let be a random variable and let . We draw iid samples of denoted as . Based on the first samples, we define the empirical mean as and the unbiased empirical covariance as . If
\SigmaN
λ\inR\geq
\begin{align} &PN+1\left((\xi(N+1)-
| \top | |
| \mu | |
| N) |
| -1 | |
| \Sigma | |
| N |
(\xi(N+1)-\muN)\geqλ2\right)\\[8pt] \leq{}&min\left\{1,
| 1 | |
| N+1 |
\left\lfloor
| ||||||||||
| N2λ2 |
\right\rfloor\right\}. \end{align}
In the univariate case, i.e. , this inequality corresponds to the one from Saw et al. Moreover, the right-hand side can be simplified by upper bounding the floor function by its argument
PN+1\left((\xi(N+1)-
| \top | |
| \mu | |
| N) |
| -1 | |
| \Sigma | |
| N |
(\xi(N+1)-\muN)\geqλ2\right)\leqmin\left\{1,
| ||||||||||
| N2λ2 |
\right\}.
As , the right-hand side tends to which corresponds to the multivariate Chebyshev inequality over ellipsoids shaped according to and centered in .
Chebyshev's inequality is important because of its applicability to any distribution. As a result of its generality it may not (and usually does not) provide as sharp a bound as alternative methods that can be used if the distribution of the random variable is known. To improve the sharpness of the bounds provided by Chebyshev's inequality a number of methods have been developed; for a review see eg.[12] [37]
Cantelli's inequality[38] due to Francesco Paolo Cantelli states that for a real random variable (
X
\mu
\sigma2
\Pr(X-\mu\gea)\le
| \sigma2 | |
| \sigma2+a2 |
where
a\geq0
This inequality can be used to prove a one tailed variant of Chebyshev's inequality with
k>0
\Pr(X-\mu\geqk\sigma)\leq
| 1 | |
| 1+k2 |
.
The bound on the one tailed variant is known to be sharp. To see this consider the random variable
X
X=1
| \sigma2 | |
| 1+\sigma2 |
X=-\sigma2
| 1 | |
| 1+\sigma2 |
.
Then
\operatorname{E}(X)=0
\operatorname{E}(X2)=\sigma2
\Pr(X<1)=1/(1+\sigma2)
The one-sided variant can be used to prove the proposition that for probability distributions having an expected value and a median, the mean and the median can never differ from each other by more than one standard deviation. To express this in symbols let
\mu
\nu
\sigma
\left|\mu-\nu\right|\leq\sigma.
There is no need to assume that the variance is finite because this inequality is trivially true if the variance is infinite.
The proof is as follows. Setting
k=1
\Pr(X-\mu\geq\sigma)\leq
| 1 | |
| 2 |
\implies\Pr(X\geq\mu+\sigma)\leq
| 1 | |
| 2 |
.
Changing the sign of
X
\mu
\Pr(X\leq\mu-\sigma)\leq
| 1 | |
| 2 |
.
As the median is by definition any real number
m
\Pr(X\leqm)\geq
| 1 | |
| 2 |
and\Pr(X\geqm)\geq
| 1 | |
| 2 |
this implies that the median lies within one standard deviation of the mean. A proof using Jensen's inequality also exists.
Bhattacharyya[40] extended Cantelli's inequality using the third and fourth moments of the distribution.
Let
\mu=0
\sigma2
\gamma=E[X3]/\sigma3
\kappa=E[X4]/\sigma4
If
k2-k\gamma-1>0
\Pr(X>k\sigma)\le
| \kappa-\gamma2-1 | |
| (\kappa-\gamma2-1)(1+k2)+(k2-k\gamma-1) |
.
The necessity of
k2-k\gamma-1>0
k
In the case
E[X3]=0
\Pr(X>k\sigma)\le
| \kappa-1 | |
| \kappa\left(k2+1\right)-2 |
fork>1.
| \kappa-1 | |
| \kappa\left(k2+1\right)-2 |
=
| 1 | - | |
| 2 |
| \kappa(k-1) | |
| 2(\kappa-1) |
+O\left((k-1)2\right)
k
| 1 | - | |
| 2 |
| k-1 | |
| 2 |
+O\left((k-1)2\right)
\kappa>1
wins a factor 2 over Chebyshev's inequality.
See main article: Gauss's inequality.
In 1823 Gauss showed that for a distribution with a unique mode at zero,[41]
\Pr(|X|\gek)\le
| 4\operatorname{E | |
| ( |
X2)}{9k2} if k2\ge
| 4 | |
| 3 |
\operatorname{E}(X2),
\Pr(|X|\gek)\le1-
| k | |
| \sqrt{3 |
\operatorname{E}(X2)} if k2\le
| 4 | |
| 3 |
\operatorname{E}(X2).
See main article: VysochanskijâPetunin inequality.
The VysochanskijâPetunin inequality generalizes Gauss's inequality, which only holds for deviation from the mode of a unimodal distribution, to deviation from the mean, or more generally, any center.[42] If
X
\mu
\sigma2
\Pr(|X-\mu|\gek\sigma)\le
| 4 | |
| 9k2 |
if k\ge\sqrt{8/3}=1.633.
\Pr(|X-\mu|\gek\sigma)\le
| 4 | |
| 3k2 |
-
| 13 | |
if k\le\sqrt{8/3}.
For symmetrical unimodal distributions, the median and the mode are equal, so both the VysochanskijâPetunin inequality and Gauss's inequality apply to the same center. Further, for symmetrical distributions, one-sided bounds can be obtained by noticing that
\Pr(X-\mu\gek\sigma)=\Pr(X-\mu\le-k\sigma)=
| 1 | |
| 2 |
\Pr(|X-\mu|\gek\sigma).
The additional fraction of
4/9
DasGupta has shown that if the distribution is known to be normal[43]
\Pr(|X-\mu|\gek\sigma)\le
| 1 | |
| 3k2 |
.
From DasGupta's inequality it follows that for a normal distribution at least 95% lies within approximately 2.582 standard deviations of the mean. This is less sharp than the true figure (approximately 1.96 standard deviations of the mean).
Several other related inequalities are also known.
See main article: PaleyâZygmund inequality.
The PaleyâZygmund inequality gives a lower bound on tail probabilities, as opposed to Chebyshev's inequality which gives an upper bound.[46] Applying it to the square of a random variable, we get
\Pr(|Z|>\theta\sqrt{E[Z2]})\ge
| (1-\theta2)2E[Z2]2 | |
| E[Z4] |
.
One use of Chebyshev's inequality in applications is to create confidence intervals for variates with an unknown distribution. Haldane noted,[47] using an equation derived by Kendall,[48] that if a variate (
x
\gamma
\kappa
z
z=x-
| \gamma | |
| 6 |
(x2-1)+
| x | |
| 72 |
[2\gamma2(4x2-7)-3\kappa(x2-3)]+ …
This transformation may be useful as an alternative to Chebyshev's inequality or as an adjunct to it for deriving confidence intervals for variates with unknown distributions.
While this transformation may be useful for moderately skewed and/or kurtotic distributions, it performs poorly when the distribution is markedly skewed and/or kurtotic.
For any collection of non-negative independent random variables with expectation 1 [49]
\Pr\left(
| ||||||||||
| n |
-1\ge
| 1 | |
| n |
\right)\le
| 7 | |
| 8 |
.
There is a second (less well known) inequality also named after Chebyshev.[50]
If
f,g:[a,b]\to\R
| 1 | |
| b-a |
| b | |
| \int | |
| a |
f(x)g(x)dx\ge\left[
| 1 | |
| b-a |
| b | |
| \int | |
| a |
f(x)dx\right]\left[
| 1 | |
| b-a |
| b | |
| \int | |
| a |
g(x)dx\right].
If
f
g
This inequality is related to Jensen's inequality,[51] Kantorovich's inequality,[52] the HermiteâHadamard inequality[52] and Walter's conjecture.[53]
There are also a number of other inequalities associated with Chebyshev:
The Environmental Protection Agency has suggested best practices for the use of Chebyshev's inequality for estimating confidence intervals.[54]