\documentclass[11pt, twoside]{article}
\input{macros-course}
%\input{../macros-course}
\usepackage{graphicx}

\renewcommand{\implies}{\longrightarrow}
\newcommand{\ignore}[1]{}
\askaboutsolutions
\begin{document}
\pset{10}{May 1, 2001}{2:35pm in lecture, Thursday, May 10, 2001}
\renewcommand{\labelenumi}{\bf (\alph{enumi})}
\renewcommand{\labelenumii}{\bf (\roman{enumi})}
\textbf{Be sure to indicate your TA's name clearly on the solutions
you turn in}.

\paragraph{Reading}
Rosen, \textit{Discrete Mathematics and Its Applications},
Sections 4.4 and 4.5

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should
mention their names on top of the problem set. If you did not
collaborate with anyone, you should explicitly say so. As a reminder,
the write-up of your solutions should be entirely your own.

\paragraph{Self-study}
The following exercises are \emph{optional;} do them if you think you
need the practice. The mini-quiz in tutorial on Friday will draw
(only) from these problems.

Exercises from Rosen (answers in the back of the book): 
Section 4.4: 21, 28, 31, 33.
Section 4.5: 27, 29, 33.


\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset10 problem2 spring98
\problem
\bparts
\ppart%{\bf (5 points)}
Let $R_1$ and $R_2$ be two independent random variables.
$R_1$ takes the values $0,1$ with equal probability.
$R_2$ has the following distribution.
\[
\begin{array}{|c|c|}
\hline
 \text{Value of }R_2 & \text{Probability} \\
\hline
           1           &    \frac{1}{2}     \\
\hline
           2           &    \frac{1}{4}     \\
\hline
           4           &    \frac{1}{4}     \\
\hline
\end{array}
\]


Compute the distribution of $2 ^{R_1} R_2$. Give your answers in a table, as shown below\footnote{You should not assume that your answer must necessarily have 3 rows} :
\[
\begin{array}{|c|c|}
\hline
 \text{Value of }2 ^{R_1} R_2  & \text{Probability} \\
\hline
 \cdots &   \cdots    \\
 \cdots &   \cdots    \\
 \cdots &   \cdots    \\\hline
\end{array}
\]

\solution{
{\bf Solution}

Let $X = 2 ^{R_1} R_2$. 

$\Pr(X = 1) = \Pr(R_1 = 0 \wedge R_2 = 1) = 1/4$.\\
$\Pr(X = 2) = \Pr((R_1 = 0 \wedge R_2 = 2)
  \vee (R_1 = 1 \wedge R_2 = 1) = 3/8$.\\
$\Pr(X = 4) = \Pr((R_1 = 0 \wedge R_2 = 4)\vee(R_1 \wedge R_2=2))=1/4$.\\
$\Pr(X = 8) = \Pr(R_1=1 \wedge R_2=4) = 1/8$.\\

To sum up:
\[
\begin{array}{|c|c|}
\hline
 \text{Value} & \text{Probability} \\
\hline
      1       &    \frac{1}{4}     \\
\hline
      2       &    \frac{3}{8}     \\
\hline
      3       &    \frac{1}{4}     \\
\hline
      4       &    \frac{1}{8}     \\
\hline
\end{array}
\]


}

\ppart%{\bf (5 points)}
Now suppose that $R_1$ and $R_2$ are no longer independent.
In particular, $R_1 = 0$ if $R_2$ is 1, and $R_1 =1$ when $R_2$ is 2 or 4.
$R_2$ has the same distribution as in part (a).

Compute the distribution of $2^{R_1} R_2$. Give your answers in a table, as you did above.

\solution{
{\bf Solution}

$\Pr(X = 1) = \Pr(R_2 = 1) = 1/2$.\\
$\Pr(X = 4) = \Pr(R_2 = 2) = 1/4$.\\
$\Pr(X = 8) = \Pr(R_2 = 4) = 1/4$.\\
So the final result is:
\[\begin{array}{|c|c|}
\hline
 \text{Value} & \text{Probability} \\
\hline
      1       &    \frac{1}{2}     \\
\hline
      4       &    \frac{1}{4}     \\
\hline
      8       &    \frac{1}{4}     \\
\hline
\end{array}
\]
}

\eparts

%%%%%%%%%%%%%%  Fall 2000  PS 11   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%  Fall 2000  PS 11   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem Several statements involving probability
are listed below.  Assume that $A$ and $B$ are events, $S$ and $T$ are
random variables, and the underlying sample space is countable.
Furthermore, assume that all expectations exist.  For each statement,
describe restrictions on $A$, $B$, $S$, and $T$ sufficient to ensure
that the statement is true.  Make your restrictions as minimal as you
can.  No proofs are necessary.

\begin{problemparts}
%\begin{enumerate}

\problempart $\Pr(A \cup B) = \Pr(A) + \Pr(B)$
%\item[\textbf{(a)}] $\Pr(A \cup B) = \Pr(A) + \Pr(B)$

\solution{
\textbf{Solution:}\\
This statement is true provided that the event $A \cap B$
has probability zero.}

\problempart $\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)$
%\item[\textbf{(b)}] $\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)$

\solution{
\textbf{Solution:}\\
This statement is always true.
}

\problempart $\Pr(A \cap B) = \Pr(A) \cdot \Pr(B)$
%\item[\textbf{(c)}] $\Pr(A \cap B) = \Pr(A) \cdot \Pr(B)$

\solution{
\textbf{Solution:}\\
This statement is true provided that events $A$ and $B$ are independent.
}
\problempart $\Pr(A \cap B) \leq \Pr(A)$
%\item[\textbf{(d)}] $\Pr(A \cap B) < \Pr(A)$

\solution{
\textbf{Solution:}\\
This statement is always true.
}
\problempart $\Pr(A \cap B) < \Pr(A)$
%\item[\textbf{(d)}] $\Pr(A \cap B) < \Pr(A)$

\solution{
\textbf{Solution:}\\
This statement is true provided $\Pr(A \cap \overline{B}) > 0$.
}

\problempart $\Ex(S + T) = \Ex(S) + \Ex(T)$
%\item[\textbf{(e)}] $\Ex(S + T) = \Ex(S) + \Ex(T)$

\solution{
\textbf{Solution:}\\
This statement is always true.
}

\problempart $\Ex(S \cdot T) = \Ex(S) \cdot \Ex(T)$
%\item[\textbf{(f)}] $\Ex(S \cdot T) = \Ex(S) \cdot \Ex(T)$

\solution{
\textbf{Solution:}\\
This statement is true provided that random variables $S$
and $T$ are independent.}

\end{problemparts}
%\end{enumerate}   

%%%%%%%%%%%%%  Fall 2000     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem %{\bf (10 points)} 
\problempart
Suppose that I roll a 4-sided die, a 6-sided
die, an 8-sided die, a 10-sided die, a 12-sided die, and a 20-sided
die.  What is the expected number of 6's that come up?  (Assume that
all of the dice are fair.)
\solution{\ssl
  
  Let $X_i$~be the number of 6's on the $i$-sided die for $i \in
  \{4,6,8,10,12,20\}$. Then the number of 6's on all dice is $X_4 +
  X_6 + X_8 + X_{10} + X_{12} + X_{20}$ and by linearity of expectation
  \begin{displaymath}
    \expect{X_4 + X_6 + X_8 + X_{10} + X_{12} + X_{20}} = 
    \expect{X_4} + \expect{X_6} + \expect{X_8}
    + \expect{X_{10}} + \expect{X_{12}} + \expect{X_{20}}.
  \end{displaymath}
  Since every die has exactly one 6, $\expect{X_i} = 1 / i$, which gives
  \begin{displaymath}
    \expect{X_4 + X_6 + X_8 + X_{10} + X_{12} + X_{20}} = 
    \frac{0}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{10} +
    \frac{1}{12} + \frac{1}{20}
    = \frac{21}{40}\,.
  \end{displaymath}
}

\problempart
Suppose that I roll $n$ dice that are
6-sided, fair, and mutually independent.  What is the expected value
of the largest number that comes up?

\hint You may want to use the ``alternative" formula for expectation:
$\expect{M} = \sum_{i=0}^{\infty} \Pr(M > i)$. (This formula is valid
since the random variables involved are non-negative.)

\solution{\ssl  
  Let the random variable $M$ be the largest number that comes up. To
  use the identity $\expect{M} = \sum_{i=0}^{\infty} \Pr(M > i)$ we
  must compute the probability of the event $M > i$; that is, the
  event that some die shows a value greater than $i$.
  \begin{displaymath}
    \Pr(M > i)
    = 1 - \Pr(\text{every die $\leq i$})
    = 1 - \prod_{k=1}^n \Pr(\text{$k$th die $\leq i$})
    = 1 - (i/6)^n,
  \end{displaymath}
  where the second equality holds since the dice are independent. Therefore,
  \begin{displaymath}
    \expect{M}
    = \sum_{i=0}^5 \Pr(M > i)
    = \sum_{i=0}^5 1 - (i/6)^n
    = 6 - \frac{1^n + 2^n + 3^n + 4^n + 5^n}{6^n}\,.
  \end{displaymath}}





\problem There is a dinner party for $n \geq 2$
couples.  The hostess chooses a seating arrangement for the $2n$
people around a circular table uniformly at random.  What is the
expected number of couples such that the husband and wife are sitting
next to each other?

\hint Use indicator random variables and linearity of expectation. What's the probability that Mr. Jones is sitting next to Mrs. Jones? 

\solution{
\textbf{Solution:}\\
Let $I_k$ be an indicator variable for the event that couple
$k$ is sitting together.  Then the number of couples sitting together
is $I_1 + I_2 + \ldots + I_n$.  The probability that a couple is
seated together is $2 / (2n-1)$, since a wife is equally likely to
occupy each of the $2n-1$ positions relative to her husband and there
are 2 positions right next to him.  Consequently, $\Pr(I_k = 1) = 2 /
(2n-1)$, and we can reason as follows:

\begin{eqnarray*}
\Ex(\text{couples sitting together})
    & = &   \Ex\left(\sum_{k=1}^n I_k\right) \\
    & = &   \sum_{k=1}^n \Ex(I_k) \\
    & = &   \sum_{k=1}^n \Pr(I_k = 1) \\
    & = &   \sum_{k=1}^n \frac{2}{2n-1} \\
    & = &   \frac{2n}{2n-1}
\end{eqnarray*}

Thus, regardless of the size of the party, the expected number of
couples seated together is always close to 1.}

\problem Suppose that I choose a listing of the
numbers $1, 2, \ldots, n$ uniformly at random.  What is the expected
number of entries that are greater than all preceding entries?  For
example, in the listing 4, 2, 1, 5, 3, the numbers 4 and 5 are greater
than all preceding entries\footnote{This problem can be equivalently phrased as follows: There are n people whose heights are $1, 2, \ldots, n$. I choose a random permutation, and line them up accordingly. What is the expected number of people who can see what's going on in front of the line? We are assuming that a person can see if and only if all the people in front of him/her are shorter.}

\hint What's the probability that the first entry is greater than all the preceding entries? What about the second one? 

\solution{
\textbf{Solution:}\\
Let $i_k$ be an indicator for the event that the $k$-th entry is
greater than the preceding $k-1$ entries.  By linearity of expectation

\begin{eqnarray*}
\Ex(\text{\# new maxima})
    & = &   \sum_{k=1}^n \Ex(i_k) \\
    & = &   \sum_{k=1}^n 1 \cdot \Pr(i_k = 1) + 0 \cdot \Pr(i_k = 0) \\
    & = &   \sum_{k=1}^n \Pr(i_k = 1)
\end{eqnarray*}

All that remains is to compute $\Pr(i_k = 1)$, which is the
probability that the $k$-th entry is greater than all preceding
entries.  Note that each of the first $k$ entries is equally likely to
be the largest.  Therefore, $\Pr(i_k = 1) = \frac{1}{k}$.
Substituting into the equation above gives:

\begin{eqnarray*}
\Ex(\text{\# new maxima})
    & = &   \sum_{k=1}^n \Pr(i_k = 1) \\
    & = &   \sum_{k=1}^n \frac{1}{k} \\
    & = &   H_n
\end{eqnarray*}
}

          


\problem

% modifed from spring 97 Pset 13, 3

There are $n$ MIT students who are taking 6.042 and 6.003 this term.  To
make it easier on themselves, the professors in charge of these classes
have decided to randomly permute their class lists and then assign
students grades based on their rank in the permutation\footnote{\dots just
as many students have suspected \texttt{:-)}}.  Assume all permutations
are equally likely and that the ranking in each class is independent of
the other.

\bparts

\ppart
What is the expected number of students that have a higher rank
in 6.042 than 6.003?

\solution{\ssl

Let $X_i$ be random variable whose value is 1 if student i has higher rank
in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$ for
6.042 than the probability that student $i$ has higher rank on 6.042,
given that the student has rank $r$ in 6.042, is $(r-1)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the
probability that student $i$ has higher rank in 6.042 is
\[
\sum_{1\leq r \leq n}  \frac{1}{n} \frac{r-1}{n} = \frac{n-1}{2n}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x} = \expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{n-1}{2}.
\]

Another way to solve this problem is to observe that students with higher
rank in one class have lower rank in the other class, so by symmetry, the
expected number of higher- and lower-ranked students in either class is
the same.  The expected number of students with the same rank equals 1 by
linearity of expectation, since probability student ranked the same in
both schools is $1/n$.  These observations now yield same answer as above.

}

\ppart
What is the expected number of students that have a ranking at
least $k$ higher in 6.042 than in 6.003?

\solution{\ssl

This part can be done in the same way as the previous one.  Let $X_i$ be
the random variable whose value is 1 if student $i$ is ranked at least $k$
higher in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$
$(r>k)$ for 6.042 than the probability that student $i$ has at least $k$
higher rank in 6.042 given student ranked $r$ in 6.042 is $(r-k)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the probability
that student $i$ has at least $k$ higher rank in 6.042 is
\[
\sum_{k+1\leq r\leq n} \frac{1}{n} \frac{r-k}{n} = \frac{(n-k)(n-k+1)}{2n^2}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x}=\expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{(n-k)(n-k+1)}{2n}.
\]

}

\eparts

\problem %{\bf (15 points)} 
In the board game Monopoly, the number of
squares that a player advances in a single turn is determined by up to
three rolls of dice as follows.

\begin{itemize}
\item Initially, the player rolls two dice, sums the results, and
advances that many squares.

\item If the same number comes up on both dice---this is called
\emph{rolling a double}---then the player rolls the dice a second time,
sums the results, and advances that many additional squares.

\item If the player rolled on double on the second roll, then the player
rolls the dice a third time, sums the results, and advances that many
additional squares.

\item However, if third roll was a double, then the player ``goes to
jail''.  We will treat this as though he had to reset his position to
where he was just before the first roll, so the total number of squares
advanced by the player in this case is zero.
\end{itemize}

What is the expected number of squares that a player advances in a single
turn?  Assume that the dice are fair and six-sided and that rolls are
mutually independent.

\solution{\ssl
Here is one approach to the problem.

It's convenient to assume the dice are \emph{always} rolled three times,
with the player simply ignoring results of any roll which was preceded by
a non-double roll.

Let the random variable $R_i$ be the sum of the two dice on the $i$th
roll, and let $I_i$ be an indicator for the event that the $i$th roll was
a double.

We can express the random variable $R$, the number of squares advanced by
the player, as follows:
\[
R = R_1 + I_1 R_2 + I_1 I_2 R_3 - I_1 I_2 I_3 (R_1 + R_2 + R_3)
\]

Since the dice rolls are independent, we know that $R_i$'s and $I_j$'s at
different rolls are independent.  We can take expectations of both sides
and reason as follows:
\begin{eqnarray*}
\expect{R}      & = &   \expect{R_1}
                 + \expect{I_1 R_2}
                 + \expect{I_1 I_2 R_3} \\
        & & \mbox{}
                 - \expect{I_1 I_2 I_3 R_1}
                 - \expect{I_1 I_2 I_3 R_2}
                 - \expect{I_1 I_2 I_3 R_3} \\
        & = &   \expect{R_1}
                 + \expect{I_1} \cdot \expect{R_2}
                 + \expect{I_1} \cdot \expect{I_2} \cdot \expect{R_3} \\
&&\mbox{}        - \expect{I_2} \cdot \expect{I_3} \cdot \expect{I_1 R_1} \\
&&\mbox{}        - \expect{I_1} \cdot \expect{I_3} \cdot \expect{I_2 R_2} \\
&&\mbox{}        - \expect{I_1} \cdot \expect{I_2} \cdot \expect{I_3 R_3}
\end{eqnarray*}

Note that the expectation of $R_i$ is $7$, and the expectation of $I_i$ is
$1/6$.  Finally, note that $\expect{I_i R_i} = 7/6$ by direct calculation.
Substituting into the formula above gives:
\begin{eqnarray*}
\expect{R}      & = &   \frac{595}{72}.
\end{eqnarray*}

}


\problem %{\bf (15 points)} 
Each bag of Doritos contains a cool
sticker.  There are $n$ different kinds of sticker, and I want to
collect at least one sticker of each kind.  (Assume that sticker kinds
in Dorito bags are uniformly random and mutually independent.)

\begin{problemparts}
\problempart Suppose that I have already collected $k$ kinds of
sticker.  What is the expected number of additional bags of Doritos
that I must eat to collect one additional kind of sticker?

\solution{\ssl We can view this as a mean time to failure problem
  where ``failure'' is the same thing as getting a kind of sticker
  that is not already in the bag. Using the standard approach from the
  lecture notes,
  \begin{eqnarray*}
    \lefteqn{\expect{\text{number of bags to get new kind}}}\\
    & = &   \sum_{i=0}^{\infty} \prob{\text{number of bags to get new kind} > i} \\
    & = &   \sum_{i=0}^{\infty} \prob{\text{only old kinds in first $i$ bags}} \\
    & = &   \sum_{i=0}^{\infty} \left(\frac{k}{n} \right)^i \\
    & = &   \frac{n}{n-k}
\end{eqnarray*}
}

\problempart What is the expected number of bags of Doritos that I
must eat to collect at least one sticker of each kind?

\solution{\ssl We sum the expected number of bags to get the first
  kind, the expected number to get the second kind, and so forth.
  (This is possible because expectation is a linear operator.)
  \begin{eqnarray*}
    \lefteqn{\expect{\text{number of bags to get all kinds}}}\\
    & = &   \sum_{k=0}^{n-1} \frac{n}{n-k} \ = \   n \cdot
    \sum_{k=0}^{n-1} \frac{1}{n-k} \\
    & = &  n \cdot \sum_{j=1}^{n} \frac{1}{j} 
    \ = \   n H_n.
  \end{eqnarray*}
}

\end{problemparts}


\end{problems}

\end{document}                            

