\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}

\begin{document}

{\bf Tutorial 11 solutions}

\date{}

\begin{enumerate}
\item
If you repeatedly flip a fair coin, what is the probability you see
the sequence HTT before you see the sequence HHT (where H is a head and T
is a tail)? 


Let $A$ be the event that we see the sequence HHT before we see 
HTT. Our first observation is the following:

\begin{lemma}
$$Pr(A) = Pr(A \mid H)$$
\end{lemma}

That is, the probability of seeing HHT before HTT is the same as
the probability of seeing HHT before HTT given that we have
seen a head (H).
 
{\em Proof. }
$$Pr(A) = Pr(A \cap H) + Pr(A \cap T)$$
$$ = Pr(A \mid H) Pr(H) + Pr(A \mid T) Pr(T)$$

Now $$Pr(A \mid T) = Pr(A)$$ since for any outcome $w$ of coin tosses
$Tw \in A$ iff $w \in A$. Therefore
$$\frac{1}{2}Pr(A) = \frac{1}{2}Pr(A \mid H)$$
$$\rightarrow Pr(A) = Pr(A \mid H)$$
\qed

To evaluate $Pr(A \mid H)$ 
consider the outcomes of the two coin tosses immediately following the first
head. 
There are four possible outcomes for these two tosses: HH,HT,TH,TT.
From the result in last week's tutorial,
$$Pr(A \mid H) = Pr(A \cap HH \mid H) + Pr(A \cap HT \mid H) + Pr(A \cap TH \mid H) + Pr(A \cap TT \mid H)$$
$$ = \frac{1}{4}(Pr(A \mid HHH) + Pr(A \mid HHT) + Pr(A \mid HTH) + Pr(A \mid HTT))$$
$$ = \frac{1}{4}(Pr(A \mid HHH) + 1 + Pr(A \mid HTH) + 0)$$

Next we evaluate these terms:
\begin{lemma}
$$Pr(A \mid HHH) = 1$$
\end{lemma}
{\em Proof. }
If we ever see a T in the remaining flips, then HHT occurs before
HTT. The probability of never seeing a T is $\lim_{n \rightarrow \infty} \frac{1}{2^n} = 0$. Hence we see a T with probability 1.
\qed

\begin{lemma}
$$Pr(A \mid HTH) = Pr(A \mid H)$$
\end{lemma}

{\em Proof. }
For any string of outcomes $w$ of coin tosses,
$HTHw \in A$ iff $Hw \in A$.
\qed


Substituting in the equation,
$$Pr(A \mid H) = \frac{1}{4}(2+Pr(A\mid H))$$
That is 
$$\frac{3}{4}Pr(A \mid H) = \frac{1}{2}$$
$$\rightarrow Pr(A \mid H) = \frac{2}{3}$$
So $$Pr(A) = \frac{2}{3}$$

\item If you repeatedly flip a fair coin as above, what is the probability
that you see the sequence HHT before you see the sequence TTH ?

In this case the answer is $\frac{1}{2}$. The proof is by a bijection
argument on the sample space. Let $A$ denote the event that you see HHT
before TTH, and $B$ denote the event that you see TTH before HHT. We will
define a bijection $g$ between $A$ and $B$ so that the probability of $g(w)$ 
is equal to the probability of $w$. The bijection is quite simple.
Given a sample point $w \in A$, define $g(w) = \bar{w}$, where $\bar{w}$ 
is the outcome where every H is replaced by a T and vice versa. For example
$g(HHT) = \overline{HHT} = TTH$.
We first observe that $g:A \rightarrow B$. This follows from the
fact that HHT precedes TTH in $w$ iff $\overline{HHT} = TTH$ precedes
$\overline{TTH} = HHT$ in $\bar{w}$. And $g$ is onto by the same reasoning.
Since $g$ is clearly an injection, we can conclude that it is a bijection.

Then we observe that $Pr(w) = Pr(g(w))$ for any $w$. This is because
$Pr(H) = Pr(T)$ and $g(w)$ has the same length as $w$. (Note: this is
a critical step in probability calculations. Otherwise, step 2 below
can fail.)
Hence,
\begin{eqnarray}
Pr(A) &=& \sum_{w \in A} Pr(w) \\
&=&\sum_{w\in A} Pr(g(w))\\
&=&\sum_{w' \in B} Pr(w')\\
 = Pr(B)
\end{eqnarray}

Step 2 is valid because $g$ preserves the probability, and step 3 is
by the bijection property with $w' = g(w)$.

Finally we have to show that $Pr(A \cup B) = 1$. This follows
from the fact that 
$$\overline{A \cup B} = \{HHH\ldots, TTT\ldots, HTTT\ldots, THHH\ldots\}$$
Each of these strings has probability $0$ of occuring. 

Hence,
$$Pr(\overline{A \cup B}) = 0 \rightarrow Pr(A \cup B) = 1$$
Since $A$ and $B$ are disjoint, this means that $Pr(A) + Pr(B) = 1$ 
and hence $Pr(A) = \frac{1}{2}$.



\end{enumerate}

\end{document}

