\bigskip
\textit{\textbf{Note:} This homework consists of two parts. The first part (questions 1-6) will be graded and will determine your score for this homework. The second part (questions 7-8) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare.}
\rule{6in}{2px}
\begin{center}
For each problem, justify all your answers unless otherwise specified.
\end{center}
\section*{Part 1: Required Problems}
\bigskip
\Question{Independent Complements}
Let $\Omega$ be a sample space, and let $A,B \subseteq \Omega$ be two independent events.
\begin{Parts}
\Part Prove or disprove: $\overline{A}$ and $\overline{B}$ must be independent.
\Part Prove or disprove: $A$ and $\overline{B}$ must be independent.
\Part Prove or disprove: $A$ and $\overline{A}$ must be independent.
\Part Prove or disprove: It is possible that $A=B$.
\end{Parts}
\Question{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 innocent?
\nosolspace{3cm}
\Question{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 \textit{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}
\Question{Mario's Coins}
Mario owns three identical-looking coins. One coin shows heads with probability $1/4$, another shows heads with probability $1/2$, and the last shows heads with probability $3/4$.
\begin{Parts}
\Part Mario randomly picks a coin and flips it. He then picks one of the
other two coins and flips it. Let $X_1$ and $X_2$ be the events of the 1st
and 2nd flips showing heads, respectively. Are $X_1$ and $X_2$ independent?
Please prove your answer.
\Part Mario randomly picks a single coin and flips it twice. Let $Y_1$ and
$Y_2$ be the events of the 1st and 2nd flips showing heads, respectively.
Are $Y_1$ and $Y_2$ independent? Please prove your answer.
\Part Mario arranges his three coins in a row. He flips the coin on the left, which shows heads. He then flips the coin in the middle, which shows heads. Finally, he flips the coin on the right. What is the probability that it also shows heads?
\end{Parts}
\Question{(Un)conditional (In)equalities}
Let us consider a sample space $\Omega = \{\omega_1, \dots, \omega_N\}$ of size
$N>2$, and two probability functions $\mathbb P_1$ and $\mathbb P_2$ on it. That
is, we have two probability spaces: $(\Omega, \mathbb P_1)$ and $(\Omega,
\mathbb P_2)$.
\begin{enumerate}[(a)]
\item If for every subset $A\subset \Omega$ of size $|A| = 2$ and every
outcome $\omega\in\Omega$ it is true that $\mathbb P_1\left( \omega ~|~ A
\right) = \mathbb P_2\left( \omega ~|~ A \right)$, then is it necessarily
true that $\mathbb P_1\left( \omega \right) = \mathbb P_2\left( \omega
\right)$ for all $\omega\in\Omega$? That is, if $\mathbb P_1$ and $\mathbb
P_2$ are equal conditional on events of size $2$, are they equal
unconditionally? (\textit{Hint}: Remember that probabilities must add up to
$1$.)
\item If for every subset $A\subset \Omega$ of size $|A| = k$, where $k$ is
some fixed element in $\{2, \dots, N\}$, and every outcome
$\omega\in\Omega$ it is true that $\mathbb P_1\left( \omega ~|~ A
\right) = \mathbb P_2\left( \omega ~|~ A \right)$, then is it
necessarily true that $\mathbb P_1\left( \omega \right) = \mathbb
P_2\left( \omega \right)$ for all $\omega\in\Omega$?
\end{enumerate}
For the following two parts, assume that $\Omega = \left\{(a_1, \dots, a_k) ~|~
\sum_{j=1}^k a_j = n\right\}$ is the set of configurations of $n$ balls into $k$
labeled bins, and let $\mathbb P_1$ be the probabilities assigned to these configurations by
throwing the balls independently one after another into the bins, and let $\mathbb P_2$
be the probabilities assigned to these configurations by uniformly sampling one of these
configurations.
\begin{enumerate}[(a)]
\setcounter{enumi}{2}
\item Let $A$ be the event that all $n$ balls land in exactly one bin. What
are $\mathbb P_1\left( \omega ~|~ A \right)$ and $\mathbb P_2\left(
\omega ~|~ A \right)$ for any $\omega\in A$? How about
$\omega\in\Omega\setminus A$? Is it true that $\mathbb P_1\left( \omega
\right) = \mathbb P_2\left( \omega \right)$ for all $\omega\in\Omega$?
\item For the special case of $n=9$ and $k=3$, please give two outcomes
$B$ and $C$, so that $\mathbb P_1(B) <
\mathbb P_2(B)$ and $\mathbb P_1(C) > \mathbb P_2(C)$.
\end{enumerate}
\bigskip
\textit{\textbf{Note:} This concludes the first part of the homework. The problems below are optional, will not affect your score, and should be attempted only if you have time to spare.}
\rule{6in}{2px}
\bigskip
\section*{Part 2: Optional Problems}
\bigskip
\Question{Boy or Girl Paradox}
You know Mr. Smith has two children, at least one of whom is a boy. Assume that gender is independent and uniformly distributed, so for any child, the probability that they are a boy is the same as the probability they are a girl, which is $1/2$.
\begin{enumerate}[(a)]
\item What is the probability that both children are boys?
\item Now suppose you knock on Mr. Smith's front door and you are greeted by a boy who you correctly deduce to be Mr. Smith's older child. What is the probability that he has two boys? Compare your answer to the answer in part (a).
\item Show that in a family of $n$ children, of which $n_g$ are girls and
$n_b$ are boys, every girl has more brothers than every boy.
\item Conditional on the youngest child being a girl, what is the
probability of her having exactly $k$ brothers? Similarly, conditional
on the youngest child being a boy, what is the probability of him having
exactly $k$ brothers?
\end{enumerate}
\Question{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:
% 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 $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 $E_S$.
What is the probability of $E_S$ for a particular set $S$ of $k$ vertices?
\Part For two sets of vertices $V_1 = \{v_1, \dots, v_{\ell}\}$ and
$V_2 = \{w_1, \dots, w_k\}$, are $E_{V_1}$ and $E_{V_2}$ independent?
\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 (d).
\end{Parts}