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

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\newcommand{\sspace}{\mathcal{S}}


\begin{document} 
\inclassproblems{9W}

\begin{problem}
Smith and Wesson are shooting at a target.  Suppose Smith's chance of
hitting the target is double that of his friend Wesson, and the
probability that at least one of them hits the target is $\frac{1}{2}$.
What is the probability that Wesson hits the target?  (Assume the event
that one hits the target is independent of the event that the other hits
the target.)

\solution{Let $S$ be the event that Smith hits, and let $W$ be the
even that Wesson hits.  We are given two facts:
\begin{eqnarray}
\pr{S}      & = &   2 \pr{W} \label{f1}\\
\pr{S \cup W}   & = &   \frac{1}{2}\label{f2}
\end{eqnarray}

Expanding the second equation using inclusion-exclusion gives:
\begin{align}
\frac{1}{2} & =  \pr{S \cup W} & \text{by~(\ref{f2})}\\
& = \pr{S} + \pr{W} - \pr{S \cap W} & \text{(inclusion-exclusion)}\\
& = \pr{S} + \pr{W} - \pr{S} \cdot \pr{W}   & \text{by independence}\\
& = 2 \pr{W} + \pr{W} - 2 \pr{W} \cdot \pr{W} & \text{by~(\ref{f1})}
\end{align}
Hence,
\begin{equation}\label{quad}
3 \pr{W} - 2 \pr{W}^2 - \frac{1}{2} = 0.
\end{equation}
Equation~(\ref{quad}) is a quadratic in $\pr{W}$; only one of its roots
makes lies between 0 and 1 and so makes sense as a probability, namely,
\[
\frac{3}{4} - \frac{1}{4} \sqrt{5} \approx 0.19.
\]}

\end{problem}


\begin{problem} 
Suppose there is a system with $n$~components, and we know from past
experience that any particular component will fail in a given year with
probability~$p$.  That is, letting $F_i$ be the event that the $i$th
component fails within one year, we have
\[
\pr{F_i} = p
\]
for $1 \leq i \leq n$.  The \emph{system} will fail if \emph{any one} of
its components fail.  What can we say about the probability that the
system will fail within one year?

Let $F$ be the event that the system fails within one year.  Without any
additional assumptions, we can't get an exact answer for $\pr{F}$.
However, we can give useful upper and lower bounds, namely,
\begin{equation}\label{pFnp}
p \le \pr{F} \le np.
\end{equation}
So for example, if $n = 100$ and $p = 10^{-5}$, we conclude that
there is at most one chance in 1000 of system fail within a year and at
least one chance in 100,000.

\bparts
\ppart Prove the inequality~(\ref{pFnp}).

\solution{
$F = \lgunion_{i=1}^n F_i$ so
\begin{align}
p & = \pr{F_1} & \text{(given)}\\
& \le \pr{\lgunion F_i} & \text{(monotonicity)}\\
& \le \sum_{i=1}^n \pr{F_i} & \text{(Boole's inequality)}\\
& = np.
\end{align}
Here, \emph{monotonicity}, refers to the obvious fact that
\[
A \subseteq B \implies \pr{A} \le \pr{B}.
\]
}

\eparts

Let's model this situation with the sample space $\sspace \eqdef
\power(\set{1, \dots,n})$ of subsets of positive integers $\le n$, where
$s \in \sspace$ corresponds to the numbers of the components which fail
within one year.  That is, $\set{2, 5}$ is the outcome that the second and
fifth components failed within a year and none of the other components
failed.  So the outcome that the system did not fail corresponds to the
emptyset, $\emptyset$.

\bparts

\ppart Show that the probability that the system fails could be as small
as $p$ by describing appropriate probabilities for the sample points.

\solution{There could be a probability $p$ of system failure if the all
individual failures occur together.  That is, let $\pr{\set{1, \dots,n}}
\eqdef p$, $\pr{\emptyset} \eqdef 1-p$, and let the probability of all
other outcomes be zero.  So $F_i = \set{s \in \sspace \suchthat i \in s}$
and $\pr{F_i} = 0 + 0 + \dots + 0 + \pr{\set{1, \dots,n}} = \pr{\set{1,
\dots ,n}} = p$.  Also, the only outcome with positive probability in $F$
is $\set{1, \dots ,n}$, so $\pr{F} = p$, as required.}

\ppart Show that the probability that the system fails could actually
could be as large as $np$ by describing appropriate probabilities for the
sample points.

\solution{Suppose at most one component ever fails at a time.  That is,
$\pr{\set{i}}=p$ for $1 \le i \le n$, $\pr{\emptyset}=1-np$, and
probability of all other points is zero.  The sum of the probabilities of
all the points is one, so this is a well-defined probability space.  Also,
the only sample point in $F_i$ with positive probability is $\set{i}$, so
$\pr{F_i} = \pr{\set{i}} = p$ as required.  Finally, $\pr{F} = np$ because
$F$ contains all the $n$ outcomes of the form $\set{i}$.}

\eparts
\end{problem}


%nikos
%TUT10s - last used Spring 99 Tutorial 11, Problem 2
%LEARNING OUTCOMES:8 (calculate probabilities)
%                  10 (study in a small group)
%New problem added this term

\begin{problem}
You are organizing a neighborhood census and instruct your census takers
to knock on doors and note the sex of any child that answers the knock.
Assume that there are two children in a household and that girls and boys
are equally likely to be children and to open the door.

A sample space for this experiment has outcomes that are triples whose
first element is either \texttt{B} or \texttt{G} for the sex of the elder
child, likewise for the second element and the sex of the younger child,
and whose third coordinate is \texttt{E} or \texttt{Y} indicating whether
the \emph{e}lder child or \emph{y}ounger child opened the door.  For
example, $(\mathtt{B},\mathtt{G},\mathtt{Y})$ is the outcome that the elder
child is a boy, the younger child is a girl, and the girl opened the door.

\bparts

\problempart Let \emph{T} be the event that the household has two girls,
and \emph{O} be the event that a girl opened the door.  List the outcomes
in \emph{T} and \emph{O}.

\solution{$T=\set{GGE,GGY}, O=\set{GGE,GGY,GBE,BGY}$}

\ppart What is the probability $\prcond{T}{O}$, that both children are
girls, given that a girl opened the door?
\solution{1/2}

\problempart Where is the mistake in the following argument?

\begin{quote}
If a girl opens the door, then we know that there is at least one girl in
the household.  The probability that there is at least one girl is
\begin{equation}
1 - \prob{\text{both children are boys}} = 1 - (1/2 \times 1/2) = 3/4.
\end{equation}
So,
\begin{eqnarray}
\lefteqn{\prcond{T}{\text{there is at least one girl in the household}}}\\
& = & \frac{\prob{T \intersect \text{there is at least one girl in the household}}}
{\pr{\text{there is at least one girl in the household}}}\\
& = & \frac{\prob{T}}{\pr{\text{there is at least one girl in the household}}}\\
& = & (1/4) / (3/4) = 1/3.
\end{eqnarray}
Therefore, given that a girl opened the door, the probability that there
are two girls in the household is \textup{1/3}.
\end{quote}

\solution{The argument is a correct proof that 
\[
\prcond{T}{\text{there is at least one girl in the household}} = 1/3.
\]
The problem is that the event, $H$, that the household has at least one girl,
namely,
\[
H \eqdef \set{\mathtt{GGE,GGY,GBE,GBY,BGE,BGY}},
\]
is not equal to the event, \emph{O}, that a girl opens the door.  These
two events differ:
\[
H-O = \set{\mathtt{BGE,GBY}},
\]
and their probabilities are different.  So the fallacy is in the final
conclusion where the value of $\prcond{T}{H}$ is taken to be the same as
the value $\prcond{T}{O}$.  Actually, $\prcond{T}{O} = 1/2$.  }

\eparts
\end{problem}

\begin{problem}

\bparts

\ppart Suppose you repeatedly flip a fair coin until you see the sequence
\texttt{HHT} or the sequence \texttt{TTH}.  What is the probability you
will see \texttt{HHT} first? \hint Symmetry between Heads and Tails.

\solution{In this case the answer is $1/2$.  The proof is by a bijection
argument on the sample space.  Let $A$ denote the event that you see
\texttt{HHT} before \texttt{TTH}, and $B$ denote the event that you see
\texttt{TTH} before \texttt{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 \texttt{H} is replaced by a
\texttt{T} and vice versa.  For example $g(\mathtt{HHT}) =
\overline{\mathtt{HHT}} = \mathtt{TTH}$.

To show that $g$ is a bijection, we first observe that $g:A \rightarrow
B$.  This follows from the fact that \texttt{HHT} precedes \texttt{TTH} in
$w$ iff $\overline{\mathtt{HHT}} = \mathtt{TTH}$ precedes
$\overline{\mathtt{TTH}} = \mathtt{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 $\prob{w} = \prob{g(w)}$ for any $w$.  This is because
$\prob{\mathtt{H}} = \prob{\mathtt{T}}$ and $g(w)$ has the same length as
$w$.  Hence,
\[
\prob{A} = \sum_{w \in A} \prob{w} = \sum_{w\in A} \prob{g(w)}
= \sum_{w' \in B} \prob{w'}  =  \prob{B}.
\]
The second equality is valid because $g$ preserves the probability, and
the third by the bijection property with $w' = g(w)$.  Note that the fact
that \texttt{H} and \texttt{T} are equally likely is critical in these
calculations; this analysis would fail for a biased coin.

Finally we have to show that $\prob{A \cup B} = 1$.  This follows from the
fact that the only way never to throw either pattern is to throw all
\texttt{H}'s or all \texttt{T}'s after the first toss, and we know that
the probability of there being an unbounded number of tosses of only H or
only T is zero.  That is, $\prob{\overline{A \cup B}} = 0$ and so $\prob{A
\cup B} = 1$.  Since $A$ and $B$ are disjoint, this means that $\prob{A} +
\prob{B} = 1$ and hence
\[
\prob{A} = \frac{1}{2}.
\]
}

\ppart What is the probability you see the sequence \texttt{HTT} before
you see the sequence \texttt{HHT}?
\hint Try to find the probability that \texttt{HHT} comes before
\texttt{HTT} conditioning on whether you first toss an \texttt{H} or a
\texttt{T}.  The answer is not $1/2$.

\solution{
\iffalse

First, we intuitively see that HHT is more likely than HTT,
because the sequence HHTT has HHT right one toss before HTT
so the appearance of HTT depends in a way in the appearance
of HHT before it. The inverse does not hold, since throwing
HHT is independent of HTT coming before it.
\fi

Let $A$ be the event that \texttt{HTT} appears before \texttt{HHT}, and let
$p \eqdef \prob{A}$.

Suppose our first toss is \texttt{T}.  Since neither of our patterns
starts with \texttt{T}, the probability that $A$ will occur from this
point on is still $p$.  That is, $\prcond{A}{\mathtt{T}} = p$.

Suppose our first toss is \texttt{H}.  To find the probability that $A$
will now occur, that is, to find $q \eqdef \prcond{A}{\mathtt{H}}$, we
consider different cases based on the subsequent throws.

Suppose the next toss is \texttt{H}, that is, the first two tosses are
\texttt{HH}.  Then neither pattern appears if we continue flipping
\texttt{H}, and when we eventually toss a \texttt{T}, the pattern
\texttt{HHT} will then have appeared first.  So in this case, event $A$
will never occur.  That is $\prcond{A}{\mathtt{HH}} = 0$.

Suppose the first two tosses are \texttt{HT}.  If we toss a \texttt{T}
again, then we have tossed \texttt{HTT}, so event $A$ has occurred.
If we next toss an \texttt{H}, then we have tossed \texttt{HTH}.  But this
puts us in the same situation we were in after rolling an \texttt{H} on
the first toss.  That is, $\prcond{A}{\mathtt{HTH}} = q$.

Summarizing this we have:
\begin{align}
\pr{A} &=
\prcond{A}{\mathtt{T}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{H}}\pr{\mathtt{H}}
& \text{(Law of Total Probability)}\\
p & = p\frac{1}{2} + q\frac{1}{2} & \text{so}\\
p & = q.\label{peq}
\end{align}

Continuing, we have
\begin{align}
\prcond{A}{\mathtt{H}} &=
\prcond{A}{\mathtt{HT}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{HH}}\pr{\mathtt{H}} &
\text{(Law of Total Probability)}\\
q &= \prcond{A}{\mathtt{HT}}\frac{1}{2} + 0\cdot\frac{1}{2}\label{here}\\
\prcond{A}{\mathtt{HT}} & =
\prcond{A}{\mathtt{HTT}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{HTH}}\pr{\mathtt{H}}
& \text{Law of Total Probability}\\
\prcond{A}{\mathtt{HT}} & = 1\cdot\frac{1}{2} + q\frac{1}{2} \label{there}\\
q & = (\frac{1}{2} + \frac{q}{2})\frac{1}{2} & \text{by~(\ref{here}) \&~(\ref{there})}\\
q & = \frac{1}{3}.
\end{align}

So \texttt{HTT} comes before \texttt{HHT} with probability $p=q =\cfrac{1}{3}$.

It is an amazing fact that these kind of events are another example of
\emph{intransitivity} of the kind we saw with some
\hyperref{http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln9.pdf}
{ln9}{intrans-dice}{special dice in Notes 9}.  Namely, if you may pick
\emph{any} pattern of three tosses such as \texttt{HTT}, then I can pick a
pattern of three tosses such as \texttt{HHT}.  If we then bet on which
pattern will appear first in a series of tosses, the odds will be in my
favor.  In particular, even if you instead picked the ``better'' pattern
\texttt{HHT}, there is another pattern I can pick that has a more than
even chance of appearing before \texttt{HHT}.  So this intransitivity
phenomenon comes up for real---you could make money on it betting in a
bar---and not just for some contrived dice.}

\eparts
\end{problem}


\begin{problem}
Prove that if $A$ and $B$ are independent events, then so are $\bar{A}$
and $B$.

\solution{From the Law of Total Probability we have
\[
\pr{B} = \pr{B \intersect \bar{A}} + \pr{B \intersect A},
\]
so
\begin{align}
\pr{B \intersect \bar{A}} & =  \pr{B} - \pr{B \intersect A}\\
 & = \pr{B} - \pr{B}\pr{A} & \text{because $A$ and $B$ are independent}\\
 & = \pr{B}(1 - \pr{A}) = \pr{B}\pr{\bar{A}}.
\end{align}
}

\end{problem}

\instatements{
\appendix

\section{Events}

\begin{eqnarray*}
\pr{\lgunion_{n \in \naturals} A_n} & = & \sum_{n \in \naturals} \pr{A_n}
\mbox{ for pairwise disjoint } A_n\\
%\item $\pr{A-B}  & = &  \pr{A} - \pr{A \intersect B}$
%
% \item $\pr{A \intersect B}  \le  \pr{A}, \label{ab<a}$
%
\pr{\bar{B}}  & = &  1 - \pr{B} \label{1-b}\\
\pr{A \union B}  & = &  \pr{A} + \pr{B} - \pr{A \intersect B}\\
\pr{A \union B} & \leq & \pr{A}+ \pr{B} \quad \mbox{[Boole's inequality]} \\
%
%\item $\pr{\lgintersect_n A_n} \ge 1 - \sum_n \pr{\overline{A_n}}$
%
\prcond{A}{B}  & = &  \frac{\pr{A \intersect B}}{\pr{B}}\\
%\pr{A \mid B} & = & \frac{\pr{B\mid A}\pr{A}}{\pr{B}} quad \mbox{[Bayes Rule]}\\
\end{eqnarray*}

\section{Law of Total Probability}
Let $B_0, B_1, \ldots$ be disjoint events whose union is the
entire sample space.  Then for all events $A$,
\[
\pr{A} = \sum_{i \in \naturals} \pr{A \cap B_i}.
\]

\section{Independence}
\begin{definition*}
Events $A$ and $B$ are independent iff
\[
\pr{A \intersect B} = \pr{A}\pr{B}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{mutually independent} iff for all
subsets $J \subset \naturals$,
\[
\pr{\lgintersect_{i\in J} A_i} = \prod_{i \in J} \pr{A_i}.
\]

\end{definition*}
}

\end{document}
