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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\begin{document}
\inclassproblems{11, Fri}

\begin{problem}\label{CMS}

Independently flip three fair coins, and define $C$ to be the number of
heads which appear and $M$ to be 1 iff all three coins match and 0
otherwise.  Also, let $S \eqdef C \bmod 2$.

What are the values of the probability density functions (pdf's) $f_C$,
$f_M$, and $f_{S}$?  Likewise for the distribution functions
$F_C$, $F_M$, and $F_{S}$?  \solution{
\begin{align*}
f_C(0)= & f_C(3)= 1/8\\
f_C(1)= & f_C(2)= 3/8\\
f_M(0)= & 3/4\\
f_M(1)= & 1/4\\
f_{S}(0) =  & f_{S}(1) = 1/2.
\end{align*}

\begin{equation*}
F_C(x) =
\begin{cases}
 0  & \text{for } x < 0,\\
1/8 & \text{for } 0 \le x < 1,\\
1/2 & \text{for } 1 \le x < 2,\\
7/8 & \text{for } 2 \le x <3,\\
 1  & \text{for } 3 \le x.
\end{cases}
\end{equation*}
}

\end{problem}


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

\bparts

\ppart

Give an example of RV's $X,Y$ on some probability space, $\sspace$, such
that $X\rho Y$ but $X\neq Y$.

\solution{Let
\begin{align*}
\sspace \eqdef & \set{\texttt{win, lose}},\\
\pr{\texttt{win}} \eqdef & 1,\\
\pr{\texttt{lose}} \eqdef & 0,\\
X(\texttt{win}) = Y(\texttt{win}) \eqdef & 5,\\
X(\texttt{lose}) \eqdef & 5,\\
Y(\texttt{lose}) \eqdef & 4.99.
\end{align*}
}

\ppart 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$.
}
\eparts

\end{problem}

\instatements{
\textbf{WE DIDN'T GET TO THE FOLLOWING TWO PROBLEMS IN CLASS.}

\begin{problem}
In addition to $C,M$, and $S$, in problem~\ref{CMS}, let $R_i$ be the
indicator variable for a Head occurring on the $i$th flip, for $i=1,2,3$.
Verify that $R_1,R_2,R_3, S$ are 3-way independent, that
$R_1,R_2,R_3,S,M,$ are pairwise independent, and that there are no
other pairs of independent variables besides these.


\solution{to appear}

\end{problem}

\begin{problem}
Let $X,Y$ be independent Binomial random variables with parameters $(n,p)$
and $(m,p)$, respectively.

\bparts
\ppart
What is $\pr{X+Y = k}$?

\solution{
The pdf of $X$ is the probability of tossing $k$ Heads out of
$n$ independent flips of a coin with bias $p$.  Likewise for $Y$ and $m$
flips.  Since, $X$ and $Y$ are independent, the pdf of $X+Y$ corresponds
to $n+m$ independent flips, \ie, $X+Y$ is a Binomial variable with
parameters $(n+m, p)$.  Hence,
\[
\binom{m+n}{k}p^k(1-p)^{m+n-k}.
\]
}

\ppart  Prove that if $p=1/2$ and $n$ is even, then

\begin{equation}
\pr{X = \frac{n}{2}} \sim \sqrt{\frac{2}{n \pi}}\label{n/2heads}.
\end{equation}

\hint Use Stirling's approximation (in the appendix).

\solution{
The probability of $m$ heads is $\binom{n}{m}/2^n$.

Using Stirling for an approximation:
\begin{eqnarray}
\binom{n}{m} & \sim &\frac{\sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n}
{\sqrt{2\pi m}\left(\dfrac{m}{e}\right)^m {\sqrt{2\pi
(n-m)}\left(\dfrac{n-m}{e}\right)^{n-m}}} \notag\\
& = & 
\frac{\sqrt{n}\left(\dfrac{n}{e}\right)^m\left(\dfrac{n}{e}\right)^{n-m}}
{\sqrt{2\pi m (n-m)}\left(\dfrac{m}{e}\right)^m
 {\left(\dfrac{n-m}{e}\right)^{n-m}}} \notag\\
& = & \sqrt{\dfrac{n}{2\pi m (n-m)}}\left(\dfrac{n}{m}\right)^m\left(\dfrac{n}{n-m}\right)^{n-m}.\label{stirsimp}
\end{eqnarray}

Setting $m = n/2$ in~(\ref{stirsimp}) yields
\begin{equation}
\binom{n}{n/2} \sim \frac{2^n}{\sqrt{n \pi/2}}\label{n/2simp},
\end{equation}
so
\begin{equation}
%\pr{\text{$n/2$ heads in $n$ flips}}
\pr{X = \frac{n}{2}}= 
 =\frac{\dbinom{n}{\ceil{n/2}}}{2^n} \sim \sqrt{\frac{2}{n \pi}},
\end{equation}
proving~(\ref{n/2heads}).

If $n$ is odd, the same asymptotic bound also holds (with $n/2$ replaced
by $\ceil{n/2}$).  }

\ppart Estimate the probability that the number of heads in 400 flips of a
fair coin will be between 195 and 205, and likewise that in 10,000 flips
it will be between 4980 and 5020.

Also, discuss writing a program to calculate the exact answer.

\solution{The numbers are all too large to calculate exactly by hand.
Computing 400!, 190!, and 210!\ exactly will overflow on any calculator,
so an exact computation by calculator would also be impractical.  In fact,
it will cause numerical overflow errors in most programming languages.
Real Scheme has infinite precision rational arithmetic and can handle
400!, but typically overflows when computing 10,000!, so exact computation
in the 10,000 case is unlikely to work in any language---remember the
answer will have around 40,000 digits\footnote{Though on machines with
enough RAM and a gigahertz+ processor, Scheme actually can handle exact
calculations with 40,000 digit integers.}.  But there are no applications
that require anywhere near such accuracy.

So we aim for an approximate solution using Stirling's approximation for
$n!$,.  But there are still pitfalls: $(400/e)^{400}$ will overflow
floating point arithmetic on calculators and essentially all computers, so
the simplified version~(\ref{stirsimp}) would be needed.  Since floating
point is usually good for 8 to 10 places on most machines, getting six
place accuracy should be manageable.

A calculator will yield the value of the righthand side of
equation~(\ref{n/2heads}) at $n=400$; it is $\approx 0.0399$.  But all the
probabilities for 195 to 205 heads are about the same, so an offhand
estimate would be $11 \times 0.0399 \approx 0.439$.  The actual answer is
0.418.

Similarly, for $n=10,000$, the value of~(\ref{n/2heads}) is about 0.00798,
and all the probabilities for 4980 to 5020 heads are about the same, so an
offhand estimate would be $41 \times 0.00798 \approx 0.327$.  The actual
answer is 0.318.}

\eparts

\end{problem}
}

\instatements{
\appendix

\subsection*{Random Variables}

A \emph{random variable} over a given sample space, $\sspace$, is a
function from $\sspace \to \reals$.

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.

A random variable, $B$, is \emph{binomial} with parameters $(n,p)$ iff its
pdf is the function $f_{n,p}: \naturals \to [0,1]$ defined by
\[
f_{n,p}(k) \eqdef \binom{n}{k} p^k (1-p)^{n-k}
\]
where parameter $n \in \naturals$ and $0 < p < 1$.  Equivalently, $B =
\sum_{k=1}^n B_k$ where $B_1,B_2,\dots,B_n$ are mutually independent
Bernoulli (indicator) variables with $\pr{B_i = 1} = p$.

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$.  They are \emph{$k$-wise
independent} iff $\set{R_i \suchthat i\in J}$ are mutually independent for
all subsets $J \subset \naturals$ with $\card{J} = k$.

\subsection*{Stirling's Approximation}
\[
n! \sim \sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n
\]

}

\end{document}

\iffalse

\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}
\fi


\iffalse
\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 \eqdef \max\set{X_1,X_2,X_3}$.  What is
the density function of $M$?

\solution{
This can be hashed out by counting the 27 possible outcomes:
\begin{equation*}
\pr{M}  =  
\begin{cases}
1 & \text{is } \dfrac{1}{27},\\
2 &\text{is } \dfrac{7}{27},\\
3 & \text{is } \dfrac{19}{27}.
\end{cases}
\end{equation*}
}

\end{problem}
\fi


\iffalse

\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}
\fi
