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

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}
%\renewcommand{\coursecopyrightyear}{2002}

\newcommand{\heads}[1]{\card{#1}_{\texttt{H}}}
\newcommand{\tails}[1]{\card{#1}_{\texttt{T}}}
\newcommand{\nhh}{\textup{NoHH}}

\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln9.pdf}
{Week 9 Notes}, Rosen \S4.4 \& 4.5 thru Example  9, p. 274.}
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

%topics: probability defs, conditional prob, independence.

%\hidesolutions         
%\showsolutions

\begin{document}
\problemset{9}

\begin{problem}
We consider a variation of Monty Hall's game.  The contestant
still picks one of three doors, with a prize randomly placed behind one
door and goats behind the other two.  But now, instead of always opening a
door to reveal a goat, Monty instructs Carol to \emph{randomly} open one
of the two doors that the contestant hasn't picked.  This means she may
reveal a goat, or she may reveal the prize.  If she reveals the prize,
then the entire game is \emph{restarted}, that is, the prize is again
randomly placed behind some door, the contestant again picks a door, and
so on until Carol finally picks a door with a goat behind it.  Then the
contestant can choose to \emph{stick} with his original choice of door or
\emph{switch} to the other unopened door.  He wins if the prize is behind
the door he finally chooses.

To analyze this setup, we define two events:
\begin{description}
\item[$GP$:] The event that the contestant \textbf{g}uesses the door with
the \textbf{p}rize behind it on his first guess.

\item[$OP$:] The event that the game is restarted at least once.  Another
way to describe this is as the event that the door Carol first
\textbf{o}pens has a \textbf{p}rize behind it.
\end{description}

\bparts

\ppart  What is $\pr{GP}$? \dots $\prcond{OP}{\bar{GP}}$?
\solution{1/3,1/2}

\ppart What is $\pr{OP}$?
\solution{
\[
\prcond{OP}{GP}\pr{GP} + \prcond{OP}{\bar{GP}}\pr{\bar{GP}} = 0\cdot 1/3 +
1/2 \cdot 2/3 = 1/3.
\]
}
\iffalse

\ppart Let $R$ be the number of times the game is restarted before Carol
picks a goat.

What is $\expect{R}$?\brule{0.8in}\\
You may express the answer as a simple closed form in terms of $p \eqdef
\pr{OP}$.

\solution{
$1/(1-p) - 1 = 3/2 -1 = 1/2$.

Think of \emph{not} having to restart as a failure.  So
$\pr{\text{failure}} = 1-p$, and $\expect{R}$ is mean time to failure
minus one---because we are only counting the number of
``successes''---namely, $1/\pr{\text{failure}} - 1$.}
\fi

\ppart What is the probability the game will continue forever?  Explain.

\solution{0.  Successive restarts are independent, so the probability of
an $n$th restart, given there have already been $n-1$ restarts, is 1/2.
Hence the probability of $\ge n$ restarts is at most $(1/2)^n
\longrightarrow 0$ as $n \longrightarrow \infty$.}

\ppart When Carol finally picks the goat, the contestant has the choice of
sticking or switching.  Let's say that the contestant adopts the strategy
of sticking.  Let $W$ be the event that the contestant wins with this
strategy, and let $w \eqdef \pr{W}$.  Express the following conditional
probabilities as simple closed forms in terms of $w$.
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}

\item $\prcond{W}{GP}$.
\solution{1}

\item $\prcond{W}{\bar{GP}\intersect OP}$.
\solution{$w$}

\item $\prcond{W}{\bar{GP}\intersect \bar{OP}}$.
\solution{0}
\end{enumerate}

\ppart What is $\pr{W}$?

\solution{1/2, because
\[\begin{array}{rcll}
w & = & \prcond{W}{GP}\pr{GP} 
        & +\ \prcond{W}{\bar{GP}\intersect OP}\pr{\bar{GP}\intersect OP}\\
  &   & & +\ \prcond{W}{\bar{GP}\intersect \bar{OP}}\pr{\bar{GP}\intersect \bar{OP}}\\
  & = & 1 \cdot 1/3 & +\ w \cdot 2/3 \cdot 1/2 + 0 \cdot 2/3 \cdot 1/2\\
  & = & 1/3 + w/3.
\end{array}\]
So $w(1- 1/3) = 1/3$.}

\ppart For any final outcome where the contestant wins with a ``stick''
strategy, he would lose if he had used a ``switch'' strategy, and vice
versa.  In the original Monty Hall game, we concluded immediately that the
probability that he would win with a ``switch'' strategy was $1-\pr{W}$.
Why isn't this conclusion quite as obvious for this new, restartable game?
Is this conclusion still sound?  Briefly explain.

\solution{Switching strategies turns wins to losses for \emph{terminated}
games.  So the probability of win with switch is $t-\pr{W}$ where $t$ is
the probability of termination.  In original Monty Hall, the game obviously
terminated after one door-opening, so $t$ was 1.

The extra complication here is that it is possible for the game to run
forever, but this event has probability 0, so $t$ is still 1, and the
conclusion is still sound.}

\iffalse

\ppart Ben Bitdiddle claims that we didn't need all this analysis to
determine a good strategy.  He says that sticking will be a losing
strategy for the contestant, just as in the original Monty Hall game.  His
reasoning is that, because it is more likely than not that the prize is
behind one of the doors the contestant didn't pick, it's to the
contestant's advantage to switch whenever he has the opportunity.  How
would you explain to Ben, briefly, what the fallacy is in his reasoning?
\fi

\eparts
\end{problem}


\begin{problem}
We consider a game in which a biased coin is flipped until two consecutive
heads come up.  The player wins if the number of flips until the game ends
is divisible by three.  Let $p$ be the probability that a coin flip comes
up Heads and $q\eqdef 1-p$ be the probability that a coin flip comes up
Tails.  Assume all flips are mutually independent.

\bparts

\ppart{What is the probability that the player wins?  Evaluate your answer at $p=1/2$}

\solution{
Let $W$ be the event that the player wins.  We define $w = \pr{W}$. 
From the law of total probability, we know that
\[
w = \prcond{W}{H}\pr{H} + \prcond{W}{T}\pr{T} 
\] 
where $H$ and $T$ are the event of flipping a head or a tail, respectively, 
on the current flip.  Let $s = \prcond{W}{T}$.

Computing $\prcond{W}{H}$:
\begin{eqnarray*}
\prcond{W}{H} & = & \prcond{W}{HH}\pr{H} + \prcond{W}{HT}\pr{T} \\
& = & 0 \cdot \pr{H} + \prcond{W}{HT}\pr{T} 
\end{eqnarray*}
since the player loses if we get HH on the first two flips.

Computing $\prcond{W}{HT}$:
\begin{eqnarray*}
\prcond{W}{HT} & = & \prcond{W}{HTH}\pr{H} + \prcond{W}{HTT}\pr{T} \\
	& = & \prcond{W}{HTH}\pr{H} + w \cdot \pr{T}
\end{eqnarray*}
since winning after flipping HTT is the same as winning starting from
scratch since the ending T can't be any part of an HH sequence.

Computing $\prcond{W}{HTH}$:
\begin{eqnarray*}
\prcond{W}{HTH} & = & \prcond{W}{HTHH}\pr{H} + \prcond{W}{HTHT}\pr{T} \\
         & = & 0 \cdot \pr{H} + s \cdot \pr{T}
\end{eqnarray*}
since a player loses after flipping HTHH on the first 4 flips, and winning
after flipping HTHT is the same as flipping a tail on the first flip (or
any flip n such that $n \mod 3 = 1$).

Putting this together, we get
\begin{eqnarray*}
w & = & \prcond{W}{H}p + sq \\
  & = & \prcond{W}{HT}qp + sq \\
  & = & (\prcond{W}{HTH}p + wq)qp + sq \\
  & = & (sqp + wq)qp + sq 
\end{eqnarray*}

This gives us one equation and 2 unknowns, so we need to compute $s$.
\[
s = \prcond{W}{T} = \prcond{W}{TH}\pr{H} + \prcond{W}{TT}\pr{T} 
\]

Computing $\prcond{W}{TH}$:
\begin{eqnarray*}
\prcond{W}{TH} & = & \prcond{W}{THH}\pr{H} + \prcond{W}{THT}\pr{T} \\
 	& = & 1 \cdot \pr{H} + w \cdot \pr{T}
\end{eqnarray*}
since a player wins after flipping THH on the first 3 flips, and the
probability of winning after flipping a THT on the first 3 flips is the
same as winning starting from scratch.

Computing $\prcond{W}{TT}$:
\begin{eqnarray*}
\prcond{W}{TT} & = & \prcond{W}{TTH}\pr{H} + \prcond{W}{TTT}\pr{T} \\
	& = & \prcond{W}{TTH}\pr{H} + w \cdot \pr{T}
\end{eqnarray*}

Computing $\prcond{W}{TTH}$:
\begin{eqnarray*}
\prcond{W}{TTH} & = & \prcond{W}{TTHH}\pr{H} + \prcond{W}{TTHT}\pr{T} \\
	 & = & 0 \cdot \pr{H} + s \cdot \pr{T}.
\end{eqnarray*}

Putting all these together, we get:
\begin{eqnarray*}
s  & = & \prcond{W}{TH}p + \prcond{W}{TT}q \\
   & = & (p+wq)p + (\prcond{W}{TTH}p + wq)q \\
   & = & (p + wq)p + (sqp +wq)q
\end{eqnarray*}

Solving for $s$, we get 
\[
s =(wqp+wq^2+p^2)/(1-q^2p).
\]

Now we only need to plug in this value for $s$ into our original equation
of $w=(wq + sqp)qp+sq.$  Solving for $w$, we get
\[
w=(q^2p^4+p^2q)/(1-3q^2p-q^3p^3-q^3)
\]
 
We know that $q = 1-p$, so we can further simplify this to
$q(1+p^2q)/(3q+3p^2q+p^4)$.

Plugging in for $p,q = 1/2$, we get $w=9/31$.  
}
\eparts

The previous part could be solved by reasoning about conditional
probabilities without explicitly defining the underlying sample space.  In
the rest of this problem, we examine exactly what the sample space should be.

Let $\set{\texttt{T},\texttt{H}}^*$ be the set of all strings made up from
the letters $\texttt{T}$ and $\texttt{H}$.  One reasonable sample space for
this game uses strings in $\set{\texttt{T},\texttt{H}}^*$ that end with a
first occurrence of $\texttt{HH}$.  That is,
\[
\sspace \eqdef \set{s \in \set{\texttt{T},\texttt{H}}^* \suchthat \text{ $s$ ends
with $\texttt{HH}$ and no proper prefix of $s$ contains $\texttt{HH}$}}.
\]
Here we say that $t$ is a \emph{prefix} of $s$ iff $s = t r$ for some
string $r$.  If also $t\neq s$, then $t$ is called a \emph{proper} prefix
of $s$.

\bparts

\ppart \label{THT}
For strings $x,y$, let $\set{x,y}^*$ be the set of strings formed by
concatenating zero or more copies of $x$ and $y$.
Prove that 
\[
\sspace = \set{s\texttt{HH} \suchthat s \in \set{T, HT}^*}.
\]

\solution{

Let $\nhh(s)$ be the predicate ``the string $s \in
\set{\texttt{H},\texttt{T}}^*$ is empty or ends with $\texttt{T}$ and
contains no occurrence of $\texttt{HH}$.''  That is,
\[
\nhh(s) \eqdef (s=\emptystring) \lor (\exists r \in
\set{\texttt{H},\texttt{T}}^* s = r\texttt{T} \land \forall u,v \in
\set{\texttt{H},\texttt{T}}^*\, s \neq u\texttt{HH}v).
\]

Note that $s$ ends with a first occurrence of $\texttt{HH}$ iff $s =
r\texttt{HH}$ for some $r$ such that $\nhh(r)$.  So it's sufficient to
prove:
\begin{lemma*}
\[
\set{\texttt{T},\texttt{HT}}^* = \set{s \in \set{\texttt{H},\texttt{T}}^*
\suchthat \nhh(s)}
\]

\begin{proof}

[$s \in \set{\texttt{T},\texttt{HT}}^* \implies \nhh(s)$]:  by structural
induction on the definition of $\set{x,y}^*$:
\begin{itemize}
\item $\emptystring \in \set{x,y}^*$,
\item if $s \in\set{x,y}^*$, then  $sx, sy \in\set{x,y}^*$.
\end{itemize}

The induction hypothesis is $\nhh(s)$.

\textbf{Base Case} ($s = \emptystring$): true by definition of $\nhh(s)$.

{\bf Inductive Step:} Assuming $\nhh(s)$, we need to show
$\nhh(s\texttt{T})$ and $\nhh(s\texttt{HT})$.
\iffalse
namely we need to show
$\nhh(s\texttt{T})$ and $\nhh(s\texttt{HT})$.
Since $\pr{s}$, we know that $s=rT$ for some $r \in {H,T}^*$ and
that $\forall u,v \in \set{\texttt{H},\texttt{T}}^*\, s \neq
u\texttt{HH}v$.
\fi

$(\nhh(s\texttt{T}))$:  Clearly $s\texttt{T}$ ends with \texttt{T}.  Any
occurrence of \texttt{HH} in $s\texttt{T}$ would have to occur in $s$, but
there are no such occurrences in $s$ since $\nhh(s)$ holds.  So there are
no occurrences of \texttt{HH} in $s\texttt{T}$, confirming that
$\nhh(s\texttt{T})$ holds, as required.

($\nhh(s\texttt{HT})$): Clearly $s\texttt{HT}$ ends with \texttt{T}.  An
occurrence of \texttt{HH} in $s\texttt{HT}$ could overlap with the final
\texttt{H} iff $s$ ended with \texttt{H}.  But $s$ ends with \texttt{T} by
hypothesis, so no such overlapping \texttt{HH} occurs.  Any other
occurrence of \texttt{HH} in $s\texttt{HT}$ would therefore have to occur
in $s$.  But there is also no such occurrence of \texttt{HH} in $s$ by
hypothesis.  So there are no occurrences of \texttt{HH} in $s\texttt{HT}$,
confirming that $\nhh(s\texttt{HT})$ holds, as required.

\medskip

[$\nhh(s) \implies s \in \set{\texttt{T},\texttt{HT}}^*$]: by strong
induction on $\card{s}$.

The induction hypothesis is:
\[
\pr{n} \eqdef \forall s\, [\card{s}=n \land \nhh(s)] \implies s \in
\set{\texttt{T,HT}}^*.
\]

{\bf Base Case:}  $(n = 0)$:  The only length 0 string is the empty string,
$\emptystring$.  But $\emptystring \in \set{\texttt{H},\texttt{HT}}^*$ by
definition of $\set{x,y}^*$.

{\bf Inductive Step:} Assume that $\pr{n}$ is true.  We need to show that
$\pr{n+1}$ is true.
\iffalse
Since $\pr{n}$, we know that all $s$ such that $\card(s)=n$ (where $s$ can
be expressed as $s=rT$ for some $r \in \set{H,T}^*$ and $\forall u,v \in
\set{\texttt{H},\texttt{T}}^*\, s \neq u\texttt{HH}v$), $s \in
\set{T,HT}^*$.  \fi

So suppose $\card{s'} = n+1$, $s'$ ends with \texttt{T}, and contains no
occurrence of \texttt{HH}.  We must show that $s' \in
\set{\texttt{T,HT}}^*$.

So $s'$ must equal $r'\texttt{T}$ where $r'$ has no occurrence of
\texttt{HH}.  There are three cases:

Case 1: $r' = \emptystring$.  Then $s = \texttt{T} \in
\set{\texttt{T,HT}}^*$ by definition of $\set{\texttt{T,HT}}^*$.

Case 2: $r'$ ends with \texttt{T}.  Then $\nhh(r')$ holds, and since
$\card{r'}=n$, we conclude that $r' \in \set{\texttt{T,HT}}^*$ by
induction hypothesis.  Hence, $s = r'\texttt{T} \in \set{\texttt{T,HT}}^*$
by the inductive definition of $\set{\texttt{T,HT}}^*$.

Case 3: $r'$ ends with \texttt{H}.  So $r' = r''\texttt{H}$ and $s =
r''\texttt{HT}$.  Now $r''$ cannot end with \texttt{H} or $s'$ would have
an occurrence of \texttt{HH} before its final \texttt{T}.  So $r''$ ends
with \texttt{T} and hence $\nhh(r'')$ holds.  But $\card{r''} = n-1$, so
by strong induction hypothesis we conclude that $r'' \in
\set{\texttt{T,HT}}^*$.  So $s = r''\texttt{HT} \in \set{\texttt{T,HT}}^*$
by the inductive definition of $\set{\texttt{T,HT}}^*$.
\end{proof}
\end{lemma*}
}

\problempart Define appropriate probabilities for the strings in $\sspace$.
Prove that your space has all the properties required of a probability
space.  \hint By part~(\ref{THT}), we know every $s \in \sspace$ can be
uniquely parsed into $k$ occurrences of $\texttt{HT}$, $j$ remaining
occurrences of $\texttt{T}$ and a unique occurrence of $\texttt{HH}$ at the
end.  Given $j,k$, the number of such strings is $\binom{j+k}{j}$.

\solution{We define
\[
\pr{s} \eqdef p^{\heads{s}}q^{\tails{s}}
\]
where $\heads{s}$ is the number of $\texttt{H}$'s in $s$ and $\tails{s}$ is
the number of $\texttt{T}$'s in $s$.  Note that $\tails{s} = \card{s} -
\heads{s}$.

To verify that this is a probability space, we must check that the sum of
the outcome probabilities is 1, namely,
\begin{equation}
\sum_{s\ in \sspace} p^{\heads{s}}q^{\tails{s}}  = 1.
\end{equation}

Using the hint, we observe that if $s \in \sspace$ parses into $k$ occurrences
of $\texttt{HT}$, $j$ remaining occurrences of $\texttt{T}$ and a unique
occurrence of $\texttt{HH}$ at the end, then
\begin{equation}\label{prs}
\pr{s} = q^j (pq)^k p^2.
\end{equation}
Hence,
\begin{align*}
\sum_{s\ \in \sspace} p^{\heads{s}}q^{\tails{s}}
& = \sum_{j,k \in \naturals} \binom{j+k}{j} q^j (pq)^k p^2 
       & \text{(by~(\ref{prs}))}\\
& =  p^2 \sum_{n \in \naturals}\ \sum_{0 \le j \le n}
        \binom{n}{j} q^j (pq)^{n-j}
      & \text{(factor $p^2$ and sum over $i+j=n$)}\\
& = p^2 \sum_{n=0}^{\infty} (q + pq)^n
     & \text{(Binomial Theorem)}\\
& = p^2 \sum_{n=0}^{\infty} (1-p + p(1-p))^n
     & (q = 1-p)\\
& = p^2 \sum_{n=0}^{\infty} (1-p^2)^n\\
& = p^2 \left(\frac{1}{1-(1-p^2)}\right)
       & \text{(sum of geometric series)}\\
& = p^2 \cdot (\frac{1}{p^2}) = 1.
\end{align*}
}

\ppart Does your probability space model the possibility of flipping an
infinite sequence of Tails?  If so, what is the probability of this event,
and what would happen if you removed this event?  If not, how do you
justify leaving it out?

\solution{
The probability space above does not have an event corresponding to
flipping Tails forever.  Nevertheless, it is a legitimate probability space
according to the formal definitions because the probabilities of the
``successful'' outcomes already sum to 1.  We could also add an outcome or
outcomes corresponding to flipping forever, but since the probabilities of
the successful events that end with $\texttt{HH}$ is already total 1, the
probability assigned to any flip-forever outcomes must be zero.

How do we select the ``right'' probability space in this case?  In fact,
could it be that both of these spaces or wrong?  There is no mathematical
way to settle this question.  The spaces described here are mathematically
well-formed probability spaces, and ``rightness'' or ``wrongness'' is not
meant in a mathematical sense but in an empirical (experimental) sense.
Namely, can we use it to predict the results of actual coin flipping?

This is actually a subtle, and philosophically controversial, question,
since there is no experimental observation that could prove the model was
wrong.  For example, if in some experiment we flipped 1000 Tails before
flipping a two Heads in a row, we still can't say that this \emph{proves}
we have chosen the wrong probability space, because the observation of 1000
tails to start is \emph{possible} in our model, just very unlikely.  In
practice, if we saw 1000 Tails in row, we would reject the model.}


\eparts

\end{problem}

%recycled from F01 ps10

\begin{problem}
All our probability identities continue to hold when all probabilities are
conditioned on the same event.  For example,
\begin{equation}\tag{Inclusion-Exclusion}
\pr{A \union B} = \pr{A} + \pr{B} - \pr{A \intersect B}
\end{equation}
becomes
\begin{equation}\tag{Conditional Inclusion-Exclusion}
\prcond{A \union B}{C} = \prcond{A}{C} + \prcond{B}{C} - \prcond{A \intersect B}{C}.
\end{equation}
Such identities carry over because for any event $C$, we can define a new
probability measure, $\prsub{}{C}$ on the same sample space by the rule
that
\begin{definition}
\label{defprs}
\[
\prsub{A}{C} \eqdef \prcond{A}{C}.
\]
\end{definition}
Now the conditional-probability version of an identity is just an instance
of the original identity using the new probability measure.  Prove that
for any probability space, $\sspace$, and event $C \subseteq
\sspace$, the function $\prsub{}{C}$ is another probability measure on
$\sspace$.  \hint Review the definition of a probability space in
\hyperref{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln9.pdf}
{ln9}{probsp}{Notes 9, Definition 5.2}.
\end{problem}

\solution{The sample space for the new probability space has not changed.
We must just show that the new probability function $\prsub{C}{}$
still satisfies the two conditions required of a probability measure.

\begin{enumerate}
\item 
To show this:
\begin{align*}
\prsub{S}{C} &= \prcond{S}{C} & \text{Definition~\ref{defprs} of $\prsub{}{C}$}\\
             &= \frac{\pr{S \cap C}}{\pr{C}} & \text{Definition of $\prcond{C}{S}$}\\
             &= \frac{\pr{C}}{\pr{C}} & \text{since $C \subseteq S$}\\
             &= 1 & \text{since $\pr{C} \neq 0$.}
\end{align*}

\item
The Sum Rule can be verified as follows:
\begin{align*}
\prsub{\lgunion_{i\in\naturals}A_i}{C}
    &= \prcond{\lgunion_{i}A_i}{C} &
          \text{Definition~\ref{defprs} of $\prsub{}{C}$}\\\\
    &= \frac{\pr{(\lgunion_{i}A_i) \cap C}}{\pr{C}} &
           \text{Definition of $\prcond{\cdot}{C}$}\\
    &= \frac{\pr{\lgunion_{i}(A_i \cap C)}}{\pr{C}}&
             \text{distributive law}\\
    &= \sum_{i} \frac{\pr{A_i \cap C}}{\pr{C}} & \text{Sum Rule}\\
    &=  \sum_{i} {\prcond{A_i}{C}} &
           \text{Definition of $\prcond{\cdot}{C}$}\\\\
    &= \sum_{i} {\prsub{A_i}{C}}.&
          \text{Definition~\ref{defprs} of $\prsub{}{C}$}
\end{align*}

\end{enumerate}
}



%source: spring00 ps8
\begin{problem}
A biased coin has probability $p$ of heads and probability $1-p$ of tails.
Suppose we flip this coin $n$ times.

\begin{problemparts}

\problempart For what values of $k$ is the probability of getting exactly
$k$ heads greater than the probability of getting exactly $k-1$ heads?
For what values of $k$ is it less?  What value of $k$ is the most likely
number of heads?

\solution{Consider the ratio of the probability of $k$ heads over the
probability of $k-1$ heads.

\begin{align*}
\frac{ \tbinom{n}{k} p^k (1-p)^{n-k}}{\tbinom{n}{k-1} p^{k-1}(1-p)^{n-k+1}}
&= \frac{\cfrac{n!}{k!(n-k)!} p}{\cfrac{n!}{(k-1)!(n-k+1)!} (1-p) } \\
&= \frac{ (n-k+1) p}{k (1-p)}
\end{align*}

This quantity is greater than 1 if and only if $(n-k+1)p>k(1-p)$.
Simplifying, we have $np+p>k$.  So, for $k<np+p$ the probability increases
as $k$ increases, and for $k>np+p$, the probability decreases as $k$
increases.  The value of $k$ the maximizes the probability is thus
$\lfloor np+p \rfloor$.}

\problempart
Show that if $p=1/n$ then the probability of getting no heads
$\longrightarrow 1/e$ as $n \longrightarrow \infty$.

\solution{
The probability of no heads is $(1-p)^n= (1-1/n)^n$.  For
large $n$, this expression approaches $1/e$.  

The probability of exactly one head is $\binom{n}{1}p(1-p)^{n-1} =
(1-1/n)^{n-1}$.  Forming the ratio, we find the probability of
no heads over the probability of exactly one head is $1-1/n$,
which is the probability of a tail. 
}
\end{problemparts}
\end{problem}


\begin{problem}
For any event, $A$, let $A^{(1)} \eqdef A$ and $A^{(-1)} \eqdef \bar{A}$.  Prove that events $A,B,C$ are mutually independent iff 

\begin{equation}
\pr{A^{(x)}}\pr{B^{(y)}}\pr{C^{(z)}} = \pr{A^{(x)} \cap B^{(y)} \cap C^{(z)}}
\end{equation}

for all $x,y,z \in {1,-1}$.

\emph{Note:} For this problem, do not use Theorem 12.3 of the Course
Notes without proof.  Feel free to prove the theorem and then apply
it.

\solution{Since we are asked to show an if and only if, we must prove this
in both directions.

First, we will show that if events $A,B,C$ are mutually independent, then
the above equation holds.  Let's consider all the possible combinations
for $(x,y,z)$ (there are 8 total).

\emph{(1,1,1)}:  This follows directly since $A,B,C$ are mutually independent.

\emph{(1,1,-1)}:  This can be shown as follows:
\begin{align*}
\pr{A^{(1)} \cap B^{(1)} \cap C^{(-1)}} 
&= \pr{A \cap B \cap \bar{C}} &
        \text{definition of $A^{(1)}$ and $A^{(-1)}$}\\
&= \pr{A \cap B} - \pr{A \cap B \cap C} &
        \text{see below}\\
&= \pr{A}\pr{B} - \pr{A}\pr{B}\pr{C} &
        \text{$A,B,C$ are mutually independent}\\
&= \pr{A}\pr{B}(1-\pr{C}) & \\
&= \pr{A}\pr{B}\pr{\bar{C}} &
        \text{complement rule}
\end{align*}
The event we are interested in is when events A and B happen, but C does
not.  This is the same as the event where A and B happen, but then we need
to subtract out the case when A, B, and C happen.  This will leave us with
the event that A and B happen, but C does not.  This can be easily
verified with a Venn Diagram.

\emph{(1,-1,1)}: similar to (1,1,-1) case.

\emph{(1,-1,-1)}: This can be shown as follows:
\begin{align*}
\lefteqn{\pr{A^{(1)} \cap B^{(-1)} \cap C^{(-1)}}}\\
&= \pr{A \cap \bar{B} \cap \bar{C}} &
        \text{definition of $A^{(1)}$ and $A^{(-1)}$}\\
&= \pr{A} - \pr{A \cap (B \cup C)} &
        \text{see below} \\
&= \pr{A} - (\pr{A \cap B} - \pr{A \cap C} + \pr{A \cap B \cap C}) & 
        \text{inclusion-exclusion} \\
&= \pr{A} - \pr{A}\pr{B} - \pr{A}\pr{C}\\
& \quad + \pr{A}\pr{B}\pr{C} &
        \text{$A,B,C$ are mutually independent}\\
&= \pr{A}(1-\pr{B}-\pr{C}+ \pr{B}\pr{C} &
        \text{algebra} \\
&= \pr{A}(1-\pr{B})(1-\pr{C})&
        \text{algebra} \\
&= \pr{A}\pr{\bar{B}}\pr{\bar{C}} &
        \text{complement rule}
\end{align*}
The event we are interested in is when A happens, but B and C do not.  We
can rewrite this as the event A but we need to subtract out the events
that also also in B or C.  To get this, we can use inclusion exclusion.
This is also easily verifiable via Venn Diagram.

\emph{(-1,1,1)}: similar to (1,1,-1) case. 

\emph{(-1,1,-1)}: similar to (1,-1,-1) case.

\emph{(-1,-1,1)}: similar to (1,-1,-1) case.

\emph{(-1,-1,-1)}: This can be shown as follows:
\[\begin{array}{rclr}
\lefteqn{\pr{A^{(-1)} \cap B^{(-1)} \cap C^{(-1)}} }\\
&=& \pr{\bar{A} \cap \bar{B} \cap \bar{C}} & 
        \text{definition of $A^{(\pm 1)}$}\\
&=& \pr{\bar{A \cup B \cup C}} & 
        \text{DeMorgan's} \\
&=& 1-\pr{A \cup B \cup C} &
        \text{complement rule} \\
&=& 1-(\pr{A}+\pr{B}+\pr{C} \\
        && - \pr{A \cap B}-\pr{A \cap C} \\
        && -\pr{B \cap C}+ \pr{A \cap B \cap C}) & 
        \text{inclusion exclusion} \\
&=& 1-\pr{A}-\pr{B}-\pr{C}\\
        && + \pr{A}\pr{B}+\pr{A}\pr{C} \\
        && +\pr{B}\pr{C} - \pr{A}\pr{B}\pr{C}) & 
        \text{mutual independence} \\
&=& (1-\pr{A})(1-\pr{B}-\pr{C} \\
        && +\pr{A}\pr{B}) &
        \text{algebra} \\
&=& (1-\pr{A})(1-\pr{B})(1-\pr{C}) &
        \text{algebra} \\
&=& \pr{\bar{A}}\pr{\bar{B}}\pr{\bar{C}} &
        \text{complement rule}
\end{array}
\]

Now, for the other direction, we must show that if we assume the equation
above is true for all $x,y,z \in {-1,1}$, then $A,B,C$ are mutally
independent.  The following must be shown for mutual independence:
\begin{eqnarray*}
\pr{A_1 \cap A_2} & = & \pr{A_1} \cdot \pr{A_2} \\
\pr{A_1 \cap A_3} & = & \pr{A_1} \cdot \pr{A_3} \\
\pr{A_2 \cap A_3} & = & \pr{A_2} \cdot \pr{A_3} \\
\pr{A_1 \cap A_2 \cap A_3} & = & \pr{A_1} \cdot \pr{A_2} \cdot \pr{A_3}
\end{eqnarray*}

Let's take $\pr{A_1 \cap A_2} = \pr{A_1} \cdot \pr{A_2}$.  We will rewrite the left side as some combination of intersections of events $A,B,C$ and their complements.   We can show that this is true as follows:

\begin{align*}
\pr{A \cap B} 
&= \pr{A \cap B \cap C} + \pr{A \cap B \cap \bar{C}} &
        \text{law of total probability} \\
&= \pr{A}\pr{B}\pr{C} +\pr{A}\pr{B}\pr{\bar{C}} &
        \text{(x,y,z)=(1,1,1) and (1,1,-1)} \\
&= \pr{A}\pr{B}(\pr{C}+\pr{\bar{C}}) &
        \text{algebra} \\
&= \pr{A}\pr{B} 
\end{align*}

The next two can be proven in symmetric ways.  What is left to prove is
the last statement.  This is obvious if we plug in $(x,y,z)=(1,1,1)$ into
the equation.

Now, while the above approach works, it is rather long and tedious.  Here
is a lemma that makes everything follow quite nicely:

\begin{lemma*}
$A_1,A_2,A_3,\dots,A_n$ are mutually independent iff
$\bar{A_1},A_2,A_3,\dots,A_n$ are mutually independent.
\end{lemma*}

\begin{proof}
$A_1,A_2,A_3,\dots,A_n$ are mutually independent

iff $A_1$ is independent of $\lgintersect_{j \in J} A_j$ for all $J
\subseteq \set{2,\dots,n}$ (by first def of Independence in Notes 9)

iff $\bar{A_1}$ is independent of $\lgintersect_{j \in J} A_j$
         for all $J \subseteq \set{2,\dots,n}$
        (from Class Problems 9-3, Problem 2 and Notes 9, Lemma 10.4)

iff $\bar{A_1},A_2,A_3,\dots,A_n$ are mutually independent
         (by first def of Independence in Notes 9).
\end{proof}

Now the whole Theorem follows straightforwardly by applying this Lemma
with $A_1^{(x_1)},\dots,A_n^{(x_n)}$ substituted for
$A_1,A_2,A_3,\dots,A_n$.
}
\end{problem}

\end{document}                            
