Probabilistic Inequalities – I
Prof. Dan A. Simovici
UMB
1/22
Outline
1 Markov and Chebyshev Inequalities
2 Hoeffding’s Inequality
2/22
Markov and Chebyshev Inequalities
Markov Inequality
Theorem
Let X be a non-negative random variable. For every a 0 we have
P(X a) E(X). a
3/22
Markov and Chebyshev Inequalities
Proof in the discrete case
Suppose that
12n where x1 < x2 < ··· < xn. Suppose further that
x1 x2 ··· xn X:pp···p,
x1
λX λ2(b−a)2 E[e]e8 .
12/22
Hoeffding’s Inequality
Proof
Sincef(x)=eλx isaconvexfunction,wehavethatforeveryt∈[0,1] and x ∈ [a, b],
f (x) (1 − t)f (a) + tf (b). Fort=x−a ∈[0,1]wehaveeλx b−xeλa+x−aeλb.
b−a b−a b−a Applying the expectation we obtain:
E(eλX) b−E(X)eλa+E(X)−aeλb b−a b−a
because E(X) = 0.
= beλa−aeλb, b−a b−a
13/22
Hoeffding’s Inequality
Proof (cont’d)
Ifh=λ(b−a),p= −a andL(h)=−hp+log(1−p+peh),then b−a
−hp=λa,1−p=1+ a = b ,and b−a b−a
eL(h)
= e−hp(1 − p + peh)
= eλa b − a eλ(b−a)
b−a a−b = beλa−aeλb.
This implies
b−a a−b
eλa − a eλb = eL(h) eλ2(b−a)2
b
b−a b−a
8
because we have shown that L(h) h2 = λ2(b−a)2 . This gives the desired 88
inequality.
14/22
Hoeffding’s Inequality
Hoeffding’s Theorem
Theorem
Let (Z1, . . . , Zm) be a sequence of iid random variables and let ̃ 1 m
Z=m Zi. i=1
Assume that
for 1 i m. Then, for every ε > 0 we have
E(Z ̃)=μandthatP(aZi b)=1
− 2mε2 P(|Z ̃−μ|>ε)2e (b−a)2 .
15/22
Hoeffding’s Inequality
Proof
LetXi=Zi−E(Zi)=Zi−μandX ̃=1m Xi. m i=1
Note that E(Xi) = 0 for 1 i m, which implies E(X ̃) = 0. Thus,
and
1m 1m Z ̃−μ= m Zi −μ=m (Zi−μ)
i=1 i=1 1 m
=m Xi=X ̃ i=1
P(|Z ̃−μ|>ε) = P(|X ̃|>ε)
= P(X ̃>ε)+P(X ̃<−ε).
16/22
Hoeffding’s Inequality
Proof (cont’d)
Let ε and λ be two positive numbers. Note that P(X ̃ ε) = P(eλX ̃ eλε). By Markov Inequality,
P(eλX ̃ eλε) E(eλX ̃). eλε
SinceX1,...,Xm areindependent,wehave mm
λX ̃ λXi λXi E(e)=E em =E(em).
i=1 i=1
17/22
Hoeffding’s Inequality
Proof (cont’d)
By Lemma 2, for every i we have
λXi λ2(b−a)2
Therefore,
P(X ̃ ε) e−λε
m i=1
e
λ 2 ( b − a ) 2 8m2
= e−λεe
λ 2 ( b − a ) 2 8m
.
Eem e8m2 .
Choosing λ = 4mε (b−a)2
yields
P(X ̃ ε)e (b−a)2 .
− 2mε2
The same arguments applied to −X ̃ yield P(X ̃ −ε) e
− 2mε2 (b−a)2 .
18/22
Hoeffding’s Inequality
By applying the union property of probabilities we have P(|X ̃|>ε) = P(X ̃ >ε)+P(X ̃ <−ε)
− 2mε2 2e (b−a)2 .
19/22
Hoeffding’s Inequality
A special case of Hoeffding’s Theorem
Theorem
Let X1, . . . , Xm be m independent and identially distributed Bernoulli randomvariableswithP(Xi =1)=pfor1im.Let
S = X1 + · · · + Xm be the binomial variable indicating the total number of succeses, so E[S] = pm. For ε ∈ [0,1] we have:
P((S >m(p+ε))∨(S
P ( | Z ̃ − p | > ε ) 2 e − 2 m ε 2 ,
or Thus,
P(|S − mp| > mε) 2e−2mε2 ,
P((S >m(p+ε))∨(S