\documentstyle[12pt,twoside]{article}
\input{macros-course}

\begin{document}

\pset{12}{May 6, 1996}{Never}

This homework is {\bf entirely optional.}  But it will be very good
practice for the final.  If you hand it in Tuesday May 12, it will be
corrected (but the grade won't count for anything).

\begin{problems}

\problem The Three-Cornered Duel.

$A$, $B$, and $C$ are to fight a three-cornered pistol duel.  They all know 
that $A$'s chance of hitting the target is $0.3$, $C$'s is $0.5$ and $B$ 
never misses.  They are to shoot in the sequence $A,B,C$ and fire at their 
choice of target until one person is left standing.  Show that $A$ is better
off missing deliberately the first shot than attempting to hit either $B$ or 
$C$.

\problem %conditional probabilities 

If you repeatedly flip a fair coin, what is the probability you see
the sequence HTT before you see the sequence HHT?  (Hint: the answer
is {\bf not} 1/2).


\problem The Prisoner's Dilemma.

Three Prisoners $A$,$B$, and $C$ have applied for parole.  The parole
board has decided to release two of the three, and the prisoners know
this but not which two.  A warder friend of prisoner $A$ knows who are
to be released.  $A$ realizes that it would be unethical to ask if he
is going to be released, but thinks of asking for the name of {\em one
  prisoner other than himself} who is to be released. Before he asks
his chances are $2/3$, but he thinks that if he asks and the warder
says ``$B$ will be released'', his own chances will become $1/2$ since
either $A$ or $C$ will be the only remaining candidates.  So $A$
decides not to reduce his chances asking.  Is $A$'s argument correct?
Show what his chances are after asking.

\problem
Show that if two events $A$ and $B$ are independent, then the events $A$ 
and $\overline B$ are also independent.

%independence 
\problem Two numbers $x$ and $y$ are selected at random from the set
 $\{1,\ldots,100\}$.  Let the events $A$, $B$ and $C$be defined
 as follows: $A = \{x > 50\}$, $B = \{y > 50\}$ and $C=\{x > y \}$.
 Are the events $A$ and $B$ independent? Are $A$ and $C$ independent?


\problem %binomial distribution
A communication system transmits binary information over a channel
that introduces random bit errors with probability $10^{-3}$.  The
transmitter transmits each information bit 5 times and a decoder
takes a majority vote of the received bits to decide on what the the
transmitted bit was. Find the probability that the receiver will make
an incorrect decision (simplify your answer to a number).


\problem Given an experiment with a fair, six-sided die, where the die
is rolled until a '6' has come up three times. \bparts

\ppart What is the
probability that at most $n$ rolls are needed?

\ppart What if the die must come up '6' three times in a row?  What is the
probability that at most $n$ rolls are needed?

\problem In a sequence of Bernoulli trials with success probability
$p$, find the probability that $a$ successes will occur before $b$
failures.

\eparts

\problem In this problem, we will prove that there is a tournament
graph with the following bizarre property: for every set of $k$ people
in the tournament, there is a certain person who has beaten all of
them---this makes it hard it identify the best $k$ players!  We'll use
a technique called the {\em probabilistic method} where you prove
something exists by showing that that the probability it exists is not
0.

Consider an $n$-vertex tournament that is generated randomly by
assigning each edge a random (equally probable) direction.

\bparts

\ppart Consider a certain set of $k$ people.  What is the probability a
particular other person beats all of them?

\ppart What is the probability that {\em nobody} beats all of them?

\ppart Using the union bound, upper bound the probability that there
is some set of $k$ people for which nobody else beats all of them?

\ppart.   Using the identities $(1-x)< e^{-x}$ and ${n \choose k} <
(en/k)^k$, simplify your answer to the previous problem.

\ppart Find the smallest $n$ (as a function of $k$) that you can for
which the above quantity is less than $1$.

\ppart Show that there is a tournament on $n$ vertices ($n$ you just
found) with the claimed bizarre property.

\eparts

\end{problems}

\end{document}


% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
