SECTION 04 / 10

Chebyshev’s inequality

On this page 6 headings

Learning goal: Use mean and variance to bound deviations on both sides.

The variance must be finite.
The standard-deviation form assumes positive standard deviation; if the variance is zero, the variable equals its mean almost surely.

The ideaTwo classes both average 50 %.
In one, everyone scored between 45 and 55.
In the other, scores range from 0 to 100.
If you also know how spread out the scores are, you can make a much sharper statement about how many are far from 50.
Chebyshev does exactly that.

Key statementTwo random variables $X_{1}$ (points far apart) and $X_{2}$ (points bunched together) with $E [X_{1}] = E [X_{2}]$ .

Chebyshev's inequalityFor any random variable X with finite mean $E [X]$ and finite variance $σ^{2}$ , and any $k > 0$ :

P (∣ X - E [X] ∣ \geq k σ) \leq \frac{1}{k ^{2}} .

Reading the formula

$∣ X - E [X] ∣$ is how far the outcome lands from the average, on either side.
That is why there is an absolute value.
$k σ$ means "k standard deviations away".
The chance of being at least k standard deviations away is at most $1/ k^{2}$ : at most 25 % for k = 2, 11.1 % for k = 3 and 4 % for k = 5.
Unlike Markov, X may be negative, and the bound works on both tails at once.
For k ≤ 1 the bound is ≥ 1, so it says nothing.

Why it is true (Chebyshev = Markov in disguise)

Let $Y = (X - E [X])^{2}$ .
Y is never negative, and $E [Y] = σ^{2}$ .
The event " $∣ X - E [X] ∣ \geq k σ$ " is the same event as " $Y \geq k^{2} σ^{2}$ ".
Apply Markov to Y:

P (Y \geq k^{2} σ^{2}) \leq \frac{E [ Y ]}{k ^{2} σ ^{2}} = \frac{σ ^{2}}{k ^{2} σ ^{2}} = \frac{1}{k ^{2}} .

Being 20 away is $k = 20/10 = 2$ standard deviations, so the bound is $1/ 2^{2} = 0.25$ .
At most 25 %, for any score distribution with this mean and spread.
If the scores happen to be normal, the true figure is about 4.6 %.

$E [X] = 3.5$ , $σ \approx 1.708$ .
What is the chance of landing 2.5 or more from 3.5, which means rolling a 1 or a 6?

Mean 100, σ = 15. Upper bound on P(X ≤ 55 or X ≥ 145)?

45 away means k = 3, so the bound is 1/9 ≈ 0.111.

What is the bound for k = 0.5, and why is it useless?

YOUR STUDY PROGRESS

Finished this section? Save your progress.