Chebyshev’s Inequality/Theorem
- guarantees that, for a wide class of probability distributions, no more than a certain fraction of values can be more than a certain distance from the mean. Specifically, no more than 1/𝑘2 of the distribution’s values can be more than 𝑘 standard deviations away from the mean (or equivalently, at least 1 − 1/𝑘2 of the distribution’s values are within k standard deviations of the mean)
- In practical usage, in contrast to the 68–95–99.7 rule, which applies to normal distributions, Chebyshev’s inequality is weaker, stating that a minimum of just 75% of values must lie within two standard deviations of the mean and 89% within three standard deviations
Theorem Statement #1
Any random variable 𝑋 with expectation 𝜇 = 𝐄(𝑋) and variance 𝜎2= 𝑉𝑎𝑟(𝑋) outputs a value OUTSIDE the interval [𝜇−𝜀, 𝜇+𝜀] with probability of at MOST (𝜎/𝜀)2, that is
- 𝑷(|𝑋 - 𝜇| > 𝜀) ≤ (𝜎/𝜀)2
-
derivation
- 𝑷(|𝑋 - 𝜇| > 𝜀) = 𝑷((𝑋 - 𝜇)2 > 𝜀2)
- 𝑷(|𝑋 - 𝜇| > 𝜀) ≤ 𝐄[(𝑋 - 𝜇)2] / 𝜀2 # Because of Markov’s Inequality
- 𝑷(|𝑋 - 𝜇| > 𝜀) ≤ 𝜎2 / 𝜀2
Any random variable 𝑋 with expectation 𝜇 = 𝐄(𝑋) and variance 𝜎2= 𝑉𝑎𝑟(𝑋) outputs a value WITHIN the interval [𝜇−𝜀, 𝜇+𝜀] with probability of at LEAST 1 − (𝜎/𝜀)2, that is
- 𝑷(|𝑋 - 𝜇| ≤ 𝜀) ≥ 1 - (𝜎/𝜀)2
Theorem Statement #2
Any random variable 𝑋 with expectation 𝜇 = 𝐄(𝑋) and variance 𝜎2 = 𝑉𝑎𝑟(𝑋) outputs a value OUTSIDE the interval [𝜇−𝜀𝜎, 𝜇+𝜀𝜎] with probability of at MOST 1/𝜀2, that is
- 𝑷(|𝑋 - 𝜇| > 𝜀𝜎) ≤ 1/𝜀2
Any random variable 𝑋 with expectation 𝜇 = 𝐄(𝑋) and variance 𝜎2 = 𝑉𝑎𝑟(𝑋) outputs a value WITHIN the interval [𝜇−𝜀𝜎, 𝜇+𝜀𝜎] with probability of at LEAST 1 - 1/𝜀2, that is
- 𝑷(|𝑋 - 𝜇| ≤ 𝜀𝜎) ≥ 1 - 1/𝜀2
Theorem Proof
- 𝜎2= 𝑉𝑎𝑟(𝑋)
- 𝜎2= 𝛴all 𝑥(𝑥 − 𝜇)2𝐏(𝑥)
- 𝜎2≥ 𝛴only 𝑥:|𝑥-𝜇|>𝜀(𝑥 − 𝜇)2𝐏(𝑥)
- 𝜎2≥ 𝛴only 𝑥:|𝑥-𝜇|>𝜀(𝜀)2𝐏(𝑥)
- 𝜎2≥ (𝜀)2𝛴only 𝑥:|𝑥-𝜇|>𝜀𝐏(𝑥)
- 𝜎2≥ (𝜀)2𝐏(|𝑋 - 𝜇| > 𝜀)
- 𝜎2/𝜀2≥ 𝐏(|𝑋 - 𝜇| > 𝜀)
- (𝜎/𝜀)2≥ 𝐏(|𝑋 - 𝜇| > 𝜀)