Mathematics for Computer Science

Chapter 19 Deviation from the Mean824

Prove that the expected absolute deviation is always less than or equal to the stan-
dard deviation,. (For simplicity, you may assume thatRis defined on a finite
sample space.)
Hint:Suppose the sample space outcomes are! 1 ;! 2 ;:::;!n, and let
pWWD.p 1 ;p 2 ;:::;pn/ wherepiD

p

PrŒ!iç;

rWWD.r 1 ;r 2 ;:::;rn/ whereriDjR.!i/j

p

PrŒ!iç:

As usual, letv
wWWD

Pn
iD 1 viuidenote the dot product ofn-vectorsv;w, and let
jvjbe the norm ofv, namely,

p

v
v.

Then verify that

jpjD1; jrjD; and ExŒjRjçDr
p:

Problem 19.15.
Prove the following “one-sided” version of the Chebyshev bound for deviation
above the mean:

Lemma(One-sided Chebyshev bound).

PrŒRExŒRçxç

VarŒRç

x^2 CVarŒRç

:

Hint: LetSaWWD.RExŒRçCa/^2 , for 0  a 2 R. SoRExŒRçx
impliesSa.xCa/^2. Apply Markov’s bound to PrŒSa.xCa/^2 ç. Chooseato
minimize this last bound.

Exam Problems

Problem 19.16.
LetDnbe the total number of heads among mutually independent tosses ofn
coins whose respective probabilities of coming up heads arep;p^2 ;:::;pn. Write
a closed-form expression for the variance ofDn.

Problem 19.17.
LetKnbe the complete graph withnvertices. Each of the edges of the graph
will be randomly assigned one of the colors red, green, or blue. The assignments
of colors to edges are mutually independent, and the probability of an edge being
assigned red isr, blue isb, and green isg(sorCbCgD 1 ).
A set of three vertices in the graph is called atriangle. A triangle ismonochro-
maticif the three edges connecting the vertices are all the same color.