\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{eepic}

%\usepackage{psfig}

\input{macros-course}


\begin{document}

\tutn{17}{11/18/99}{November 17, 1999}

\begin{problems}

\problem Suppose the Let's Make A Deal/Monty Hall game is changed
slightly: instead of having 3 doors with 1 grand prize, in the new game
there are 4 doors with 2 grand prizes.  The rule of the game remains the
same.  Therefore the game now becomes:

\begin{quote}
At one stage of the game, a contestant is shown 4 doors.  The contestant
knows that there are 2 grand prizes behind 2 of the doors and that there
are goats behind the 2 other doors.  At the beginning, the contestant
picks a door. To build suspense, the assistant of the game then opens a
{\em different} door, revealing a goat.  The contestant can then stick
with his original door or switch to another unopened door.  He wins a
prize only if he now picks the door with the prize.
\end{quote}

In the new game, what is the probability of winning with the ``stick''
strategy?  How about the ``switch'' strategy?  Can you explain why the two
probabilities do not sum up to 1?

\solution{

The player wins with a ``stick'' strategy iff he chooses one of the
``correct'' doors in the first place.  Therefore the probability of
winning with the ``stick'' strategy is 1/2.

To calculate the probability of winning with a ``switch'' strategy, we
could draw the tree of possibililities and add up probabilities as in
Lecture 18 Notes, but a simpler argument can be made using conditional
probability:

Let $E_1$ be the event that ``the player chooses a correct door at his
first chance''.  Let $E_2$ be the event that ``the player switches to a
correct door at his second chance''.
\begin{eqnarray*}
\prob{\mbox{winning with ``switch''
strategy}} & = & 
  \prob{E_2 \mid E_1}\prob{E_1} + \prob{E_2 \mid \overline{E_1}}\prob{\overline{E_1}}\\
& = & \frac{1}{2}\cdot\frac{1}{2}+1\cdot\frac{1}{2} = \frac{3}{4}.
\end{eqnarray*}

The two probabilities do not sum up to 1.  The reason is that at a given
sample point (location of winning prizes, location of opened door) winning
by the ``switch'' strategy does not imply losing by the ``stick''
strategy, and vice versa.  So winning by one strategy is not a disjoint
event from winning by the other strategy.

}

\problem 
We saw in lecture that
\[
\prob{A \union B}  =  \prob{A} + \prob{B} - \prob{A \intersect B}.
\]
A weaker statement known as \emph{Boole's inequality} is 
an immmediate corollary:
\[
\prob{A \union B}  \le  \prob{A} + \prob{B}.
\]

Obvious as it is, Boole's inequality can be useful.  For example, we will
use it to analyse reliability in manufacturing circuit boards.

Say that each board requires a total of $n$ wiring connections to be made
among it components.  Based on past experience, we judge that any
particular connection will be made \emph{incorrectly} with probability $p$, for
some (hopefully small) number $p$.  That is, we assume
\[
\prob{\mbox{$i^{th}$ connection is wrong}} = p
\]
for $1 \le i \le n$.  What is the probability that a circuit is wired
correctly, i.e., there are no incorrect connections?  Although we can't
give a definite answer without more information, we can still come up with
useful bounds on the probability of boards with buggy wiring.

\bparts

\ppart
Prove that if we select a circuit board at random from the assembly line, then
\[
1-p \geq \prob{\mbox{all connections on the board are OK}} \geq 1-np.
\]

\hint Let $A_i$ denote the event that connection $i$ is made
\emph{correctly}.  Now
\[
\prob{\mbox{all connections are OK}}  = \prob{\Intersect_{i=1}^n A_i}.
\]
Remember that $\prob{\overline{B}} =  1 - \prob{B}$.

\solution{
Then $\overline{A_i}$ is the event that connection $i$
is made incorrectly, so $\prob{\overline{A_i}} = p$.  Now,
\begin{eqnarray*}
1-p & = & \prob{A_1}\\
& \geq &  \prob{\Intersect_{i=1}^n A_i} \qquad\mbox{(because $A
    \subseteq A_1$ implies $\prob{A} \leq \prob{A}$)}\\
& = & 1 - \prob{\Union_{i=1}^n \overline{A_i}} \qquad\mbox{(by DeMorgan
             and the hint)}\\
& \ge & 1 - \sum_{i=1}^n \prob{\overline{A_i}} \qquad\mbox{(by Boole's Inequality)}\\
& = & 1-np.
\end{eqnarray*}
}

\eparts

So for example, if $n = 10$ and $p = 0.01$, the previous part
establishes that
\[
0.99 \geq \prob{\mbox{all connections are OK}} \geq 0.9.
\]
In other words, the chance is somewhere between 90\% and 99\% that all
connections on a board are okay.

These bounds are actually the best ones possible when the only information
available is the probability of failure of each connection.  To show why
this holds, we can model the wiring scenario with a sample space, $S$, of
binary words of length 10.  Each point $(b_1,b_2,\dots,b_{10}) \in S$
describes the bad set of connections in a circuit: $b_i= 0$ if the $i$th
connection is bad and $b_i = 1$ if it is OK.

\bparts

\ppart

Show that the probability that a circuit gets wired correctly actually
could be as high as 99\% by describing appropriate probabilities for the
sample points in $S$.

\solution{

There could be 99\% reliability if the individual errors occur
in such a way that whenever you make one connection wrong, all the
connections are wrong.

So let $\prob{(1,1,\dots, 1)} \eqdef 0.99$, $\prob{(0,0, \dots, 0)}\eqdef
0.01$, and let the probability of all other points be zero.  So $A_i =
\set{(b_1,\dots,b_{10}) \in S : b_i = 1}$.  But since except for
$(1,1,\dots,1)$, all points in $A_i$ have probability zero, we have
$\prob{A_i} = \prob{(1,1,\dots,1)} = 0.99$.

}

\ppart Show that the probability that a circuit gets wired correctly
actually could be as low as 90\% by describing appropriate probabilities
for the sample points.

\solution{

Suppose there is never more than one wrong connection.  That is,
\begin{eqnarray*}
\prob{(1,1,\dots,1)} & \eqdef & 0.9,\\
\prob{(b_1,\dots,b_{10})} & \eqdef & 0.01\text{ if } \sum_{i=1}^{10}b_i =9,\\
\prob{(b_1,\dots,b_{10})} & \eqdef & 0  \text{ otherwise}.
\end{eqnarray*}
Note that the sum of the probabilities of all these points is one, so this
is a well-defined probability space.  Also, the only sample point in
$\overline{A_i}$ with positive probability is $1^{i-1}01^{n-i}$, so
$\prob{\overline{A_i}} = \prob{1^{i-1}01^{n-i}} = 0.01$ as required.

}

\eparts


\problem Lecture 18 Notes ended with an example of three loaded dice A, B,
C with the properties
\begin{itemize}
\item Die A always comes up 3.
\item Die B is 2 with prob $p$ and 5 otherwise.
\item Die C is 4 with prob $p$ and 1 otherwise.
\end{itemize}
These were claimed to have the property that on any roll of dice A and B, the
probability that A beats B is $p = (\sqrt{5} - 1)/2 = 0.618\ldots$, on a
roll of B and C the probability that B beats C is $p$, and likewise on a
roll of C and A, the probability that C beats A is $p$.  That is, the
``probably beats'' relation on these dice is \emph{intransitive}.

\bparts
\ppart Prove the claim. \hint Note that $p$ is a root of $x^2 + x - 1$.

\solution{

It's clear that A beats B, and C beats A, each with probability $p$.

From the hint we have $1 - p^2 = p$.  Now the probability that B beats C
is
\[
\prob{\text{B rolls to 5}} + \prob{\text{B rolls to 2 and C rolls to 1}}
= (1-p) + p(1-p) = 1 - p^2 = p.
\]

}

\eparts

Can we increase this probability?  That is, can we construct dice so that
the probability of A beating B, B beating C, C beating A are each, say, at
least 3/4?  The answer is ``No.''  In fact, the probabilities cannot all
exceed 2/3.  More precisely, consider the experiment of rolling all three
dice.  Define $A$ to be the event that A beats B, $B$ the event that B
beats C, and $C$ the event that C beats A.

\bparts

\ppart Prove that
\[
\min \set{\prob{A}, \prob{B}, \prob{C}} \leq \frac{2}{3}.
\]
\hint Observe that $\prob{A \intersect B \intersect C} = 0$ and apply
Boole's Inequality to the complement.

\solution{

\begin{proof}
\[\begin{array}{rcll}
\prob{A \intersect B \intersect C}
    & = & 1 - \prob{\bar{A} \union \bar{B} \union \bar{C}} 
          & \mbox{by equation~\ref{1-b} and DeMorgan}\\
    & \geq & 1 - (\prob{\bar{A}}+ \prob{\bar{B}} + \prob{\bar{C}}
                & \mbox{by Boole's Inequality}\\
    & = & \prob{A} + \prob{B} + \prob{C}) - 2 & \mbox{by equation~\ref{1-b}}.
\end{array}\]
But $\prob{A \intersect B \intersect C} = 0$,
since it is impossible that on any single roll, die A is higher than die B,
\emph{and} B is higher than C, {\em and} C is higher than A.
Hence
\[2  \geq  \prob{A} + \prob{B} + \prob{C} \geq 3 \min \set{\prob{A},\prob{B},\prob{C}}\]
and therefore
\[2/3 \geq \min \set{\prob{A}, \prob{B}, \prob{C}}.\]
\end{proof}

\textbf{Extra Credit Problem}: Show that the 2/3 bound can be improved to $p
= (\sqrt{5} - 1)/2 = 0.618\ldots$, and that this is the minimum bound.

}

\eparts

\end{problems}

\newpage

\section*{The Sum Rule and Boole's Inequality}
\textbf{Review}: In lecture we noted
\begin{theorem}
\emph{Sum Rule for two events}
\[\prob{A \union B} = \prob{A} + \prob{B}\]
for all disjoint events $A,B$.
\end{theorem}

This first fact generalizes easily to any countable union:
\begin{theorem}\emph{Sum Rule for Events}
\[\prob{\Union_{n=0}^\infty A_n} =  \sum_{n=0}^\infty \prob{A_n}\]
for any sequence $A_0,A_1,\dots$ of pairwise disjoint\footnote{A set of
events is ``pairwise disjoint'' when the intersection of any two different
events in the set is empty.} events.
\end{theorem}

It follows that
\begin{corollary}\label{ABA-B}
\[
\prob{A} = \prob{A \intersect B} + \prob{A - B}
\]
\end{corollary}
for \emph{all} events $A, B$, from which we then can directly derive:
\begin{corollary}

\begin{eqnarray}
\prob{A-B} & = & \prob{A} - \prob{A \intersect B}, \mbox{ so} \label{a-b}\\
\prob{\bar{B}} & = & 1 - \prob{B} \label{1-b}.\\
\prob{A \union B} & = & \prob{A} + \prob{B} - \prob{A \intersect B}, \mbox{ so}\\
\prob{A \intersect B} & \le & \prob{A}, \label{ab<a} \mbox{and}\\
\prob{A \union B} & \le & \prob{A} + \prob{B}. \label{boole}
\end{eqnarray}

\end{corollary}
The last inequality~\ref{boole} is known as \emph{Boole's Inequality},
where equality holds if and only if $\prob{A \intersect B} = 0$.  Boole's
Inequality can also be extended to any countable number of events:

\begin{theorem}[Boole's Inequality]\label{infbool}
\[\prob{\Union_{n=0}^\infty A_n} \leq \sum_{n=0}^\infty \prob{A_n}.\]
\label{thm:n-union}
\end{theorem}

\end{document}
