\problemdata                                                             
        {probability-conditional-2} % latex-friendly label for the prob.
        {Conditional Probability, Structural Induction, Probability K-Events} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S02 PS9} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
\newcommand{\heads}[1]{\card{#1}_{\texttt{H}}}
\newcommand{\tails}[1]{\card{#1}_{\texttt{T}}}
\newcommand{\nhh}{\textup{NoHH}}
                                                                         
\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.

\begin{problemparts}

\problempart{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$.  
}

\end{problemparts}

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$.

\begin{problemparts}

\problempart \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*}
}

\problempart 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.}


\end{problemparts}

\end{problem}