\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! use the macros

%\backwardscompatibility        % !! use for backwards compatibility
\showsolutions                  % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query


\renewcommand{\exampreamble}{   % !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{llll}
  Ashish    & Carole   & Christos & Eric   \\
  George    & Jack     & Nick     & Tina   
  \end{tabular}
  \end{center}
  \begin{itemize}
  \item 
  This final is \textbf{closed book}.  There is an Appendix giving the 
  definitions of some standard operations on relations.
  \item 
  There are four (4) problems totaling 100 points.  Problems are
  labeled with their point values.
  \item 
  Put your name on the top of {\bf every} page -- \emph{these
  pages may be separated for grading}.
  \item 
  Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.
  \item 
  You may assume any of the results presented in class or in the
  lecture notes.
  \item  
  \textbf{Be neat and write legibly}.  You will be graded not only on
  the correctness of your answer, but also on the clarity with which
  you express it.
  \item 
  GOOD LUCK!
  \end{itemize}}




\begin{document} 
\final                          % !! start the paper



\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}


\begin{problem}
Recall the notion of pairwise independence of events from lecture.
Pairwise independence of random variables can be defined similarly.

\begin{definition*}
  Random variables $R_1, R_2, \dots R_m$ are \emph{pairwise independent} if
  for any $i\neq j$,
\[
\forall r, r'\;\prob{R_i=r\wedge R_j=r'}=\prob{R_i=r}\cdot\prob{R_j=r'}
\]
\end{definition*}
\begin{problemparts}
\ppart[7] 
  We can use probability distribution tables to express the
mutual probabilities of random variables.  For exmple, in the table
below $p=\prob{A=0, B=0, C=0}$.

Suppose $A, B, C$ are pairwise independent random variables which take
the values 0 or 1 with probability $1/2$ (i.e. uniformly distributed).
Fill in the remaining entries of the table in terms of $p$.

\[
\begin{array}{|c||c|c|c|c|}
\hline
\rule[-0.2in]{0in}{.5in}&A=0, B=0&A=0, B=1&A=1, B=0&A=1, B=1\\
\hline\hline
C=0\rule[-0.2in]{0in}{.5in}&p&&&\\
\hline
C=1\rule[-0.2in]{0in}{.5in}&&&&\\
\hline
\end{array}
\]
\solution{
\[
\begin{array}{|c||c|c|c|c|}
\hline
\rule[-0.2in]{0in}{.5in}&A=0, B=0&A=0, B=1&A=1, B=0&A=1, B=1\\
\hline\hline
C=0\rule[-0.2in]{0in}{.5in}&p&1/4-p&p&1/4-p\\
\hline
C=1\rule[-0.2in]{0in}{.5in}&1/4-p&p&1/4-p&p\\
\hline
\end{array}
\]
}
\ppart[6]
Prove or give a counterexample:

\emph{Every set of pairwise independent random variables is also
  mutually independent.}
\solution{
In the example above, for any $0\leq p\leq 1/4$ if $p\neq 1/8$ then $A, B,
C$ are pairwise independent but not mutually independent.
}
\ppart[6]
Prove or give a counterexample:

\emph{Every set of mutually independent random variables is also
  pairwise independent.}
\solution{
Maybe too hard to solve/grade?
%From the definition of mutual independence,
%\[
%\pr{\lgintersect_{i} [R_i = x_i]} = \prod_{i} \pr{R_i = x_i},
%\]
}

\ppart[4] 
Suppose $R_1, R_2, \dots R_m$ are pairwise independent
random variables uniformly distributed over $\set{1, 2, \dots
  n}$.  For a given $i\neq j$, show that $\pr{R_i=R_j}$ is $1/n$. 
\solution{
\begin{eqnarray*}
\pr{R_i=R_j}&=&\sum_{r=1}^n\pr{R_i=r\wedge R_j=r}\\
&=&\sum_{r=1}^n\pr{R_i=r}\pr{R_j=r}\\
&=&\sum_{r=1}^n\frac{1}{n}\cdot\frac{1}{n}\\
&=&n\cdot\frac{1}{n}\cdot\frac{1}{n}=\frac{1}{n}
\end{eqnarray*}
}

\ppart[8]
Show that the converse of the above statement is not necessarily true.
Specifically, fill in the following probability table for random
variables $A, B$ satisfying the conditions:

\begin{itemize}
\item $A$ and $B$ are uniformly distributed over $\set{1, 2, 3}$.
\item $\pr{A=B}=\frac{1}{3}$
\item $A$ and $B$ are {\bf not} independent.
\end{itemize}
Leave your answers as fractions.  We have filled in the first entry to
get you started.

\[
\begin{array}{|c||c|c|c|}
\hline
\rule[-0.2in]{0in}{.5in}\rule{0.7in}{0in}
&\rule{0.2in}{0in}A=1\rule{0.2in}{0in}
&\rule{0.2in}{0in}A=2\rule{0.2in}{0in}
&\rule{0.2in}{0in}A=3\rule{0.2in}{0in}\\
\hline\hline
B=1\rule[-0.2in]{0in}{.5in}&\frac{1}{9}&&\\
\hline
B=2\rule[-0.2in]{0in}{.5in}&&&\\
\hline
B=3\rule[-0.2in]{0in}{.5in}&&&\\
\hline
\end{array}
\]
\solution{
All rows and columns, as well as the main diagonal, must sum to $1/3$,
but not all entries are $1/9$.
\[
\begin{array}{|c||c|c|c|}
\hline
\rule[-0.2in]{0in}{.5in}\rule{0.7in}{0in}
&\rule{0.2in}{0in}A=1\rule{0.2in}{0in}
&\rule{0.2in}{0in}A=2\rule{0.2in}{0in}
&\rule{0.2in}{0in}A=3\rule{0.2in}{0in}\\
\hline\hline
B=1\rule[-0.2in]{0in}{.5in}&\frac{1}{9}=\frac{5}{45}&\frac{9}{45}&\frac{1}{45}\\
\hline
B=2\rule[-0.2in]{0in}{.5in}&\frac{7}{45}&\frac{2}{45}&\frac{6}{45}\\
\hline
B=3\rule[-0.2in]{0in}{.5in}&\frac{3}{45}&\frac{4}{45}&\frac{8}{45}\\
\hline
\end{array}
\]
}

Let us revisit the Birthday Problem discussed in lecture, where $L$ is
the number of collisions, $m$ the number of people, and $N$ the number
of days in the year.  Recall that when birthdays are mutually
independent, the probability of one or more collisions is
\[
\pr{L>0} = 1 - \frac{N!}{(N-m)! \ N^m}
\]
We now consider a scheme in which birthdays are \emph{pairwise}
independent, rather than being mutually independent.  They are still
uniformly distributed over the days of the year.

For one particular scheme, we calculate the
probability of $L\in\set{1, 2, 3\dots}$ to be
\[
\pr{L>0} = \frac{m(m-1)}{2N}
\]
where $m(m-1)<2N$.
\ppart[2]
Use this fact to determine precisely the probability distribution of
$L$.
\solution{
$L$ is a Bernoulli variable with 
\[
L=\left\{
\begin{array}{ll}
0&\textrm{  with probability }1 - \frac{m(m-1)}{2N}\\
1&\textrm{  with probability }\frac{m(m-1)}{2N}
\end{array}\right.
\]
}

\ppart[8]
Prove your answer above.
\solution{
  
There are ${m \choose 2}=\frac{m(m-1)}{2}$ possible pairs of people,
or that many potential collisions.  The probability of one
particular collision is $1/N$ as shown earlier.  Also $L$ is
constrained to be an integer, so $L>0\Leftrightarrow L\geq 1$.

We can now proceed in {\bf either} of two ways:
\begin{itemize}
\item
Using indicator variables, we see that
$\expect{L}=\frac{m(m-1)}{2}\cdot\frac{1}{N}$.  From Markov's
inequality,
\[
\pr{L\geq 1} \leq \frac{\expect{L}}{1} = \frac{m(m-1)}{2N}
\]
with equality holding only if $L$ takes on \emph{only} the values 0
and 1.
\item
Let $C_i$ denote the event that the $i$'th pair comprises a collision,
with $1\leq i\leq {m \choose 2}$.  From the union bound, 
\begin{eqnarray*}
\pr{L\geq 1} &=& \pr{\bigvee_{i=1}^{m \choose 2}C_i}\\
&\leq&\sum_{i=1}^{m \choose 2}\pr{C_i}={m \choose 2}\cdot\frac{1}{N}=\frac{m(m-1)}{2N}
\end{eqnarray*}
with equality holding only if all the $C_i$'s are disjoint events,
i.e. at most one collision occurs at a time.
\end{itemize}
Following either line of reasoning tells us that $L$ is a Bernoulli
variable, and $\pr{L=1}=\expect{L}=\frac{m(m-1)}{2N}$.

(Distributions satisfying this property can actually be constructed).
}
\end{problemparts}
\end{problem}


\end{document}
