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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\begin{document} 
\inclassproblems{10, Mon}

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


\begin{problem}
\bparts

\ppart 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{\dbinom{4}{2} \cdot \dbinom{26}{5} - 2 \cdot 4 \cdot \dbinom{13}{5}}
                {\dbinom{52}{5}}
\approx 0.15
\end{equation*}
}

\ppart Suppose you repeatedly flip a fair coin (\emph{fair} means that
heads and tails are equally likely to appear).  What is the probability
that you flip exactly 4 heads out of 8?  between 3 and 5 heads?

\solution{
The probability of exactly $m$ heads in $n$ tosses is $\binom{n}{m}/2^n$.  So
the probability of exactly 4 heads is:
\[
\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, the probability of between 3 and 5 heads is:
\[
\frac{\dbinom{8}{3} + \dbinom{8}{4} + \dbinom{8}{5}}{2^{8}} \approx 0.60.
\]
}

\iffalse

\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}}} \notag\\
& = & 
\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}}} \notag\\
& = & \sqrt{\dfrac{n}{2\pi m (n-m)}}\left(\dfrac{n}{m}\right)^m\left(\dfrac{n}{n-m}\right)^{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 Stirling'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 the righthand side of
equation~(\ref{n/2heads}) at $n=400$; it is $\approx 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 \approx 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 \approx 0.327$.  The actual
answer is 0.318.}

\fi

\eparts

\end{problem}


\begin{problem}
Here is a coin-flipping game: flip a fair coin at most four times but stop
sooner if two Heads come up in a row.
\bparts

\ppart
What is a suitable sample space (set of outcomes) for this game?
\solution{
The sample points are:
\[
TTTT, TTTH, TTHT, TTHH, THTT, THTH, THH, HTTT, HTTH, HTHT, HTHH, HH
\]
which we obtained by drawing a tree (not shown) illustrating the outcomes
after each flip.}

\ppart
What are reasonable probabilities to assign to the sample points?

\solution{
Each node of the tree that is not a leaf has two branches describing the
outcomes Head and Tail, and these are equally likely.  So the probability
of any final pattern, $s$, of Heads and Tails is
\[
\pr{s} \eqdef \frac{1}{2^{\lnth{s}}},
\]
where $\lnth{s}$  is the length of $s$.
}

\ppart You win when two Heads in a row have come up.  Are the odds of
winning this game in your favor?

\solution{
Winning points are HH, THH, TTHH, and HTHH so
\[
\pr{\text{win}} = \frac{1}{2^2} + \frac{1}{2^3} + 2\cdot \frac{1}{2^4}  +  =
\frac{4+2+2\cdot 1}{16} = \frac{1}{2}.
\]
So the odds of losing are the same as those of winning.
}

\eparts

\end{problem}


\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 then of the form:
\begin{center}
(contestant-initial-choice, Carol-choice, contestant-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 whose
probabilities had to sum to 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}


\iffalse

\begin{problem}

Each morning Theory Rhino 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 Rhino 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 Rhino 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 Rhino 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 Rhino visits $(4, 4)$ in
\begin{equation*}
\binom{8}{4} \cdot 2^2   =    280
\end{equation*}
of these outcomes.  So the probability that Theory Rhino visits
position $(4, 4)$ within his first 10 bounds is
\begin{equation*}
\frac{280}{2^{10}}  =  \frac{35}{128} \approx 0.27.
\end{equation*}
}
\end{problem}
\fi


\end{document}
