 #jsDisabledContent { display:none; } My Account |  Register |  Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

# Chebyshev's inequality

Article Id: WHEBN0000156533
Reproduction Date:

 Title: Chebyshev's inequality Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### Chebyshev's inequality

In probability theory, Chebyshev's inequality (also spelled as Tchebysheff's inequality, Russian: Нера́венство Чебышёва) guarantees that in any probability distribution, "nearly all" values are close to the mean — the precise statement being that no more than 1/k2 of the distribution's values can be more than k standard deviations away from the mean (or equivalently, at least 1−1/k2 of the distribution's values are within k standard deviations of the mean). 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 completely arbitrary distributions (unknown except for mean and variance). For example, it can be used to prove the weak law of large numbers.

In practical usage, in contrast to the 68-95-99.7% rule, which applies to normal distributions, under Chebyshev's inequality a minimum of just 75% of values must lie within two standard deviations of the mean and 89% within three standard deviations.

The term Chebyshev's inequality may also refer to Markov's inequality, especially in the context of analysis.

## Contents

• History 1
• Statement 2
• Probabilistic statement 2.1
• Measure-theoretic statement 2.2
• Example 3
• Sharpness of bounds 4
• Proof (of the two-sided version) 5
• Probabilistic proof 5.1
• Measure-theoretic proof 5.2
• Extensions 6
• Asymmetric two-sided case 6.1
• Bivariate case 6.2
• Two correlated variables 6.3
• Multivariate case 6.4
• Vector version 6.5
• Infinite Dimensions 6.6
• Higher moments 6.7
• Exponential version 6.8
• Inequalities for bounded variables 6.9
• Finite samples 7
• Dependence of sample size 7.1
• Samuelson's inequality 8
• Sharpened bounds 9
• Standardised variables 9.1
• Semivariances 9.2
• Selberg's inequality 9.3
• Cantelli's inequality 9.4
• Bhattacharyya's inequality 9.5
• Mitzenmacher and Upfal's inequality 9.6
• Related inequalities 10
• Zelen's inequality 10.1
• He, Zhang and Zhang's inequality 10.2
• Hoeffding's lemma 10.3
• Van Zuijlen's bound 10.4
• Unimodal distributions 11
• Unimodal symmetrical distributions 11.1
• Notes 11.2
• Bounds for specific distributions 12
• Zero means 13
• Unit variance 13.1
• Integral Chebyshev inequality 14
• Other inequalities 14.1
• Haldane's transformation 15
• Chernoff bounds 16
• Notes 17
• See also 18
• References 19
• Further reading 20
• External links 21

## History

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

## Statement

Chebyshev's inequality is usually stated for random variables, but can be generalized to a statement about measure spaces.

### Probabilistic statement

Let X (integrable) be a random variable with finite expected value μ and finite non-zero variance σ2. 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 ≤ 1 the right hand : \frac{1}{k^2} \geq 1. and the inequality is trivial as all probabilities are ≤ 1.

As an example, using k = 2 shows that the probability that values lie outside the interval (μ2σ, μ + 2σ) does not exceed 1/2.

Because it can be applied to completely arbitrary distributions (unknown except for 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 standard
deviations of mean
Max % beyond k standard
deviations from mean
1 0% 100%
2 50% 50%
1.5 55.56% 44.44%
2 75% 25%
3 88.8889% 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%

### Measure-theoretic statement

Let (X, Σ, μ) 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 < ∞,

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

More generally, if g is an extended real-valued measurable function, nonnegative and nondecreasing on the range of f, then

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

The previous statement then follows by defining g(t) as t^2 if t\ge 0 and 0 otherwise, and taking |f| instead of f.

## Example

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 SDs of the mean) must be more than 75%, because there is less than 1k2
= 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 that is a 75% chance the word count is between 770 and 1230 (which is an even tighter bound).

## Sharpness of bounds

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 ≥ 1,

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

For this distribution, mean μ = 0 and standard deviation σ = 1/k, so

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

Chebyshev's inequality is an equality for precisely those distributions that are a linear transformation of this example.

## Proof (of the two-sided version)

### Probabilistic proof

Markov's inequality states that for any real-valued random variable Y and any positive number a, we have Pr(|Y| > a) ≤ E(|Y|)/a. One way to prove Chebyshev's inequality is to apply Markov's inequality to the random variable Y = (Xμ)2 with a = (σk)2.

It can also be proved directly. For any event A, let IA be the indicator random variable of A, i.e. IA equals 1 if A occurs and 0 otherwise. Then

\begin{align} \Pr(|X-\mu| \geq k\sigma) &= \operatorname{E} \left (I_{|X-\mu| \geq k\sigma} \right ) \\ &= \operatorname{E} \left (I_{\left (\frac{X-\mu}{k\sigma} \right )^2 \geq 1} \right ) \\[6pt] &\leq \operatorname{E}\left(\left({X-\mu \over k\sigma} \right)^2 \right) \\[6pt] &= {1 \over k^2} {\operatorname{E}((X-\mu)^2) \over \sigma^2} \\ &= {1 \over k^2}. \end{align}

The direct proof shows why the bounds are quite loose in typical cases: the number 1 to the right of "≥" is replaced by [(X − μ)/(kσ)]2 to the left of "≥" whenever the latter exceeds 1. In some cases it exceeds 1 by a very wide margin.

### Measure-theoretic proof

Fix t and let A_t be defined as A_t = \{x\in X\mid f(x)\ge t\}, and let 1_{A_t} be the indicator function of the set A_t. Then, it is easy to check that, for any x,

0\leq g(t) 1_{A_t}\leq g(f(x))\,1_{A_t},

since g is nondecreasing on the range of f, and therefore,

\begin{align}g(t)\mu(A_t)&=\int_X g(t)1_{A_t}\,d\mu\\ &\leq\int_{A_t} g\circ f\,d\mu\\ &\leq\int_X g\circ f\,d\mu.\end{align}

The desired inequality follows from dividing the above inequality by g(t).

## Extensions

Several extensions of Chebyshev's inequality have been developed.

### Asymmetric two-sided case

An asymmetric two-sided version of this inequality is also known.

When the distribution is known to be symmetric for any k_1 + k_2 = 0

\Pr( k_1 < X < k_2) \ge 1 - \frac{ 4 \sigma^2 }{ ( k_2 - k_1 )^2 }

where σ2 is the variance.

Similarly when the distribution is asymmetric or is unknown and k_1 + k_2 = 2 \mu

\Pr( k_1 < X < k_2 ) \ge \frac{ 4 [ ( \mu - k_1 )( k_2 - \mu ) - \sigma^2 ] }{ ( k_2 - k_1 )^2 },

where σ2 is the variance and μ is the mean.

### Bivariate case

A version for the bivariate case is known.

Let X1, X2 be two random variables with means μ1, μ2 and finite variances σ1, σ2 respectively. Then

\Pr( k_{ 11 } \le X_1 \le k_{ 12 }, k_{ 21 } \le X_2 \le k_{ 22 }) \ge 1 - \sum T_i

where for i = 1, 2,

T_i = \frac{ 4 \sigma_i^2 + [ 2 \mu_i - ( k_{ i1 } + k_{ i2 } ) ]^2 } { ( k_{ i2 } - k_{ i1 } )^2 }.

### Two correlated variables

Berge derived an inequality for two correlated variables X1, X2. Let ρ be the correlation coefficient between X1 and X2 and let σi2 be the variance of Xi. Then

\Pr\left( \bigcap_{ i = 1}^2 \left[ \frac{ | X_i - \mu_i | } { \sigma_i } < k \right] \right) \ge 1 - \frac{ 1 + \sqrt{ 1 - \rho^2 } } { k^2 }.

Lal later obtained an alternative bound

\Pr\left( \bigcap_{i=1}^2 \left[ \frac{|X_i - \mu_i|}{\sigma_i} \le k_i \right] \right) \ge 1 - \frac{k_1^2 + k_2^2 + \sqrt{ ( k_1^2 + k_2^2 )^2 - 4 k_1^2 k_2^2 \rho}}{2( k_1 k_2)^2}

Isii derived a further generalisation. Let

Z = \Pr\left(\left (-k_1 < X_1 < k_2 \right) \cap \left(-k_1 < X_2 < k_2 \right) \right), \qquad 0 < k_1 \leq k_2.

and define:

\lambda = \frac{ k_1( 1 + \rho ) + \sqrt{ ( 1 - \rho^2 )( k_1^2 + \rho ) } }{ 2k_1 - 1 + \rho }

There are now three cases.

• Case A: If 2k_1^2 > 1 - \rho and k_2 - k_1 \ge 2 \lambda then
Z \le \frac{ 2 \lambda^2 } { 2 \lambda^2 + 1 + \rho }.
• Case B: If the conditions in case A are not met but k1k2 ≥ 1 and
2 ( k_1 k_2 - 1 )^2 \ge 2( 1 - \rho^2 ) + ( 1 - \rho )( k_2 - k_1 )^2
then
Z \le \frac{ ( k_2 - k_1 )^2 + 4 + \sqrt{ 16 ( 1 - \rho^2 ) + 8 ( 1 - \rho )( k_2 - k_1 ) } }{ ( k_1 +k_2 )^2 }.
• Case C: If none of the conditions in cases A or B are satisfied then there is no universal bound other than 1.

### Multivariate case

The general case is known as the Birnbaum–Raymond–Zuckerman inequality after the authors who proved it for two dimensions.

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

where Xi is the i-th random variable, μi is the i-th mean and σi2 is the i-th variance.

If the variables are independent this inequality can be sharpened.

\Pr\left (\bigcap_{i = 1}^n \frac{|X_i - \mu_i|}{\sigma_i} \le k_i \right ) \ge \prod \left (1 - \frac{1}{k_i^2} \right)

Olkin and Pratt derived an inequality for n correlated variables.

\Pr\left(\bigcap_{i = 1 }^n \frac{|X_i - \mu_i|}{\sigma_i} < k_i \right) \ge 1 - \frac{1}{n^2} \left(\sqrt{U} + \sqrt{n-1} \sqrt{n \sum_i{\frac{1}{ k_i^2} - u}} \right)^2

where the sum is taken over the n variables and

u = \sum_{i=1}^n \frac{1}{ k_i^2} + 2\sum_{i=1}^n \sum_{j

where ρij is the correlation between Xi and Xj.

Olkin and Pratt's inequality was subsequently generalised by Godwin.

### Vector version

Ferentinos has shown that for a vector X = (x1, x2, ...) with mean μ = (μ1, μ2, ...), variance σ2 = (σ12, σ22, ...) and an arbitrary norm || ⋅ || that

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

A second related inequality has also been derived by Chen. Let N be the dimension of the stochastic vector X and let 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 YT is the transpose of Y.

### Infinite Dimensions

There is a straightforward extension of the vector version of Chebyshev's inequality to infinite dimensional settings. Let X be a random variable which takes values in a Fréchet space \mathcal X (equipped with seminorms || ⋅ ||α). This includes most common settings of vector-valued random variables, e.g., when \mathcal X is a Banach space (equipped with a single norm), a Hilbert space, or the finite-dimensional setting as described above.

Suppose that X is of "strong order two", meaning that

\operatorname{E}\left(\| X\|_\alpha^2 \right) < \infty

for every seminorm || ⋅ ||α. This is a generalization of the requirement that X have finite variance, and is necessary for this strong form of Chebyshev's inequality in infinite dimensions. The terminology "strong order two" is due to Vakhania.

Let \mu \in \mathcal X be the Pettis integral of X (i.e., the vector generalization of the mean), and let

\sigma_a := \sqrt{\operatorname{E}\|X - \mu\|_\alpha^2}

be the standard deviation with respect to the seminorm || ⋅ ||α. In this setting we can state the following:

General Version of Chebyshev's Inequality. \forall k > 0: \quad \Pr\left( \|X - \mu\|_\alpha \ge k \sigma_\alpha \right) \le \frac{1}{ k^2 }.

Proof. The proof is straightforward, and essentially the same as the finitary version. If σα = 0, then X is constant (and equal to μ) almost surely, so the inequality is trivial.

If

\|X - \mu\|_\alpha \ge k \sigma_\alpha^2

then ||Xμ||α > 0, so we may safely divide by ||Xμ||α. The crucial trick in Chebyshev's inequality is to recognize that 1 = \tfrac{\|X - \mu\|_\alpha^2}{\|X - \mu\|_\alpha^2}.

The following calculations complete the proof:

\begin{align} \Pr\left( \|X - \mu\|_\alpha \ge k \sigma_\alpha \right) &= \int_\Omega \mathbf{1}_{\|X - \mu\|_\alpha \ge k \sigma_\alpha} \, \mathrm d\Pr \\ & = \int_\Omega \left ( \frac{\|X - \mu\|_\alpha^2}{\|X - \mu\|_\alpha^2} \right ) \cdot \mathbf{1}_{\|X - \mu\|_\alpha \ge k \sigma_\alpha} \, \mathrm d\Pr \\ &\le \int_\Omega \left (\frac{\|X - \mu\|_\alpha^2}{(k\sigma_\alpha)^2} \right ) \cdot \mathbf{1}_{\|X - \mu\|_\alpha \ge k \sigma_\alpha} \, \mathrm d\Pr \\ &\le \frac{1}{k^2 \sigma_\alpha^2} \int_\Omega \|X - \mu\|_\alpha^2 \, \mathrm d\Pr && \mathbf{1}_{\|X - \mu\|_\alpha \ge k \sigma_\alpha} \le 1\\ &= \frac{1}{k^2 \sigma_\alpha^2} \left (\operatorname{E}\|X - \mu\|_\alpha^2 \right )\\ &= \frac{1}{k^2 \sigma_\alpha^2} \left (\sigma_\alpha^2 \right )\\ &= \frac{1}{k^2} \end{align}

### Higher moments

An extension to higher moments is also possible:

\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.

### Exponential version

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(x, t) be the cumulant generating function,

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

Taking the Legendre–Fenchel transformation of K(x, t) and using the exponential Chebyshev's inequality we have

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

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

### Inequalities for bounded variables

If P(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 P(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 P(x).

Sharp bounds for a bounded variate have been derived by Niemitalo

Let 0 ≤ XM where M > 0. Then

• Case 1:
\Pr(X k \quad \text{and} \quad \operatorname{E}(X^2) < k\operatorname{E}(X) + M\operatorname{E}(X) - kM
• Case 2:
\Pr(X k \quad \text{and} \quad E( X^2 )\ge k\operatorname{E}(X) + M\operatorname{E}(X) - kM \\ \qquad \qquad \qquad \text{or} \\ \operatorname{E}(X) \le k \quad \text{and} \quad \operatorname{E}(X^2)\ge k\operatorname{E}(X) \end{cases}
• Case 3:
\Pr(X

## Finite samples

Saw et al extended Chebyshev's inequality to cases where the population mean and variance are not known and may not exist, but you want to use the sample mean and sample standard deviation from N samples to bound the expected value of a new drawing from the same distribution.

P( | X - m | \ge ks ) \le \frac{ g_{ N + 1 }\left( \frac{ N k^2 }{ N - 1 + k^2 } \right) }{ N + 1 } \left( \frac{ N }{ N + 1 } \right)^{ 1 / 2 }

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. g(x) is defined as follows:

Let x ≥ 1, Q = N + 1, and R be the greatest integer less than Q / x. Let

a^ 2 = \frac{ Q( Q - R ) } { 1 + R( Q - R ) }.

Now

g_Q(x) = R \quad \text{if }R \text{ is even}
g_Q(x) = R \quad \text{if }R \text{ is odd and }x < a^2
g_Q(x) = R - 1 \quad \text{if } R \text{ is odd and } x \ge a^2.

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 per cent confidence interval for the mean m is (m - Cs, m + Cs) where C = 4.447 x 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).

Kabán gives a somewhat less complex version of this inequality.

P( | X - m | \ge ks ) \le \frac{ 1 }{ [ N( N + 1 ) ]^{ 1 / 2 } }\left[ \left( \frac{ N - 1 }{ k^2 } + 1 \right) \right]

If the standard deviation is a multiple of the mean then a further inequality can be derived,

P( | X - m | \ge ks ) \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

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

Beasley et al have suggested a modification of this inequality

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

In empirical testing this modification is conservative but appears to have low statistical power. Its theoretical basis currently remains unexplored.

### Dependence of sample size

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 and let k = 3. Chebyshev's inequality states that at most approximately 11.11% of the distribution will lie outside these limits. Kabán's version of the inequality for a finite sample states that at most approximately 12.05% of the sample lies outside these limits. The dependence of the confidence intervals on sample size is further illustrated below.

For N = 10, the 95% confidence interval is approximately ±13.5789 standard deviations.

For N = 100 the 95% confidence interval is approximately ±4.9595 standard deviations; the 99% confidence interval is approximately ±140.0 standard deviations.

For N = 500 the 95% confidence interval is approximately ±4.5574 standard deviations; the 99% confidence interval is approximately ±11.1620 standard deviations.

For N = 1000 the 95% and 99% confidence intervals are approximately ±4.5141 and approximately ±10.5330 standard deviations respectively.

The Chebyshev inequality for the distribution gives 95% and 99% confidence intervals of approximately ±4.472 standard deviations and ±10 standard deviations respectively.

## 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 will lie within √(N − 1) standard deviations of the mean. Chebyshev's bound improves as the sample size increases.

When N = 10, Samuelson's inequality states that all members of the sample lie within 3 standard deviations of the mean: in contrast Chebyshev's states that 99.5% of the sample lies within 13.5789 standard deviations of the mean.

When N = 100, Samuelson's inequality states that all members of the sample lie within approximately 9.9499 standard deviations of the mean: Chebyshev's states that 99% of the sample lies within 10 standard deviations of the mean.

When N = 500, Samuelson's inequality states that all members of the sample lie within approximately 22.3383 standard deviations of the mean: Chebyshev's states that 99% of the sample lies within 10 standard deviations of the mean.

## Sharpened bounds

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.

### Standardised variables

Sharpened bounds can be derived by first standardising the random variable.

Let X be a random variable with finite variance Var(x). Let Z be the standardised form defined as

Z = \frac {X - \operatorname{E}(X) } { \operatorname{Var}(X)^{ 1/2 } }.

Cantelli's lemma is then

P(Z \ge k) \le \frac{ 1 } { 1 + k^2 }.

This inequality is sharp and is attained by k and −1/k with probability 1/(1 + k2) and k2/(1 + k2) respectively.

If k > 1 and the distribution of X is symmetric then we have

P(Z \ge k) \le \frac { 1 } { 2 k^2 } .

Equality holds if and only if Z = −k, 0 or k with probabilities 1 / 2 k2, 1 − 1 / k2 and 1 / 2 k2 respectively. An extension to a two-sided inequality is also possible.

Let u, v > 0. Then we have

P(Z \le -u \text{ or } Z \ge v) \le \frac{ 4 + (u - v)^2 } { (u + v)^2 } .

### Semivariances

An alternative method of obtaining sharper bounds is through the use of semivariances (partial moments). The upper (σ+2) and lower (σ2) semivariances are defined

\sigma_+^2 = \frac { \sum (x - m)^2 } { n - 1 }
\sigma_-^2 = \frac { \sum (m - x)^2 } { n - 1 }

where m is the arithmetic mean of the sample, n is the number of elements in the sample and the sum for the upper (lower) semivariance is taken over the elements greater (less) than the mean.

The variance of the sample is the sum of the two semivariances

\sigma^2 = \sigma_+^2 + \sigma_-^2.

In terms of the lower semivariance Chebyshev's inequality can be written

\Pr(x \le m - a \sigma_-) \le \frac { 1 } { a^2 }.

Putting

a = \frac{ k \sigma } { \sigma_- }.

Chebyshev's inequality can now be written

\Pr(x \le m - k \sigma) \le \frac { 1 } { k^2 } \frac { \sigma_-^2 } { \sigma^2 }.

A similar result can also be derived for the upper semivariance.

If we put

\sigma_u^2 = \max(\sigma_-^2, \sigma_+^2) ,

Chebyshev's inequality can be written

\Pr(| x \le m - k \sigma |) \le \frac { 1 } { k^2 } \frac { \sigma_u^2 } { \sigma^2 } .

Because σu2σ2, use of the semivariance sharpens the original inequality.

If the distribution is known to be symmetric, then

\sigma_+^2 = \sigma_-^2 = \frac{ 1 } { 2 } \sigma^2

and

\Pr(x \le m - k \sigma) \le \frac { 1 } { 2 k^2 } .

This result agrees with that derived using standardised variables.

Note
The inequality with the lower semivariance has been found to be of use in estimating downside risk in finance and agriculture.

### Selberg's inequality

Selberg derived an inequality for P(x) when axb. To simplify the notation let

Y = \alpha X + \beta

where

\alpha = \frac{ 2 k }{ b - a }

and

\beta = \frac{ - ( b + a ) k }{ b - a }.

The result of this linear transformation is to make P(aXb) equal to P(|Y| ≤ k).

The mean (μX) and variance (σX) of X are related to the mean (μY) and variance (σY) of Y:

\mu_Y = \alpha \mu_X + \beta
\sigma_Y^2 = \alpha^2 \sigma_X^2.

With this notation Selberg's inequality states that

P( | Y | < k ) \ge \frac{ ( k - \mu_Y )^ 2 }{ ( k - \mu_Y )^2 + \sigma_Y^2 } \quad\text{ if }\quad \sigma_Y^2 \le \mu_Y ( k - \mu_Y )
P( | Y | < k ) \ge 1 - \frac{ \sigma_Y^2 + \mu_Y^2 }{ k^2 } \quad\text{ if }\quad \mu_Y ( k - \mu_Y ) \le \sigma_Y^2 \le k^2 - \mu_Y^2
P( | Y | < k ) \ge 0 \quad\text{ if }\quad k^2 - \mu_Y^2 \le \sigma_Y^2.

These are known to be the best possible bounds.

### Cantelli's inequality

Cantelli's inequality due to Francesco Paolo Cantelli states that for a real random variable (X) with mean (μ) and variance (σ2)

P(X - \mu \ge a) \le \frac{\sigma^2}{ \sigma^2 + a^2 }

where a ≥ 0.

This inequality can be used to prove a one tailed variant of Chebyshev's inequality with k > 0

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

The bound on the one tailed variant is known to be sharp. To see this consider the random variable X that takes the values

X = 1 with probability \frac{ \sigma^2 } { 1 + \sigma^2 }
X = - \sigma^2 with probability \frac{ 1 } { 1 + \sigma^2 }.

Then E(X) = 0 and E(X2) = σ2 and P(X < 1) = 1 / (1 + σ2).

An application – distance between the mean and the median

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 μ, ν, and σ be respectively the mean, the median, and the standard deviation. Then

\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 in the statement for the one-sided inequality gives:

\Pr(X - \mu \geq \sigma) \leq \frac{ 1 }{ 2 } \implies \Pr(X \geq \mu + \sigma) \leq \frac{ 1 }{ 2 }.

Changing the sign of X and of μ, we get

\Pr(X \leq \mu - \sigma) \leq \frac{ 1 }{ 2 }.

Thus the median is within one standard deviation of the mean.

A proof using Jensen's inequality also exists.

### Bhattacharyya's inequality

Bhattacharyya extended Cantelli's inequality using the third and fourth moments of the distribution.

Let μ = 0 and σ2 be the variance. Let γ = E(X3) / σ3 and κ = E(X4) / σ4.

If k2kγ − 1 > 0 then

P(X > k\sigma) \le \frac{ \kappa - \gamma^2 - 1 }{ (\kappa - \gamma^2 - 1) (1 + k^2) + (k^2 - k\gamma - 1) }.

The necessity of k2kγ − 1 > 0 requires that k be reasonably large.

### Mitzenmacher and Upfal's inequality

Mitzenmacher and Upfal note that

( X - \operatorname{E}[ X ] )^{ 2k } > 0

for any real k > 0 and that

\operatorname{E}[ ( X - \operatorname{E}( X ) )^{ 2k } ]

is the 2kth central moment. They then show that for t > 0

\Pr\left( | X - \operatorname{E}[ X ] | > t \operatorname{E}[ ( X - \operatorname{E}[ X ] )^{ 2k } ]^{ 1 / 2k } \right) \le \frac{ 1 }{ t^{ 2k } } .

For k = 1 we obtain Chebyshev's inequality. For t ≥ 1, k > 2 and assuming that the kth moment exists, this bound is tighter than Chebyshev's inequality.

## Related inequalities

Several other related inequalities are also known.

### Zelen's inequality

Zelen has shown that

\Pr( X - \mu \ge k \sigma ) \le \left[1 + k^2 + \frac{\left( k^2 - k \theta_3 - 1 \right)^2}{\theta_4 - \theta_3^2 - 1} \right]^{-1}

with

k \ge \frac{\theta_3 + \sqrt{\theta_3^2 + 4}}{ 2 }, \qquad \theta_m = \frac{ M_m }{ \sigma_m }

where Mm is the m-th moment and σ is the standard deviation.

### He, Zhang and Zhang's inequality

For any collection of n non-negative independent random variables Xi with expectation 1 

\Pr\left ( \frac{\sum_{i=1}^n X_i }{n} - 1 \ge \frac{1}{n} \right) \le \frac{ 7 }{ 8 }.

### Hoeffding's lemma

Let X be a random variable with aXb and E[X] = 0, then for any s > 0, we have

E \left[ e^{ sX } \right ] \le e^{ \frac{1}{8}s^2 ( b - a )^2 }.

### Van Zuijlen's bound

Let Xi be a set of independent Rademacher random variables: Pr(Xi = 1) = Pr(Xi = −1) = 0.5. Then

\Pr \left( \left | \frac{\sum_{i=1}^n X_i} {\sqrt n} \right| \le 1 \right ) \ge 0.5.

The bound is sharp and better than that which can be derived from the normal distribution (approximately Pr > 0.31).

## Unimodal distributions

A distribution function F is unimodal at ν if its cumulative distribution function is convex on (−∞, ν) and concave on (ν,∞) An empirical distribution can be tested for unimodality with the dip test.

In 1823 Gauss showed that for a unimodal distribution with a mode of zero

P( | X | \ge k ) \le \frac{ 4 \operatorname{ E }( X^2 ) } { 9k^2 } \quad\text{if} \quad k^2 \ge \frac{ 4 } { 3 } \operatorname{E} (X^2),
P( | X | \ge k ) \le 1 - \frac{ k^2 } { 3 \operatorname{ E }( X^2 ) } \quad \text{if} \quad k^2 \le \frac{ 4 } { 3 } \operatorname{ E }( X^2 ).

If the second condition holds then the second bound is always less than or equal to the first.

If the mode (ν) is not zero and the mean (μ) and standard deviation (σ) are both finite then denoting the root mean square deviation from the mode by ω, we have

\sigma \le \omega \le 2 \sigma,

and

| \nu - \mu | \le \sqrt{ \frac{ 3 }{ 4 } } \omega.

Winkler in 1866 extended Gauss' inequality to rth moments  where r > 0 and the distribution is unimodal with a mode of zero:

P( | X | \ge k ) \le \left( \frac{ r } { r + 1 } \right)^r \frac{ \operatorname{ E }( | X | )^r } { k^r } \quad \text{if} \quad k^r \ge \frac{ r^r } { ( r + 1 )^{ r + 1 } } \operatorname{ E }( | X |^r ),
P( | X | \ge k) \le \left( 1 - \left[ \frac{ k^r }{ ( r + 1 ) \operatorname{ E }( | X | )^r } \right]^{ 1 / r } \right) \quad \text{if} \quad k^r \le \frac{ r^r } { ( r + 1 )^{ r + 1 } } \operatorname{ E }( | X |^r ).

Gauss' bound has been subsequently sharpened and extended to apply to departures from the mean rather than the mode due to the Vysochanskiï–Petunin inequality.

The Vysochanskiï–Petunin inequality has been extended by Dharmadhikari and Joag-Dev

P( | X | > k ) \le \max\left( \left[ \frac{ r }{( r + 1 ) k } \right]^r E| X^r |, \frac{ s }{( s - 1 ) k^r } E| X^r | - \frac{ 1 }{ s - 1 } \right)

where s is a constant satisfying both s > r + 1 and s(s − r − 1) = rr and r > 0.

It can be shown that these inequalities are the best possible and that further sharpening of the bounds requires that additional restrictions be placed on the distributions.

### Unimodal symmetrical distributions

The bounds on this inequality can also be sharpened if the distribution is both unimodal and symmetrical. An empirical distribution can be tested for symmetry with a number of tests including McWilliam's R*. It is known that the variance of a unimodal symmetrical distribution with finite support [ab] is less than or equal to ( b − a )2 / 12.

Let the distribution be supported on the finite interval [ −NN ] and the variance be finite. Let the mode of the distribution be zero and rescale the variance to 1. Let k > 0 and assume k < 2N/3. Then

P( X \ge k ) \le \frac{ 1 }{ 2 } - \frac{ k }{ 2 \sqrt{ 3 } } \quad \text{if} \quad 0 \le k \le \frac{ 2 }{ \sqrt{ 3 } },
P( X \ge k ) \le \frac{ 2 }{ 9k^2 } \quad \text{if} \quad \frac{ 2 }{ \sqrt{ 3 } } \le k \le \frac{ 2N }{ 3 }.

If 0 < k ≤ 2 / √3 the bounds are reached with the density

f( x ) = \frac{ 1 }{ 2 \sqrt{ 3 } } \quad \text{if} \quad | x | < \sqrt{ 3 }
f( x ) = 0 \quad \text{if} \quad | x | \ge \sqrt{ 3 }.

If 2 / √3 < k ≤ 2N / 3 the bounds are attained by the distribution

( 1 - \beta_k ) \delta_0 ( x ) + \beta_k f_k( x ),

where βk = 4 / 3k2, δ0 is the Dirac delta function and where

f_k( x ) = \frac{ 1 }{ 3k } \quad \text{if} \quad | x | < \frac{ 3k }{ 2 },
f_k( x ) = 0 \quad \text{if} \quad | x | \ge \frac{ 3k }{ 2 }.

The existence of these densities shows that the bounds are optimal. Since N is arbitrary these bounds apply to any value of N.

The Camp–Meidell's inequality is a related inequality. For an absolutely continuous unimodal and symmetrical distribution

P( | X - \mu | \ge k \sigma ) \le 1 - \frac{ k }{ \sqrt{ 3 } } \quad \text{if} \quad k \le \frac{ 2 }{ \sqrt { 3 } }
P( | X - \mu | \ge k \sigma ) \le \frac{ 4 }{ 9k^2 } \quad \text{if} \quad k > \frac{ 2 }{ \sqrt { 3 } }

The second of these inequality is the same as the Vysochanskiï–Petunin inequality.

DasGupta has shown that if the distribution is known to be normal

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

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.