CS 70 Discrete Mathematics and Probability Theory Spring 2017(verified, all answers correct)

CS 70 Discrete Mathematics and Probability Theory Spring 2017 Rao HW 9 1 Sundry Before you start your homework, write down your team. Who else did you work with on this homework? List names and email addresses. (In c ...

CS 70 Discrete Mathematics and Probability Theory Spring 2017 Rao HW 9 1 Sundry Before you start your homework, write down your team. Who else did you work with on this homework? List names and email addresses. (In case of homework party, you can also just describe the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for your "Sundry" grade. Please copy the following statement and sign next to it: I certify that all solutions are entirely in my words and that I have not looked at another student’s solutions. I have credited all external sources in this write up. I certify that all solutions are entirely in my words and that I have not looked at another student’s solutions. I have credited all external sources in this write up. (Signature here) 2 Cliques in Random Graphs Consider 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. So for example if n = 2, then with probability 1/2, G(V,E) is the graph consisting of two vertices connected by an edge, and with probability 1/2 it is the graph consisting of two isolated vertices. (a) What is the size of the sample space? (b) A k-clique in graph is a set of k vertices which are pairwise adjacent (every pair of vertices is connected by an edge). For example a 3-clique is a triangle. What is the probability that a particular set of k vertices forms a k-clique? (c) Prove that the probability that the graph contains a k-clique for k = 4dlogne+1 is at most 1/n. Solution: (a) There 3 Student Request Collector After a long night of debugging, Alvin has just perfected the new homework party/office hour queue system. CS 70 students sign themselves up for the queue, and TAs go through the queue, resolving requests one by one. Unfortunately, our newest TA (let’s call him TA Bob) does not understand how to use the new queue: instead of resolving the requests in order, he always uses the Random Student button, which (as the name suggests) chooses a random student in the queue for him. To make matters worse, after helping the student, Bob forgets to click the Resolve button, so the student still remains in the queue! For this problem, assume that there are n total students in the queue. (a) Suppose that Bob has already helped k students. What is the probability that the Random Student button will take him to a student who has not already been helped? (b) Let Xir be the event that TA Bob has not helped student i after pressing the Random Student button a total of r times. What is Pr[Xir]? Assume that the results of the Random Student button are independent of each other. Now approximate the answer using the inequality 1%x  e%x. (c) Let Tr represent the event that TA Bob presses the Random Student button r times, but still has not been able to help all n students. (In other words, it takes TA Bob longer than r Random Student button presses before he manages to help every student). What is Tr in terms of the events Xr i ? (Hint: Events are subsets of the probability space W, so you should be thinking of set operations...) (d) Using your answer for the previous part, what is an upper bound for Pr[Tr]? (You may leave your answer in terms of Pr[Xir]. Use the inequality 1%x  e%x from before.) (e) Now let r = anlnn. What is an upper bound for Pr[Xir]? (f) Calculate an upper bound for Pr[Tr] using the same value of r as before. (This is more formally known as a bound on the tail probability of the distribution of button presses required to help every student. This distribution will be explored in more detail later, in the context of random variables.) CS 70, Spring 2017, HW 9 2 (g) What value of r do you need to bound the tail probability by 1/n2? In other words, how many button presses are needed so that the probability that TA Bob has not helped every student is at most 1/n2? Solution: ( 5 Geometric Distribution Two faulty machines, M1 and M2, are repeatedly run synchronously in parallel (i.e., both machines execute one run, then both execute a second run, and so on). On each run, M1 fails with probability CS 70, Spring 2017, HW 9 4 p1 and M2 fails with probability p2, all failure events being independent. Let the random variables X1, X2 denote the number of runs until the first failure of M1, M2 respectively; thus X1, X2 have geometric distributions with parameters p1, p2 respectively. Let X denote the number of runs until the first failure of either machine. Show that X also has a geometric distribution, with parameter p1 + p2 % p1p2. Solution: 2 •Âk=0 |Pr(X = k) % Pr(Y = k)|. Show that d(X,Y)  Pr(X 6= Y). [Hint: Use the Law of Total Probability to split up the events according to {X = Y} and {X 6= Y}.] (f) Show that Pr(Ân i=1 Xi 6= Ân i=1Yi)  Ân i=1 Pr(Xi 6= Yi). [Hint: Maybe try the Union Bound.] (g) Finally, for the Xi and Yi defined above, show that d(Ân i=1 Xi,Ân i=1Yi)  Ân i=1 p2 i . Solution: