\documentclass[12pt]{article}
\usepackage{latex-macros/course}

%\hidesolutions
%\showsolutions
%\newcommand{\rem}{\operatorname{\,rem\,}}

\begin{document}

\inclassproblems{13, Mon.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Suppose that you flip three fair, mutually independent coins.
Define the following events:
\begin{itemize}
\item Let $A$ be the event that \emph{the first} coin is heads.
\item Let $B$ be the event that \emph{the second} coin is heads.
\item Let $C$ be the event that \emph{the third} coin is heads.
\item Let $D$ be the event that \emph{an even number of} coins are heads.
\end{itemize}
\bparts

\ppart 
Are these events pairwise independent?

\solution{
The sample space  consists of eight, equiprobable outcomes:
\[
\set{H, T}^3  =  \set{ HHH, HHT, HTH, HTT, THH, THT, TTH, TTT }
\]
Each sequence of three symbols specifies the outcomes of the three
coin tosses.

The first three events ($A$, $B$, and $C$) are pairwise independent,
since they are mutually independent.  All that remains is to check
that each of these is independent of~$D$.  By symmetry, we need 
only check just one of the three, say $A$:
\begin{align*}
\pr{A}	&= \dfrac{1}{2} \\
\pr{D}	&= \pr{\set{ HHT, HTH, THH, TTT }} = \dfrac{1}{2} \\
\pr{A \cap D} &= \pr{\set{HHT, HTH}} = \dfrac{1}{4}
\end{align*}
Therefore, $\pr{A \cap D} = \pr{A} \cdot \pr{D}$, and so these events
are independent.  We conclude that all four events are pairwise
independent.}

\ppart Are these events three-way independent?  That is, does
\[
\pr{X \cap Y \cap Z}  =  \pr{X} \cdot \pr{Y} \cdot \pr{Z}
\]
always hold when $X$, $Y$, and $Z$ are distinct events drawn
from the set $\set{ A, B, C, D}$?

\solution{
Because the coin tosses are mutually independent, we know:
\[
\pr{A \cap B \cap C} = \pr{A} \cdot \pr{B} \cdot \pr{C}.
\]
What remains is to check that equality holds for the other subsets of
three events: $\set{A,B,D}$, $\set{A,C,D}$, and $\set{B,C,D}$.  By symmetry,
again, we need only check one, say the first one.
\[
\pr{A \cap B \cap D} = \pr{\set{HHT}} = \dfrac{1}{8}.
\]
Since this is equal to $\pr{A} \cdot \pr{B} \cdot \pr{D}$, these three
events are independent.  

We conclude that all four events are three-way independent.}

\ppart Are these events mutually independent?

\solution{
No, because:
\[
\pr{A \cap B \cap C \cap D}
	 \neq  \pr{A} \cdot \pr{B} \cdot \pr{C} \cdot \pr{D}
\]
The probability on the left is zero, but the product on the right is
equal to $1/16$.
}

\eparts                                                                                
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}
There is a set of 1000 people.
%
\begin{itemize}
\item The favorite color of 20\% of these people is blue.
\item The favorite color of 30\% is green.
\item The favorite color of 50\% is red.
\end{itemize}
\bparts

\ppart Suppose we select a sequence of two distinct people $(p_1, p_2)$ by
selecting $p_1$ uniformly at random, and then selecting $p_2$ uniformly at
random among the remaining 999 people.  Let the random variable $C_i$ be
the favorite color of person $p_i$.  Are $C_1$ and $C_2$ independent?
Justify your answer.

\solution{No.  For example,
\[
\pr{C_1 = \text{blue}} \pr{C_2 = \text{blue}} = \frac{200}{1000}.
\]
However,
%
\[
\prcond{C_2 = \text{blue}}{C_1 = \text{blue}} = \frac{199}{999}.
\]
%
since 199 of the remaining 999 people like blue after one person who
likes blue is selected.}


\ppart Suppose we select a sequence of two people $(q_1, q_2)$ uniformly
at random.  (Now it may be that $q_1=q_2$.)  Let the random variable $D_i$
be the favorite color of $q_i$.  Now are $D_1$ and $D_2$ independent?
Justify your answer.

\solution{Yes.  Let $c(p)$ be the color that person $p$ likes.  The random
variables $q_1$ and $q_2$ are independent.  Functions of independent
random variables are independent, so $C_1 \eqdef c(q_1)$ and $C_2 \eqdef
c(q_2)$ are independent.}

\eparts

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse
\begin{problem}
Many of the best computer algorithms rely on randomization.  However,
generating uniform, mutually independent random bits is not so easy!
(The mathematician John von Neumann said, ``Anyone who considers
arithmetic methods of producing random digits is, of course, in a
state of sin.'')  Fortunately, some algorithms work equally well with
\textit{pairwise-independent} random bits, which are relatively
``cheap''.  In particular, one can convert a set of mutually
independent bits into an \textit{exponentially larger} set of
pairwise-independent random bits.

Let $B$ be a set of $n$ uniform, mutually-independent 0-1 random
variables.

\bparts

\ppart Let $S$ be a nonempty subset of the bits in $B$.  Let the
random variable $s$ be the \textsc{xor} of all the bits in $S$
\footnote{The quantity $a_1 \textsc{ xor } a_2 \textsc{ xor } \cdots
\textsc{ xor } a_n$ is equal to the remainder of $a_1 + a_2 + \cdots +
a_n$ divided by 2.}.  Show that $s$ is uniformly distributed on
$\set{0,1}$.

\hint Let $b$ be one of the bits in $S$ and let $s'$ be the \textsc{xor}
of all other bits in $S$.)

\solution{
\begin{align*}
\pr{s = 0}
    & = \pr{s' = 0 \cap b = 0} + \pr{s' = 1 \cap b = 1} \\
    & = \pr{s' = 0} \pr{b = 0} + \pr{s' = 1} \pr{b = 1} \\
    & = \frac{1}{2} \pr{s' = 0} + \frac{1}{2} \pr{s' = 1} \\
    & = \frac{1}{2} (\pr{s' = 0} + \pr{s' = 1}) \\
    & = \frac{1}{2}
\end{align*}
%
We first rewrite the event $s = 0$ and then use the independence of
$b$ and $s'$.  The remaining steps use the facts that $b$ is 0 or 1
with equal probability and that $s'$ is either 0 or 1 (with unknown
probabilities).  Since $s = 0$ with probability $1/2$, we must have $s
= 1$ with probability $1/2$ as well, so $s$ is uniformly distributed
on $\set{0,1}$.}

\ppart Now let $T$ be another nonempty subset of bits in $B$.  Let the
random variable $t$ be the \textsc{xor} of all the bits in $T$.  Show
that $s$ and $t$ are independent.

\hint Define $s'$ to be the \textsc{xor} of bits in $S -
T$, $t'$ to be the \textsc{xor} of bits in $T - S$, and $i$ to be the
\textsc{xor} of bits in $S \cap T$.  Now consider three cases: (1) $S
\cap T = \emptyset$, (2) $S \cap T = S$ or $S \cap T = T$, and (3) $S
\cap T \neq \emptyset, S, \text{ or } T$.)

\solution{We must show that $\pr{s = a \cap t = b} = \pr{s = a} \pr{t
= b}$ for all $a$ and $b$.  By the preceding problem part, $\pr{s = a}
= \pr{t = b} = 1/2$.  So we really only need to show that for all $a$
and $b$:
%
\[
\pr{s = a \cap t = b} = 1/4
\]

Define random variables $s'$, $t'$, and $i$ as described above.  These
random variables are mutually independent since they are functions of
mutually independent bits.  We can rewrite the quantity we're trying
to analyze, $\pr{s = a \cap t = b}$, in terms of these variables as
follows:
%
\begin{align}
\pr{s = a \cap t = b}
   & = \pr{s' = a \cap t' = b \cap i = 0} \notag\\ 
   & + \pr{s' = \overline{a} \cap t' = \overline{b} \cap i = 1} \notag\\
   & = \pr{s' = a} \pr{t' = b} \pr{i = 0} \notag\\
   & + \pr{s' = \overline{a}} \pr{t' = \overline{b}} \pr{i = 1}.  \label{eqn:main}
\end{align}
%
Now we analyze the three cases:

\begin{enumerate}

\item If $S \cap T = \emptyset$, then $\pr{i = 1} = 1$ and $\pr{i = 0}
= 0$.  However, the sets $S - T$ and $T - S$ are nonempty, so $\pr{s'
= a} = \pr{t' = b} = 1/2$ by the preceding part.  Substituting
into~\eqref{eqn:main} gives:
%
\[
\pr{s = a \cap t = b} = \frac{1}{2} \cdot \frac{1}{2} \cdot 1 +
                        \frac{1}{2} \cdot \frac{1}{2} \cdot 0
                      = \frac{1}{4}
\]

\item If $S \cap T = S$, then $S - T = \emptyset$ and so $\pr{s' = 1}
= 1$ and $\pr{s' = 0} = 0$.  The sets $S \cap T$ and $T - S$ are
nonempty, so $i$ and $t'$ are uniformly distributed by the preceding
part.  Substituting into~\eqref{eqn:main} gives:
%
\[
\pr{s = a \cap t = b} = 0 \cdot \frac{1}{2} \cdot \frac{1}{2} +
                        1 \cdot \frac{1}{2} \cdot \frac{1}{2}
                      = \frac{1}{4}
\]
%
If $S \cap T = T$, then a symmetric argument applies.

\item If $S \cap T \neq \emptyset, S, \text{ or } T$, then the sets $S
  - T$, $T - S$, and $S \cap T$ are all nonempty.  Therefore, $s'$,
  $t'$, and $i$ are all uniformly-distributed.  Substituting
  into~\eqref{eqn:main} gives:
%
\[
\pr{s = a \cap t = b} = \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} +
                        \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2}
                      = \frac{1}{4}
\]

\end{enumerate}
%
Therefore, $s$ and $t$ are independent.
}

\ppart Explain how to construct a set of $2^n-1$ uniform,
pairwise-independent 0-1 random variables from a set of $n$ uniform,
mutually-independent 0-1 random variables.

\solution{Take the sums of all nonempty subsets modulo 2.  In the two
preceding parts, we proved that these random variables are uniform and
pairwise independent.}

\eparts

\end{problem}
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\instatements{\newpage}

\begin{problem}
Suppose that we create a national database of DNA profiles.  Let's make
some simplifying assumptions (for the purposes of this problem,
don't worry about whether these assumptions are reasonable):
%
\begin{itemize}
\item Each person can be classified into one of \underline{20 billion}
different ``DNA types''.  (For example, you might be type \#13,646,572,661
and the person next to you might be type \#2,785,466,098.)

\item Each DNA type is equally probable.

\item The DNA types of Americans are mutually independent.
\end{itemize}

\bparts

\ppart A congressman argues that there are only about 250 million
Americans, so even if a profile for every American were stored in the
database, the probability of even one coincidental match would be very
small.  How many profiles must the database actually contain in order
for the probability of at least one coincidental match be about $1/2$?

\solution{By the birthday principle, the probability of
a match is around half when the number of entries is:
\[
\sqrt{2 \ln 2 \cdot 20,000,000,000} = 166,511.
\]
}


\ppart Person $x$ is arrested for a crime that was committed by person
$y$.  At trial, jurors must determine whether $x = y$.  The crime lab says
$x$ and $y$ have the same DNA type.  The prosecutor argues that the
probability that $x$ and $y$ are different people is only 1 in 20 billion.
Let $T(x)$ denote the DNA type of person $x$.  Using $T$, write the
prosecutor's assertion in mathematical notation, and explain her error.

\solution{The prosecutor is asserting that:
\[
\prcond{\text{$x$ and $y$ are different people}}{T(x) = T(y)} = 2 \cdot 10^{-10}.
\]

This assertion is false using the probability model that is implicitly
being assumed.  Namely, we associate each person with a DNA-type-valued
random variable with uniform distribution over the $2 \cdot 10^{-10}$
types, and we assume all these variables are mutually independent.  We
also consider $x$ and $y$ to be distinct people-valued independent random
variables with uniform distribution over the $2.5 \cdot 10^{-8}$ people in
the US.

With this model, the actual probability is
\begin{equation}\label{126}
\prcond{x \neq y}{T(x) = T(y)} = \frac{1}{126},
\end{equation}
as we show below.

The prosecutor's argument \textit{sounds} confusingly similar to a correct
assertion: 
\[
\prcond{T(x) = T(y)}{x \neq y} = 2 \cdot 10^{-10}.
\]
The prosecutor can validly argue that \textit{either} an amazing 1-in-20
billion coincidence involving DNA has occurred \textit{or else} $x$ and
$y$ are the same person.  On this basis, a jury might conclude that $x$ is
guilty.

On the other hand, the defense attorney could argue from~\eqref{126} that,
given the DNA match, the probability that $x$ is not guilty is much
greater $2 \cdot 10^{-10}$, but is in fact 1/126.  He could then argue to
the jury that 125/126 does not meet the legal standard of being guilty
``beyond reasonable doubt,'' and so the jury should not convict $x$.

To prove~\eqref{126}, note that
\[
\prcond{x \neq y}{T(x) = T(y)}  = 1 - \prcond{x = y}{T(x) = T(y)}.
\]
Then we have,
\begin{align*}
\lefteqn{\prcond{x = y}{T(x) = T(y)}}\\
  & \eqdef \frac{\pr{x = y \text{ and } T(x) =T(y)}}{\pr{T(x)=T(y)}}\\
  & = \frac{\pr{x = y}}{\prcond{T(x)=T(y)}{x=y}\pr{x=y} +
          \prcond{T(x)=T(y)}{x\neq y}\pr{x \neq y}}\\
  &= \frac{2.5 \cdot 10^{-8}}{1 \cdot 2.5 \cdot 10^{-8} +
          2\cdot 10^{-10}(1 - 2.5\cdot 10^{-8})}\\
  & \approx \frac{2.5 \cdot 10^{-8}}{2.5 \cdot 10^{-8} +
          (2.5 \cdot 10^{-8}/125) \cdot 1}\\
  &= \frac{1}{1 + 1/125} = \frac{125}{126}.
\end{align*}
}


\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}
Suppose there are 100 people in a room.  Assume that their birthdays are
independent and uniformly distributed.  
As stated in lecture:
\begin{quote}
If there are $N$ days in a year and $m$ people in a room, then the
probability that no two people in the room have the same birthday is very
close to:
\[
e^{-m^2/(2N)}
\]
\end{quote}
It follows that with probability \mbox{$> 99\%$} there will be two people
with the same birthday.

Now suppose you learn the birthdays of all the people in the room except
one---call her ``Jane''---and find all 99 dates to be different.

\bparts

\ppart 
What's wrong with the following argument:
\begin{quotation}
With probability greater than 99\%, some pair of people in the room have
the same birthday.  Since the 99 people we asked all had different
birthdays, it follows that with probability greater than~99\% Jane has the
same birthday as some other person in the room.
\end{quotation}

\solution{
Here's the problem with the argument: Let $A$ be the event that some two
people in the room have the same birthday.  Let $B$ be the event that the
99 people we asked all have different birthdays.

It is true that $\pr{A} > 0.99$ (that is indeed the probability spoken
about in the lecture notes).  However, that is the \emph{a priori}
probability, that is, assuming all the birthdays are uniform and
independent, with no other constraints.  The argument above makes the
erroneous assumption that event $A$ has probability of at least $99\%$
even once we know that event $B$ holds.  But once we know that event $B$
holds, the birthdays are no longer independent.  Thus $\prcond{A}{B}$ is
not necessarily equal to $\pr{A}$ (in our case, they are actually quite
different, as will be computed in part~(b)).}

\ppart 
What is the actual probability that Jane has the same birthday
as some other person in the room?

\solution{ Let $S$ be the set of birthdays of the 99 people in the room
other than Jane. By assumption, $|S| = 99$.  Let $b$ be the date of Jane's
birthday.  Since $b$ is uniformly distributed over a set of size 365, and
$b$ is independent of all the birthdays in $S$, we have
\[
\prcond{A}{B} = \pr{b\in S} =  \frac{\card{S}}{365} = 
\frac{99}{365} \approx 27.1\%,
\]
where $B$ is the event that the 99 people we asked all have
different birthdays.
}
\eparts
\end{problem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{document}

\iffalse
\ppart Suppose the congressman argues that the assumption that
the DNA type is equally probable is outrageous.  How would
you respond?  (A brief qualitative answer would be enough in a
Congressional hearing).
\solution{
If the DNA types were not equally probable, then the probability
of a match only goes up.
}
\fi
