University of California, Berkeley - CS 70 hw9-sol. CS 70 Discrete Mathematics and Probability Theory. (Spring 2019). Homework 9 Solutions.

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Fall 2019 Alistair Sinclair and Yun S. Song HW 9 Note: This homework consists of two parts. The first part (questions 1-6) will be graded and will... determine your score for this homework. The second part (questions 7-8) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare. For each problem, justify all your answers unless otherwise specified. Part 1: Required Problems 1 Independent Complements Let W be a sample space, and let A;B ⊆ W be two independent events. (a) Prove or disprove: A and B must be independent. (b) Prove or disprove: A and B must be independent. (c) Prove or disprove: A and A must be independent. (d) Prove or disprove: It is possible that A = B. 2 Lie Detector A lie detector is known to be 4=5 reliable when the person is guilty and 9=10 reliable when the person is innocent. If a suspect is chosen from a group of suspects of which only 1=100 have ever committed a crime, and the test indicates that the person is guilty, what is the probability that he is innocent? 3 Balls and Bins, All Day Every Day Suppose n balls are thrown into n labeled bins one at a time, where n is a positive even integer. (a) What is the probability that exactly k balls land in the first bin, where k is an integer 0 ≤ k ≤ n? (b) What is the probability p that at least half of the balls land in the first bin? (You may leave your answer as a summation.) CS 70, Fall 2019, HW 9 2 (c) Using the union bound, give a simple upper bound, in terms of p, on the probability that some bin contains at least half of the balls. (d) What is the probability, in terms of p, that at least half of the balls land in the first bin, or at least half of the balls land in the second bin? (e) After you throw the balls into the bins, you walk over to the bin which contains the first ball you threw, and you randomly pick a ball from this bin. What is the probability that you pick up the first ball you threw? (Again, leave your answer as a summation.) 4 Mario’s Coins Mario owns three identical-looking coins. One coin shows heads with probability 1=4, another shows heads with probability 1=2, and the last shows heads with probability 3=4. (a) Mario randomly picks a coin and flips it. He then picks one of the other two coins and flips it. Let X1 and X2 be the events of the 1st and 2nd flips showing heads, respectively. Are X1 and X2 independent? Please prove your answer. (b) Mario randomly picks a single coin and flips it twice. Let Y1 and Y2 be the events of the 1st and 2nd flips showing heads, respectively. Are Y1 and Y2 independent? Please prove your answer. (c) Mario arranges his three coins in a row. He flips the coin on the left, which shows heads. He then flips the coin in the middle, which shows heads. Finally, he flips the coin on the right. What is the probability that it also shows heads? 5 (Un)conditional (In)equalities Let us consider a sample space W = fw1;:::;wNg of size N > 2, and two probability functions P1 and P2 on it. That is, we have two probability spaces: (W;P1) and (W;P2). (a) If for every subset A ⊂ W of size jAj = 2 and every outcome w 2 W it is true that P1 (w j A) = P2 (w j A), then is it necessarily true that P1 (w) = P2 (w) for all w 2 W? That is, if P1 and P2 are equal conditional on events of size 2, are they equal unconditionally? (Hint: Remember that probabilities must add up to 1.) (b) If for every subset A ⊂ W of size jAj = k, where k is some fixed element in f2;:::;Ng, and every outcome w 2 W it is true that P1 (w j A) = P2 (w j A), then is it necessarily true that P1 (w) = P2 (w) for all w 2 W? For the following two parts, assume that W = n(a1;:::;ak) j ∑kj=1 aj = no is the set of configurations of n balls into k labeled bins, and let P1 be the probabilities assigned to these configurations by throwing the balls independently one after another into the bins, and let P2 be the probabilities assigned to these configurations by uniformly sampling one of these configurations. CS 70, Fall 2019, HW 9 5 (c) Let A be the event that all n balls land in exactly one bin. What are P1 (w j A) and P2 (w j A) for any w 2 A? How about w 2 WnA? Is it true that P1 (w) = P2 (w) for all w 2 W? (d) For the special case of n = 9 and k = 3, please give two outcomes B and C, so that P1(B) < P2(B) and P1(C) > P2(C). Note: This concludes the first part of the homework. The problems below are optional, will not affect your score, and should be attempted only if you have time to spare. Part 2: Optional Problems 6 Boy or Girl Paradox You know Mr. Smith has two children, at least one of whom is a boy. Assume that gender is independent and uniformly distributed, so for any child, the probability that they are a boy is the same as the probability they are a girl, which is 1=2. (a) What is the probability that both children are boys? (b) Now suppose you knock on Mr. Smith’s front door and you are greeted by a boy who you correctly deduce to be Mr. Smith’s older child. What is the probability that he has two boys? Compare your answer to the answer in part (a). (c) Show that in a family of n children, of which ng are girls and nb are boys, every girl has more brothers than every boy. CS 70, Fall 2019, HW 9 7 (d) Conditional on the youngest child being a girl, what is the probability of her having exactly k brothers? Similarly, conditional on the youngest child being a boy, what is the probability of him having exactly k brothers? 7 Cliques in Random Graphs In last week’s homework you worked on a graph G = (V;E) on n vertices which is generated by the following random process: for each pair of vertices u and v, we flip a fair coin and place an (undirected) edge between u and v if and only if the coin comes up heads. Now consider: (a) What is the size of the sample space? (b) A k-clique in graph is a set S of k vertices which are pairwise adjacent (every pair of vertices is connected by an edge). For example a 3-clique is a triangle. Let’s call the event that S forms a clique ES. What is the probability of ES for a particular set S of k vertices? (c) For two sets of vertices V1 = fv1;:::;v‘g and V2 = fw1;:::;wkg, are EV1 and EV2 independent? (d) Prove that nk ≤ nk. Optional: Can you come up with a combinatorial proof? Of course, an algebraic proof would also get full credit. (e) Prove that the probability that the graph contains a k-clique, for k ≥ 4logn+1, is at most 1=n. (The log is taken base 2). Hint: Apply the union bound and part (d). [Show More]

Last updated: 2 years ago

Preview 1 out of 10 pages