\documentclass[12pt,twoside]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\graphicspath{{../problemRepository/figs/}}
\usepackage{amsmath}
\usepackage{psfig}  
\input{../handouts/macros-course}
\newcommand{\cross}{\times}
\newcommand{\eqdef}{\mathbin{::=}}
\newcommand{\ignore}[1]{}

%\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}
\renewcommand{\labelenumi}{\arabic{enumi})}  
\setlength{\itemsep}{0cm}

%\newcommand{\solution}[1]{}
%\renewcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\askaboutsolutions

\begin{document}
\handout{tut10}{Mini-Quiz 10}{April 20, 2001}
\begin{enumerate}
\item Your name:
\item What is the probability that a five-card poker hand contains the
two of diamonds, the three of spades, the six of hearts, the ten of
clubs, and the king of hearts?
\end{enumerate}
\newpage
\thispagestyle{empty}
\mbox{}
\setcounter{page}{0}
\newpage
\handout{tut10}{Tutorial 10 Problems}{April 20, 2001}
\begin{problems} 

\problem{\bf Warm-up}

A Dungeons and Dragons player rolls several dice and sums the results
to determine how many points of damage his warrior does to a
fire-breathing dragon.  If the warrior does $20$ or more points of
damage, then the dragon is slain.  If the warrior does fewer than $20$
points of damage, then the dragon survives and makes a nice pot-roast
out of the warrior.  What is the probability that the warrior survives
if:

\bparts
\ppart The player rolls two 12-sided dice.
\solution{${15}/{12^2} = 0.104$. (We're counting the number of dice
rolls with sum $\ge20$. The first die must be $\ge 8$. If it's $8$,
there's $1$ possibility for the second die; if $9$, $2$ possibilities,
up to if $12$, $5$ possibilities for a total of $15$.)}
\ppart The player rolls three 8-sided dice.
\solution{$35/8^3 = 0.068$. (We're counting the number of dice rolls
with sum $\ge20$. The first die must be $\ge 4$. If it's $4$, there's
$1$ way to choose the other dice; if it's $5$, $1+2$ ways, up to if
$8$, $1+2+3+4+5$ ways, for a total of $35$.)}
\eparts


\problem 
Suppose that {\em Let's Make a Deal} is modified
so that there are four doors.  As before, a prize is hidden behind one
door.  The contestant picks a door, Carol opens a different door to
reveal no prize, and then the contestant is allowed to stay with his
or her original door or to pick one of the other two that are still
closed.  If the contestant chooses the door concealing the prize in
this second stage, then he or she wins it.

\begin{problemparts}

\problempart Contestant Stu, a sanitation engineer from Trenton, New Jersey,
stays with his original door.  What is the probability that he wins
the prize?

\solution{Stu guesses the right door initially with probability
$\frac{1}{4}$ and guesses the wrong door with probability
$\frac{3}{4}$.  If he was right initially, then he surely wins the
prize.  If he was wrong initially, then he surely does not win the
prize.  Therefore, his probability of winning is $\frac{1}{4} \cdot 1
+ \frac{3}{4} \cdot 0 = \frac{1}{4}$.
}

\problempart Contestant Zelda, an alien abduction researcher from Helena,
Montana, randomly picks one of the other two doors with equal
probability.  What is the probability that she wins the prize?

\solution{Zelda also guesses the right door initially with probability
$\frac{1}{4}$ and guesses the wrong door with probability
$\frac{3}{4}$.  If she was right initially, then she can not win.  If
she was wrong initially, then she wins with probability $\frac{1}{2}$.
Therefore, her probability of winning is $\frac{1}{4} \cdot 0 +
\frac{3}{4} \cdot \frac{1}{2} = \frac{3}{8}$.
}

\end{problemparts}

\ignore{
\problem 
We know 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{
\textbf{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{

\textbf{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{

\textbf{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 Consider 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 are 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}.

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

\solution{

\textbf{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.
\]

}

\ignore{\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{

\textbf{Solution:}\\
\begin{proof}
\[\begin{array}{rcll}
\prob{A \intersect B \intersect C}
    & = & 1 - \prob{\bar{A} \union \bar{B} \union \bar{C}} 
          & \mbox{DeMorgan's Law}\\
    & \geq & 1 - (\prob{\bar{A}}+ \prob{\bar{B}} + \prob{\bar{C}}
                & \mbox{by Boole's Inequality}\\
    & = & \prob{A} + \prob{B} + \prob{C}) - 2 & 
\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}

\problem
Consider a game in which three players work as a team. For each player, a red
hat or a blue hat is chosen randomly, each with probability 1/2. Each player
can see the other two players' hats, but not his own. No communication of any
kind is allowed among the players (except for agreeing on strategy, before
the hats are chosen).

The game proceeds with each player making a move simultaneously. The move
consists of either guessing the player's own hat color, or refusing to guess.
The team wins if at least one player guesses, and all guesses are correct;
otherwise the team loses.

\bparts
\ppart
Design the best strategy you can for the players, where the quality of
a strategy is measured by the probability that the team wins, and find
this probability for the strategy you design.

\solution{
The strategy is the same for all players: if the two hats a player can
see are the same color, he guesses that his hat is the other color.
If they're different colors, he doesn't guess. 

To see how well the strategy works, consider the eight
possible hat assignments for players 1, 2, and 3. Of these, two (RRR
and BBB) have all hats the same color. In this case (which occurs with
probability 2/8=1/4), the strategy fails. The other six possibilities
(BBR, BRB, BRR, RBB, RBR, RRB) all have two hats of the same color and
one of the other color. In this case exactly one player (the one with
the one hat of the other color) will see two hats of the same color,
and this player guesses correctly, so the strategy succeeds. This case
occurs with probability 6/8=3/4, and is the only case where success
occurs, so the probability of success is 3/4.
}
\ppart
Show that no better strategy is possible.

\solution{
Assume for contradiction that there's a strategy with success
probability $>3/4$. A strategy can be viewed as a function from the
set of 8 hat assignments (ordered triples of colors) to the set of
responses by the 3 players (ordered triples of elements of \{red,
blue,none\}). 

Denote by $r$ the number of hat assignments which map
to sets of responses such that at least one guess is included and all
guesses are correct (i.e. hat assignments for which the strategy
works).
 Denote by $w$ the number of hat assignments which
map to sets of responses having no guess or some wrong guess
(i.e. hat assignments for which the strategy fails). By
assumption $r>3w$. 

Now denote by $g_r$ the total number of guesses over all hat
assignments for which the strategy works, and denote by $g_w$ the
total number of guesses over all hat assignments for which the
strategy fails. Since $r>3w$, $g_r>3w$ (at least one right guess per
successful hat assignment). But $g_w\le 3w$ (at most 3 guesses per
wrong hat assignment since there are 3 players). Thus $g_r>g_w$.

We can show that $g_r=g_w$ and get a contradiction by counting the
total number of guesses. The way to do it is to add up the guesses in 
pairs---any guess made by a player $A$ for a given hat assignment $H$ will
also be made by $A$ for the hat assignment obtained by taking $H$ and
choosing the other color for $A$, and will be wrong in one case and
right in the other. Thus $g_r=g_w$, contradicting $g_r>g_w$.
}
\eparts

\problem
Suppose you are given a biased coin (probability of heads $p$ with $p$
not necessarily 1/2). Can you devise a procedure to simulate a {\em
fair} coin-flip using the biased coin?

\solution{
Flip the biased coin twice. If the results are the same for the two
flips, continue making two flips of the biased coin until the results
differ. Then say a ``head'' is when the two flips are HT and a
``tail'' is when they're TH. (Unfortunately uses conditional
probability, which we're not up to yet. $p(1-p)=(1-p)p$ and each
divided by their sum (the conditional probability of HT or TH given
it's one of each) is $1/2$.)
}
\end{problems}

\end{document}











