Mathematics for Computer Science

Chapter 18 Deviation from the Mean650

(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).

Class Problems

Problem 18.5.
The hat-check staff has had a long day serving at a party, and at the end of the party
they simply return thenchecked hats in a random way such that the probability
that any particular person gets their own hat back is1=n.
LetXibe the indicator variable for theith person getting their own hat back. Let
Snbe the total number of people who get their own hat back.

(a)What is the expected number of people who get their own hat back?

(b)Write a simple formula for ExŒXiXjçfori¤j.Hint:What is Pr



XjD 1 jXiD 1



?

(c)Explain why you cannot use the variance of sums formula to calculate VarŒSnç.

(d)Show that ExŒSn^2 çD 2 .Hint:Xi^2 DXi.

(e)What is the variance ofSn?

(f)Show that there is at most a 1% chance that more than 10 people get their own
hat back. Try to give an intuitive explanation of why the chance remains this small
regardless ofn.

Problem 18.6.
For any random variable,R, with mean,, and standard deviation,, the Cheby-
shev Bound says that for any real numberx > 0,

PrŒjRjxç



x

 2

:

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

: (18.28)

Hint:First assumeD 0 and letRonly take values0;x;andx.