\documentstyle[psfig,11pt]{article}

\pagestyle{empty}

\textheight 9.3in
\addtolength{\oddsidemargin}{-0.7in}
\addtolength{\textwidth}{1.2in}
\topmargin -0.3in
\headheight 0.1in
\headsep 0.1in


% magic for a Postscript figure:
%
%\begin{figure}[h]
%\centerline{\psfig{file=,width=}}
%\caption{}
%\end{figure}

\begin{document}

{\small These problems were adapted from {\it Fifty Challenging Problems in
Probability with Solutions}, by Frederick Mosteller, published by
Dover Publications (1965).}  It's a great little book, and it costs only \$5.

\begin{enumerate}

\item
{\bf The Flippant Juror} A 3-person jury has two rational members, 
each of whom independently has a probability $p$ of making the correct
decision, and a third member who just flips a coin for each decision
(the majority rules).  A one-person jury has probability $p$ of making
the correct decision.

{\it {\bf Problem}: Which jury has the better probability of making the correct
decision?}

Suppose the members of the 3-person jury are Socrates, Plato, and
Homer Simpson.  Here is one way to break down all the ways that the
3-person jury could be right:
\begin{itemize}
\item
Socrates and Plato are both right, and Homer is irrelevant: probability $p^2$;

\item
Socrates is right, Plato is wrong, and Homer is right: probability $\frac{1}{2} p (1-p)$;

\item
Socrates is wrong, Plato is right, and Homer is right: probability $\frac{1}{2} p (1-p)$.
\end{itemize}

These events are disjoint, so the probability that one of them occurs
is the sum $p^2 + p(1-p) = p$.  Thus the 3-person jury and the
1-person jury have the {\it same} probability of making the correct
decision.
        
\item
{\bf Tennis Tournaments.} A tennis tournament has 8 players. The
players are assigned randomly to positions in the first round of a
tournament ladder (see below).

\begin{figure}[h]
\centerline{\psfig{file=tournament.eps,width=3in}}
\end{figure}

{\it {\bf Warmup}: Suppose the best player always defeats everybody else, and
the second-best player always defeats everybody but the best. What
is the chance that the second-best player comes in second place?}

In order to come in second place, the second-best player has to meet
the winner in the final round.  That happens if and only if the best
player and the second-best player start out in different brackets of
four; in other words, if the best player starts in position 1-4 of the
first round, then the second-best must start in positions 5-8, and
vice versa.

Here are two ways to determine the probability.  The first way counts
complete assignments: there are 8 ways to place the best player in the
first round, then 4 ways to place the second-best, then $6!$ ways to
place the remaining players.  Divide by the size of the sample space
($8!$, the total number of ways to assign all eight players with no
constraints) to get $4/7$.

The second way treats each player's position as a different random
selection.  The best player can be placed anywhere.  Given the best
player's position, the second-best player can be placed in only 4 of
the remaining 7 positions.  (Not 4 out of 8, because the best player
is already occupying one!  This is a common error -- the positions of
the players can't be treated like independent coin flips or dice
rolls, because no two players can occupy the same position.)  The
remaining players can be put anywhere (6 out of 6 positions, then 5
out of 5, etc.)  Thus the probability is $4/7$.


{\it {\bf Problem}: Suppose the 8 tennis players are equally good, and they
include the twins Tom and Mot. What is the chance that Tom and Mot
meet in a match during the tournament?}

The probability that Tom and Mot will meet in the first round is $1/7$
(Tom can be placed anywhere, but given Tom's position, Mot has only 1
choice in 7).

Tom and Mot will meet in the second round if and only if both win
their first-round matches (with probability $1/4 \cdot 1/4$) and both
are in different groups of two but the same group of four (probability
$2/7$).

Tom and Mot will meet in the third round if and only if both win two
matches (with probability $1/2^2 \cdot 1/2^2$) and both are in different
groups of four (probability $4/7$).

Since these events are disjoint, the probability that Tom and Mot meet in any round is just the sum:
$$\frac{1}{7} + \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{2}{7} + \frac{1}{4} \cdot \frac{1}{4} \cdot \frac{4}{7} = \frac{1}{4}$$


\item
{\bf Craps.} The game of craps is played with two dice. The player
rolls both dice, winning immediately if the total is 7 or 11, and
losing immediately if the total is 2, 3, or 12. Any other total is
called the ``point.'' If the first roll is a point, then the player
continues rolling repeatedly until rolling the point again (which
wins), or rolling 7 (which loses). [You may want to use a calculator
for this problem.]

{\it {\bf Warmup}: What is the chance of winning on the first roll?}

Recall from lecture the probability function for a pair of dice:

\begin{center}
\begin{tabular}{r|r}
Roll & Prob \\
\hline
2 & $1/36$ \\
3 & $2/36$ \\
4 & $3/36$ \\
5 & $4/36$ \\
6 & $5/36$ \\
7 & $6/36$ \\
8 & $5/36$ \\
9 & $4/36$ \\
10 & $3/36$ \\
11 & $2/36$ \\
12 & $1/36$ \\
\end{tabular}
\end{center}

So the probability of rolling a 7 or 11 on the first roll is just
$6/36 + 2/36 = 2/9$.


{\it {\bf Problem}: What is the overall chance of winning?}

The first way to win is by rolling 7 or 11 on the first roll, which we
now know has probability $2/9$.  Otherwise, we must win by rolling a
point: getting 4, 5, 6, 8, 9, or 10 on the first roll, then eventually
rolling the same number again without rolling 7 first.  Since the odds
of rolling each point value is different, let $w_r$ be the probability
of winning with point $r$, for $r \in \{4, 5, 6, 8, 9, 10\}$.

One way to compute $p_r$ is by summing over all possible roll
sequences:
$$w_r = \Pr(\mbox{first roll is $r$}) 
\sum_{i=0}^{\infty} \Pr(\mbox{the next $i$ rolls are neither $r$ nor 7})
                    \Pr(\mbox{the final roll is $r$})$$

Let $p_r$ be the probability of rolling $r$ on a single roll (e.g.,
$p_4 = 3/36$). Then the formula for $w_r$ reduces to:
\begin{eqnarray*}
w_r & = & p_r \sum_{i=0}^{\infty} (1-p_r-p_7)^i p_r \\
    & = & p_r p_r \sum_{i=0}^{\infty} (1-p_r-p_7)^i \\
    & = & p_r \frac{p_r}{1-(1-p_r-p_7)}\\
    & = & p_r \frac {p_r}{p_r+p_7}\\
\end{eqnarray*}

So the probability of winning with point 4 (for example) is 
\begin{eqnarray*}
w_4 & = & {3 \over 36}{{3 \over 36} \over {3 \over 36} + {6 \over 36}} \\
    & = & {3 \over 36}{3 \over 9} \\
    & = & {1 \over 36}
\end{eqnarray*}
By similar calculations we get
\begin{eqnarray*}
w_5 & = & {4 \over 36}{{4 \over 36} \over {4 \over 36} + {6 \over 36}} = {2 \over 45} \\
w_6 & = & {5 \over 36}{{5 \over 36} \over {5 \over 36} + {6 \over 36}} = {25 \over 396}
\end{eqnarray*}

Note that the chance of rolling 8 is the same as rolling 6, so
$w_8=w_6$, $w_9=w_5$, and $w_10=w_4$, so we can simply double the
probability $w_4+w_5+w_6$ to find the total probability of winning
with a point.

So the overall chance of winning is
$${2 \over 9} + 2 ({1 \over 36} + {2 \over 45} + {25 \over 396}) \approx 0.493$$

In other words, the odds of winning are slightly worse than 50-50.

Here's a way of computing $w_r$ that neatly avoids the infinite sum.
When you're trying to roll your point, none of the rolls matter except
the last one, when you either roll your point and win or roll 7 and
lose.  So we can {\it ignore} the intermediate rolls, and just
consider the probability of rolling your point given that you rolled
either your point or 7.\footnote{If you have trouble believing that
you can just ignore the intermediate rolls, consider this simpler
example.  Imagine using a die to simulate a coin flip as follows: if
you roll 1, the result is heads.  If you roll 2, the result is tails.
If you roll anything else, just roll again.  Since you're only keeping
rolls of 1 and 2, all that matters is the relative probability of
rolling 1 and 2.} This argument leads directly to the formula:
$$w_r = p_r \frac {p_r}{p_r+p_7}$$


\item
{\bf Three-Cornered Duel.} This problem involves old-fashioned duels
by pistol.  [You may want to use a calculator for this problem.]

{\it {\bf Warmup}: A and C are engaged in a duel.  Each takes turns firing
a shot at the other until one of them is hit and falls down. On each
shot, A has probability 0.3 of hitting, and C has probability 0.5. If
A shoots first, what is the chance that A will win this duel?}

One approach we might take to this problem uses infinite sums, as in
the craps problem above.  In other words, suppose $p_i$ is the
probability that A wins after $i$th turns.  To win on the first turn,
A must hit immediately, so $p_0 = 0.3$.  To win on the second turn, A
must miss, then B must miss, then A must hit, giving $p_1 = 0.7 \cdot
0.5 \cdot 0.3$.  In general, $p_i = (0.7 \cdot 0.5)^i 0.3$.  Summing this over all $i$ gives:
\begin{eqnarray*}
\sum_{i=0}^\infty p_i & = & \sum_{i=0}^\infty (0.7 \cdot 0.5)^i 0.3 \\
& = & 0.3 {1 \over 1 - 0.7 \cdot 0.5} \\
& \approx & 0.462
\end{eqnarray*}

Another approach relies on the problem's {\it self-similarity.}
Suppose A misses on the first turn, then B misses.  Now the situation
is exactly the same as it was at the beginning: it's A's turn, and
both duellists still have the same probability of hitting.  So the
probability that A wins given that A just missed and B just missed
must be the same as the overall probability that A wins.  If we let
$p$ be the probability that A wins overall, we can write:
\begin{eqnarray*}
\Pr(\mbox{A wins eventually}) & = & \Pr(\mbox{A hits on first turn}) + \Pr(\mbox{A hits after the first turn}) \\
\Pr(\mbox{A wins eventually}) & = & \Pr(\mbox{A hits on first turn}) \\
& & + \Pr(\mbox{A wins eventually} | \mbox{A missed then B missed})\Pr(\mbox{A missed then B missed}) \\
p & = & 0.3 + 0.7 \cdot 0.5 p \\
(1 - 0.35)p & = & 0.3 \\
p & \approx & 0.462
\end{eqnarray*}


{\it {\bf Problem}: A, B, and C are to fight a ``three-cornered duel.''
They take turns (in the order A,B,C, cyclically) firing at their
choice of target.  Once hit, a duellist falls down, dropping out of
the duel. The duel continues until only one is left standing. They all
know that A has probability 0.3 of hitting a target, and C has
probability 0.5. But B never misses! (Assume that B is rational, and
always eliminates the most serious threat.)  What should A's strategy
be?}

If B has a chance, B will shoot and kill C in the first round, because
C is the most serious threat.  So A must decide whether to shoot at B
(which might be wise, because B is incredibly dangerous) or at C
(which might be better, because leaving B alive ensures that C won't
get a shot at either of them).

Suppose A aims at B in
the first round.  If A hits B (probability 0.3), and C shoots at and
misses A (probability 0.5), then A and C will be left in a duel
identical to the warmup problem (with probability 0.462 that A wins).
If A misses B (probability 0.7), then B will hit C (probability 1),
and A will get one more chance to hit B before certain annihilation
(probability 0.3).  So the probability that A wins by aiming at B is about
$0.3 \cdot 0.5 \cdot 0.462 + 0.7 \cdot 0.3 = 0.279$.

Now suppose A aims at C in the first round.  If A hits C, then A
definitely loses, since B will unerringly shoot and hit A.  If A
misses C (probability 0.7), then B will take out C and A will get one
chance at B (probability 0.3).  So the probability that A wins by
aiming at C is exactly $0.7 \cdot 0.3 = 0.21$.

But there's a third alternative: A can intentionally miss everybody.
Then B shoots C, and A has one chance to hit B (probability 0.3).  So
the probability that A wins by shooting in the air is exactly $0.3$,
which makes it the best strategy.

\item
{\it {\bf Theater Row.} Eight men and seven women, all single, happen
randomly to have purchased single seats in the same 15-seat row of a
theater.}

{\it {\bf Warmup}: What is the probability that the first two seats contain
a (legally) marriageable couple?}

Here's one way to do it.  There are ${15 \choose 2} = 105$ possible
pairs that could occupy the first two seats, but only $8\cdot7 = 56$
of them are marriageable couples.  So the probability is $56/105
= 8/15$.

{\it {\bf Problem}: How many pairs of adjacent seats contain marriageable
couples, on the average?}

Let the random variable S be the number of pairs of seats containing a
marriageble couple; we want to find $E[S]$.  We can solve this problem
by introducing an indicator random variable $S_i$, where $S_i = 1$ if
there is a marriageable couple in seats $i$ and $i+1$, and $S_i = 0$
otherwise.  So we have $$S = \sum_{i=1}^{14} S_i$$

Since each seat is like any other, the probability that seats $i$ and
$i+1$ contain a marriageable couple is the same as in the warmup
problem, $8/15$.  Thus $E[S_i] = 1\cdot\Pr(S_i=1) + 0\cdot\Pr(S_i=0) =
8/15.$ 

Because expectation is linear,
\begin{eqnarray*}
E[S] & = & \sum_{i=1}^{14} E[S_i] \\
& = & 14\cdot{8 \over 15} \\
& = & 7{7 \over 15}
\end{eqnarray*}

Note that this approach works despite the fact that the indicator
random variables $S_i$ are not independent!  That's the beauty of
linearity of expectation.

\end{enumerate}

\end{document}
