Probability and Stochastic Processes

PROBABILITY AND STOCHASTIC PROCESS 51

5. Modes of Convergence
5.1. Some important inequalities. We start this section by proving a result known as Markov
inequality.
Lemma 5.1 (Markov inequality). If X is a non-negative random variable whose expected
value exists, then for all a > 0,
E(X)
P(X ≥ a) ≤ .
a
Proof. Observe that, since X is non-negative
h i
E[X] = E X1{X≥a} + X1{X<a} ≥ E[X1{X≥a} ] ≥ aP(X ≥ a).
Hence the result follows. 
Corollary 5.2. If X is a random variable such that E[|X|] < +∞, then for all a > 0
E(|X|)
P(|X| ≥ a) ≤ .
a
Example 5.1. A coin is weighted so that its probability of landing on heads is 20%. Suppose
the coin is flipped 20 times. We want to find a bound for the probability it lands on heads at
least 16 times. Let X be the number of times the coin lands on heads. Then X ∼ B(20, 15 ). We
use Markov inequality to find the required bound:
E(X) 4 1
P(X ≥ 16) ≤ = = .
16 16 4
The actual probability that this happen is
20  
X 20
P(X ≥ 16) = (0.2)k (0.8)20−k ≈ 1.38 × 10−8 .
k
k=16

Lemma 5.3 (Chebyschev’s inequality). Let Y be an integrable random variable such that
Var(Y ) < +∞. Then for any ε > 0
Var(Y )
P(|Y − E(Y )| ≥ ε) ≤ .
ε2
Proof. To get the result, take X = |Y − E(Y )|2 and a = ε2 in Markov inequality. 
Example 5.2. Is there any random variable X for which

1
P µ − 3σ ≤ X ≤ µ + 3σ = ,
2
2
where µ = E(X) and σ = Var(X).
Solution: Observe that




P µ − 3σ ≤ X ≤ µ + 3σ = P |X − µ| ≤ 3σ = 1 − P |X − E(X)| > 3σ .
By Chebyschev’s inequality, we get that



σ2
P |X − E(X)| > 3σ ≤ P |X − E(X)| ≥ 3σ ≤ 2 ,
9σ
and hence

1 8
P µ − 3σ ≤ X ≤ µ + 3σ ≥ 1 − = .
9 9
1
Since 2 < 89 , there exists NO random variable X satisfying the given condition.

, 52 A. K. MAJEE

In principle Chebyshev’s inequality asks about distance from the mean in either direction, it
can still be used to give a bound on how often a random variable can take large values, and will
usually give much better bounds than Markov’s inequality. For example consider Example 5.1.
Markov’s inequality gives a bound of 14 . Using Chebyshev’s inequality, we see that
Var(X) 1
P(X ≥ 16) = P(X − 4 ≥ 12) ≤ P(|X − 4| ≥ 12) ≤ = .
144 45
Lemma 5.4 (One-sided Chebyschev inequality). Let X be a random variable with mean 0 and
variance σ 2 < +∞. Then for any a > 0,
σ2
P(X ≥ a) ≤ .
σ 2 + a2
Proof. For any b ≥ 0, we see that X ≥ a is equivalent to X + b ≥ a + b. Hence by Markov’s
inequality, we have
E[(X + b)2 ] σ 2 + b2
P(X ≥ a) = P(X + b ≥ a + b) ≤ P((X + b)2 ≥ (a + b)2 ) ≤ =
(a + b)2 (a + b)2
σ 2 + b2 σ2
=⇒ P(X ≥ a) ≤ min = .
b≥0 (a + b)2 σ 2 + a2

One can use one-sided Chebyschev inequality to arrive at the following corollary.
Corollary 5.5. If E[X] = µ and Var(X) = σ 2 , then for any a > 0,
σ2
P(X ≥ µ + a) ≤
σ 2 + a2
σ2
P(X ≤ µ − a) ≤ 2 .
σ + a2
Example 5.3. Let X be a Poisson random variable with mean 20. Show that one-sided Cheby-
shev inequality gives better upper bound on P(X ≥ 26) compare to Markov and Chebyschev
inequalities. Indeed, by Markov inequality, we have
E[X] 10
p = P(X ≥ 26) ≤ = .
26 13
By Chebyschev inequality, we get
Var(X) 10
p = P(X − 20 ≥ 6) ≤ P(|X − 20| ≥ 6) ≤ = .
36 18
One-sided Chebyschev inequality gives
Var(X) 10
p = P(X − 20 ≥ 6) ≤ = .
Var(X) + 36 28
Theorem 5.6 (Weak Law of Large Number). Let {Xi } be a sequence of iid random variables
with finite mean µ and variance σ 2 . Then for any ε > 0
Sn
σ2
P | − µ| > ε ≤ 2 ,
n nε
where Sn = ni=1 Xi . In particular,
P

Sn

lim P | − µ| > ε = 0 .
n→∞ n
Proof. First inequality follows from Chebyschev’s inequality. Sending limit as n tends to infinity
in the first inequality, we arrive at the second result.