CS 70 Discrete Mathematics and Probability Theory Summer 2015 Chung-Wei Lin HW 6 Due Tuesday August 4 at Noon 1. CS70 Casino (8 points) Do you want to play this game? Bet: 5 homework points. 52 cards with 4 suits (, , , ) and 13 values (A,2,3,4,5,6,7,8,9,T,J,Q,K). In each round, you draw a card and put it in front of you. If two cards in front of you have the same value, the game is over; otherwise, you survive this round and earn 1 homework point. Hint: We expect you to write some codes or use a spreadsheet to calculate this. 2. Basic Proofs (32 points, 8 points for each part) True or false? For the following statements, provide either a proof or a counterexample. Let X,Y, Z be arbitrary discrete random variables. (a) If (X,Y ) are independent and (Y, Z) are independent, then (X, Z) are independent. (b) If (X,Y ) are dependent and (Y, Z) are dependent, then (X, Z) are dependent. (c) If Var(X) = 0, then X is a constant. (d) E[X]4 E[X 4 ]. 3. A Variance To Kill (20 points, 10 points for each part) This problem will give you practice using the \"standard method\" to compute the variance of a sum of random variables that are not pairwise independent (so you cannot use \"linearity\" of variance). (a) A building has n oors numbered 1, 2, . . . , n, plus a ground oor G. At the ground oor, m people get on the elevator together, and each gets off at a uniformly random one of the n oors (independently of everybody else). What is the variance of the number of oors the elevator does not stop at? (In fact, the variance of the number of oors the elevator does stop at must be the same (do you see why?) but the former is a little easier to compute.) (b) A group of three friends has n books they would all like to read. Each friend (independently of the other two) picks a random permutation of the books and reads them in that order, one book per week (for n consecutive weeks). Let X be the number of weeks in which all three friends are reading the same book. Compute Var(X). CS 70, Summer 2015, HW 6 1 4. Cookies! (20 points, 4 points for each part) (a) The TAs want to distribute k cookies and k glasses of milk to n students. They will blindly pick a student and give her/him a cookie. Same goes for the glasses of milk. Let A be the event that every student gets a cookie. Let B be the event that every student gets a glass of milk. Prove that 1 Pr[A B] (1 n(1 n )k )2 . (Hints: independence, complement, and union bound.) (b) Use the bound in Part (a). If there are 10 students, what should k be such that there is probability at least 0.64 that every single student gets at least one cookie and a glass of milk? (c) What if we have three categories of items: cookies, glasses of milk, and napkins? Derive a bound similar to that in Part (a). (d) Given k and n, how many cookies can each student expect to get? (e) Your TA decides to use an alternate method instead, to try and distribute cookies faster. For each student, she/he ips a coin. If the coin is heads up, then she/he gives the student a cookie and ips again. If it comes up tails, she/he moves onto the next student. How many cookies does a student expect to get? 5. A Very Small Hashing Problem (20 points, 4 points for each part) Suppose we hash three distinct objects randomly into a table with three (labelled) entries. We are interested in the lengths of the linked lists at the three table entries. (a) How many possible outcomes are there after hashing all 3 objects into the table? (b) Let X be the length of the linked list at entry 1 of the table. What is the distribution and expectation of X? (c) Let Y be the length of the longest linked list among all three. What is the distribution and expectation of Y ? (d) Is the expectation of X larger than, equal to, or smaller than that of Y ? In the general case, where there are m objects being hashed randomly into a table with n entries, would your answer still hold? Explain. (e) What is the distribution and expectation of X for the general case when m objects are hashed randomly into a table of size n? For the distribution, give an expression for the probability that X takes on each value in its range. 6. College Applications (20 points, 4/8/8 points for each part) There are n students applying to n colleges. Each college has a ranking over all students (i.e., a permutation) which, for all we know, is completely random and independent of other colleges. College number i will admit the rst ki students in its ranking. If a student is not admitted to any college, he or she might le a complaint against the board of colleges, and colleges want to avoid that as much as possible. (a) If for all i, ki = 1, i.e., if every college only admits the top student on its list, what is the chance that all students will be admitted to at least one college? (b) What is the chance that a particular student, Alice, does not get admitted to any college? Prove that if the average of all ki 's is 2 ln n, then this probability is at most 1/n2 . (Hint: derive the probability and use the inequality 1 x < ex .) (c) Prove that when the average ki is 2 ln n, then the probability that at least one student does not get admitted to any college is at most 1/n. CS 70, Summer 2015, HW 6 2