%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%prelude for spring98 final #8,9 (added by Ivan)
\end{problems}
The next two problems are based on the following scenario: an urn contains red,
white and blue colored balls.  The fraction of red, white, and blue balls
is $r,w,b$, respectively (so $r + w + b =1$).  A gambler repeatedly pulls
a ball at random from the urn.  That is, at any point during succesive
pulls, each ball in the urn is equally likely to be the next one pulled.
The gambler puts the ball back into the urn before making the next pull.
He keeps pulling balls until he pulls \emph{two red balls in a row}.
\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spring98 final #9 (added by Ivan)
\problem\points{15} The sequence of pulls by the Gambler can be regarded
as a sequence of \emph{tries}, where the first try begins with the first
ball pulled.  Each try consists of a sequence of pulled balls continuing
until either a white ball, a blue ball, or two red balls in a row, are
pulled.  For example, if the colors of pulled balls are RBBWRWRR, then
there are five tries which we indicate with slashes: /RB/B/W/RW/RR/.
Note that each try consists of one or two consecutive balls.


\bparts

\ppart\points{15}  What is the expected length of a try?

\medskip
\solution{
\textbf{Solution}: $1\cdot (1-r) + 2 \cdot r = 1 + r$
}

\ppart\points{5}  What is the expected number of tries?

\medskip
\solution{
\textbf{Solution}: A series of tries ends iff only the last try consists
of two reds.  We know from lecture that the ``mean time to failure'' is
the reciprocal of the probability of failure, so $\expect{\mbox{num
tries}}$ is the $1/\pr{\mbox{2 reds}}= 1/r^2$.
}

\ppart\points{5} Write a simple expression in terms of your answers to
the previous parts of this problem for the expected number of balls pulled
by the Gambler.  Briefly justify your reasoning, citing appropriate
results from the attached Handout 60.

\medskip
\solution{
\textbf{Solution}:  By Wald's Thm 
\[\expect{\mbox{num pulls}} = \expect{\mbox{pulls per
try}} \cdot \expect{\mbox{num tries}} = (1+r)\frac{1}{r^2}.\]
}

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} A box initially contains $n$ black balls.
The following procedure is repeated.  A ball is drawn from the box at
random.  If the ball is white, then it is returned to the box.  If the
ball is black, then with probability $p$ a white ball is returned to
the box and with probability $1-p$ a black ball is returned to the
box.  What is the expected number draws needed to fill the box with
white balls?

\solution{Suppose that the box contains $k$ white balls.  The
probability that a black ball is drawn and replaced by a white ball is
$\frac{n-k}{n} \cdot p$.  Therefore, the expected number of draws to
introduce one more white ball is $\frac{n}{p(n-k)}$.  By linearity
of expectation, the expected number of draws required to fill the box
with white balls is:

\begin{eqnarray*}
\sum_{k=0}^{n-1} \frac{n}{p(n-k)}
    & = &   \frac{n}{p} \cdot \sum_{k=0}^{n-1} \frac{1}{n-k} \\
    & = &   \frac{n}{p} \cdot \sum_{j=1}^n \frac{1}{j} \\
    & = &   \frac{nH_n}{p}
\end{eqnarray*}

The second step uses the substituion $j = n - k$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (5 points)} The number of people that enter Filene's
Basement in the last hour before closing on Christmas Eve is a random
variable taking on an integer value in the range 0 to 100 uniformly.

Each shopper picks at least one present to buy.  After selecting each
present, a shopper is equally likely to continue shopping and to go
pay at the checkout register.  Shoppers' decisions to continue buying
are mutually independent.

The checkout clerk throws two fair, independent dice for each item and
then charges a number of dollars equal to the sum.

What is the expected total amount of money spent by these last-minute
shoppers at Filene's Basement?

\solution{Applying Wald's Theorem twice, the expected amount of money
spent is the product of the expectations of the three random variables
described in the problem.

\begin{eqnarray*}
\Ex(\text{money spent})
    & = &   \Ex(\text{num people}) \cdot
        \Ex(\text{num gifts}) \cdot
        \Ex(\text{price}) \\
    & = &   50 \cdot 2 \cdot 7 \\
    & = &   700
\end{eqnarray*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (5 points)} Suppose that I roll a die, but conceal the
result from you.  You then repeatedly guess at the number that I
rolled, and I will tell you whether each guess is right or wrong.  No
proofs are required for this problem.

\begin{problemparts}

\problempart {\bf (2 points)} Suppose that you guess 1, 2, 3, 4, 5,
and then 6 in that order.  What is the expected number of guesses that
you need to get the right number?

\examonly{\vspace{3in}}

\solution{
From the definition of expected value, the answer is

\begin{eqnarray*}
\frac{1}{6} \cdot (1 + 2 + 3 + 4 + 5 + 6)
    & = &   \frac{7}{2}.
\end{eqnarray*}
}

\problempart {\bf (3 points)} Suppose that you repeatedly guess
numbers in the range 1 to 6 uniformly and mutually independently at
random.  What is the expected number of guesses that you need to get
the right number?

\solution{Let the expected number of guesses be $X$.  After a wrong
guess, the expected number of guesses is the same as before.  The
rules of the game imply the following equation.

\begin{eqnarray*}
X   & = &   \frac{1}{6} \cdot 1 + \frac{5}{6} \cdot (1 + X)
\end{eqnarray*}

By solving the equation, we find that the expected number of guesses
is $X = 6$.
}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 10
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{6} \textbf {Die Rolling}

Say you roll a fair 6-sided die.  If you get a 6, you may roll again,
and add 6 to the outcome; if you roll multiple 6's in a row, you
continue to roll again.  So, for example, if you roll a 6 and then a
5, the outcome is 11; if you roll a 6, then a 6, then a 6, then a 2,
the outcome is 20.

What is the expected value of the outcome?  Your answer should be in
closed form.

\solution{\bigskip {\bf Solution:}

Let $R_i$ be the value of the $i$th die roll (if there is one).  Let
$Q$ be the number of die rolls.  Since Ex$(R_i)$ does not depend on $i$,
we can use Wald's theorem to find the solution.

Ex$(R_i) = \frac{1}{6} (1 + 2 + 3 + 4 + 5 + 6) = \frac{21}{6} = \frac{7}{2}$.

Ex$(Q) = \sum_{i=0}^{\infty} \frac{1}{6^i} = \frac{1}{1 - (1/6)} =
\frac{6}{5}$.

So, Ex($\sum_{i=1}^Q R_i) = $Ex($R_i$)Ex($Q$) = $\frac{42}{10} =
\frac{21}{5}$.

Another way of doing this problem would be to note that 

$Ex(X) = \frac{1}{6}(1 + 2 + 3 + 4 + 5 + (6 + Ex(X))) = \frac{7}{2} + Ex(X)/6$.

Solving gives

$\frac{5 Ex(X)}{6} = \frac{7}{2}$

so 

$Ex(X) = \frac{42}{10} = \frac{21}{5}$
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 7
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{16} \textbf {Coloring Grid Graphs, Yet Again}

Let $G$ be a 4 by 4 grid graph: 

\begin{center}\includegraphics[height=2.75in]{problem7.eps}\end{center}


Suppose we pick a random 4 color graph coloring of $G$, where the
colors being used are red, green, blue, and yellow.  That is, we pick
uniformly at random from the set of all valid colorings.  Let $A$ be
the event that vertex (1,1) is colored red, $B$ be the event that
vertex (1,2) is colored red, and $C$ be the event that (1,1) and (2,2)
are the same color.  Let $X$ be the number of ``points'' the graph
coloring gives, where each red node is worth 1 point, each yellow node
is worth 2 points, each blue node is worth 3 points, and each green
node is worth 6 points.

\problempart {\bf (2 points)} What is Pr$(A)$?

\solution{\bigskip {\bf Solution:}

By symmetry, vertex (1,1) should be no more likely to be any one
particular color than any other.  Thus, the probability is $1/4$.
}

\problempart {\bf (2 points)} What is Pr$(B|\overline{A})$?

\solution{\bigskip {\bf Solution:}

By symmetry, vertex (1,2) should be no more likely to be any one
particular valid color (given that vertex (1,1) is colored red) than
any other.  Thus, the probability is $1/3$.
}
\problempart {\bf (2 points)} What is Pr$(A|C)$?

\solution{\bigskip {\bf Solution:}

By symmetry, if vertices (1,1) and (2,2) are the same color, they
should not be more likely to be any one color than any other.  Thus,
the probability is $1/4$.
}

\problempart {\bf (2 points)} What is Pr$(B|\overline{A} \cap C)$?

\solution{\bigskip {\bf Solution:}

By symmetry, if vertices (1,1) and (2,2) are both not red (which is what
having $\overline{A}$ and $C$ both be true means), then vertex (1,2) should be 
no more likely to be any one valid color than any other.  No matter which
color vertices (1,1) and (2,2) are, red is one of three valid colors for
vertex (1,2), so the probability is $1/3$.
}

\problempart {\bf (4 points)}  Which pairs of the events $A, B,$ and $C$ are 
independent?  

\solution{\bigskip {\bf Solution:} 

Obviously, since $A$ and $B$ cannot both be true at the same time,
they are not independent.

However, $Pr(A|C) = Pr(A)$ so $A$ and $C$ are independent.

$Pr(B|C) = 1/4$ since if vertices (1,1) and (2,2) are the same color,
they should be equally likely to be any particular color.  With
probability 3/4, they are not red, and then with probability 1/3,
vertex (1,2) is red.  With probability 1/4, (1,1) and (2,2) are red,
and then with probability 0, vertex (1,2) is red.  Thus, $Pr(B|C) =
(3/4)(1/3) + (1/4)0 = 1/4 = Pr(B)$.  Thus, $B$ and $C$ are independent.
}

\problempart {\bf (4 points)} What is Ex$(X)$?

\solution{ \bigskip {\bf Solution:}
Let $X_v$ be a random variable for vertex $v$, which determines the
number of points that vertex contributes.  Since $X = \sum_{v \in G} X_v$,
by linearity of expectation, we have that

Ex$(X) = \sum_{v \in G} $Ex$(X_v)$.  

Since Ex$(X_v) = (1)(1/4) + (2)(1/4) + (3)(1/4) + (6)(1/4) = 12(1/4) = 3$,
and there are sixteen vertices in $G$, this gives that 

Ex$(X) = 48$.
}
