Description
1 Double-Check Your Intuition
(a) (i) Let X ∼ Bin(5,1/4). Let Y be a random variable equal to 5−X. 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
2
]?
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.
(b) 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?
(c) If C is an integer-valued random variable, then is E[C
2
] = E[C]
2
?
(d) If X and Y are random variables and E[X] > 100E[Y], then is P(X > Y) > 1/100?
(e) If X and Y are random variables taking positive values, then is E[
X
X+Y
] = E[X]
E[X+Y]
?
(f) If A,B,C are events such that P(A∩B∩C) = P(A)P(B)P(C), then are A,B,C mutually independent?
(g) Is an event A never independent with itself?
(h) If A and B are independent events, then are A and B independent?
CS 70, Fall 2018, HW 9 1
2 Airport Revisited
(a) 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?
(b) 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
(a) 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?)
(b) Recall the Euler totient function from Homework 4:
φ(n) = |{i : 1 ≤ i ≤ n,gcd(i,n) = 1}|.
Suppose n = p
α1
1
p
α2
2
··· p
αk
k where p1, p2,…, pk are distinct primes and α1,α2,…,αk are positive integers. Prove that
φ(n)
n
=
k
∏
j=1
1−
1
pj
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.
(a) What is the size of the sample space?
CS 70, Fall 2018, HW 9 2
(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
n
k
≤ n
k
.
Optional: Can you come up with a combinatorial proof? Of course, an algebraic proof would
also get full credit.
(d) 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.
(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.)
(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.)
CS 70, Fall 2018, HW 9
