Description

Maximum credit for this homework will be given for any score of 50% or more.
Sundry
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
1 Independent Complements
Let Ω be a sample space, and let A,B ⊆Ω 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 guilty?
3 Flipping Coins
Consider the following scenarios, where we apply probability to a game of flipping coins. In the game, we flip one coin each round. The game will not stop until two consecutive heads appear.
(a) What is the probability that the game ends by flipping exactly five coins?
(b) Given that the game ends after flipping the fifth coin, what is the probability that three heads appear in the sequence?
(c) If we change the rule that the game will not stop until three consecutive tails or three consecutive heads appear, what is the probability that the game stops by flipping at most six coins?
4 To Be Fair
Suppose you have a biased coin with P(heads)6= 0.5. How could you use this coin to simulate a fair coin? (Hint: Think about pairs of tosses.)
5 Identity Theft
A group of n friends go to the gym together, and while they are playing basketball, they leave their bags against the nearby wall. An evildoer comes, takes the student ID cards from the bags, randomly rearranges them, and places them back in the bags, one ID card per bag.
(a) What is the probability that no one receives his or her own ID card back?
Hint: Use the inclusion-exclusion principle.
(b) What is the limit of this proability as n →∞?
Hint: ex kk!.
6 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?
(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.)
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 ={v1,…,v`} and V2 ={w1,…,wk}, are EV1 and EV2 independent?
(d) Prove that nk .
(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).