\Question{Double-Check Your Intuition}
\begin{Parts}
\Part \begin{enumerate}[(i)]
\item Let $X \sim \text{Bin} (5, 1 / 4)$. Let $Y$ be a random variable equal to $5 - X$. What are the distributions of $X$ and $Y$?
\item Let $Z$ be a random variable denoting the result of a die roll (so $1 \leq Z \leq 6$ uniformly at random). What is $\E[Z^2]$?
\end{enumerate}
\nosolspace{.5in}
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.
\Part If $A$ and $B$ are integer-valued random variables such that for every integer $i$, $\Pr(A = i) = \Pr(B = i)$, then is $\Pr(A = B) > 0$?
\nosolspace{0.5in}
\Part If $C$ is an integer-valued random variable, then is $\E[C^2] = \E[C]^2$?
\nosolspace{0.5in}
\Part If $X$ and $Y$ are random variables and $\E[X] > 100 \E[Y]$, then is $\Pr(X > Y) > 1 / 100$?
\nosolspace{0.5in}
\Part If $X$ and $Y$ are random variables taking positive values, then is $\E[\frac{X}{X+Y}] = \frac{\E[X]}{\E[X+Y]}$?
\nosolspace{0.5in}
\Part If $A, B, C$ are events such that $\Pr(A \cap B \cap C) = \Pr(A) \Pr(B) \Pr(C)$, then are $A, B, C$ mutually independent?
\nosolspace{0.5in}
\Part Is an event $A$ never independent with itself?
\nosolspace{0.5in}
\Part If $A$ and $B$ are independent events, then are $\overline{A}$ and $\overline{B}$ independent?
\nosolspace{1in}
\end{Parts}
\Question{Airport Revisited}
\begin{Parts}
\Part 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?
\Part 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$).
\end{Parts}
\Question{Fizzbuzz}
\begin{Parts}
\Part 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?)
\nosolspace{.5in}
\Part Recall the Euler totient function from Homework 4: $$\phi(n) = \left| \{ i : 1 \leq i \leq n, \texttt{gcd} (i, n) = 1 \} \right|.$$ Suppose $n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ where $p_1, p_2, \ldots, p_k$ are distinct primes and $\alpha_1, \alpha_2, \ldots, \alpha_k$ are positive integers. Prove that $$\frac{\phi(n)}{n} = \prod_{j = 1}^k \left( 1 - \frac{1}{p_j} \right)$$
\nosolspace{1in}
\end{Parts}
\Question{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.
\begin{Parts}
\Part What is the size of the sample space?
\Part 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?
\Part Prove that ${n \choose k} \le n^k$.
\textit{Optional:} Can you come up with a combinatorial proof? Of course, an algebraic proof would also get full credit.
\Part Prove that the probability that the graph contains a $k$-clique, for $k \geq 4{\log n}+1$, is at most
$1/n$. (The log is taken base 2).
\textit{Hint:} Apply the union bound and part (c).
\end{Parts}
\Question{Balls and Bins, All Day Every Day}
You throw $n$ balls into $n$ bins uniformly at random, where $n$ is a positive \emph{even} integer.
\begin{Parts}
\Part What is the probability that exactly $k$ balls land in the first bin, where $k$ is an integer $0 \le k \le n$?
\nosolspace{1.5cm}
\Part 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.)
\nosolspace{1.5cm}
\Part 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.
\nosolspace{1.5cm}
\Part 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?
\nosolspace{1.5cm}
\Part 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.)
\nosolspace{1.5cm}
\end{Parts}