Page 512 - Discrete Mathematics and Its Applications

7.4 Expected Value and Variance 491

Chebyshev’s Inequality

How likely is it that a random variable takes a value far from its expected value? Theorem 8,
called Chebyshev’s inequality, helps answer this question by providing an upper bound on the
probability that the value of a random variable differs from the expected value of the random
variable by more than a specified amount.

THEOREM 8 CHEBYSHEV’S INEQUALITY Let X be a random variable on a sample space S with
probability function p.If r is a positive real number, then

2
p(|X(s) − E(X)|≥ r) ≤ V(X)/r .

Proof: Let A be the event

A ={s ∈ S |X(s) − E(X)|≥ r}.

2
What we want to prove is that p(A) ≤ V(X)/r . Note that
2
V(X) = (X(s) − E(X)) p(s)
s∈S

2 2
= (X(s) − E(X)) p(s) + (X(s) − E(X)) p(s).
s∈A s ∈A
The second sum in this expression is nonnegative, because each of its summands is nonnegative.
2
2
Also, because for each element s in A, (X(s) − E(X)) ≥ r , the first sum in this expression is at
2 2 2 2
least r p(s). Hence, V(X) ≥ r p(s) = r p(A). It follows that V(X)/r ≥ p(A),
s∈A s∈A
2
so p(A) ≤ V(X)/r , completing the proof.
EXAMPLE 19 Deviation from the Mean when Counting Tails Suppose that X is the random variable
that counts the number of tails when a fair coin is tossed n times. Note that X is the number
of successes when n independent Bernoulli trials, each with probability of success 1/2, are
performed. It follows that E(X) = n/2 (by Theorem 2) and V(X) = n/4 (by Example 18).
√
Applying Chebyshev’s inequality with r = n shows that
√ √ 2
p(|X(s) − n/2|≥ n) ≤ (n/4)/( n) = 1/4.

Consequently, the probability is no more than 1/4 that the number of tails that come up when a
√
fair coin is tossed n times deviates from the mean by more than n. ▲
Chebyshev’s inequality, although applicable to any random variable, often fails to provide
a practical estimate for the probability that the value of a random variable exceeds its mean by
a large amount. This is illustrated by Example 20.

EXAMPLE 20 Let X be the random variable whose value is the number appearing when a fair die is rolled.
We have E(X) = 7/2 (see Example 1) and V(X) = 35/12 (see Example 15). Because the
only possible values of X are 1, 2, 3, 4, 5, and 6, X cannot take a value more than 5/2 from its
mean, E(X) = 7/2. Hence, p(|X − 7/2|≥ r) = 0if r> 5/2. By Chebyshev’s inequality we
2
know that p(|X − 7/2|≥ r) ≤ (35/12)/r .
For example, when r = 3, Chebyshev’s inequality tells us that p(|X − 7/2|≥ 3) ≤
(35/12)/9 = 35/108 ≈ 0.324, which is a poor estimate, because p(|X − 7/2|≥ 3) = 0. ▲