\documentstyle[12pt,macpsfig,psfig,amstex,amssymb]{article}
\input{macros-course}

\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}

\setcounter{page}{0}

%\newcommand{\pr}{\problem}

\begin{document}

\qsol{3}{December 6, 1995}

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%1
\problem
Suppose I roll two independent standard dice and subtract the smaller
value from the larger value.
\bparts
\ppart What is the probability distribution for the resulting 
difference? (i.e. give the probability of getting the result $k$ for
all $k$)

Let $R$ be the random variable that is the larger die roll minus the
smaller die roll.  The easiest way to see the probability distribution
of $R$ is to make a table of the 36 outcomes and see what the value of the
larger minus the smaller is.

\begin{tabular}{c|c|c|c|c|c|c|}
  & 1 & 2 & 3 & 4 & 5 & 6  \\ \hline
1 & 0 & 1 & 2 & 3 & 4 & 5  \\ \hline
2 & 1 & 0 & 1 & 2 & 3 & 4  \\ \hline
3 & 2 & 1 & 0 & 1 & 2 & 3  \\ \hline
4 & 3 & 2 & 1 & 0 & 1 & 2  \\ \hline
5 & 4 & 3 & 2 & 1 & 0 & 1  \\ \hline
6 & 5 & 4 & 3 & 2 & 1 & 0 \\  \hline
\end{tabular}

Since these entries are all equally likely, the probability
$R=k$ is just the number of entries that are $k$ divided by 36.

\begin{align*}
  Pr(R<0) &= 0 \\
  Pr(R=0) &= \frac{6}{36} = \frac{1}{6}\\
  Pr(R=1) &= \frac{10}{36} = \frac{5}{18}\\
  Pr(R=2) &= \frac{8}{36} = \frac{2}{9}\\
  Pr(R=3) &= \frac{6}{36} = \frac{1}{6}\\
  Pr(R=4) &= \frac{4}{36} = \frac{1}{9}\\
  Pr(R=5) &= \frac{2}{36} = \frac{1}{18}\\
  Pr(R>5) &= 0 
\end{align*}


\ppart What is the mean of the result?

The mean is  
\begin{align*}
E[R] &= \sum_{k=0}^5 k Pr(R=k) \\ 
&= (1)\frac{6}{36} + (2)\frac{10}{36}
 + (3)\frac{8}{36}+(4)\frac{6}{36}+(5)\frac{4}{36}+(6)\frac{2}{36} \\
&= \frac{70}{36} \\
&= \frac{35}{18}
\end{align*}


\ppart What is the variance of the result?

The variance is $E[R^2] -(E[R])^2$.
\begin{align*}
 E[R^2] &= \sum_{k=0}^5 k^2 Pr(R=k) \\
&= (1^2)\frac{6}{36} + (2^2)\frac{10}{36}
 +
 (3^2)\frac{8}{36}+(4^2)\frac{6}{36}+(5^2)\frac{4}{36}+(6^2)\frac{2}{36}\\
&= \frac{210}{36} \\
&= \frac{105}{18} \\
E[R] &= \frac{35}{18} \;\;\;\; {\rm(from\;part\;b)}
\end{align*}

So the variance is
$$ \frac{105}{18} - \left( \frac{35}{18} \right)^2 = \frac{665}{324} $$


\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%2
\problem 
Suppose I roll two independent standard dice, and consider the
following three events:
\begin{itemize}
\item the first die is odd
\item the second die is odd
\item the sum of the dice is odd
\end{itemize}
\bparts
\ppart Show these events are pairwise independent.

Let $A,B$ and $C$ denote the first second and third events
respectively.

The first and the second events are independent by definition:
$P(A)=P(B)=1/2=P(A|B).$

The first and the third events are independent because given the first
die is odd the sum is odd if and only if the second die is even,
an event which happens with probability 1/2. Thus $P(C|A)=1/2.$ On the other
hand, the unconditional probability of the third event is 1/2,
too. Indeed: $P(C)=P(A)P(\bar{B})+ +P(\bar{A})P(B)=1/4+1/4=1/2.$ Thus
$P(C)=P(A|C)$ as claimed.

An identical argument shows that $B$ and $C$ are independent.


\ppart Are they mutually independent?  Why, or why not?

$A, B$ and $C$ are not mutually independent since $P(A)P(B)P(C)=(1/2)^3=(1/8)$
whereas $P(A\cap B\cap C)=0$. (Indeed: if both dice are odd, the sum is
necessarily even).

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%3
\problem 
There is a bag with $999$ regular nickels and $1$ two-headed
nickel. Experiment X1 consists of pulling a coin out of the bag at
random and flipping it once before putting it back in.
\bparts
\ppart You perform X1 once. What is the probability you get 1  head?

The probability is
$$\frac{999}{1000} \cdot \frac{1}{2} + \frac{1}{1000} \cdot 1 = 
\frac{1001}{2000}.$$

\ppart You repeat X1 10 times (i.e. you pull a coin out, flip it and 
put it back in, repeating the whole process 10 times). What is the
probability you get 10 heads?

Since the experiments are independent, the probability 
is $$\left( \frac{1001}{2000} \right)^{10}.$$

\ppart
You repeat X1 10 times. What is the most likely number of heads you
get, i.e. for which $k$ is the probability of getting $k$ heads
maximized? (Justify your answer)

The distribution of heads is binomial, with success probability
$p = \frac{1001}{2000}$.  Thus, by taking ratios of $Pr(X = k-1)$ 
to $Pr(k)$ for 
increasing values of $k$ as in class, we see that the probability
increases for $k \leq np = \frac{5005}{1000}$, and then
decreases.  Thus the most likely outcome is $5$.

\eparts

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

\problem
There is a bag with $999$ regular nickels and $1$ two-headed
nickel. Experiment X2$(k)$ consists of pulling a coin out of the bag at
random and then flipping the same coin $k$ times before putting it
back.
\bparts
\ppart
You perform X2$(10)$. What is the probability you get 10 heads?

Let $A$ be the event you draw the two-headed nickel and $B$
be the event you get 10 heads in a row.
Then,

\begin{eqnarray*}
Pr(B) & = & Pr(B \wedge A) + Pr(B \wedge \overline{A}) \\
& = & Pr(B|A) Pr(A) + Pr(B|\overline{A})Pr(\overline{A}) \\
\end{eqnarray*}

Clearly, $Pr(A) = 1/1000$ and $Pr(B) = 999/1000$.
If you get the two-headed nickel, you will get all
heads, so $Pr(B|A) = 1$.  The probability of getting ten heads with the
fair nickel is $2^{-10}$.  Thus, $Pr(B|\overline{A})=2^{-10}$.
Therefore, 
\[
Pr(B) = \frac{1}{1000} + \frac{999}{1000}2^{-10} =\frac{2023}{1024000}
\]


\ppart
You perform X2$(10)$. Given that you get $10$ heads what is the probability that you pulled out the two-headed coin?

\[
Pr(A|B) = \frac{Pr(A \wedge B)}{Pr(B)}
\]

We have $Pr(B)$ from (a).  $Pr(A \wedge B) = 1/1000$, since
if we draw the two-headed nickel, we will get all heads.

Thus,
\[
Pr(A|B) = \frac{1/1000}{2023/1024000} = \frac{1024}{2023}
\]


\ppart
You perform X2$(10)$. Given that you get $10$ heads what is the
probability that another $10$ flips with the coin you pulled out will
all come up heads?

Let $C$ be the event that the next 10 flips are heads.
There are two ways to do this problem.

Method 1:

Note that the event $C\wedge B$ is equivalent to getting 20 heads in a row.

\begin{eqnarray*}
Pr(C|B) &=& \frac{Pr(C\wedge B)}{Pr(B)} \\
&=& \frac{Pr(\mbox{20 heads} )}{Pr(\mbox{10 heads})} \\
&= & \frac{\frac{1}{1000} + \frac{999}{1000}2^{-20}}
	{\frac{1}{1000} + \frac{999}{1000}2^{-10}} \\
&=& \frac{1,049,575}{2,071,552}
\end{eqnarray*}

Method 2:

\begin{eqnarray*}
Pr(C|B) &=& Pr(C \wedge A|B) + Pr(C \wedge \overline{A}|B) \\
&=& Pr(C|A\wedge B)Pr(A|B) + Pr(C|\overline{A} \wedge B) Pr(\overline{A}|B) \\
\end{eqnarray*}

In (b), we determined $Pr(A|B)$.  $Pr(\overline{A}|B) = 1- Pr(A|B)$.

Now, $Pr(C|A\wedge B) = 1$, since the coin is two headed.
$Pr(C|\overline{A} \wedge B) = 2^{-10}$, since the flips
are independent.

Therefore,
\[
Pr(C|B) = \frac{1024}{2023} + \left(1-\frac{1024}{2023}\right) 2^{-10}
= \frac{1,049,575}{2,071,552}
\]



\eparts

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

\problem 
A space station can tolerate up to $k$ meteor hits in its
lifetime. Each year there is a probability $p$ that it gets hit by
exactly one meteor and probability $1-p$ that it gets hit by none.
\bparts
\ppart 
What is the probability $P(n)$ that the space-station survives exactly
$n$ years, i.e. the $k$'th meteor hits the space-station in year $n$?

In order for the space station to survive exactly $n$
  years, we have to have the $k^{th}$ meteor hit at year $n$.  This
  can be rephrased in terms of two independent events.  Let $S$ be the
  event that the space station survives exactly $n$ years.  Let $M$ be
  the number of meteor strikes in years $1,\ldots,n-1$.  Let $A$ be
  the event that a meteor hits in year $n$.  Then $S$ occurs only if
  the event $M=k$ occurs and also the event $A$ occurs.  Since the
  events $A$ and $M=k$ are independent, we see that
  \begin{align*}
  \Pr[S] &= \Pr[A]\cdot\Pr[M=k]\\
  \intertext{Of course, $M$ has the binomial distribution, meaning}
  \Pr[M=k] &= \binom{n-1}{k-1}p^{k-1}(1-p)^{(n-1)-(k-1)}\\
  \intertext{Therefore, since $\Pr[A]=p$, we have}
  \Pr[S] &=  p\cdot \binom{n-1}{k-1}p^{k-1}(1-p)^{n-k}
  \end{align*}

\ppart 
For a given $j$, what is the expected time between the $j^{th}$
and $(j+1)^{st}$ meteor hits?

Let $W_j$ be the year the $j^{th}$ meteor hits ($W_0=0$),
  and let $X_{j}=W_{j+1}-W_{j}$ be the time between the $j^{th}$ and
  $(j+1)^{st}$ meteor hits.  As discussed in tutorial regarding the
  coupon collector problem, $X_j$ is independent of $W_j$ and has the
  negative binomial distribution with parameter $p$, so
  \[
  E[X_j] = 1/p.
  \]

\ppart 
What is the expected life of the space-station? (You will get partial
credit for a non-closed form solution, but do not waste time
evaluating hairy sums.)

By the definitions of the previous section, the time we
  care about is $W_k=\sum_{j=0}^{k-1}X_j$.  It follows by linearity of
  expectation that
  \begin{align*}
  E[W_k] &= E[\sum_{j=0}^{k-1} X_j]\\
  &= \sum_{j=0}^{k-1} E[X_i]\\
  &= \sum_{j=0}^{k-1} 1/p\\
  &= k/p
  \end{align*}

\eparts

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

\problem  
Suppose I have an experiment with $n$ possible outcomes, of which the
$i^{th}$ happens with probability $p_i$.  Suppose I perform the
experiment once to establish a ``goal outcome.''  Now I repeat the
experiment over and over until the ``goal outcome'' occurs again.  Not
including the first experiment, what is the expected number of
experiments I will perform?  (Justify your answer, and do not make any
assumptions about the $p_i$'s)

Let $G$ be the goal outcome, and let $X$ be the number of
experiments that are performed after the first.  From the problem
definition, we see that
\[
\Pr[G=i] = p_i.
\]
Now suppose that $G=i$.  Then we start performing experiments until
the outcome $i$ occurs.  Since the probability of outcome $i$ is
$p_i$, the number of experiments $X$ has the negative binomial
distribution with parameter $p_i$.  The expected
value of this distribution is $1/p_i$.  That is,
\[
E[X \mid G=i] =1/p_i.
\]
It follows from the theorem for conditional expectations that
\begin{align*}
E[X] &= \sum_{i=1}^n E[X \mid G=i] \cdot \Pr[X=i]\\
&= \sum_{i=1}^n \frac1{p_i}\cdot p_i\\
&= \sum_{i=1}^n 1\\
&= n
\end{align*}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem  
Adam and Eve marry and begin having children.  Each child is a boy
or a girl independently with probability 1/2, and Adam and Eve stop
having children once they have two children of the {\bf same} sex.   Let $c$
be the expected number of children they have.
\bparts
\ppart  What is the value of $c$?

Suppose by symmetry the first child is a boy.  Then the second
child is a boy with probability $\frac12$, in which case they stop;
otherwise, by the pigeonhole principle (two genders, three children),
they will stop on their third child.  Thus the expected number of
children is $2.5$.

\ppart 
Suppose each descendant grows up, marries a non-descendant of Adam and
Eve, and follows the same child bearing rules as Adam and Eve. What is
the expected {\bf total} number of descendants of Adam and Eve up to and
including the $n^{th}$ generation, if Adam and Eve are generation 0,
their children generation 1, and so on?

Since the number of children born to each couple is independent,
we can apply Wald's theorem to the resulting branching process to
conclude that the number of children born in generation $n$ is
$(2.5)^n)$.  Thus the number of descendants up to and including 
generation $n$ is $\sum_{j=1}^n (2.5)^j$.

\eparts


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

\end{problems}

\end{document}



