CS代考计算机代写 Probabilistic Inequalities – I

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 np+a)∨(X np+a)􏰀npq andP(X 0 we have
λ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(a􏰀Zi 􏰀b)=1
− 2mε2 P(|Z ̃−μ|>ε)􏰀2e (b−a)2 .
15/22

Hoeffding’s Inequality
Proof
LetXi=Zi−E(Zi)=Zi−μandX ̃=1􏰍m Xi. m i=1
Note that E(Xi) = 0 for 1 􏰀 i 􏰀 m, which implies E(X ̃) = 0. Thus,
and
􏰄1􏰆m 􏰅 1􏰆m 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 􏰄m􏰅m λ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)=pfor1􏰀i􏰀m.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 0, a = 0, and b = 1 we have
P ( | Z ̃ − p | > ε ) 􏰀 2 e − 2 m ε 2 ,
or Thus,
P(|S − mp| > mε) 􏰀 2e−2mε2 ,
P((S >m(p+ε))∨(S m(p+ε))􏰀e−2mε2, P(S