Mathematics for Computer Science

Chapter 19 Deviation from the Mean822

Show that for any real number,, and real numbersx > 0, there is anRfor
which the Chebyshev bound is tight, that is,

PrŒjRjxçD



x

 2

: (19.26)

Hint:First assumeD 0 and letRtake only the values0;x;andx.

Problem 19.10. (a)A computer program crashes at the end of each hour of use
with probability1=p, if it has not crashed already. IfHis the number of hours
until the first crash, we know

ExŒHçD

1

p

;

VarŒHçD

q

p^2

;

whereqWWD 1 p.

(b)What is the Chebyshev bound on

PrŒjH.1=p/j> x=pç

wherex > 0?

(c)Conclude from part (b) that fora 2 ,

PrŒH > a=pç

1 p

.a1/^2

Hint:Check thatjH.1=p/j> .a1/=piffH > a=p.

(d)What actually is

PrŒH > a=pç‹

Conclude that for any fixedp > 0, the probability thatH > a=pis an asymptoti-
cally smaller function ofathan the Chebyshev bound of part (c).

Problem 19.11.
LetRbe a positive integer valued random variable.

(a)If ExŒRçD 2 , how large can VarŒRçbe?

(b)How large can ExŒ1=Rçbe?

(c)IfR 2 , that is, the only values ofRare 1 and 2, how large can VarŒRçbe?