• Double-Check Your Intuition
• (i) Let X Bin(5,1/4). Let Y be a random variable equal to 5X. What are the distributions of X and Y?

(ii) Let Z be a random variable denoting the result of a die roll (so 1 Z 6 uniformly at random). What is E[Z²]?

For each of the problems below, if you think the answer is yes then provide a proof. If you think the answer is no, then provide a counterexample.

• If A and B are integer-valued random variables such that for every integer i, P(A = i) = P(B =

i), then is P(A = B) > 0?

• If C is an integer-valued random variable, then is E[C²] = E[C]²?
• If X and Y are random variables and E[X] > 100E[Y], then is P(X >Y) > 1/100?
• If X and Y are random variables taking positive values, then is_Y]?
• If A,B,C are events such that P(ABC) = P(A)P(B)P(C), then are A,B,C mutually independent?
• Is an event A never independent with itself?
• If A and B are independent events, then are A and B independent?

2 Airport Revisited

• Suppose that there are n airports arranged in a circle. A plane departs from each airport, and randomly chooses an airport to its left or right to fly to. What is the expected number of empty airports after all planes have landed?
• Now suppose that we still have n airports, but instead of being arranged in a circle, they form a general graph, where each airport is denoted by a vertex, and an edge between two airports indicates that a flight is permitted between them. There is a plane departing from each airport and randomly chooses a neighboring destination where a flight is permitted. What is the expected number of empty airports after all planes have landed? (Express your answer in terms of N(i) the set of neighboring airports of airport i, and deg(i) the number of neighboring airports of airport i).

3 Fizzbuzz

• Fizzbuzz is a classic software engineering interview question. You are given a natural number n, and for each integer i from 1 to n you have to print either fizzbuzz if i is divisible by 15, fizz if i is divisible by 3 but not 15, buzz if i is divisible by 5 but not 15, or the integer itself if i is not divisible by 3 or 5.

If n is a multiple of 15, then how many printed lines will contain an integer?

(Hint: If you pick a line uniformly at random, then what is the probability that the printed line contains an integer?)

• Recall the Euler totient function from Homework 4:

(n) = |{i : 1 i n,gcd(i,n) = 1}|.

Suppose n = p₁¹p₂² p_k^k where p₁,p₂,,p_k are distinct primes and ₁,₂,,_k are positive integers. Prove that

(n)

n = _j

4 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.

• What is the size of the sample space?
• 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?
• Prove that ⁿ_k.

Optional: Can you come up with a combinatorial proof? Of course, an algebraic proof would also get full credit.

• 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 (c).

5 Balls and Bins, All Day Every Day

You throw n balls into n bins uniformly at random, where n is a positive even integer.

• What is the probability that exactly k balls land in the first bin, where k is an integer 0 k n?
• 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.)
• 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.
• 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?
• 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.)