\documentclass[11pt, twoside]{article}
\usepackage{epsf}
%\usepackage{amsmath}

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}
\newcommand{\Ex}{\text{Ex}}
\newcommand{\eqdef}{\mathbin{::=}}
\newcommand{\Fib}{{\sf Fib}}
 
\askaboutsolutions

\begin{document}
\ifshowsolutions
%\psol{11}{December 7, 2000}{2:35pm in lecture, Thursday, December 7, 2000}
\psol{11}{December 7, 2000}
\else
\pset{11}{November 28, 2000}{2:35pm in lecture, Thursday, December 7, 2000}
\fi

\textbf{Be sure to indicate your TA's name clearly on the solutions
your turn in}.

-----------------------------------------------------------------------------------------------

\textbf{Self-study}
Read: Rosen Sections 4.4, 4.5  \\
Self-study problems (not to be handed in): Rosen 4.5: 27, 29, 33, 43, 49
%[[[Miniquiz for tut11: Rosen 4.5, 43]]]

-----------------------------------------------------------------------------------------------

\textbf{Reading:}
Lecture notes;  Rosen 4.4, 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.
 
\medskip
\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem 

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 justify
your answer.

\bparts
\ppart  $(X \bmod 3) + (Y \bmod 3)$ and $(X \bmod 2) + (Y \bmod 2)$

\solution{
\textbf{Solution:}\\
Independent.  $X \bmod 3$ and $X \bmod 2$ are independent,
which you can see by drawing a 3x2 table of values of $X \bmod 3$
versus values of $X \bmod 2$.  Obviously, $Y\bmod 3$ and $Y \bmod 2$
are independent as well.  Furthermore, it is true in general that if
$A$ is independent of $B$ and $A'$ is independent of $B'$ then
$f(A,B)$ is independent of $g(A',B')$ for any functions $f$ and $g$.
Here the two functions are addition over integers.}


\ppart $((X+Y)\bmod{2})$ and $((X*Y)\bmod{2})$

\solution{ 
\textbf{Solution:}\\
These random variables are not independent.  $(X+Y\bmod 2)
= 1$ iff $X$ and $Y$ have different parity.  $(X*Y\bmod 2) =1$ iff
both $X$ and $Y$ have odd parity.  Therefore, if $(X*Y\bmod 2) =1$
then $(X+Y\bmod2)=0$, and hence the two events depend on each other.}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem

Consider the process of tossing a sequence of $n$ independent fair
coins $X_1,X_2,\ldots,X_n$.  Let $V$ be the first time two consecutive
heads occur in the sequence, i.e. $(X_{V-1},X_V)=(H,H)$ and
$(X_{i-1},X_i)\neq (H,H)$ for all $2\leq i<V$.  If the sequence of $n$
coin tosses does not contain two consecutive heads, then we assign
$V=n+1$.

Prove that $V$ has distribution
\[\Pr(V=k) = \frac{\Fib(k-2)}{ 2^k} \ \ \ \ (2\leq k\leq n) \]
where $\Fib(k)$ is the $k$-th Fibonacci number (assume 
$\Fib(0)=\Fib(1)=1$.)

\solution{
% This problem is taken from spring 96, problem 10
%
\textbf{Solution:}\\
Let's count the sequences of coin tosses of length $k$ such that the
only pair {\em HH} that occurs in the sequence is at the end. Let
$H(k)$ be the number of such sequences that start with $H$, and let
$T(k)$ be the number of such sequences that start with $T$.  Observe
that $H(2) = 1$ and $T(2) = 0$. Similarly, $H(3) = 0$ and $T(3) =
1$. Given a valid sequence {\em HS} of length $k$ that starts with
$H$, the sequence {\em THS} is also valid and starts with $T$.  Given
a valid sequence {\em TS} of length $k$ that starts with $T$, the
sequences {\em HTS} and {\em TTS} are also valid and start with $H$
and $T$ respectively. From this we deduce the recurrence relations
\begin{eqnarray*}
H(k+1) &=& T(k)\\
T(k+1) &=& H(k) + T(k){.}
\end{eqnarray*}
The total number of valid sequences of length $k$ is $T(k)+H(k)$,
hence it satisfies the following recurrence
\begin{eqnarray*}
T(k+1)+ H(k+1) &=& (T(k) + H(k)) + T(k)\\
&=& (T(k) + H(k)) + (T(k-1) + H(k-1)){.}
\end{eqnarray*}
This is the same recurrence relation that defines the Fibonacci
numbers, and with the given initial conditions we can conclude that
the total number of valid sequences of length $k$ is $\Fib(k-2)$.

Now the total number of sequences of length $n$ such that the first
pair of heads occurs after $k$-th toss is $\Fib(k-2)2^{n-k}$, since we
don't care what the coin tosses are in the last $n-k$ places.

The sample space in this problem is the set of all sequences of coin
tosses of length $n$, so its size is $2^n$. Therefore the probability
\[
P(V=k) = \frac{\Fib(k-2)2^{n-k}}{ 2^n} = \frac{\Fib(k-2)}{ 2^k}{,}
\]
as desired.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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) < \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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\solution{
\textbf{Solution:}\\
Let the random variable $M$ be the largest number that comes
up.  We will use the identity

\begin{eqnarray*}
\Ex(M)	& = &	\sum_{i=0}^{\infty} \Pr(M > i)
\end{eqnarray*}

We must compute the probability of the event $M > i$; that is, the
event that some die shows a value greater than $i$.

\begin{eqnarray*}
\Ex(M)
	& = &	\sum_{i=0}^5 \Pr(M > i) \\
	& = &	\sum_{i=0}^5 1 - \Pr(\text{every die $\leq i$}) \\
	& = &	\sum_{i=0}^5 1 - (\Pr(\text{one die $\leq i$}))^n \\
	& = &	\sum_{i=0}^5 1 - \left(\frac{i}{6}\right)^n \\
	& = &	6 - \frac{1^n + 2^n + 3^n + 4^n + 5^n}{6^n}
\end{eqnarray*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

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

\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  \textbf{The World Series}

The Yankees and Mets have both made it to the World Series again in 2001.
Assume that the Yankees win each game with probability 2/3 independently of
the outcomes of other games.  Let $R$ be the
random variable denoting the number of the 4th game won by the Yankees, e.g.,
if the Yankees win the 1st, 2nd, 4th, and 6th games, then $R=6$; let $R \eqdef 0$ if
the Yankees do not win four games.

Let's generalize the rules slightly and assume the
teams keep playing, possibly forever, until the Yankees have indeed
won 4 games.  This makes $R$ a random variable taking on all natural
number values.

\bparts

\ppart For $n>0$, give a simple closed form expression for $\prob{R = n}$.

\solution{
\textbf{Solution:}\\
For $0<n<3$, we have $\prob{R=n} = 0$. For $4\leq n$, we have
\[
\prob{R=n} = \binom{n-1}{3} \cdot (2/3)^4  \cdot \frac{1}{3^{n-4}}=
\frac{8(n-1)(n-2)(n-3)}{3^{n+1}}.
\]
}
 
\ppart What is the probability that Yankees never win 4 games under
the generalized rules?

\solution{
\textbf{Solution:}\\
0
}


\ppart What is the probability that the Yankees really win the 7 game
Series?

\solution{
\textbf{Solution:}
\[
\prob{4 \leq R\leq 7}= \prob{R=4}+\prob{R=5}+\prob{R=6}+\prob{R=7} = 0.8267
%\frac{?}{?}.
\]
}

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem \textbf{Wald's Theorem.}
% Spring 99 Final. 

Suppose successive digits from zero to nine are generated independently
until the four digit sequence \textbf{9999} appears.

What is the expected number of digits generated? 

\hint Parse the sequence into consecutive ``tries to get 9999'', where a
``try'' is either a single digit other than 9, or a 9 followed by a single
digit other than 9, etc.  For example, the sequence 92349982999769999
parses into eight tries:
\[
/92/3/4/998/2/9997/6/9999/.
\]

\solution{
\textbf{Solution:}
11110.

By Wald's Theorem, the expected number is the mean time to a successful
try, namely $10^4$, times the expected length of a try.  Notice that a try
is of length four iff it begins with three nines, so the probability of a
length four try is $1/10^3$.  That means the expected length of a try is
\[
1 \cdot \frac{9}{10} + 2 \cdot \frac{1}{10}\frac{9}{10} + 3 \cdot
(\frac{1}{10})^2\frac{9}{10} + 4 \cdot (\frac{1}{10})^3
 =  (900 + 180 + 27 + 4)/1000 = 1111/1000
\]
Thus on average, we will have to read 11110 digits in order to see
``9999''.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems}
\end{document}
