\documentclass[11pt]{article}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\usepackage{latexsym,amsmath,amssymb}
\usepackage[all]{xy}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{Mathematics 375 -- Probability Theory}
\centerline{Solutions for Problem Set 2}
\centerline{September 16, 2011}
\vskip 10pt
\noindent
2.25.  This is clearly nonsense.  While it is true that every car
is either a Volkswagen or not, the numbers of Volkswagens and other
cases are certainly not the same.  The probability should be 
$$\frac{\# {\rm Volkswagens}}{\# {\rm all\ cars}}.$$
\vskip 10pt
\noindent
2.26.  (a) Number the cans 1 - 4 in such a way that
cans 1 and 2 contain water and 3 and 4 do not. 
(Note:  There are other, more complicated, ways to solve this too, in 
which each possible assignment of the cans actually containing water
is also taken into account, but this approach is better since the numbering
can be done in one particular way to start.)  Each sample point will consist
of a 4-tuple where the entries indicate whether the ``expert'' found water in the 
corresponding can using the divining rod.  Say $W$ means the ``expert'' found
water in that can, and $NW$ means the ``expert'' found no water in that can.
The sample space consists of all 4-tuples containing 2 $W$'s and 2 $NW$'s:
\begin{align*}
S &=\{(W,W,NW,NW),(W,NW,W,NW),(W,NW,NW,W),(NW,W,W,NW),(NW,W,NW,W),\\
  &\quad (NW,NW,W,W)\}.
\end{align*}
(b)  If the ``expert'' is just guessing, that is equivalent to selecting
one of the sample points at random with each possibility equally likely.  
The probability that the correct one
$(W,W,NW,NW)$ is chosen is $\frac{1}{6}$.  
\vskip 10pt
\noindent
2.29.  Let the men be $m1,m2,m3,m4$ and the women $w1,w2$.
(a)  The experiment consists of selecting two individuals 
independently and at random out of the 6.  A sample point
will consist of a set (unordered pair) like $m3w1$.

(b)  The sample space consists of 
\begin{align*} 
S &= \{m1m2,m1m3,m1m4,m1w1,m1w2,m2m3,m2m4,m2w1,m2mw2,m3m4,\\
   & \quad m3w1,m3w2,m4w1,m4w2,w1w2\}.
\end{align*}

(c)  The probability is $1/15$.  
\vskip 10pt
\noindent
2.33.  (a)  The sample points are ordered 4-tuples where
the entries indicate whether the corresponding family's income
was above ($H$) or below or equal to the median ($L$).  
(b)   We have
\begin{align*}
A &= \{(H,H,L,L),(H,L,H,L),(H,L,L,H),(L,H,H,L),(L,H,L,H),(L,L,H,H),\\
  &\quad (H,H,H,L),(H,H,L,H),(H,L,H,H),(L,H,H,H),(H,H,H,H)\}\\
B &= \{(H,H,L,L),(H,L,H,L),(H,L,L,H),(L,H,H,L),(L,H,L,H),(L,L,H,H)\}\\
C &= \{(H,H,H,L),(H,H,L,H),(H,L,H,H),(L,H,H,H)\}.
\end{align*}
(c)  Since each sample point is equally likely, we assign probability 
$\frac{1}{16}$ to each one.  Then $P(A) = \frac{11}{16}$,
$P(B) = \frac{6}{16} = \frac{3}{8}$ and $P(C) = \frac{4}{16} = \frac{1}{4}$.
\vskip 10pt
\noindent 
2.34. (a)  The sample points are triples representing the stations
chosen by each of the three patients.  There are 27 of these:
\begin{align*}
S &= \{(1,1,1), (1,1,2), (1,1,3), (1,2,1), (1,2,2), (1,2,3), (1,3,1), (1,3,2),\\
&\quad (1,3,3), (2,1,1), (2,1,2), (2,1,3), (2,2,1), (2,2,2), (2,2,3), (2,3,1),\\
&\quad (2,3,2), (2,3,3), (3,1,1), (3,1,2), (3,1,3), (3,2,1), (3,2,2), (3,2,3),\\
&\quad (3,3,1), (3,3,2), (3,3,3)\}.
\end{align*}
(b)  The event $A = \{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)\}$.
(c)  If the selection of the station is completely random, we would expect
each sample point in $S$ to be equally likely.  Therefore 
$P(A) = \frac{6}{27} = \frac{2}{9}$.  
\vskip 10pt
\noindent
2.36.  The number is the same as the number of permutations
of the set $\{1,2,3\}$: $3\cdot 2 \cdot 1 = 3! = 6$.
\vskip 10pt
\noindent
2.37. (a) There are $6! = 720$ different orderings of the six cities.

(b)  Intuitively, the answer should be $1/2$ because there should
be an equal chance of visiting Denver first or of visiting
San Francisco first if an itinerary is chosen randomly.  To show
this rigorously, there are several different possible approaches.

{\it ``Brute Force:''}  Note that the orderings in which Denver (D) is visited 
before San Francisco (S) are of $\binom{6}{2}$ types:  
$DSxyzw, DxSyzw, \cdots, xyzwDS$ (corresponding to the different
possible placements of $D,S$ among the 6 cities.  
For each of these types, the other four cities can be visited
in any of $4!$ possible orders.  So there are 
$\binom{6}{2}\cdot 4!$ such itineraries.  Then 
$P($D before S$) = \frac{\binom{6}{2}\cdot 4!}{6!} = \frac{1}{2}.$

{\it ``Slick:''}  For each ordering in which Denver is visited
before San Francisco, there is a corresponding ordering in which
San Francisco is visited before Denver -- just switch the 
order of those two cities, leaving the others fixed.  For instance
$$DxSyzw \mapsto SxDyzw.$$
Since we can always switch back too:
$$SxDyzw \mapsto DxSyzw,$$
this mapping is invertible, hence
one-to-one and onto.  Therefore, the number of orderings in which
$D$ comes before $S$ is the same as the number in which $S$ comes
before $D$.  Since every ordering of the 6 cities falls into 
one of these classes or the other, this means
that each of them is exactly half of the total.  
\vskip 10pt
\noindent
2.38.  By the $m\times n$ rule applied repeatedly, 
there are $4 \times 3 \times 4 \times 5  = 240$ possible dinners.
\vskip 10pt
\noindent
2.40.  (a)  This is just like 2.38 above: $5 \times 4 \times 2 = 40$
different combinations.  (Note that the color is not included in this part.)
(b)  Now by the $m \times n$ rule again taking colors into account too,
$40 \times 8 = 320$ different combinations of all 4 features (style, engine,
transmission, color).  
\vskip 10pt
\noindent
2.45.  The coefficient is the multinomial coefficient 
$$\left( \begin{array}{ccc} &17& \\ 2 & 5 & 10 \end{array} \right) = \frac{17!}{2!5!10!} = 408408.$$
\noindent
2.46.  Note that by numbering the games, we are thinking of them as
distinguishable.  But the two teams playing in game 1 do not
have any particular order -- just a set of two teams.  
So there are $\binom{10}{2}$ possible assignments
of teams for game 1, then $\binom{8}{2}$ assignments for game 2 from
the remaining 8 teams, etc.  The total number is
$$\binom{10}{2} \cdot \binom{8}{2}\cdot \binom{6}{2} \cdot\binom{4}{2}\cdot\binom{2}{2}.$$ 
This is the same as the multinomial coefficient 
$$\left(\begin{array}{ccccc} & &10& & \\ 2&2&2&2&2 \end{array}\right) = 113400.$$
\noindent
2.50.  The potential winning numbers were the ones containing only 
4 and 6 digits: 
$$444, 446, 464, 644, 466, 646, 664, 666.$$
(So if one of these numbers was chosen at random and played in the 
lottery the chance of winning would have been $\frac{1}{8}$ rather 
than the probability $\frac{1}{1000}$ without the ``doctoring''
of the Ping-Pong balls.) 
\vskip 10pt
\noindent
2.55.  (a)  The sample is an unordered set of size
10 chosen from the 90 total nurses so the number of 
possible samples is $\binom{90}{10}$.  (b)  The possible samples
described here consist of $4$ out of the $20$ men, and $6$ out
of the $70$ women.  The number of such samples is found by the
$m \times n$ rule:  $\binom{20}{4} \binom{70}{6}$.  
So the probability of getting a 
sample of this form is:
$$\frac{\binom{20}{4}\binom{70}{6}}{\binom{90}{10}} \doteq .111$$
\noindent
2.64.  There are $6! = 720$ possible orders of the $6$ distinct
numbers $1,2,3,4,5,6$, and $6^6 = 46656$  possible 
outcomes for the six tosses of the dice, all equally likely.  
Hence the probability
is 
$$
6!\cdot \left(\frac{1}{6}\right)^6 = \frac{720}{46656} = \frac{5}{324}.
$$
\noindent
2.65.  Now there are $5! = 120$ different orders of the $5$
distinct numbers $1,2,3,4,5$.  The difference between this
situation and the one in 2.64 is that it is now twice as 
likely that a $5$ will be rolled.  So the probability is
$$
5!\cdot \left(\frac{1}{6}\right)^4 \frac{2}{6} = \frac{5}{162}.
$$
\noindent
2.70.  The multinomial coefficients are the coefficients 
of the various terms $x_1^{n_1} \cdots x_k^{n_k}$
in the expanded and collected form of 
$$(x_1 + \cdots + x_k)^n$$
(note $n_1 + \cdots + n_k = n$ in each term).  If
we substitute $x_1 = \cdots x_k = 1$ in both sides of the 
equation, we get
$$k^n = {\rm sum\ of\ all\ multinomial\ coefficients\ with\ upper\ index\ } n.$$
This establishes the fact to be proved.  

\vskip 10pt 
\noindent
{\it Extra Credit:}  The formula 
$$(y_1 + \cdots + y_k)^n = \sum \left(
\begin{array}{ccccc} &&n&&\\ n_1 & n_2 &\cdots & n_{k-1} & n_k \end{array}\right) y_1^{n_1} \cdots y_k^{n_k}$$
can be established by induction on $k$.  The base case is $k = 2$, where this 
formula is the ordinary binomial theorem, since when $n = n_1 + n_2$, 
$$\left(\begin{array}{ccc} &n& \\ n_1 & & n_2 \end{array}\right) = 
\frac{n!}{n_1!n_2!} = \frac{n!}{n_1! (n - n_1)!} = \binom{n}{n_1}.$$
For the induction step we want to assume the formula holds for the expansion of 
the $n$th power of a sum of $k$ terms, and consider the expansion of the $n$th power of a sum of 
$k+1$ terms.  We have by the induction hypothesis for powers
of sums of $k$ terms, then the base case for the expansion of the 
$(y_k + y_{k+1})^{n_k}$:
\begin{eqnarray*}
(y_1 + \cdots + y_k + y_{k+1})^n &=& ((y_1 + \cdots + y_{k-1} + (y_k + y_{k+1}))^n \\
&=& \sum \left(
\begin{array}{ccccc} &&n&&\\ n_1 & n_2 &\cdots & n_{k-1} & n_k \end{array}\right) y_1^{n_1} \cdots y_{k-1}^{n_{k-1}} (y_k+y_{k+1})^{n_k}\\
&=& \sum \left(
\begin{array}{ccccc} &&n&&\\ n_1 & n_2 &\cdots & n_{k-1} & n_k \end{array}\right) y_1^{n_1} \cdots y_{k-1}^{n_{k-1}} \cdot \sum_{\ell + m = n_k} \binom{n_k}{\ell} y_k^\ell y_{k+1}^m.
\end{eqnarray*}
For any particular $\ell$ and $m$, since $\ell + m = n_k$, the coefficient of 
$$y_1^{n_1} \cdots y_{k-1}^{n_{k-1}} y_k^\ell y_{k+1}^m$$ 
when we expand this out will be:
\begin{eqnarray*}
\left(\begin{array}{ccccc} &&n&&\\ n_1 & n_2 &\cdots & n_{k-1} & n_k \end{array}\right) \binom{n_k}{\ell}
&=&
\frac{n!}{n_1!\cdots n_{k-1}! n_k!} \cdot \frac{n_k!}{\ell!\, m!}\\
&=& 
\frac{n!}{n_1!\cdots n_{k-1}!\, \ell!\, m!}\\
&=& \left(\begin{array}{cccccc} &&n&&&\\ n_1 & n_2 &\cdots & n_{k-1} & \ell & m \end{array}\right).
\end{eqnarray*}
This shows what we want since $(n_1, \ldots, n_{k-1}, \ell, m)$ now
runs over all collections of $k+1$ nonnegative integers satisfying
$n_1 + \cdots + n_{k-1} + \ell + m = n$.  
\noindent
\vskip 10pt
2.71.  (a)  $P(A|B) = \frac{P(A\cap B)}{P(B)} = \frac{1}{3}$.

(b) $P(B|A) = \frac{P(A\cap B)}{P(A)} = \frac{1}{5}$

(c)  We have $P(A\cup B) = P(A) + P(B) - P(A\cap B) = .7$.
Therefore, $P(A|A\cup B) = \frac{P(A)}{P(A\cup B)} = \frac{5}{7}$.

(d) $P(A|A\cap B) = 1$, since $(A\cap B)\cap A = A\cap B$.
 
(e) $P(A\cap B|A\cup B) = \frac{1}{7}$.
\vskip 10pt
\noindent
2.72.  (a)  $P(A\cap M) = .24$ while $P(A) = .6$ and $P(M) = .4$.
Since $P(A\cap M) = P(A)P(M)$, the events $A, M$ \emph{are independent}
(see Definition 2.10).

(b)  $P(\overline{A} \cap F) = .24$ while $P(\overline{A}) = .4$
and $P(F) = .6$.  Since $P(\overline{A} \cap F) = P(\overline{A})P(F)$,
these events are also independent. 
\vskip 10pt
\noindent
2.74. (a)  $P(A\cap D) = .2$, while $P(A) = .61$ and $P(D) = .3$ 
since $.2 \ne (.61)(.3)$, $A$ and $D$ are \emph{not independent}.

(b)  $P(B \cap D) = .09 = P(B)P(D) = (.3)(.3)$.  So $B$ and $D$
\emph{are independent}.

(c)  $P(C \cap D) = .01$, but  $P(C)P(D) = (.09)(.3) = .027$.
So $C$ and $D$ are \emph{not independent}.
\vskip 10pt
\noindent
2.77.  (a) $P(A) = .4$ (b) $P(B) = .37$ (c)  $P(A\cap B) = .1$ (d)
$P(A \cup B) = .67$ (e) $P(\overline{A}) = .6$ (f) $P(\overline{A\cup B}) = .33$
(g) $P(\overline{A\cap B}) = .9$ (h) $P(A|B) = \frac{P(A\cap B)}{P(B)} \doteq .27$
(i) $P(B|A) = \frac{P(A\cap B)}{P(A)} = .25$.    
\end{document}
