Chapter 19 Deviation from the Mean832
(b)What would the Markov bound be on the probability that the gambler will win
at least 108 hands on a given day?
(c)Assume the outcomes of the card games arepairwise, but possiblynotmutu-
ally, independent. What is the variance in the number of hands won per day? You
may answer with a numerical expression that is not completely evaluated.
(d)What would the Chebyshev bound be on the probability that the gambler will
win at least 108 hands on a given day? You may answer with a numerical expres-
sion that is not completely evaluated.
(e)Assuming outcomes of the card games aremutuallyindependent, show that
the probability that the gambler will win at least 108 hands on a given day is much
smaller than the bound in part (d).Hint:e^1 ^2 ln^2 0:7
Class Problems
Problem 19.28.
We want to store 2 billion records into a hash table that has 1 billion slots. Assum-
ing the records are randomly and independently chosen with uniform probability
of being assigned to each slot, two records are expected to be stored in each slot.
Of course under a random assignment, some slots may be assigned more than two
records.
(a)Show that the probability that a given slot gets assigned more than 23 records
is less thane ^36.
Hint: Use Chernoff’s Bound, Theorem 19.6.1,. Note thatˇ.12/ > 18, where
ˇ.c/WWDclnc cC 1.
(b)Show that the probability that there is a slot that gets assigned more than 23
records is less thane ^15 , which is less than1=3;000;000.Hint: 109 < e^21 ; use
part (a).
Problem 19.29.
Sometimes I forget a few items when I leave the house in the morning. For example,