\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}


\begin{document}
\inclassproblems{10W}

\begin{problem}
Consider the binary relation $\rho$ on the set of all real-valued
random variables,
\[
X\rho Y \iff \pr{ X\neq Y } = 0.
\]
Prove that $\rho$ is an equivalence relation.

\solution{The trick is to observe that 
\begin{align*}
\pr{ X\neq Y } = 0 & \iff \pr{X = Y} = 1\\
 & \iff X(w) = Y(w)\\
 & \quad \text{for all outcomes $w \in \sspace$ such that }\pr{w} \neq 0.
\end{align*}

Now Reflexivity and Symmetry are immediate.  To prove Transitivity,
suppose $\pr{X =Y} =1 \land \pr{Y = Z} =1$.  So, $X(w) = Y(w)$ and $Y(w) =
Z(w)$ for all $w$ such that $\pr{w} \neq 0$.  By transitivity of equality,
$X(w) = Z(w)$ for all $w$ such that $\pr{w} \neq 0$.  Hence, $\pr{X=Z}
=1$, as required.

An alternative proof of transitivity that works for general probability
spaces---not just the ``discrete'' spaces considered in 6.042---makes
ingenious use of Inclusion-Exclusion:
\begin{align}
\pr{X = Z} & \ge \pr{X =Y \land Y=Z} & \text{(monotonicity)}\\
 & =  \pr{X=Y} + \pr{Y=Z} - \pr{X = Y \lor Y= Z} & \text{(inclusion-exclusion)} \\
 & \ge 1 + 1 - 1 = 1.
\end{align}
So $\pr{X=Z} = 1$.
}

\end{problem}

\begin{problem}
Let $X_1$, $X_2$, and $X_3$ be three mutually independent random
variables, each having the uniform density, $\pr{ X_i = k }$ equal to
$1/3$ for each of $k = 1,2,3$.  Let $M$ be another random variable giving
the maximum of these three random variables.  What is the density function
of $M$?

\solution{
This can be easily hashed out by counting the possible outcomes:
\begin{eqnarray*}
M & \textrm{ is }  & 1 \textrm{ with probability } \frac{1}{27}  \\
  &  & 2 \textrm{ with probability } \frac{7}{27}  \\
  &  & 3 \textrm{ with probability } \frac{19}{27}  
\end{eqnarray*}
}

\end{problem}

\begin{problem}
Let $A,B,C$ be events, and let $I_A,I_B,I_C$ be the corresponding
indicator variables.  Prove that $A,B,C$ are mutually independent iff the
random variables $I_A,I_B,I_C$ are mutually independent.

\solution{
($\implies$):  
\begin{eqnarray*}
\pr{I_A = 1 \wedge I_B= 0 \wedge I_C = 1} & = & \pr{A \intersect \bar{B}
\intersect C}\\
& = & \pr{A \intersect C} - \pr{A \intersect B \intersect C}\\
& = & \pr{A} \cdot \pr{C} - \pr{A} \cdot \pr{B} \cdot \pr{C}\\
& = & \pr{A} \cdot \pr{C} (1 -  \pr{B})\\
& = & \pr{A} \cdot \pr{C} \pr{\bar{B}}\\
& = & \pr{I_A = 1} \cdot \pr{I_C = 1} \pr{I_B = 0}\\
& = & \pr{I_A = 1} \cdot \pr{I_B = 0} \cdot \pr{I_C = 1}
\end{eqnarray*}
and similarly for any other three binary values in place of 101.

($\longleftarrow$):  
\begin{eqnarray*}
\pr{A \intersect B \intersect C} & = & 
        \pr{I_A = 1 \wedge I_B = 1 \wedge I_C = 1}\\
& = & \pr{I_A = 1} \cdot \pr{I_B = 1 } \cdot \pr{I_C = 1}\\
& = & \pr{A} \cdot \pr{B} \cdot \pr{C}
\end{eqnarray*}
Also,
\begin{eqnarray*}
\pr{A \intersect B} & = & \pr{A \intersect B \intersect C}
                       + \pr{A \intersect B \intersect \bar{C}}\\
& = & \pr{I_A = 1 \wedge I_B = 1 \wedge I_C = 1} + \pr{I_A = 1 \wedge I_B = 1 \wedge I_C = 0}\\
& = & \pr{I_A = 1} \cdot \pr{I_B = 1} \cdot \pr{I_C = 1}
       + \pr{I_A = 1} \cdot \pr{I_B = 1} \cdot \pr{I_C = 0}\\
& = & \pr{A} \cdot \pr{B} \cdot \pr{C} + \pr{A} \cdot \pr{B}
                       \cdot \pr{\bar{C}}\\
& = & \pr{A} \cdot \pr{B} (\pr{C} + \pr{\bar{C}})\\
& = & \pr{A} \cdot \pr{B}
\end{eqnarray*}
and similarly for ${B \intersect C}$ and ${A \intersect C}$.
}
\end{problem}

\begin{problem}
Let $R$ and $T$ be independent random variables, and $f$ and $g$ be any
functions on the real numbers, \ie $f,g : \reals \to \reals$.  Prove that
$f(R)$ and $g(T)$ are independent random variables.

\solution{The event $[f(R) = a]$ is the disjoint union of all the events
$[R = r]$ for $r \in f^{-1}(a)$, so
\[
\pr{f(R) = a} = \sum_{r \in f^{-1}(a)} \pr{R = r}.
\]
Similarly for the event $[g(T) = b]$.  Also, the event $[f(R) = a \mbox{
and } g(T) = b]$ is the disjoint unon of the events $[R = r\mbox{ and
}T = t]$ for $(r,t) \in f^{-1}(a) \times g^{-1}(b)$.  Hence,
\begin{eqnarray*}
\lefteqn{\pr{f(R) = a \mbox{ and } g(T) = b}}\\
& = & \sum_{(r,t) \in f^{-1}(a) \times g^{-1}(b)}
                \pr{R = r \mbox{ and } T = t}\\
& = & \sum_{(r,t) \in f^{-1}(a) \times g^{-1}(b)} \pr{R = r} \pr{T = t}
            \hspace{0.5in}\mbox{[because $R,T$ independent]}\\
& = & \sum_{t \in g^{-1}(b)} \sum_{r \in f^{-1}(a)} \pr{R = r} \pr{T =
               t}\\
& = & \sum_{t \in g^{-1}(b)} \pr{T = t} (\sum_{r \in f^{-1}(a)} \pr{R = r})\\
& = & \sum_{t \in g^{-1}(b)} \pr{T = t} (\pr{f(R) = a})\\
& = & \pr{f(R) = a} \sum_{t \in g^{-1}(b)} \pr{T = t}\\
& = & \pr{f(R) = a} \pr{g(T) = b}
\end{eqnarray*}
}
\end{problem}

\instatements{
\appendix

\section{Appendix}

\subsection{Events}

\begin{align}
\pr{\lgunion_{n \in \naturals} A_n} & = \sum_{n \in \naturals} \pr{A_n}
\quad \mbox{for pairwise disjoint $A_n$} \tag{Sum Rule}\\
\pr{A-B}  & =  \pr{A} - \pr{A \intersect B} \tag{Difference Rule} \\
\pr{\bar{B}}  & =  1 - \pr{B} \label{1-b} \tag{Complement Rule}\\
\pr{A \union B}  & = \pr{A} + \pr{B} - \pr{A \intersect B} \tag{Inclusion-Exclusion}\\
\pr{A \union B} & \le \pr{A}+ \pr{B} \tag{Boole's inequality} \\
\pr{A} & \le \pr{B} \quad\text{ for } A \subseteq B, \tag{Monotonicity}\\
\pr{A \intersect B} & \le  \pr{A}, \notag\\
\pr{A} & \le \pr{A \union B} \notag\\
\prcond{A}{B} {\pr{B}}  & =  \pr{A \intersect B}\tag{Product Rule}\\
\prcond{A}{B} & = \frac{\prcond{B}{A}\pr{A}}{\pr{B}} \tag{Bayes Rule}
\end{align}

\begin{lemma*}[Law of Total Probability]
Let $B_0, B_1, \ldots$ be disjoint events whose union is the
entire sample space.  Then for all events $A$,
\begin{align}
\pr{A} &= \sum_{i \in \naturals} \pr{A \cap B_i}, \notag\\
\pr{A} &= \sum_{i \in \naturals} \pr{A | B_i}\pr{B_i}. \tag{conditional form}
\end{align}
\end{lemma*}

\subsection{Independence}

Events $A$ and $B$ are \emph{independent} iff
\[
\pr{A \intersect B} = \pr{A}\pr{B}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{mutually independent} iff for all
subsets $J \subseteq \naturals$,
\[
\pr{\lgintersect_{i\in J} A_i} = \prod_{i \in J} \pr{A_i}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{$k$-wise independent} iff $\set{A_i
\suchthat i\in J}$ are mutually independent for all subsets $J \subset
\naturals$ with $\card{J} = k$.

\iffalse

\subsection{Birthdays}

Suppose there are $s$ students and $d$ days in the year.  Let $D$ be the
event that all the students have \emph{\textbf{d}}ifferent birthdays.  Then
\begin{equation*}%\label{birthapprox}
\pr{D}  \sim  e^{{\,}^{-\cfrac{s^2}{2d}}}.
\end{equation*}
as long as $s = o(\sqrt[3]{d^2})$.
\end{definition*}
\fi

\subsection{Random Variables}

A \emph{random variable} over a given sample space is a function that maps
every outcome to a real number.

The \emph{probability density function (pdf)} for a random variable $R$ is
the function $f_R : \range{R} \to [0,1]$ defined by:
\[
f_R(x) \eqdef \pr{R = x}
\]

For any event $A$, its \emph{indicator variable}, $I_A$, is the 0-1 valued
variable such that the event $[I_A = 1]$ is the same as the event $A$.  It
follows that $[I_A = 0]$ is the same as $\bar{A}$.

A random variable, $U$, is \emph{uniform} iff all its values are equally
likely.  That is
\[
\pr{U = a} = \pr{U=b}
\]
for all $a,b \in \range{U}$.   In other words, its pdf is constant.


Random variables $R_1, R_2, \dots$ are \emph{mutually independent} iff
\[
\pr{\lgintersect_{i} [R_i = x_i]} = \prod_{i} \pr{R_i = x_i},
\]
for all $x_1, x_2, \dots \in \reals$.
}

\end{document}
