Chapter 18 Deviation from the Mean656
- Given that the last line in theprogramis buggy, the probability that the next-
to-last line in the program will also be buggy is greater thanb. - The expectation of the indicator variable for the last line in thesamplebeing
buggy isb. - Given that the first two lines of code selected in thesampleare the same
kind of statement—they might both be assignment statements, or both be
conditional statements, or both loop statements,... —the probability that the
first line is buggy may be greater thanb. - There is zero probability that all the lines in thesamplewill be different.
Problems for Section 18.7
Class Problems
Problem 18.16.
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:ForcD 12 , the value ofclnc cC 1 is greater than 18.
(b)Show that the probability that there is a slot that gets assigned more than 23
records is less thane ^15. This is less than1=3;000;000.Hint:ln 109 < 21.
Problem 18.17.
Sometimes I forget a few items when I leave the house in the morning. For example,
here are probabilities that I forget various pieces of footwear:
left sock 0:2
right sock 0:1
left shoe 0:1
right shoe 0:3(a)LetXbe the number of these that I forget. What is ExŒXç?