Mathematics for Computer Science

19.7. Really Great Expectations 825

(a)Letmbe the probability that any given triangle,T, is monochromatic. Write
a simple formula formin terms ofr;b;andg.

(b)LetITbe the indicator variable for whetherTis monochromatic. Write simple
formulas in terms ofm;r;b;andgfor ExŒITçand VarŒITç.

LetTandUbe distinct triangles.
(c)What is the probability thatT andUare both monochromatic if they do not
share an edge?... if they do share an edge?

Now assumerDbDgD

1

3

.

(d)Show thatITandIUare independent random variables.

(e)LetMbe the number of monochromatic triangles. Write simple formulas in
terms ofnandmfor ExŒMçand VarŒMç.

(f)LetWWDExŒMç. Use Chebyshev’s Bound to prove that

PrŒjMj>

p

logç

1

log

:

(g)Conclude that

lim

n!1

PrŒjMj>

p

logçD 0

Problem 19.18.
IfAis a finite set of real numbers, then thecollection-varianceCVar.A/ofAis
defined asA’s average square deviation from its mean:

CVar.A/WWD

P

a 2 A.a/

2

jAj

;

whereis the average value of the numbers inA.
There is a herd of cows whose average body temperature turns out to be 100
degrees, while the collection-variance of all the body temperatures is 20. Our ther-
mometer produces such sensitive readings that no two cows have exactly the same
body temperature.
The herd is stricken by an outbreak ofwacky cow disease, which will eventually
kill any cow whose body temperature differs from the average by 10 degrees or
more.