Jump to content

Chebyshev's inequality: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
DrMicro (talk | contribs)
DrMicro (talk | contribs)
Line 111: Line 111:


==Chebyshev's Inequality (More General)==
==Chebyshev's Inequality (More General)==

Several extensions of Chebyshev's inequality have been developed.

===A more general form===

A more general version of Chebyshev's Inequality states:
A more general version of Chebyshev's Inequality states:


:<math> \Pr(|X| \ge \varepsilon) \le \frac{\operatorname{E}{X^2}}{\varepsilon^2}</math>
:<math> \Pr( | X | \ge \varepsilon ) \le \frac{ \operatorname{ E }{ X^2 } }{ \varepsilon^2 }</math>


This version can be proved from [[Markov's inequality]]. Also, this version can be used to derive the more specific statement above.
This version can be proved from [[Markov's inequality]]. Also, this version can be used to derive the more specific statement above.


===Exponential Chebyshev's inequality===


A related inequality sometimes known as the exponential Chebyshev's inequality is the inequality
A related inequality sometimes known as the exponential Chebyshev's inequality is the inequality
Line 135: Line 141:
This inequality may be useful in obtaining exponential inequalities for unbounded variables.
This inequality may be useful in obtaining exponential inequalities for unbounded variables.


===Higher moments===


An extension to higher moments is also possible
An extension to higher moments is also possible
Line 142: Line 149:
where ''λ'' > 0 and ''n'' ≥ 2.
where ''λ'' > 0 and ''n'' ≥ 2.


===Asymmetric two sided case===


A asymmetric two sided version of this inequality is also known<ref name=Steliga2010>Steliga K, Szynal D (2010) Int J Pure App Math 58 (2) 137-152</ref>.
A asymmetric two sided version of this inequality is also known<ref name=Steliga2010>Steliga K, Szynal D (2010) Int J Pure App Math 58 (2) 137-152</ref>.
Line 156: Line 164:


where ''σ''<sup>2</sup> is the variance and μ is the [[mean]].
where ''σ''<sup>2</sup> is the variance and μ is the [[mean]].

===Bivariate case===

A version for the bivariate case is also known.<ref name=Ferentinos1982>Ferentinos K (1982) On Tchebycheff type inequalities. Trabajos Estadıst Investigacion Oper 33: 125-132</ref>

Let


==Sharpened bounds==
==Sharpened bounds==

Revision as of 15:29, 23 May 2012

In probability theory, Chebyshev’s inequality (also spelled as Tchebysheff’s inequality) guarantees that in any data sample or 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. 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.

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

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é.[1] The theorem was first stated without proof by Chebyshev in 1874.[2] His student Andrey Markov provided a proof in 1884 in his PhD thesis.[3]

Statement

It can be stated quite generally using measure theory; the statement in the language of probability theory then follows as a particular case, for a space of measure 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,

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

The previous statement then follows by defining g(t) as

and taking |f| instead of f.

Probabilistic statement

Let X be a random variable with finite expected value μ and non-zero variance σ2. Then for any real number k > 0,

Only the case k ≥ 1 provides useful information (when k < 1 the right-hand side is greater than one, so the inequality becomes vacuous, as the probability of any event cannot be greater than one). As an example, using k = 2 shows that at least half of the values lie in the interval (μ2σ, μ + 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 possible if something is known about the distribution involved.

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

As demonstrated in the example above, the theorem will typically provide rather loose bounds. However, the bounds provided by Chebyshev’s inequality cannot, in general (remaining sound for variables of arbitrary distribution), be improved upon. For example, for any k ≥ 1, the following example meets the bounds exactly.

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

Equality holds only for distributions that are a linear transformation of this one.

Variant: One-sided Chebyshev inequality

A one-tailed variant with k > 0, is[4]

The one-sided version of the Chebyshev inequality is called Cantelli's inequality, and is due to Francesco Paolo Cantelli.

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 (i.e., the expected value) and the median can never differ from each other by more than one standard deviation. To express this in mathematical notation, let μ, m, and σ be respectively the mean, the median, and the standard deviation. Then

(There is no need to rely on an assumption that the variance exists, i.e., is finite. Unlike the situation with the expected value, saying the variance exists is equivalent to saying the variance is finite. But 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:

By changing the sign of X and so of μ, we get

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

For a proof using Jensen's inequality see An inequality relating means and medians.

Proof (of the two-sided Chebyshev's inequality)

Measure-theoretic proof

Fix t and let At be defined as At  := {x ∈ X | ƒ(x) ≥ t}, and let 1At be the indicator function of the set At. Then, it is easy to check that, for any x

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

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

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

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

Chebyshev's Inequality (More General)

Several extensions of Chebyshev's inequality have been developed.

A more general form

A more general version of Chebyshev's Inequality states:

This version can be proved from Markov's inequality. Also, this version can be used to derive the more specific statement above.

Exponential Chebyshev's inequality

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

where t > 0.


Let K( x , t ) be the cumulant generating function. In symbols

Taking the Legendre-Frenchel transform of K( x , t ) and using the exponential Chebyshev's inequality we have

This inequality may be useful in obtaining exponential inequalities for unbounded variables.

Higher moments

An extension to higher moments is also possible

where λ > 0 and n ≥ 2.

Asymmetric two sided case

A asymmetric two sided version of this inequality is also known[5].

When the distribution is known to be symmetric

where σ2 is the variance.

When the distribution is asymmetric or is unknown

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

Bivariate case

A version for the bivariate case is also known.[6]

Let

Sharpened bounds

Standardised variables

Sharpened bounds can be derived by first standardising the random variable.[7] Let X be a random variable with finite variance Var( x ). Let Z be the standardised form defined as

Cantelli's lemma is then

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

Equality holds if and only if Z = -k, 0 or k with probabilities 1 / 2 k2, 1 - 1 / k2 and 1 / 2 k2 respectively.[7]

An extension to a two sided inequality is also possible.

Let u, v > 0. Then we have[7]

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

where m is the arithmetic mean of the sample, n+ ( n- ) is the number of elements greater (less) than the mean and the sum is taken over the number of elements greater (less) than the mean respectively.

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

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

Putting

Chebyshev's inequality can now be written

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

Chebyshev's inequality can be written

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

If the distribution is known to be symmetric

and

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

Specific distributions

DasGupta has determined a set of best possible bounds for a normal distribution for this inequality.[9]

Steliga and Szynal have extended these bounds to the Pareto distribution.[5]

See also

References

  1. ^ Donald Knuth, "The Art of Computer Programming", 3rd ed., vol. 1, 1997, p.98
  2. ^ Chebyshev P (1874) Sur les valeurs limites des integrales, J Math Pure Appl 19: 157–160
  3. ^ Markov A (1884) On certain applications of algebraic continued fractions, Ph.D. thesis, St Petersburg
  4. ^ Grimmett and Stirzaker, problem 7.11.9. Several proofs of this result can be found here.
  5. ^ a b Steliga K, Szynal D (2010) Int J Pure App Math 58 (2) 137-152
  6. ^ Ferentinos K (1982) On Tchebycheff type inequalities. Trabajos Estadıst Investigacion Oper 33: 125-132
  7. ^ a b c Ion RA (2001) Ph.D. thesis. Sharp Chebyshev-Type Inequalities. Chapter 4 [full citation needed][clarification needed]
  8. ^ Berck P, Hihn JM (1982) Using the semivariance to estimate safety-first rules. Am J Agric Econ 64: 298-300
  9. ^ DasGupta A (2000) Best constants in Chebyshev inequalities with various applications. Metrika, 51: 185-200

Further reading

  • A. Papoulis (1991), Probability, Random Variables, and Stochastic Processes, 3rd ed. McGraw-Hill. ISBN 0-07-100870-5. pp. 113–114.
  • G. Grimmett and D. Stirzaker (2001), Probability and Random Processes, 3rd ed. Oxford. ISBN 0-19-857222-0. Section 7.3.