\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{Note:} You may prove this inequality algebraically, but a combinatorial proof is possible as well.
\Part Prove that the probability that the graph contains a $k$-clique for $k = 4\ceil{\log n}+1$ is at most
$1/n$.
\textit{Hint:} Apply the union bound and part (c).
\end{Parts}
\Question{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.
\begin{Parts}
\Part What is the probability that no one receives his or her own ID card back?
\textit{Hint}: Use the inclusion-exclusion principle.
\Part What is the limit of this proability as $n \to \infty$?
\textit{Hint:} $\e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}$.
\end{Parts}
\Question{Solve the Rainbow}
Your roommate was having Skittles for lunch and they offer you some.
There are five different colors in a bag of Skittles: red, orange, yellow, green, and purple, and there are 20 of each color.
You know your roommate is a huge fan of the green Skittles.
With probability $1/2$ they ate all of the green ones, with probability $1/4$ they ate half of them, and with probability $1/4$ they only ate 5 green ones.
\begin{Parts}
\Part If you take a Skittle from the bag, what is the probability that it is green?
\Part If you take two Skittles from the bag, what is the probability that at least one is green?
\Part If you take three Skittles from the bag, what is the probability that they are all green?
\Part If all three Skittles you took from the bag are green, what are the probabilities that your roommate had all of the green ones, half of the green ones, or only 5 green ones?
\Part If you take three Skittles from the bag, what is the probability that they are all the same color?
% \Part If you take three Skittles from the bag, what is the probability that they are all different colors?
\end{Parts}
\Question{Probability Potpourri}
Prove a brief justification for each part.
\begin{Parts}
\Part For two events $A$ and $B$ in any probability space, show that $\Pr(A \setminus B) \geq \Pr(A) - \Pr(B)$.
\Part If $|\Omega| = n$, how many distinct events does the probability space have?
\Part Find some probability space $\Omega$ and three events $A, B$, and $C \subseteq \Omega$ such that $\Pr(A) > \Pr(B)$ and $\Pr(A \mid C) < \Pr(B \mid C)$.
\Part If two events $C$ and $D$ are disjoint and $\Pr(C) > 0$ and $\Pr(D) > 0$, can $C$ and $D$ be independent? If so, provide an example. If not, why not?
\Part Suppose $\Pr(D \mid C) = \Pr(D \mid \overline{C})$, where $\overline{C}$ is the complement of $C$. Prove that $D$ is independent of $C$.
\Part Two six sided dice are rolled. Find three events such that they are all pairwise independent, but aren't mutually independent.
\end{Parts}
\Question{Faulty Lightbulbs}
Box $1$ contains $1000$ lightbulbs of which $10 \%$ are defective. Box $2$ contains $2000$ lightbulbs of which $5 \%$ are defective.
\begin{enumerate}[(a)]
\item Suppose a box is given to you at random and you randomly select a lightbulb from the box. If that lightbulb is defective, what is the probability you chose Box $1$?
\item Suppose now that a box is given to you at random and you randomly select two light- bulbs from the box. If both lightbulbs are defective, what is the probability that you chose from Box $1$?
\end{enumerate}
\Question{Friendly Independence}
Let's start with the basics. You have two friends, Olivia and Fitz. We're interested in the things they do. Specifically, we're interested in whether Olivia eats popcorn and whether Fitz retires to Vermont on any given day. For the purposes of this question, we can assume these events are independent.
\begin{Parts}
\Part Show that Olivia not eating popcorn and Fitz retiring to Vermont are independent. That is, $\bar O$ and $F$ are independent.
\Part Show that Olivia eating popcorn and Fitz not retiring to Vermont are independent. That is, $O$ and $\bar F$ are independent.
\Part Show that Olivia not eating popcorn and Fitz not retiring to Vermont are independent. That is, $\bar O$ and $\bar F$ are independent.
\Part You've made a new friend Cyrus, who sometimes yells passionately at people. Olivia eating popcorn, Fitz retiring to Vermont, and Cyrus yelling are mutually independent events. Show that Olivia eating popcorn and Fitz retiring to Vermont $\cap$ Cyrus yelling are independent. That is, $O$ and $(F \cap C)$ are independent.
\Part Show that Olivia eating popcorn and Fitz retiring to Vermont $\bigtriangleup$ Cyrus yelling are independent. That is, $O$ and $(F \bigtriangleup C)$ are independent. Recall that $\bigtriangleup$ is the symmetric difference of two sets. $A \bigtriangleup B = (B-A) \cup (A-B)$.
\Part More generally, let $\mc A$ be a finite collection of mutually independent events. Let $K$ be an indexing set and for each $k \in K$, let $\mc A_k$ be a subset of $\mc A$ such that as $k$ ranges over $K$, the collections $\mc A_k$ are pairwise disjoint. Show that the events $\{\bigcap_{A \in \mc A_k} A, \; k \in K\}$ are mutually independent.
\end{Parts}
\Question{Cookie Jars}
You have two jars of cookies, jar $1$ and jar $2$.
Each jar starts with $n$ cookies initially.
Every day, when you come home, you pick one of the two jars randomly (each jar is chosen with probability $1/2$).
One day, you come home and reach inside one of the jars of cookies, but you find that is empty!
Let $X$ denote the number of remaining cookies in the two jars.
What is the distribution of $X$?
\Question{Combinatorial Coins}
Allen and Alvin are flipping coins for fun. Allen flips a fair coin $k$ times and Alvin flips $n-k$ times, with $k \le n - k$.
In total there are $n$ coin flips.
\begin{Parts}
\Part Use a combinatorial proof to show that $$\sum_{i=0}^k \binom{k}{k - i} \binom{n - k}{i} = \binom{n}{k}.$$
\Part Prove that the probability that Allen and Alvin flip the same number of heads is equal to the probability that there are a total of $k$ heads.
\end{Parts}