\documentclass[11pt, twoside]{article}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}
\setlength{\parskip}{0.2\baselineskip}          % Interparagraph Spacing

%%% rjr -- I was trying to avoid these, by this is maddening...
\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}
\newcommand{\mquote}[1]{\mathify{\textrm{``$#1$''}}}
\newcommand{\mdash}{\mathify{\textrm{-}}}
%\newcommand{\set}[1]{\mathify{\{#1\}}}
\newcommand{\where}{{\ \scriptstyle{|} \ }}
\newcommand{\size}[1]{\mathify{\left| #1 \right|}}
\newcommand{\equivalent}{\mathify{\ \Longleftrightarrow \ }}
\newcommand{\ifandonlyif}{\equivalent}
%\newcommand{\implies}{\mathify{\ \Longrightarrow \ }}
%\newcommand{\etc}{ {\scriptstyle\ldots} }
%\newcommand{\union}{\cup}
%\newcommand{\intersect}{\cap}
\newcommand{\kignore}[1]{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\typein[\answer]{Include solutions? (y/n) }
\def\yes{y}
\ifx\answer\yes
\typeout{}
\typeout{Solutions *INCLUDED*.}
\newcommand{\reading}[1]{}
\newcommand{\omitsolution}[1]{\textbf{Solution.} #1 }
\newcommand{\omitnonsolution}[1]{}
%\usepackage[dark,first,bottom]{draftcopy}
%\draftcopyName{Solutions}{155}
%
\newcommand{\handoutlabel}{sol8}
\newcommand{\handouttitle}{Problem Set 8 Solutions}
\newcommand{\handoutdate}{April 20, 2000}
\newcommand{\collaboration}{}
\newcommand{\titlebar}{%
  \handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else
\typeout{}
\typeout{Solutions *NOT INCLUDED*.}
\newcommand{\reading}[1]{%
%    \mbox{}\\ %
  \hrule%\mbox{} \\ %\bigskip %
  #1%
%    \mbox{} \\ %\bigskip %
  \hrule %
    %\vfill\mbox{}\newpage%
  }
\newcommand{\omitsolution}[1]{}
\newcommand{\omitnonsolution}[1]{#1}
%
\newcommand{\handoutlabel}{ps8}
\newcommand{\handouttitle}{Problem Set 8}
\newcommand{\handoutdate}{April 11, 2000}
\newcommand{\duedate}{Thursday, April 20, 2000 in lecture}
\newcommand{\collaboration}{\collaborationnote}
\newcommand{\titlebar}{%
  \handout{\handoutlabel}{\handouttitle}{\handoutdate}
  \centerline{{\bf Due  Date: \duedate.}}
  \vspace*{\baselineskip}}
                                %
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}


\titlebar

\reading{%
  \begin{description}\itemsep 0\baselineskip
  \item[Self-study:] \mbox{} \\
    Self-study reading: Rosen \S 4.7\\
    Self-study problems: \S 4.7 1, 3, 5, 9
    
  \item[Reading:] \mbox{} \\[-\baselineskip]
    \vspace*{-0.5\baselineskip}
    \begin{description}\itemsep 0\baselineskip
    \item[Rosen, \textit{Discrete Mathematics and Its Applications}:]       \S 4.4--4.5 (pp. 260-271)
    \end{description}
  \end{description}
  }

\section*{Problems:}

\begin{problems}

% Monty Hall: Spring 98
\problem Suppose the game {\em Let's Make A Deal} 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?

\omitsolution{ The player wins with a ``stick'' strategy iff he
chooses the ``correct door'' in the first place. Therefore the
probability of winning with the ``stick'' strategy is $\frac{1}{2}$.

To calculate the probability of winning with a ``switch'' strategy,
let $E_1$ be the event that ``the player chooses the correct door at
his first chance''. Let $E_2$ be the event that ``the player switches
to the correct door at his second chance''.
\begin{eqnarray*}
P(\mbox{winning with ``switch'' strategy})&=&P(E_2|E_1)P(E_1)+P(E_2|\overline{E_1})P(\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 need to sum up to 1. They are calculated
in a different probability space. In particular, the player winning
by the ``switch'' strategy does not imply he will lose by the
``stick'' strategy, and vice versa. Therefore, the same winning event
can be counted in both cases at the same time.

}


% Max value: Spring 98
\problem In a lottery, 6 distinct integers are drawn randomly from 1
to 45 without replacement. 
\begin{problemparts}
\ppart What is the probability that the first of the 6 numbers is at
most $k$, where $1 \le k \le 45$?
\ppart
What is the probability that the maximum of the 6 numbers is $k$, where $1\leq k\leq45$?
\end{problemparts}

\omitsolution{ 
\begin{enumerate}
\item There are 45 equally likely values of the first number picked.
The probability that the first number is at most $k$ is therefore
$\frac{k}{45}$.

\item There are ${45\choose6}$ ways to pick 6 numbers out of
45. For a set of 6 numbers whose maximum element is $k$, it has to
have $k$ and all of 5 other numbers are smaller than $k$. Therefore
there are ${k-1\choose5}$ such sets. Since every set of 6 numbers are
equally likely to occur, the desired probability is simply
$\frac{{k-1\choose5}}{{45\choose6}}$.
\end{enumerate}

}


% Spring 99
\problem There are three prisoners, $A$, $B$, and $C$.  The parole
board will release two of the prisoners, but has not yet announced
which two.  The pair to be released is selected by the board uniformly
at random; that is, each of the three pairs of prisoners has a
$\frac{1}{3}$ probability of being chosen.

Prisoner $A$ figures that he will be released with probability
$\frac{2}{3}$.  A guard offers to tell prisoner $A$ the name of one of
the other prisoners who will be released (either $B$ or $C$).
However, prisoner $A$ declines the offer.  He reasons that if the
guard says, for example, ``$B$ will be released'', then his own
probability of release will drop to $\frac{1}{2}$.  This is because he
will then know that either he or $C$ will be released, and these two
events are equally likely.

Either prove that prisoner $A$ has reasoned correctly or prove that he
is wrong.  Assume that if the guard has a choice of saying either $B$
or $C$, because both are to be released, then he picks one at random
with equal probability for each.

\omitsolution{Prisoner $A$ is wrong.  He is conditioning on the event that
prisoner $B$ is to be released and not on the event that the guard
says prisoner $B$ is to be released.  A correct calculation is given
below.

\begin{eqnarray*}
\Pr(\text{$A$ is released} \mid \text{guard says $B$})
        & = &   \frac{\Pr(\text{$A$ is released} \cap \text{guard says $B$})}
                        {\Pr(\text{guard says $B$})} \\
        & = &   \frac{\Pr(\text{$A$ and $B$ are released})}
                        {\Pr(\text{guard says $B$})} \\
        & = &   \frac{\frac{1}{3}}{\frac{1}{2}} \\
        & = &   \frac{2}{3}
\end{eqnarray*}

Thus, the probability that prisoner $A$ will be released is not
changed by what the guard tells him.
}

%
\problem What is the probability that a random poker
hand contains cards from at most two suits?

\omitsolution{

The sample space consists of the ${52 \choose 5}$ possible
hands.  Each hand is equally likely and comes up with probability $1 /
{52 \choose 5}$.  Therefore, the probability that a hand contains at
most two suits is equal to the number of different hands of this type
multiplied by $1 / {52 \choose 5}$.  All that remains is to count the
number of poker hands with at most two suits.

There are ${4 \choose 2}$ ways to choose two suits and ${26 \choose 5}$
ways to choose five cards from these two suits.  However, this
triple-counts hands containing cards from a single suit.  (For
example, a hand with all spades is counted once as a spades-hearts
hand, a second time as a spades-clubs hand, and a third time as a
spades-diamonds hand.)  The number of hands with a single suit is $4
\cdot {13 \choose 5}$.  Therefore, the number of hands with at most two
suits is
\[
{4 \choose 2} \cdot {26 \choose 5} - 2 \cdot 4 \cdot {13 \choose 5}.
\]

The probability that a random poker hand contains cards from at most
two suits is:

\begin{eqnarray*}
\Pr(\text{hand has at most two suits})
        & = & \frac{{4 \choose 2} \cdot {26 \choose 5} -
                        2 \cdot 4 \cdot {13 \choose 5}}
                {{52 \choose 5}} \\
        & \approx & 0.15
\end{eqnarray*}
}

% Fall 97
\problem
\begin{problemparts}
\problempart You roll two dice.  What is the probability that their
sum is not 6?

\problempart You roll three dice. What is the probability that
at least one of the {\em pairwise} sums is something other than 6?
\end{problemparts}

\omitsolution{
\begin{enumerate}
\item There are five ways the sum can be 6: 
$(1,5),(5,1),(2,4),(4,2),(3,3)$

There are $6 \cdot 6 = 36$ ways the dice can land, so the probability
that their sum is six is $\frac{5}{36}$. Therefore the probability
that the sum is not six is $\frac{31}{36}$.


\item First, we calculate the probability of the complement event,
that all pairwise sums equal 6.  This can only occur when all three
dice show ``3''.  This event occurs with probability $\frac{1}{216}$.
Therefore the probability that at least one of the pairwise sums is
not 6, is $\frac{215}{216}$.

\end{enumerate}
}

% Fall 97
\problem
We know from statistics that when a policeman gets shot he/she survives with
probability $0.8$ if he/she wears a bullet-proof vest and survives with
probability $0.12$ if the policeman doesn't wear a vest.
Given that 15\% of the policemen wear bullet-proof vests, what is the
probability that a random policeman was wearing a bullet-proof vest if he/she
survived a firearm attack?

\omitsolution{
Let $B$ be the event the policeman wears a vest.  Let $W$ be the
event the policeman survives an attack.
We want to compute $Pr(B|W)$.  By Bayes' 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
\]

An equally valid solution would be to draw out a tree of the
conditional probabilities and to calculate the solution
``graphically''.
}


% Fall 94
\problem
A biased coin has probability $p$ of heads and probability $1-p$ of tails.
Suppose we flip this coin $n$ times.
\begin{problemparts}
\problempart
What is the probability of getting exactly $k$ heads?
\problempart
For what values of $k$ is the probability of getting exactly $k$ heads
greater than the probability of getting exactly $k-1$ heads?
For what values of $k$ is it less?
What value of $k$ is the most likely number of heads?
\problempart
Show that if $p=1/n$ then the probability of getting no heads is 
$\sim 1/e$ (for large $n$).
What is the ratio of the probability of no heads to the probability
of exactly one head?
\end{problemparts}

\omitsolution{
\begin{enumerate}
\item
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}
\]

\item
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$.

\item
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{enumerate}
}


% Fall 97
\problem

\begin{problemparts}
\problempart

Prove that $Pr(\overline{A}|C) = 1 - Pr(A|C)$ for any events $A$ and $C$.

\problempart

Is it possible for $Pr(A|B)$ and $Pr(A|C)$ to be very small, if 
$Pr(A|B\cap C)$ is large? Give a counterexample or a proof to justify 
your answer.
\end{problemparts}

\omitsolution{

\begin{enumerate}
\item
\begin{eqnarray*}
1 - Pr(A|C) &=& 1 - \frac{Pr(A\cap C)}{Pr(C)} \\
            &=& \frac{Pr(C) - Pr(A\cap C)}{Pr(C)} \\
            &=& \frac{Pr(\overline{A}\cap C)}{Pr(C)}\\
            &=& Pr(\overline{A}|C)
\end{eqnarray*}

\item
Yes, it is.  
Consider the uniform sample space $S=\{1,2,\ldots, 2 \cdot 10^6\}$. \\
Let $A = \{1\}, B = \{1,2,\ldots,10^6 \}, C = \{1,10^6+1,\ldots,2 \cdot 10^6 -1\}$. \\
Then $Pr(A \mid  B)  = Pr(A \mid C) = 10^{-6}$, while $Pr(A \mid B \cap C) = 1$.
\end{enumerate}
}

\end{problems}

\end{document}





