\documentclass[11pt, twoside]{article}
\input{macros-course}
\def\lab#1#2#3{\substack{\text{#1}\\ \text{#2}\\ \text{#3}}}
%\input{../macros-course}
\usepackage{graphicx}

\renewcommand{\implies}{\longrightarrow}
\newcommand{\ignore}[1]{}
\askaboutsolutions
\begin{document}
\pset{10a}{May 1, 2001}{In tutorial, May 11, 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  \goals{Discrete Probability, teams} %{\bf (10 points)}
%{\bf (10 points)}
\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{\ssl

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{\ssl

$\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


\problem  \goals{Discrete Probability, teams} %{\bf (10 points)} %{\bf (15 points)} 
Let random variables $X$ and $Y$ be the
outcomes of two dice rolls.  Assume that the dice are fair, 6-sided,
and independent.  Each problem part below lists two random variables
derived from $X$ and $Y$.  State whether or not these two random
variables are independent and briefly sketch a justification for your
answer.

\begin{problemparts}
\problempart $X$ and $Y ^ 2$

\solution{\ssl
These random variables are independent.  For all $x$, $y$,

\begin{eqnarray*}
\Pr(X = x \cap Y^2 = y)
        & = &   \Pr(X = x \cap Y = \sqrt{y}) \\
        & = &   \Pr(X = x) \cdot \Pr(Y = \sqrt{y}) \\
        & = &   \Pr(X = x) \cdot \Pr(Y^2 = y)
\end{eqnarray*}

The second equation uses the independence of $X$ and $Y$.
}

\problempart $X + Y$ and $X - Y$

\solution{\ssl
These random variables are not independent.  For example:

\begin{eqnarray*}
\Pr(X + Y = 2)  & = &   \frac{1}{36} \\
\Pr(X - Y = 0)  & = &   \frac{1}{6} \\
\Pr(X + Y = 2 \cap X - Y = 0)
                & = &   \frac{1}{36} \\
                & \neq &        \frac{1}{36} \cdot \frac{1}{6}
\end{eqnarray*}
}

\problempart $\lfloor\frac{X-1}{2}\rfloor +
\lfloor\frac{Y-1}{2}\rfloor$ and $(X \bmod 2) + (Y \bmod 2)$

\solution{\ssl
These random variables are independent.  The quantities
$\lfloor\frac{X-1}{2}\rfloor$ and $(X \bmod 2)$ are independent, and
so are the analogous expressions involving $Y$.

\begin{eqnarray*}
\Pr\left(\left\lfloor\frac{X-1}{2}\right\rfloor = a\right)
        & = &   \frac{1}{3} \quad \quad a \in \{0, 1, 2\} \\
\Pr\left(X \bmod 2 = b\right)   & = &   \frac{1}{2}
        \quad \quad b \in \{0, 1 \} \\
\Pr\left(\left\lfloor\frac{X-1}{2}\right\rfloor = a
                \ \cap \ X \bmod 2 = b\right)
        & = &   \frac{1}{6} \quad \quad a \in \{0, 1, 2\}, b \in \{0, 1 \} \\
        & = &   \frac{1}{3} \cdot \frac{1}{2}
\end{eqnarray*}


Thus, the above expressions involve four mutually independent random
variables; two are summed in the first expression and two are summed
in the second.  Consequently, the two expressions are independent.
}

\end{problemparts}

\problem   \goals{Discrete Probability, teams} %{\bf (10 points)} % \textbf{Binomial distribution}

A highly parallel supercomputer has 65,536 processors.  The cooling
system can't always keep up, and any processor can fail during the
computation, independently with probability $10\%$.  Using
sophisticated failure-recovery algorithms, the software can handle the
failure of up to 7,000 processors.  Use the approximations in the
lecture notes to derive an approximate lower bound on the probability
that the computation will complete successfully, assuming all
processor failures are independent.

\solution{\ssl

Let $n = 65536$, $p = 0.9$, and $\alpha = \frac{n -
7000}{n}$.  The probability that at most $n - 7000$ processors
will be OK is $F_{n,p}(\alpha \cdot n)$. By theorem~3.1 in lecture
notes~21, we have
\begin{align*}
F_{n,p}(\alpha n) &\leq
\frac{1-\alpha}{1 - \frac{\alpha}{p}} f_{n,p}(\alpha n)
\\&\approx \frac{1-\alpha}{1 - \alpha/p} \cdot \frac{2^{(\alpha
\log_2(\frac{p}{\alpha}) + (1-\alpha)
\log_2(\frac{1-p}{1-\alpha})) \cdot n}}{\sqrt{2\pi \alpha
(1-\alpha) n}}
\\&\approx 4.56 \cdot 10^{-9}.
\end{align*}
(Note that we can use that result, since $\alpha < p$.)  We see
that the probability that $n - 7000$ or more processors will be OK
(implying that the computation will complete successfully) is at
least $1 - 4.56\cdot 10^{-9}$.

}

\problem  \goals{Discrete Probability, computational processes, teams}
In class we studied Penney Ante and determined the probability you
won.  One might also be interested in the length of the game. This
length is a random variable.  Its probability distribution can be
determined, but the algebra gets messy.  We'll consider an easier but
similar case.  Suppose we flip an unbiased coin until we get two heads
in a row.  What is the probability distribution of the number of flips
we must make?

\begin{problemparts}
  \ppart Let $P_T(k)$ (respectively, $P_H(k)$) denote the probability
  that we need to perform $k$~additional flips if the last flip we saw
  was a tail (respectively, a head) and the game is not already over after the last flip we saw. (That is, for $P_H(k)$, the next-to-last flip can be assumed to be $T$.) Using the law of total
  probability, give recurrence relations for $P_T(k)$ and $P_H(k)$ in
  terms of each other.

  \solution{\ssl
    We condition on the next flip, it is either a head or a tail with
    equal probability. Therefore,
    \begin{eqnarray*}
      P_H(k) &=& 0 \cdot \frac{1}{2} + P_T(k-1)\frac{1}{2}\,, \\
      P_T(k) &=& P_H(k-1)\frac{1}{2} + P_T(k-1)\frac{1}{2}\,.
    \end{eqnarray*}
    }

  \ppart Solve the resulting recurrences to get closed form
  expressions for $P_T(k)$ and $P_H(k)$.

  \solution{\ssl
    The first equation above gives $P_H(k) = P_T(k-1) / 2$.  If we
    insert this in the second equation above, we get the second order
    linear homogeneous recurrence
    \begin{displaymath}
      P_T(k) = P_T(k-2)\frac{1}{4} + P_T(k-1)\frac{1}{2}
    \end{displaymath}
    which has the characteristic polynomial
    \begin{displaymath}
      \lambda^2 - \lambda/2 - 1/4 = 0 \iff
      \lambda = \frac{1 \pm \sqrt{5}}{4}\,.
    \end{displaymath}
    So,
    \begin{eqnarray*}
      P_H(k) &=&
      \frac{c_1}{2} \biggl(\frac{1+\sqrt{5}}{4}\biggr)^{k-1}
      + \frac{c_2}{2} \biggl(\frac{1-\sqrt{5}}{4}\biggr)^{k-1},\\
      P_T(k) &=&
      c_1 \biggl(\frac{1+\sqrt{5}}{4}\biggr)^{k}
      + c_2 \biggl(\frac{1-\sqrt{5}}{4}\biggr)^{k}.
    \end{eqnarray*}
    Since $P_T(1) = 0$ and $P_H(1) = 1/2$,
    \begin{eqnarray*}
      \frac{c_1}{2} + \frac{c_2}{2} &=& \frac{1}{2}\,, \\
      \frac{1+\sqrt{5}}{4}c_1 + \frac{1-\sqrt{5}}{4}c_2 & = & 0,
    \end{eqnarray*}
    which can be simplified to
    \begin{eqnarray*}
      c_1 + c_2 &=& 1, \\
      (1+\sqrt{5})c_1 + (1-\sqrt{5})c_2 & = & 0.
    \end{eqnarray*}
    The solution to this system is
    \begin{eqnarray*}
      c_1 &=& 1 - c_2, \\
      c_2 &=& \frac{1+\sqrt{5}}{2\sqrt{5}}\,,
    \end{eqnarray*}
    or, equivalently,
    \begin{eqnarray*}
      c_1 &=& \frac{1}{2} - \frac{\sqrt{5}}{10}\,, \\
      c_2 &=& \frac{1}{2} + \frac{\sqrt{5}}{10}\,.
    \end{eqnarray*}
    To conclude,
    \begin{eqnarray*}
      P_H(k) &=&
      \biggl(\frac{1}{4} - \frac{\sqrt{5}}{20}\biggr)
      \biggl(\frac{1+\sqrt{5}}{4}\biggr)^{k-1}
      +
      \biggl(\frac{1}{4} + \frac{\sqrt{5}}{20}\biggr)
      \biggl(\frac{1-\sqrt{5}}{4}\biggr)^{k-1},\\
      P_T(k) &=&
      \biggl(\frac{1}{2} - \frac{\sqrt{5}}{10}\biggr)
      \biggl(\frac{1+\sqrt{5}}{4}\biggr)^{k}
      +
      \biggl(\frac{1}{2} + \frac{\sqrt{5}}{10}\biggr)
      \biggl(\frac{1-\sqrt{5}}{4}\biggr)^{k}.
    \end{eqnarray*}
    }

  \ppart Give the probability distribution for the number of coin
  flips needed to see two heads in a row.

  \solution{\ssl
    We condition on the first flip; it is either head or tail with
    equal probability. Therefore,
    \begin{displaymath}
      \Pr[\mbox{need $k$~flips}]
      =
      P_H(k-1)\frac{1}{2} + P_T(k-1)\frac{1}{2}
      =
      P_T(k),
    \end{displaymath}
    If we insert the above expressions for $P_T$ and~$P_H$, we get
    \begin{displaymath}
      \Pr[\mbox{need $k$~flips}]
      =
      \biggl(\frac{1}{8} + \frac{\sqrt{5}}{40}\biggr)
      \biggl(\frac{1+\sqrt{5}}{4}\biggr)^{k-2}
      +
      \biggl(\frac{1}{8} - \frac{\sqrt{5}}{40}\biggr)
      \biggl(\frac{1-\sqrt{5}}{4}\biggr)^{k-2}.
    \end{displaymath}
    A shortcut to the final answer is given by the observation that
    \begin{displaymath}
      P_H(k-1)\frac{1}{2} + P_T(k-1)\frac{1}{2}
      =
      P_T(k)
    \end{displaymath}
    by the recurrence relation for~$P_T$. This gives
    \begin{displaymath}
      \Pr[\mbox{need $k$~flips}]
      =
      \biggl(\frac{1}{2} - \frac{\sqrt{5}}{10}\biggr)
      \biggl(\frac{1+\sqrt{5}}{4}\biggr)^{k}
      +
      \biggl(\frac{1}{2} + \frac{\sqrt{5}}{10}\biggr)
      \biggl(\frac{1-\sqrt{5}}{4}\biggr)^{k}.
    \end{displaymath}
    The fact that $\Pr[\mbox{need $k$~flips}] = P_T(k)$ has an
    intuitive explanation: The probability that someone who just saw a
    tail will need to flip an additional $k$~coins is the same as the
    probability that someone who is just starting to flip coins will
    need $k$~flips. This is because flipping a tail resets the game in
    a certain sense. Imagine the game having three states, state~0 is
    the state corresponding to ``just started'', state~1 corresponds
    to ``half way towards the goal of two heads in a row'' and state~2
    is ``just flipped two heads in a row. The equality $\Pr[\mbox{need
      $k$~flips}] = P_T(k)$ states that a player returns to state~0
    from state~1 if she flips a head.}
\end{problemparts}

\problem  \goals{Discrete Probability, teams}

Casey's at bat.  For each pitch, Casey swings (and strikes) with
probability $p$.  After three strikes, Casey is out.  Give the
probability distribution function on the number of pitches Casey takes
to strike out. \hint What is the last pitch in any sequence of
pitches that produces a strikeout?  And what must be true of the
sequence of pitches before that pitch?
\solution{\ssl
The last pitch in any sequence of pitches that produces a strikeout must be a strike. Moreover, if that pitch produces a strikeout, the preceding sequence must have included exactly two strikes.

Let $N$ be the number of pitches Casey takes to strike out. We want to find $\Pr [N=k]$, namely, the probability that Casey strikes out after exactly $k$ pitches. Obviously, $\Pr [N=k]=0$ if $k< 3$. Casey strikes out after $k$ strikes if and only if the previous sequence (of length $k-1$) contained precisely two strikes \emph{and} the $k$th pitch is a strike. The events are independent, so we have:
\[
\Pr[N=k]\quad=\quad
\underbrace{\binom{k-1}{2}}_{\lab{ways to}{choose the}{2 strikes}}
\overbrace{p^2}^{\lab{prob. of}{getting}{2 strikes} }\underbrace{(1-p)^{k-1-2}}_{\lab{prob. that}{remaining are}{not strikes}} \overbrace{p}^{\lab{prob. that}{last one}{is strike}}\quad =\quad \binom{k-1}{2}p^3(1-p)^{k-3}
\]  
}

%%%%%%%%%%%%%  Fall 2000     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem  \goals{Discrete Probability, teams} %{\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 except the 4-sided one has exactly one 6,
  $\expect{X_4} = 0$ and $\expect{X_i} = 1 / i$ for $i \in
  \{6,8,10,12,20\}$, which gives
  \begin{displaymath}
    \expect{X_4 + X_6 + X_8 + X_{10} + X_{12} + X_{20}} = 
    0 + \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  \goals{Discrete Probability, teams} 
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{\ssl

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  \goals{Discrete Probability, teams}
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.  Or equivalently, it can be seen as studying the number of
  ``record setting'' events when a sequence of variables are all drawn
  from the same probability distribution.}

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

\solution{\ssl

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*}
}

          




\end{problems}

\end{document}                            

