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

\begin{document}

\handout{ps8}{Problem Set 8}{April 8, 1994}

\pset{8}

{\bf Reading:\ }Maurer \& Ralston: Sections 6.1--6.3.

\medskip

There are only a few oral problems this week,
due in tutorial on Monday, April 11.
The written problems are due next week in recitation, April 15.

\bigskip

\begin{problems}

\oproblem 
Consider the {\it Lets Make a Deal} game, when host Monty Hall 
chooses a door to contain the prize with some non-uniform distribution---%
he hides the prize behind door number $i$ with some probability $p_i$, 
for $i=1,2,3$ and $\sum_i p_i =1$.
Suppose you, the contestant, (not knowing the $p_i$'s) follow the 
strategy of selecting a door
uniformly at random---you choose door $i$ with probability $1/3$---and
then switching doors when offered.
Determine the probability that you will win the prize by 
listing all events in the sample space 
along with the probabilities that they occur.

\oproblem
Suppose instead that Monty Hall chooses a door behind which to 
hide the prize according to the uniform distribution (all $p_i = 1/3$),
but you the contestant select a door according to some non-uniform
distribution---you select door $i$ with some probability $p_i$, 
where $i=1,2,3$ and $\sum_i p_i =1$---and then switch when offered.
Again determine the probability that you will win the prize by 
listing all events in the sample space along with 
the probabilities that they occur.

\oproblem
Consider the original {\it Lets Make a Deal} game, where there are
4 doors instead of 3.
Monty and you choose doors according to the uniform distribution;
Monty opens 2 doors (other than the one you chose) to reveal goats
and then offers you the chance to switch to the remaining unopened door;
you switch doors.
Again determine the probability that you will win the prize by 
listing all events in the sample space and the probabilities that they occur.
What is the probability that you will win if there are $n$ doors?

\oproblem
Consider the {\it Lets Make a Deal} game yet one more time (please!),
this time with host Malicious Monty Hall, who wants you to lose.
In particular, if you initially choose a losing door, 
he may decide to end the game right there, opening your door to reveal
the goat you have ``won'', never giving you the chance to switch doors.
If Monty does give you the chance to switch in this game, should you?  
What is the probability of winning if you play the don't-switch strategy?  
What if you play the switch strategy?


\oproblem
Every evening at the Boston Symphony Orchestra (winter, spring, and summer)
Bostonians check their hats (and scarves and gloves)
at the coatroom on their way into the concert hall.
Every evening, the hats are handed back randomly. 
Show that if the number of hats checked is $n$, then the probability
that no one gets his own hat back is~$\sim 1/e$ as $n$ gets large.
(Hint:  Derangements.)

\oproblem
What is the probability of getting exactly 9 cards of the same suit
in a bridge hand (which consists of 13 randomly chosen cards)?
Define a ``5-card major'' to be a hand with either
exactly 5 spades or exactly 5 hearts or both.
What is the proabability of getting a 5-card major?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remove{
\wproblem\footnote{From Drake's book.}
To the best of our knowledge, with probability 0.8 Al is guilty of 
the crime for which he is about to be tried.
Bo and Cy, each of whom knows whether or not Al is guilty,
have been called to testify

Bo is a friend of Al's and will tell the truth if Al is innocent
but will lie with probability 0.2 if Al is guilty.
Cy hates everybody but the judge and will tell the truth if Al is guilty
but will lie with probability 0.3 if Al is innocent.

\begin{problemparts}
\problempart
Determine the probability that the witnesses give conflicting testimony.
\problempart
Which witness is more likely to commit perjury?
\end{problemparts}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\wproblem
Joe, the bookie, is attempting to establish odds on an exhibition (!)
baseball game.  From many years of experience, he has learned that his
prime consideration should be the selection of the starting pitcher.
The Red Sox have only two pitchers, one of whom must start:
$R_1$, their best pitcher; and $R_2$, a worse pitcher.
The other team, the Yankees, has only three pitchers, one of whom must start:
$Y_1$, their best pitcher; $Y_2$, a worse one; and $Y_3$, an even worse one.
By carefully weighting information from various sources, Joe has decided
to make the following assumptions:  The Yankees will not start $Y_1$ 
if $R_1$ does not start.  If $R_1$ does start, the Yankees will start $Y_1$
with probability 1/3.  The Red Sox are equally likely to start $R_1$ or
$R_2$, no matter what the Yankees do.  $Y_2$ will pitch for the Yankees
with probability 3/4 if $Y_1$ does not pitch, no matter what else occurs.
The probability the Red Sox will win if $R_1$ pitches is $m/(m+1)$
where $m$ is the number (subscript) of the Yankee pitcher.
The probability the Yankees will win if $R_2$ pitches is $1/m$, 
where again $m$ is the number of the Yankee pitcher.
\begin{problemparts}
\problempart
What is the probability that the Red Sox will win?
\problempart
If $Y_2$ does not start, what is the probability that the Red Sox will win?
\problempart
If $R_2$ and $Y_2$ start, what is the probability that the Yankees will win?
\end{problemparts}


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

\wproblem
[[[NOTE FOR NEXT YEAR:  IT'S NOT A GOOD IDEA TO ASK THEM TO SHOW THAT
 THE CORRECT ANSWER IS INDEED CORRECT.  TOO MANY OF THEM BS'D THEIR WAYS
 THROUGH IT WITHOUT REALLY KNOWING WHAT THEY WERE DOING.
 ALSO, IT'S NOT CLEAR EXACTLY WHAT WE WANT THEM TO SAY FOR THESE PARTS.]]]
Assume everyone's birthday is randomly and uniformly chosen out 
of the $n$ days in a year.
Suppose we have a room of $p$ people, and we repeatedly choose a person
uniformly at random and write his or her birthday on a blackboard. 
If someone has the same birthday, he or she may shout out and we
end the game.  If not, we randomly choose another person and write
his or her birthday on the board.
\begin{problemparts}
\problempart
Show that the probability that we will write $t$ names on the board
without matching anyone's birthday is $$ n! (n-t)^{p-t} \over (n-t)! n^p$$.
\problempart
Use Stirling's approximation to show that this probability is
\[
\sim e^{-t} (1-t/n)^{p-n}. \]
\problempart
Use the approximation 
$1-t/n \approx e^{-\frac{t}{n} - \Theta(\frac{t^2}{n^2})}$
to show that the probability is approximately
\[
e^{-\frac{tp}{n} + \Theta(\frac{t^2(n-p)}{n^2})}
\]
and that if $t=o(p)$, then the probability is $\sim e^{-\frac{tp}{n}}$.
\problempart
Calculate the exact value of this probability for 
$n= 365$, $p=100$, and $t=5$.
How does this compare to the asymptotic estimate with these values?
\end{problemparts}


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


\wproblem
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}


\end{problems}


\end{document}



