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

\begin{document}


\pset{11}{April 29, 1997}{May 6, 1997}

{\bf \Large WARNING:  THIS IS AN INCOMPLETE ROUGH DRAFT}

{\bf Reading:} Rosen 4.4-4.5 up to ``independence,'' 4.6.

In the problems below, try to simplify your answers as much as
possible.  There are a lot of questions, but many of them can be
answered with one equation and a brief explanation.

\begin{problems}


\problem  
Several dice and an urn.
\bparts
\ppart
When rolling a pair of fair dice, what is the probability of getting 
a sum of two on the dice? a sum of seven on the dice? a sum of eleven on 
the dice?

There are 6 possible outcomes for each die, and these occur independently
so there are 36 equally likely outcomes.  (Notice that getting the same
numbers but on different dice corresponds to different outcomes).
The probability of the above events is thus the number of outcomes
corresponding to those events divided by 36.  There is exactly 1 outcome
corresponding to a sum of two on the dice, so this happens with probability
$\frac{1}{36}$.  There are 6 outcomes corresponding to a sum of seven on the
dice, so this happens with probability $\frac{6}{36} = \frac{1}{6}$.  There are 2 outcomes
corresponding to a sum of eleven on the dice, so this happens with
probability $\frac{2}{36} = \frac{1}{18}$.

\ppart
Pepys wrote Newton to ask which of three events is more likely: that a
person
get (i) at least one six when $6$ dice are rolled, (ii) at least two sixes
when $12$ diced are rolled, or (iii) at least three sixes when $18$ dice are
rolled.  What is the answer?

The answer is (i).
In all cases, the number of sixes is binomially distributed.
The probability of (i) is $1 - (5/6)^6$, which is about $0.665$.
The probability of (ii) is $1 - (5/6)^12 - {12 \choose 1} \cdot (1/6)
\cdot (5/6)^11$, which is about $0.619$.
The probability of (iii) is $1 - (5/6)^18 - {18 \choose 1} \cdot
(1/6) \cdot (5/6)^17 - {18 \choose 2} \cdot (1/6)^2 \cdot (5/6)^16$,
which is about $0.597$.

\ppart %multinomial
A six-sided die is tossed 12 times.   What is the probability of
obtaining exactly 2 of each number from 1 to 6?

The number of distinct sequences in which each number appears
exactly twice is the same as the number of permutations of
1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6.  This is

\begin{equation}
{{12!} \over {2! 2! 2! 2! 2! 2!}} = {12! \over {2^6}}
\end{equation}

There are $6^{12}$ possible outcomes in 12 tosses of a die.  If we
suppose that al of these have equal probabilities, then the
probability of obtaining a sequence in which each face appear exactly
twice is

\begin{equation}
{{12! \over {2^6}} \over {6^12}} = 3.4(10^{-3})
\end{equation}

\ppart %combinations (easy)
An urn contains five balls numbered $1, 2, 3, 4, 5$.  Suppose
we draw three balls with replacement.  What is the probability that
all three balls are different?

There are $5^3=125$ possible outcomes, which we will suppose are
all equally likely.  The number of these outcomes for which the three draws
are different is given by $5(4)(3)=60$.  Thus the probability that all
three balls are different is ${60 \over 125} = 0.48$.

\eparts



\problem % sample tree
When playing {\em Let's Make a Deal} in class, I decided to
``speed things up'' (give contestants a better chance of winning) by
adding a 4th box and, after your choice, revealing 2 that don't have
the prize.  Draw the tree of outcomes for the ``always switch'' rule
when 4 boxes are involved.  What is the probability that you win?

The probability that you win is $\frac{3}{4}$.

\problem % sample tree
Consider a best 3 out of 5 playoff.  If team 1 has a probability $1/2$
of winning each game that it plays, what is the most likely (that is,
highest probability) number of games in the playoff?  What if the
first team's win probability is $9/10$?

There are 2 (mutually exclusive) ways that the playoff can end in 3 games,
each with probability $\frac{1}{8}$.
So the playoff ends in 3 games with probability $2 \cdot \frac{1}{8} =
\frac{1}{4}.$
A playoff consisting of 4 games must involve three wins by one team and
one win by the other team, with this win being any one of the first three
games.  (If it was the fourth, the playoff would have ended after the
first three games).
There are two ways of choosing which team wins, so there are 6 ways
that the playoff can last exactly 4 games.  Each way has probability
$\frac{1}{16}$, so the probability that the playoff has exactly
4 games is $6 \cdot \frac{1}{16} = \frac{3}{8}$.
The probability of the playoff having exactly 5 games is
$1 - \frac{1}{4} -  \frac{3}{8} =  \frac{3}{8}$.
Thus the most likely numbers of games are 4 and 5 (happening with
equal probability).

If the first team's win probability is $9/10$, then the first team
can win the playoff in 3 games exactly one way, which happens with
probability $(\frac{9}{10})^3$ and the second team can win the
playoff in 3 games exactly one way, which happens with probability
$(\frac{1}{10})^3$.  So the probability that the playoff ends in exactly
three games is $(\frac{9}{10})^3 + (\frac{1}{10})^3 = \frac{73}{100}$.
The first team can win in exactly 4 games three different ways, each
with probability $(\frac{9}{10})^3 \cdot \frac{1}{10}$.
The second team can also win in exactly 4 games three different ways, but
these each occur with probability
$(\frac{1}{10})^3 \cdot \frac{9}{10}$.
So the probability that the playoff will have exactly 4 games is
$3 \cdot (\frac{9}{10})^3 \cdot \frac{1}{10} + 3 \cdot (\frac{1}{10})^3 \cdot
\frac{9}{10} = \frac{1107}{5000}$.
The probability that the playoff will have exactly 5 games is
$1 - \frac{73}{100} - \frac{1107}{5000} = \frac{243}{5000}$.
So in this case, the most likely number of games in the playoff is 3.

\problem %sample space, combinations, inclusion/exclusion
Suppose you are dealt a random poker hand of 5 cards from a
deck of 52 cards. Compute the probability that you are dealt
\bparts
\ppart Four of a kind (four cards with the same value)

There are $C(52,5)={52! \over {5! 47!}}$ ways to choose $5$ cards.
There are $13$ ways to choose four of a kind and 48 ways to choose the
$5^{th}$ card.  The probability of four of a kind is ${{13 \cdot 48}
\over {52! \over {5! 47!}}}$.

\ppart A flush (5 cards from the same suit)
There is $4$ ways to choose a suit and $C(13, 5)$ ways to choose 5
cards from the same suit.  The probability of a flush is ${{4\cdot
C(13,5)} \over {52! \over {5! 47!}}} = {4{13! \over {5! (13 -
5)!}}\over {52! \over {5! 47!}}}$.

\ppart Two pair (two pairs, where each pair is two cards with the same
value, but the two pairs have different values and the remaining card
does not have either value)

There are $13$ of a kind and $C(4,2)$ ways to choose 2 cards out of 4
of a kind.  There are $12$ of a kind and $C(4,2)$ ways to choose 2
cards out of 4 of a kind and 44 ways to choose the $5^{th}$ card.  The
probability is ${13 \cdot C(4,2) \cdot 12 \cdot C(4,2) \cdot 44} \over
{52! \over {5! 47!}}$.

\eparts

\problem % combinations
A batch of 50 items contains 10 defective items.  Suppose 5
of these items are selected at random (without replacement) and
tested. 
 
\bparts 
\ppart
What is the probability that exactly 4 of the items tested
are defective?  

\begin{equation}
{{10 \choose 4}{40 \choose 1}} \over { 50 \choose 5}
\end{equation}

\ppart What is the most likely number of defective items in the
sample?

\begin{eqnarray*}
\Pr[\mbox{0 defects}] &=&{{{10 \choose 0}{40 \choose 5}} \over { 50 \choose 5}} \\
\Pr[\mbox{1 defect}] &=&{{{10 \choose 1}{40 \choose 4}} \over { 50 \choose 5}} \\
\Pr[\mbox{2 defects}] &=&{{{10 \choose 2}{40 \choose 3}} \over { 50 \choose 5}} \\
\Pr[\mbox{3 defects}] &=&{{{10 \choose 3}{40 \choose 2}} \over { 50 \choose 5}} \\
\Pr[\mbox{4 defects}] &=&{{{10 \choose 4}{40 \choose 1}} \over { 50 \choose 5}} \\
\Pr[\mbox{5 defects}] &=&{{{10 \choose 5}{40 \choose 0}} \over { 50 \choose 5}} \\
\end{eqnarray*}

Thus, it is most likely that that there exists 1 defective item in the sample.
\eparts


\problem %multinomial
Suppose that I randomly permute the letters in MISSISSIPPI.
What is the probability that all the S's end up next to each other?

There are ${11 \choose 1, 4, 4, 2}$ permutations of the letters (all
equally likely).  We can count the number of permutations with all
the S's next to each other by replacing them with a single new
letter.  So there are ${8 \choose 1, 4, 1, 2}$ of them.
Thus the probability that all the S's end up next to each other
is $\frac{{8 \choose {1, 4, 1, 2}}}{{11 \choose {1, 4, 4, 2}}} = \frac{4}{165}$.

\iffalse
\problem Suppose that I have $n$ dollars.  Each day I buy either a
pretzel (1\$), a soda (2\$) or a croissant (2\$).  
\bparts
\ppart
How many different
ways are there for me to spend my money?  Hint: devise and solve a
linear recurrence.
\ppart If all such ways are equally likely, what is the probability
that I never buy a pretzel?
\eparts
\fi

\problem Prove that if $A_1,\ldots,A_n$ is a partition of the sample
space, $S$,
then
\[
\Pr[B] = \sum_{i=1}^n \Pr[B \mid A_i] \cdot \Pr[A_i]
\]

Let $S$ be the sample space partitioned by $A_1, \ldots , A_n$.

\begin{eqnarray*}
\Pr[B] &=& \Pr[B \cap S]  \\
       &=& \Pr[B \cap (A_1 \cup A_2 \cup \ldots \cup A_n)]
\qquad \mbox{since $A_1, \ldots , A_n$ partions $S$}\\
       &=& \Pr[(A_1 \cap B) \cup \cdots \cup (A_n \cap
B)]  \\
       &=& \Pr[A_1 \cap B] + \Pr[A_2 \cap B] + \cdots +
\Pr[A_n \cap B]  \\
       &=& \Pr[B \mid A_1] \cdot \Pr[A_1] + \ldots + \Pr[B \mid A_n]
\cdot \Pr[A_n] \qquad \mbox{by conditional probability} \\
       &=& \sum_{i=1}^n \Pr[B \mid A_i] \cdot \Pr[A_i]
\end{eqnarray*}


\problem

A witness to a crime says that the criminal had a beard.
We know from experience that if a criminal has a beard, 
witnesses will say so with probability~$0.8$, 
and if the criminal does not have a beard, witnesses will say that
he does with probability $0.12$.
If 15\% of the population has beards, what is the probability 
that a random criminal has a beard if the witness says he does?

Let $A$ be the event that the witness says the criminal has a beard
and $B$ be the event that the criminal actually does have a beard.
The given information is that
$\Pr[A \mid B] = 0.8, \Pr[A \mid \bar{B}] = 0.12,$ and
$\Pr[B] = 0.15$.
So $\Pr[A \cap B] = \Pr[A \mid B] \cdot Pr[B] = 0.8 \cdot 0.15 = 0.12$
and
$\Pr[A \cap \bar{B}] = \Pr[A \mid \bar{B}] \cdot Pr[\bar{B}] =
0.12 \cdot (1 - 0.15) = 0.102.$
Then
$\Pr[A] = Pr[A \cap B] + Pr[A \cap \bar{B}] = 0.12 + 0.102 = 0.222.$
We are asked to find $Pr[B \mid A]$, which is given by
$Pr[B \mid A] = \frac{\Pr[B \cap A]}{\Pr[A]} = \frac{0.12}{0.222} = 
\frac{20}{37}.$



\problemopt %sample tree
Suppose you are playing the {\em Let's Make a Deal} game, but
you happen to know that the prize is going to be behind doors 1, 2, or
3 with probabilities $p_1 \geq p_2 \geq p_3$, respectively.  How
should you play?  What are your chances of winning?  Can you prove
your strategy is optimal?


\problemopt
Let $f$ be a function $f\colon \{0,1\}^n \to \{0,1\}$.
We think of $f$ as an electoral system in which 
if people vote $X_1,\ldots, X_n$, 
$f(X_1,\ldots,X_n)$ wins the elections.

A natural requirement on $f$ is monotonicity:
\[\forall i.X_i\leq Y_i \Rightarrow
 f(X_1,\ldots, X_n)\leq f(Y_1,\ldots, Y_n),\]
i.e. if some people change their vote from 
$V$ to $1-V$, this can only change the 
result of the elections from $V$ to $1-V$.

We measure the quality of an  electoral system $f$
by the probability that a randomly selected 
person $R$ can change the outcome of the elections 
by changing his vote, when all other people vote 
independently and uniformly at random.

What is the the ``best" electoral system, i.e., 
which monotone function $f$ maximizes the 
probability that 
\[f(X_1,\ldots, X_R,\ldots, X_n)\neq 
  f(X_1,\ldots, 1-X_R,\ldots, X_n)\]
when $X_1,\ldots, X_n$ are independent 
uniform binary random variables 
and $R$ is an independent uniform random 
variable with values in $\{1,\ldots,n\}$?
 

\end{problems}

\end{document}


% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
