\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\begin{document} 
\inclassproblems{9M}

%TUT10 - last used Spring 99 Tutorial 10, Problem 1
%Fall01

\begin{problem}
Suppose the game \emph{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.  Otherwise, the rules of the game remain the same:
\begin{enumerate}
\item The contestant picks one of the doors.

\item Assistant Carol opens a different door that has a goat behind it.

\item The contestant can then \textbf{stick} with his original pick or
\textbf{switch} to an unopened door.  He wins a prize only if his final
pick is the door with the prize.

\end{enumerate}

Assume that the prizes are equally likely to be placed behind each of the
doors, and that Carol and the contestant are also equally likely to pick
each door among their possible choices.

\bparts

\ppart In the new game, what is the probability of winning with the ``stick''
strategy?  How about the ``switch'' strategy?


\solution{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 $1/2$.

To analyze the switch strategy we form the usual tree, as shown in
Figure~(\ref{mont-mod}).  
%CAK/ASHM INSERT ONE HERE.

\begin{figure}[htb]
\begin{center}
%\includegraphics[width=4in]{figures/mont-mod}
\input{figures/mont-mod.latex}
\end{center}
\caption{Coding Numbered Trees}
\label{mont-mod}
\end{figure}

By symmetry, we may assume that the prizes are behind doors 1 \& 2.  The
possible outcomes are of the form:
\begin{center}
(contest-choice, Carol-choice, contest-switch-choice)
\end{center}
with probabilities:
\begin{center}
\begin{tabular}{ccc}
doors & probability & win-with-switch\\
\hline\\
(1,3,2) & 1/16 & win\\
(1,3,4) & 1/16 & lose\\
(1,4,2) & 1/16 & win\\
(1,4,3) & 1/16 & lose\\
(2,3,1) & 1/16 & win\\
(2,3,4) & 1/16 & lose\\
(2,4,1) & 1/16 & win\\
(2,4,3) & 1/16 & lose\\
(3,4,1) & 1/8 & win\\
(3,4,2) & 1/8 & win\\
(4,3,1) & 1/8 & win\\
(4,3,2) & 1/8 & win
\end{tabular}
\end{center}
So the switch strategy wins 3/4 of the time.}

\ppart
In the original Monty Hall game, the probabilities of the
winning-with-stick and the winning-with-switch strategies summed to one,
but here they don't.  How come?

\solution{
In the original Monty Hall game with one prize, the switch strategy would
win iff the stick strategy would not win, so winning-with-stick and
winning-with-switch were complementary events who sum had to be one.

This time the two probabilities do not need to sum up to 1 because they
are no longer disjoint events.  It is possible for both the ``switch'' and
the ``stick'' strategy to pick doors that both have a prize behind them,
because there are two prizes.  So the same outcome can be a win for both
strategies.}

\eparts

\end{problem}

\begin{problem}
Suppose you repeatedly flip a fair coin (\emph{fair} means that heads and
tails are equally likely to appear).

\bparts

\ppart What is the probability that you flip exactly 4 heads out of 8?
between 3 and 5 heads?

\solution{
The probability of exactly 4 heads is about 0.27.
\[
\frac{\binom{8}{4}}{2^8} = \frac{8 \cdot 7 \cdot 6 \cdot 5}{4 \cdot 3
\cdot 2 \cdot 1 \cdot 2 ^ 8} = \frac{35}{128} \approx 0.27.
\]
Similarly, there will be from 3 to 5 heads 60\% of the time:
\[
\frac{\binom{8}{3} + \binom{8}{4} + \binom{8}{5}}{2^8} \approx 0.60.
\]
}

\ppart Suppose you flip a fair coin $n$ times.  What is the probability
that you flip exactly $m$ heads?  Write a formula for the exact answer,
and write a closed-form formula for an approximate answer.

\solution{
The probability of $m$ heads is $\binom{n}{m}/2^n$.  Using Stirling for an
approximation:
\begin{eqnarray}
\binom{n}{m} & \sim &\frac{\sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n}
{\sqrt{2\pi m}\left(\dfrac{m}{e}\right)^m {\sqrt{2\pi
(n-m)}\left(\dfrac{n-m}{e}\right)^{n-m}}}\\
& = & 
\frac{\sqrt{n}\left(\dfrac{n}{e}\right)^m\left(\dfrac{n}{e}\right)^{n-m}}
{\sqrt{2\pi m (n-m)}\left(\dfrac{m}{e}\right)^m
 {\left(\dfrac{n-m}{e}\right)^{n-m}}}\\
& = & \frac{\sqrt{n}\left(\dfrac{n}{m}\right)^m\left(\dfrac{n}{n-m}\right)^{n-m}}
{\sqrt{2\pi m (n-m)}}.\label{stirsimp}
\end{eqnarray}
}

\ppart How would you actually calculate the probability that the number of
heads in 400 flips was between 195 and 205?\dots in 10,000 flips was
between 4980 and 5020?  Could you do it exactly by hand? \dots with a
calculator? with a computer program in some language (what language)?
What about approximately to two decimal places?...six decimal places?
This is intended as a discussion question.  You should be prepared to
defend your conclusions with appropriate technical arguments.

\solution{The numbers are all too large to calculate by hand.  Computing
400!, 190!, and 210!\ exactly will overflow on any calculator, so an exact
computation by calculator would also be impractical.  In fact, it will
cause numerical overflow errors in most programming languages.  Real
Scheme has infinite precision rational arithmetic and can handle 400!, but
\emph{not} 10,000!, so exact computation in the 10,000 case is unlikely to
work in any language: remember the answer will have around 40,000 digits.
(It's conceivable that the Scheme heap size could be set large enough to
hold a hash table with $10,000^2$ entries each of which might be up to
40,000 digits, though this is a stretch.  If so, you could use the Pascal
recursion
\[
\binom{n+1}{m} =  \binom{n}{m-1} + \binom{n}{m} 
\]
in a memoized computation to get an exact answer.)  But there are no
applications that require anywhere near such accuracy.

For the approximate case, we can use Stirliing's approximation for $n!$,
but there are still pitfalls: $(400/e)^{400}$ will overflow floating point
arithmetic on calculators and essentially all computers, so the simplified
version~(\ref{stirsimp}) would be needed.  Since floating point is usually
good for 8 to 10 places on most machines, getting six place accuracy
should be manageable.

In fact there's a rough approximation for the probability that's easy:
setting $m = n/2$ in~(\ref{stirsimp}) yields
\begin{equation}
\binom{n}{n/2} \sim \frac{2^n}{\sqrt{n \pi/2}}\label{n/2simp},
\end{equation}
so
\begin{equation}
\pr{\text{$n/2$ heads in $n$ flips}} =\frac{\dbinom{n}{n/2}}{2^n} \sim
\sqrt{\frac{2}{n \pi}}\label{n/2heads}.
\end{equation}
A calculator will yield the value of~(\ref{n/2heads}) for $n=400$; to
three places it is 0.0399.  But all the probabilities for 195 to 205 heads
are about the same, so an offhand estimate would be $11 \times 0.0399 =
0.439$.  The actual answer is 0.418.

Similarly, for $n=10,000$, the value of~(\ref{n/2heads}) is about 0.00798,
and all the probabilities for 4980 to 5020 heads are about the same, so an
offhand estimate would be $41 \times 0.00798 = 0.327$.  The actual answer
is 0.318}

\eparts

\end{problem}


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

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

There are $\binom{4}{2}$ ways to choose two suits and $\binom{26}{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 \binom{13}{5}$.  Therefore, the number of hands with at most two
suits is
\[
\binom{4}{2} \cdot \binom{26}{5} - 2 \cdot 4 \cdot \binom{13}{5},
\]
and the probability that a random poker hand contains cards from at most
two suits is:
\begin{equation*}
\frac{\binom{4}{2} \cdot \binom{26}{5} - 2 \cdot 4 \cdot \binom{13}{5}}
                {\binom{52}{5}}
\approx 0.15
\end{equation*}
}
\end{problem}


\begin{problem}Each morning Theory Pig pops out of his desk
drawer home--- all bright and perky--- and goes bounding off to play
around the Laboratory for Computer Science.  The desk drawer is
located at position $(0, 0)$.  At each time step, Theory Pig is
equally likely to bound north or east.  A northward bound increments
the first coordinate of his position, and an eastward bound increments
the second coordinate of his position.  (Assume that his direction at
one time step is independent of his direction at all other time
steps.)

At position $(4, 4)$, 6.042 TA Brian Dean is waiting with a bat, for
some reason.  What is the probability that Theory Pig visits position
$(4, 4)$ within his first 10 bounds?

\solution{ Each possible route can be described by the length 10 sequence
of \emph{N}'s and \emph{E}'s indicating the direction of a move; we use
these as the outcomes.  There are $2^{10}$ such outcomes.  Since \emph{N}
and \emph{E} equally likely, we assign uniform probabilities to the
outcomes.

Theory Pig visits position $(4, 4)$ if 4 of his first 8 bounds are north,
4 of his first 8 bounds are east, and his remaining two bounds are in any
direction.  Therefore, Theory Pig visits $(4, 4)$ in
\begin{equation*}
\binom{8}{4} \cdot 2^2   =    280
\end{equation*}
of these outcomes.  So the probability that Theory Pig visits
position $(4, 4)$ within his first 10 bounds is
\begin{equation*}
\frac{280}{2^{10}}  =  \frac{35}{128}.
\end{equation*}
}
\end{problem}


\end{document}
