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

\addtolength{\topmargin}{-.35in}
\setlength{\textheight}{9in}

\newcommand{\problm}{\problem \rm}
\renewcommand{\ppart}{\problempart \rm}
\newcommand{\pf}{\begin{proof}\sf}
\newcommand{\soln}{\sf}
\newcommand{\thm}{\begin{theorem}\ \ }
\newcommand{\mystrut}{\rule{0pt}{14pt}}

\begin{document}

\psol{9}{November 22, 1994}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\bparts
\ppart \mbox{}
\vspace{3in}

The sum of the winning probabilities is $2/3$.


\ppart \mbox{}
\vspace{3in}

The sum of the winning probabilities is $2/3$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\bparts
\ppart
In this case, you should always pick Box 1.  Monty (Prof. Leighton)
will be forced to reveal the location of the other ``Nerd Pride'' pin.
Upon switching, you will be guaranteed to win the ice cream (i.e.
the probability of winning is 1).  If you
pick a box besides 1, Monty can always reveal Box 1 (giving you no
additional information), and you will have a 1/2 chance of winning.

\ppart
If you play the ``don't-switch strategy'', you will win whenever you
pick the correct box initially.  Thus, you will win with probability
1/3.  If you play the ``switch strategy'', you will lose every time
you initially pick the wrong box, since Monty can decide to end the game.
Everytime you pick the right box, Monty will reveal a bad box, and
then you will switch to a bad box.  Thus, you lose again.
Therefore, the probability of winning is 0 with the ``switch strategy''.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\bparts

\ppart Stick both times.

You will win only if you pick the correct box initially.
This happens with probability 1/4.

\ppart Switch both times.

You will win only if you have selected a bad box before the last
switch.  This can occur two different ways.
\begin{enumerate}
\item You first pick the good box and then switch to a bad box.
The probability of picking the good box is 1/4.
After your first switch, you will always pick a bad box.

\item You first pick a bad box (with probability 3/4) and then
switch to another bad box.  At this point, you have the choice
of switching to either the good box or another bad box.  The probability
of picking the bad box is 1/2.  Thus, the probability of this entire
event is 3/8.
\end{enumerate}

Therefore, the probability of winning with this strategy
is $1/4+3/8=5/8$.

\ppart Stick the first time, switch the second time.

Again, you will win if you have selected a bad box before the switch.
Since you sticked the first time, this occurs with probability 3/4.


\ppart Switch the first time, stick the second time.

You will win if you switch onto the good box.  In order to do this,
you must first pick a bad box (with probability 3/4) and then switch
onto the good box (with probability 1/2).  Thus, your probability of winning
is 3/8.

By comparing probabilities, it is best to ``Stick the first time, and
switch the second''.  This strategy gives you a 3/4 chance of winning.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Total number of hands is ${52 \choose 13}$.
To count the number of hands with 9 cards of the same suit,
we need to (1) choose the suit, (2) choose the 9 cards of the same suit,
and (3) choose the remaining 4 cards.
This can be done in $4{13 \choose 9}{39 \choose 4}$ ways.
Note, there is no possible double counting, since
a hand can have at most one 9-carded suit.
Thus, the probability is 
\[
\frac{4{13 \choose 9}{39 \choose 4}}{{52 \choose 13}} = 0.0003704 
%235237860/635013559600
\]

The number of hands with exactly 5 spades is ${13 \choose 5}{39 \choose 8}$,
which is the same as the number of hands with exactly 5 hearts.
However, we double counted.   The number of hands with both 5 spades
and 5 hearts is ${13 \choose 5}{13 \choose 5}{26 \choose 3}$.
Thus, the probability is 
\[
\frac{2{13 \choose 5}{39 \choose 8}-{13 \choose 5}{13 \choose 5}{26 \choose 3}}
{{52 \choose 13}} = 0.2426 %158362127352- 4306559400/635013559600=
\]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\begin{problemparts}
\problempart

For a given ticket, it will win if any of ${20 \choose 10}$ sets of
numbers are choosen.  Since there are ${80 \choose 10}$ equally likely
sets of numbers, the probability of winning is
\[
\frac{{20 \choose 10}}{{80 \choose 10}} = 0.0000001122
%184756/1646492110120
\]
We will denote this probability by ${\cal P}$.

\problempart
For the lower bound, if all of the students select the same
set of numbers,  then the probability of winning is the same as above.
Thus, the lower bound is ${\cal P}$.

For the upper bound, 
the probability of any student winning is at most the sum of
probabilities of each student winning, which is $100 {\cal P}$.


\ppart
Here, we are only concerned about the number of distinct tickets.
For an upper bound, the probability of a win is at
most the sum of the probabilities of each distinct ticket of winning
-- $k{\cal P}$.

The lower bound is more difficult to analyze.  We need to analyze
the number of distinct sets of ten numbers.  A simple lower bound
is probability of a single ticket winning -- ${\cal P}$.

\ppart
All the students could have choosen the same ticket.  In that case, if one
students wins, they all win.  Thus, a lower bound on the probability
of exactly one winner is zero.  On the other hand, the tickets
could be arranged to that no two different tickets have the same 10 numbers
choosen.  In that case, if exaclty one person can win at any given time.
The probability of a win is as in (b), $100 {\cal P}$.

\ppart
Let $s$ be the number of distinct tickets chosen by only
one person (i.e. $p_i=1$).  For there to be exactly one winner,
one of these $s$ tickets must be chosen and no other ticket wins.
This probability has an upper bound of $s{\cal P}$.
For the lower bound, it is possible that every set of 10 numbers
appears on two different tickets.  Thus, the lower bound is zero.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Let $B$ be the event the criminal has a beard.  Let $W$ be the
event the witness says the criminal has a beard.
We want to compute $Pr(B|W)$.  By Bayes's theorem,
\[
Pr(B|W)=\frac{Pr(W|B)Pr(B)}{Pr(W|B)Pr(B)+Pr(W|\overline{B})Pr(\overline{B})}
= \frac{(0.8)(.15)}{(0.8)(0.15)+(0.12)(0.85)} =0.54
\]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%	From Drake's book.
\problem \mbox{}

\begin{problemparts}
\problempart
Let $A$ be the event that Al is innocent.  Also, let $B$ and
$C$ be the events that Bo and Cy, respectively, testify that Al is
innocent.

\vspace{2in}

There is conflicting testimony when the outcomes either $B$ and $\overline{C}$
or $\overline{B}$ and $C$.
The probability of these outcomes is $(0.8)(0.2)+(0.2)(0.3)=0.22$.


\problempart
Bo commits perjury in the outcomes with ($A$ and $\overline{B}$) or
($\overline{A}$ and $B$).
Thus, his probability of committing perjury is $(0.8)(0.2)=0.16$.

Similary, Cy will commit perjury in outcomes with
($A$ and $\overline{C}$) or
($\overline{A}$ and $C$).
His probability of perjury is $(0.2)(0.3)=0.06$.

Thus, Bo is more likely to commit perjury.
\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\begin{problemparts}
\problempart
Out of the $n$ tosses, $k$ of them are heads and $n-k$ of them are
tails.  The probability of any particular sequence is $p^k(1-p)^{n-k}$.
For a sequence of $n$ coins, there are ${n \choose k}$ ways 
to pick a sequence with $k$ heads.  Thus, the probability
of exactly $k$ heads is 
\[
{n \choose k} p^k (1-p)^{n-k}
\]

\problempart
Consider the ratio of the probability of $k$ heads over the
probability of $k-1$ heads.
\begin{eqnarray*}
\frac{{n \choose k}p^k(1-p)^{n-k}}{{n \choose {k-1}}p^{k-1}(1-p)^{n-k+1}}
& = &\frac{\frac{n!}{k!(n-k)!}p}{\frac{n!}{(k-1)!(n-k+1)!(1-p)}} \\
& = & \frac{(n-k+1)p}{k(1-p)}
\end{eqnarray*}

This quantity is greater than 1 if and only if $(n-k+1)p>k(1-p)
\Longleftrightarrow np+p>k$.
So, for $k<np+p$ the probability increase from $k-1$ to $k$,
and for $k>np+p$, the probability decreases.
The value of $k$ the maximizes the probability is thus
$\lfloor np+p \rfloor$.

\problempart
The probability of no heads is $(1-p)^n= (1-\frac{1}{n})^n$.  For
large $n$, this expression approaches $1/e$.  

The probability of
exactly one head is ${n \choose 1}p(1-p)^{n-1} =
(1-\frac{1}{n})^{n-1}$.  Forming the ratio, we find the probability of
no heads over the probability of exactly one head is
$\frac{1}{1-1/n}$, which is one over the probability of a tail.

\end{problemparts}


\end{problems}

\end{document}
