\documentclass[11pt, twoside]{article}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

\askaboutsolutions

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


\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{sol10}
  \newcommand{\handouttitle}{Problem Set 10 Solutions}
  \newcommand{\handoutdate}{May 4, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else
  \newcommand{\reading}[1]{%
%    \mbox{}\\ %
    \hrule\mbox{} \\ %\bigskip %
    #1%
%    \mbox{} \\ %\bigskip %
    \hrule %
    %\vfill\mbox{}\newpage%
    }
%
  \newcommand{\handoutlabel}{ps10}
  \newcommand{\handouttitle}{Problem Set 10}
  \newcommand{\handoutdate}{April 25, 2000}
  \newcommand{\duedate}{May 2, 2000}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \medskip
  \textbf{Solution.} \par %
  #1
%  \mbox{} \\
%  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%  \raisebox{-0.25\baselineskip}{$\square$}%
%  \hspace*{1ex}\ignorespaces\hrulefill%
%  \nopagebreak%
  \fi}


%\newcommand{\solutionname}{Solution}
%\renewenvironment{solution}[1][\solutionname]{%
%  \par
%  \normalfont
%  \topsep6\p@\@plus6\p@ \trivlist
%  \item[\hskip\labelsep\bfseries
%    #1\@addpunct{.}]~~\ignorespaces
%}{%
%\mbox{} \\
%\mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%\raisebox{-0.25\baselineskip}{$\square$}%
%\hspace*{1ex}\ignorespaces\hrulefill%
%\nopagebreak%
%}

%\renewcommand{\solution}[1]{%
%  %\begin{solution}
%    #1
%  %\end{solution}
%  }

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


\begin{document}


\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}
\newcommand{\mquote}[1]{\mathify{\textrm{``$#1$''}}}
\newcommand{\mdash}{\mathify{\textrm{-}}}
\newcommand{\where}{{\ \mid \ }}
\newcommand{\size}[1]{\mathify{\left| #1 \right|}}
\newcommand{\equivalent}{\mathify{\ \Longleftrightarrow \ }}
\newcommand{\ifandonlyif}{\equivalent}
\renewcommand{\prob}[1]{\mathify{\textrm{Pr}\left[\, #1 \,\right]}}
\newcommand{\compliment}[1]{\overline{#1}}
\newcommand{\Ex}{\text{Ex}}


\titlebar

\reading{%
  \vspace{-2\baselineskip}
  \begin{description}\itemsep 0\baselineskip
  \item[Self-study:] Games of unbounded length \\
    Exercises 1, 2 and 3 in Handout 42 (Dice Game)

  \item[Reading:] \ \\
    6.042 Fall 97 Lecture notes: Lectures 21 and 22 (available from course webpage)
  \end{description}
  }

\section*{Problems:}

% [[[ Should be about 8 problems.
%
% Coverage:
% L21:
% Random variables
% Probability distributions: Bernoulli, uniform, binomial
% Uniform: Numbers game
% Binomial:
%   Bounding tails
%   Polling
%
% L22:
% Expectation
%   Shortcut for computing
%   MTTF
%   Expectation based on divergent series
%   Linearity of expectation
%   Expectation and combinatorial equalities
% ]]]


\begin{problems}

% [[[ My lecture notes for Tuesday already appear in the lectures
%    directory, under lecture21.tex.
% I haven't gotten to Thursday yet.  But it will be pretty close to
%    the previous lecture 22.tex.
%
% I've been trying to think of a nice problem involving independence of
% random variables.  No luck...]]]


\problem %
% (Numbers game, uniform distribution)

Recall the envelope guessing game demonstrated in lecture.
(You do go to lecture, right?)
You are shown two envelopes, each lying face down on a table.
There is a number from $\{0,\ldots, n\}$ written inside each. You pick an
envelope and get to see the number in that envelope.
You can then either choose to stay with that number, or switch to the number
written in the other envelope.
You {\em win} if the number you end up with
is the larger of the two (that is, if either you originally picked
the larger and stayed, or if you originally picked the
smaller and switched).

A randomized strategy for this game
is a function that, for each number $i$ that may be revealed in the
envelope you look at, assigns a probability $p_i$ of switching. For example,
a strategy where $p_i = \frac{1}{2}$ for all $i$ effectively ignores the number
revealed and chooses randomly. A strategy where
$p_i = 1$ for $i < \frac{n}{2}$ and $p_i = 0$ for $i \geq \frac{n}{2}$
would switch if the number revealed is in the lower half of the range and
stay if it is in the upper half of the range.


\begin{problemparts}
\problempart
Prove that the strategy described in class for winning with probability
better than $1/2$ is optimal if the envelopes are filled with $x$ and $x+1$,
where $x$ is chosen uniformly from $\{0,\ldots, n-1\}$. In other words,
since we have shown that the strategy given in lecture wins with probability
at least $\frac{1}{2}+\frac{1}{2n}$, show that the expected value of wins per
guess with \emph{any} randomized strategy (any set of $\{p_0, p_1, \ldots p_n\}$ is
\emph{at most} $\frac{1}{2}+\frac{1}{2n}$.

\solution{
Let $p_i$ denote the probability that you switch if you see the number
$i$.  Then, the  probability that you win if the envelopes contain
the pair $(i,i+1)$
is the probability that you will see the smaller number and switch or you
will see the bigger number and stay.  Since the probability of picking either
envelope (and thus number) is $1/2$, the probability that you win is
\[
\frac{1}{2}p_i + \frac{1}{2}(1-p_{i+1})
\]
Then, the total
probability that you win is:

\[
\sum_{i=0}^{n-1} \frac{1}{n} \left(\frac{1}{2}p_i + \frac{1}{2}(1-p_{i+1})\right)
= \frac{1}{2}+\frac{1}{2n}\sum_{i=0}^{n-1} (p_i-p_{i+1})
= \frac{1}{2}+\frac{1}{2n} (p_0 - p_n) \leq \frac{1}{2}+\frac{1}{2n}
\]
}

\problempart
\emph{Optional question:} Can you think of another strategy that is also optimal
as described above? Is this new strategy `really' optimal?

\solution{
This can almost be read directly off of the probability formula. The strategy is
to switch if $0$ is revealed, stay if $n$ is revealed, and act arbitrarily
otherwise (always switch, always stay, switch half the time, etc). This is
reasonable, since those two choices are guaranteed to lead to a win.

No, it's not truly an optimal strategy - there is no guarantee that the
distribution of the envelopes even includes the endpoints, in the general case.
It relies on the envelopes being filled with the given distribution.
}

\end{problemparts}

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

\problem %
% (Bounding tails of binomial dist)

A new fault-tolerant computer network contains 100,000 computer nodes,
and is designed to function adequately when no more than 5000
computers are down.
Suppose that the probability that any particular computer is down
is 4\%; moreover, these probabilities are independent for different
computers.

\begin{problemparts}

\problempart
Estimate the probability that exactly 5000 computers are down.

\solution{
\[
f_{100000,0.04}(5000) = 1.7264 \cdot 10^{-55}
\]
}

\problempart
Estimate the probability that the network can function adequately.

\solution{ %
  Here, we must estimate the probability that more than 95000
  computers are fault free. As a rough but high approximation, we can notice
  that the expected number of computers to be down is 4000. If we assume that
  all numbers of down computers from 5001 to 100,000 are less likely to occur
  than 5000 computers being down, we can upper bound the probability that
  more than 5000 computers are down by 
  \[
  95000 \cdot \prob{95000 \; computers \; working} = 95000 \cdot 1.7264 \cdot 10^{-55}
   = 1.640 \cdot 10^{-50}
  \]
  which should suggest that the probability of a functioning network is extremely high,
  $\geq 1 - 1.640 \cdot 10^{-50}$.

	For a more precise bound, we can find a lower bound on the probability that
	the network can function adequately:	
  \begin{equation*}
    \prob{> 95000 \; computers \; working} = 1 - \prob{\leq 95000 \; computers \; working}
  \end{equation*}

  An upper bound for $\prob{\leq 95000 \; computers \; working}$ is given by:

  \begin{eqnarray*}
    F_{100000,0.96}\left(0.95 \cdot 100000\right)
    & \leq &
    \frac{1-\alpha}{1 - \frac{\alpha}{p}} f_{n,p}(\alpha \cdot n) \\
    & = &
    \frac{1-\alpha}{1 - \frac{\alpha}{p}} f_{n,(1-p)}((1-\alpha) \cdot n) \\
    & \approx & 4.8 \cdot f_{n,(1-p)}((1-\alpha) \cdot n)
%     \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}}
  \end{eqnarray*}

  Plugging in for $f_{n,(1-p)}((1-\alpha) \cdot n)$ from part a, we get:

  \begin{equation*}
    F_{100000,0.96}\left(0.95 \cdot 100000\right) \leq 8.2866 \cdot 10^{-55}
  \end{equation*}

  Thus, it follows that:

  \begin{equation*}
    \prob{> 95000 \; computers \; working} \approx 1
  \end{equation*}

  %
  }

\end{problemparts}

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

\problem %
% (Polling)

The Gallup polling service is conducting a poll to see what percentage
of Americans believe that 6-year-olds should be
given the legal right to decide where they should live.
They would like to be accurate (after all, this is a very serious
issue) to within a 2\% margin of error, with at least 98\% probability.
Estimate how many people they would need to poll to be able to make
this claim of reliability. (As in lecture, assume that they are polling
with replacement, so they may poll the same person twice).

\solution{
We can follow the form used in lecture, using the bounds shown there.
(Note that this does not tell us the \emph{minimum} number of people
we need to poll to be sure enough, just a sufficient number). Using the
general formula
\[
 \delta \leq 2 F_{n,\frac{1}{2}}((\frac{1}{2}-\epsilon) n)
\]
we have $\delta = 0.02$, $\epsilon = 0.02$, so
\begin{eqnarray*}
\delta & \leq  & 2 F_{n,\frac{1}{2}}(\frac{12}{25}n)  \\
 & \leq  & 2 \cdot \frac{1 - 0.48}{1 - \frac{0.48}{0.5}} \cdot f_{n,\frac{1}{2}}(0.48n)  \\
 & \leq  & 26 \cdot 
  \left( \frac{2^{\left( 0.48lg\left(\frac{0.5}{0.48}\right) + 0.52lg\left(\frac{0.5}{0.52}\right) \right)n} }
              {\sqrt{2 \pi 0.48 \cdot 0.52 n}} 
 \right)  \\
 & \leq  & 26 \cdot 
  \left( \frac{2^{-0.004622 \cdot n} }
              {1.2492\sqrt{n}} 
 \right)  \\
\delta & \leq & 20.813 \cdot \frac{2^{-0.004622 \cdot n}}{\sqrt{n}} \\
\end{eqnarray*}

The easiest way to solve this is just plugging in each potential $n$ into the final
equation until we find where it must be that $\delta \leq 0.02$:
\[
\begin{array}{rl}
\textbf{n} & \textbf{max $\delta$}  \\
10 & 6.374 \\
100 & 1.511 \\
1000 & 0.026 \\
10000 & 2.54 \cdot 10^{-15} \\
2000 & 0.000768 \\
1200 & 0.0129 \\
1100 & 0.0185 \\
1080 & 0.0199 \\
1078 & 0.0201 \\
1079 & 0.0200 \\
\end{array}
\]
So it would be sufficient to survey approximately 1079 people.
}

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

\problem
% (Random vars, expected value)

%[[[ New problem, from Feller Vol. 1, p. 223, prob. 8.]]]

Let $X_1$, $X_2$, and $X_3$ be three mutually independent random
variables, each having the uniform distribution, $\prob{X_i = k}$
equal to 1/3 for each of $k=1$, $k=2$, and $k=3$.
Let $M$ be another random variable giving the maximum of these three random
variables.

\begin{problemparts}
\problempart
What is the distribution of $M$?

\solution{
This can be easily hashed out by counting the possible outcomes:
\begin{eqnarray*}
M & \textrm{ is }  & 1 \textrm{ with probability } \frac{1}{27}  \\
  &  & 2 \textrm{ with probability } \frac{7}{27}  \\
  &  & 3 \textrm{ with probability } \frac{19}{27}  \\
\end{eqnarray*}
}

\problempart
What is the expected value of $M$?

\solution{
Directly from the above, it is:
\[
\frac{1}{27}(1) + \frac{7}{27}(2) + \frac{19}{27}(3) = \frac{8}{3}
\]
}

\problempart
Generalize to $n$ variables with possible values $1, 2, \ldots n$.

\solution{
We can solve this by examining the probabilities as follows:
\[
\prob{M \leq k} = \prob{no \; X_i \; is \; greater \; than \; k}
 = \left( \frac{k}{n} \right)^n
\]
However,
\begin{eqnarray*}
\prob{M = k} & = & \prob{M \leq k} - \prob{M \leq k-1}  \\
             & = & \left( \frac{k}{n} \right)^n - \left( \frac{k-1}{n} \right)^n  \\
\end{eqnarray*}

And the expectation of $M$ becomes:
\begin{eqnarray*}
\sum_{k=1}^{n} \left[k \cdot
         \left(
             \left( \frac{k}{n} \right)^n - \left( \frac{k-1}{n} \right)^n  
         \right) \right]   & = &    
\sum_{k=1}^{n} \left[k \cdot
         \left(
             \left( \frac{k}{n} \right)^n 
         \right) \right]   -
\sum_{k=1}^{n} \left[k \cdot
         \left(
             \left( \frac{k-1}{n} \right)^n 
         \right) \right]   \\
& = &    
\sum_{k=1}^{n} \left[k \cdot
         \left(
             \left( \frac{k}{n} \right)^n 
         \right) \right]   -
\sum_{k=0}^{n-1} \left[(k+1) \cdot
         \left(
             \left( \frac{k}{n} \right)^n 
         \right) \right]   \\
& = &    
\sum_{k=1}^{n} \left[k \cdot
         \left(
             \left( \frac{k}{n} \right)^n 
         \right) \right]   -
\sum_{k=0}^{n-1} \left[k \cdot
         \left(
             \left( \frac{k}{n} \right)^n 
         \right) \right]   -
\sum_{k=0}^{n-1} \left( \frac{k}{n} \right)^n    \\
& = &    
   n - \sum_{k=0}^{n-1} \left( \frac{k}{n} \right)^n    \\
\end{eqnarray*}

}

\end{problemparts}

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

%[[[This is similar to fall 98, hw 11, problem 5.]]]
\problem
% ( expectation, substrings)

Suppose a length $n$ string of 0's and 1's is chosen uniformly
randomly (e.g., by $n$ independent tosses of fair coin)
and then wrapped around to form a circle.

\begin{problemparts}
\problempart
What is the maximum number of occurrences of the string
$0^k$ ($k$ 0's) in this circle?
What is the expected number of occurrences of $0^k$?
(Note: A string of $k+1$ 0's counts as \emph{two} strings of length
$k$ -- starting in the first position of the string and starting in
the second position. Also remember that there is no particular start
or end of the circle.)

\solution{
This can be done by simply adding up probabilities of the separate
events that the string occurs starting at position $i$, which should be
$\frac{n}{2^k}$. While the events are not independent, we are
`overcounting' in exactly the correct way. This concept is referred to,
of course, as \emph{linearity of expectation}.

To be more rigorous, define random variables $X_i$ for $i = 1, 2, \ldots n$,
where $X_i = 1$ if a string of $k$ 0's starts at position $i$ and 0 if it 
does not. Then, we are looking for $E[X_1+X_2+\ldots+X_n]$, which by linearity
of expectation must be $E[X_1] + E[X_2] + \ldots + E[X_n]$. 

This can be envisioned as
a counting problem instead. There are $2^n$ possible strings. Each
position will begin a substring of $0^k$ for $2^{n-k}$ different
strings. Thus, the total number of such substrings divided by the
number of possible strings is $\frac{n2^{n-k}}{2^n}$, which simplifies
to $\frac{n}{2^k}$.
}

\problempart
Suppose $k$ is even.
What is the expected number of occurrences of
$0^{\frac{k}{2}}1^{\frac{k}{2}}$ (total length $k$)?

\solution{
This is the same as in the previous part, since the reasoning
does not change (perhaps surprisingly).
}

\problempart
Now fix $n = 8$, $k = 4$.
Is the probability that $0000$ appears in the circle equal to the
probability that $0011$ appears?

\solution{

%This can be done with inclusion-exclusion, with much pain.
%Else, it can be done with more ad-hoc methods. For instance, the
%$0011$ substrings may not overlap at all. There may only be $4$ at most
%in a particular string. However, there are $8$ substrings of $0000$ in
%the all-zero string. Since the expectations are the same, this implies
%that there are less strings with substring $0000$, but with a greater
%average number of occurrences for those that have it.

This can be reasoned out by counting the strings in each case. 

For 
$0000$, there is one string that contains 8 copies, $00000000$.
The rest of the strings containing $0000$ can be ordered by the number
of copies of $0000$ that they contain; each one can also have the long
string of 0's begin at any of the 8 positions:
\[
\begin{array}{rcr}
 1 \; string  & 00000000 & (8 \; copies) \\
 8 \; strings & 00000001 & (4 \; copies) \\
 8 \; strings & 00000011 & (3 \; copies) \\
16 \; strings & 000001x1 & (2 \; copies) \\
32 \; strings & 00001xx1 & (1 \; copy) \\
\end{array}
\]
Thus, in total, 65 of the 256 possible strings contain a copy of $0000$. 
(Note that there are 128 copies in total; this agrees with the expectation
of $\frac{n}{2^k}$ multiplied by the number of possible strings, $2^n$).
So the probability of a random string containing a copy of $0000$ is
\[
\frac{65}{256}
\]

%(We could have done the problem with inclusion-exclusion.
%We then get, for each digit:
%\[
%\begin{array}{rrcr}
%8 copies: &  1 string  & 00000000 & (i, i+1, i+2, i+3, i+4, i+5, i+6, i+7) \\
%4 copies: &  2 strings & 0000000X & (i, i+1, i+2, i+3)   \\
%          &  1 string  & 00000000 & (any other combo)   \\
%3 copies: &  4 strings & 000000XX & (i, i+1, i+2) \\
%          &  2 strings & 0000000X & (i, i+1, i+3), (i, i+2, i+3) \\
%          &  1 string  & 00000000 & (i, i+1, i+3), (i, i+2, i+3) \\
%2 copies: & 64 strings & 00000XXX & (2 copies or more) \\
%1 copies: &128 strings & 0000XXXX & (1 copy or more) \\
%% sorry, this is a disaster!
%\end{array}
%\]
%Then, we have the total number of such strings as $ = $ 

For 
$0011$, we get the following:
\[
\begin{array}{rcr}
  4 \; strings & 00110011 & (2 \; copies) \\
120 \; strings & 0011xxxx & (1 \; copy) \\
\end{array}
\]
The number of strings with one copy is a bit complex; the $0011$ sequence
can start in any of $8$ places, and the other four characters can be 
any of the $16$ possibilities except $0011$.
Altogether, 124 of the 256 possible strings contain a copy of $0000$. 
(Note that there are again 128 copies in total).
The probability of a random string containing a copy of $0011$ is
\[
\frac{124}{256}
\]


Thus, the probability is not the same; it is significantly more likely
that a substring of $0011$ will appear.
}

\problempart
Justify your answer for the previous part. If your answers in the previous
parts seem to be ``contradictory'',
explain.

\solution{
Although the expectations are the same, the extra overlapping
possibilities for 0000 make the conditional probability
of a second occurrence, conditioned on a first occurrence, higher than
it is for 0011. Since it is more likely that there will be a second
occurrence, the expectation must be composed of less situations in which
the target string occurs at all.
}

\end{problemparts}

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

\problem %
%( expectation, indicator variables, harmonic numbers)

%%%fall 98, pset 11, problem 4

Suppose that you choose a listing (permutation) of the numbers $1, 2, \ldots, n$
uniformly at random.  What is the expected number of entries that are
greater than all entries that follow them?  For example, in the listing
4, 2, 5, 1, 3, the numbers 3 and 5 are greater than all following entries.
(Hint: Try using indicator variables).

\solution{
Let $i_k$ be an indicator for the event that the $k$-th entry is
greater than the following $n-k$ 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)$.  Note that no matter what the last
$n-k+1$ numbers are, each of the last $n-k+1$  entries is equally likely to be 
the largest.  Therefore, $\Pr(i_k = 1) = \frac{1}{n-k+1}$.
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}{n-k+1} \\
        & = &   \sum_{k=1}^n \frac{1}{k} \\
        & = &   H_n
\end{eqnarray*}
}


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

\problem %

%[[[Something with MTTF?]]]

Every day in Boston, a rainstorm occurs with probability 1/3 (independently
of any other day).
Each day it rains, the radar system at the Nashua airport breaks with
probability 1/25. The system never breaks on fair days.

\begin{problemparts}
\problempart
Assuming that the radar was working yesterday (but may break today, if it
happens to rain),
how many days can we expect the Nashua radar system to work correctly
before it next breaks?

\solution{
This can be done with a simple recurrence:
\begin{eqnarray*}
w  & =  & \frac{2}{3}(1+w)+\frac{1}{3}(\frac{24}{25}(1+w))  \\
w  & =  & \frac{2}{3}+\frac{2}{3}w+\frac{8}{25}+\frac{8}{25}w  \\
\frac{1}{75}w & = & \frac{74}{75} \\
w & = & 74
\end{eqnarray*}
Notice that in this case, we could have tried to predict the expected time
the system will work as simply $\frac{1}{p_{failure}}$, because it never
breaks on non-rainy days. However, this would technically be off by $1$,
since it counts the day that the system breaks as well.
}

\problempart
\emph{Optional question:}
Suppose that the first time the radar system breaks (on a rainy day
with probability 1/25), it is only patched-up with a quick hack to
keep it working. (As a computer science student, you should be able
to relate to this). After being patched-up, it will fail on future
rainy days with probability 1/10, after which the system will need
major repairs.
Calculate the expected number of days until the radar system needs
\emph{major} repairs.
\solution{
\begin{eqnarray*}
w  & =  & \frac{2}{3}(1+w)+\frac{1}{3}(\frac{24}{25}(1+w)+ \frac{1}{25}(1+v))  \\
v  & =  & \frac{2}{3}(1+v)+\frac{1}{3}(\frac{9}{10}(1+v))  \\
v  & =  & \frac{2}{3}+\frac{2}{3}v+\frac{3}{10}+\frac{3}{10}v  \\
\frac{1}{30}v & = & \frac{29}{30} \\
v & = & 29  \\
w  & =  & \frac{2}{3}(1+w)+\frac{1}{3}(\frac{24}{25}(1+w)+ \frac{1}{25}(30))  \\
w  & =  & \frac{2}{3}+\frac{2}{3}w+\frac{8}{25}+\frac{8}{25}w + \frac{30}{75}  \\
\frac{1}{75}w & = & \frac{104}{75} \\
w & = & 104
\end{eqnarray*}
Although you could have also seen these as independent events that occur 
sequentially.
}

\end{problemparts}

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

\problem
% (fall 98, pset 11, some version of problem 6.
% conditional expectation.

Suppose that $R$ is a random variable.  Let $E$ be an event.
The {\em conditional expectation} of $R$ given that event $E$ occurs is
denoted $\Ex(R \mid E)$ and is defined to be

\begin{eqnarray*}
\Ex(R \mid E)   & = &   \sum_{x \in \text{range}(R)} x \cdot \Pr(R = x \mid E)
\end{eqnarray*}

\begin{problemparts}

\problempart Suppose I flip a fair coin 4 times. Compute the expected
number of heads, given that all 4 values are not the same.

\solution{
Let the random variable $R$ be the number of heads, and let
$E$ be the event that not all flips are the same.

\begin{eqnarray*}
\Ex(R \mid E)   & = &   \sum_{x=1}^{4} \Pr(R = x \mid E)(x) \\
                & = &   0(0) + \frac{4}{14}(1) + \frac{6}{14}(2)
                             + \frac{4}{14}(3) + 0(4) \\
                & = &   2
\end{eqnarray*}
}

\problempart Compute the expected value of the number rolled on a
fair, 6-sided die, given that the outcome is prime.

\solution{
Define $R$ as the number rolled and $E$ as the event that a prime number
is rolled.

\begin{eqnarray*}
\Ex(R \mid \overline{E})
        & = &   \sum_{x=1}^{6} x \cdot \Pr(R = x \mid \overline{E}) \\
        & = &   1 \cdot 0 + 2 \cdot \frac{1}{3} +
                3 \cdot \frac{1}{3} + 4 \cdot 0 +
                5 \cdot \frac{1}{3} + 6 \cdot 0 \\
        & = &   \frac{10}{3}
\end{eqnarray*}
}

\problempart Prove the following identity, assuming that all
expectations exist.

\begin{eqnarray*}
\Ex(R)  & = &   \Pr(E) \cdot \Ex(R \mid E) +
                        \Pr(\overline{E}) \cdot \Ex(R \mid \overline{E})
\end{eqnarray*}

\solution{We transform the right side into the left side.  All
summations are over $x \in \text{Range}(R)$.

\begin{eqnarray*}
\lefteqn{\Pr(E) \cdot \Ex(R \mid E) +
        \Pr(\overline{E}) \cdot \Ex(R \mid \overline{E})} \\
        & = &   \Pr(E) \cdot \left( \sum_{x}
                        x \cdot \Pr(R = x \mid E) \right)
                + \Pr(\overline{E}) \cdot  \left( \sum_{x}
                        x \cdot \Pr(R = x \mid \overline{E}) \right) \\
        & = &   \Pr(E) \cdot \left( \sum_{x}
                        x \cdot \frac{\Pr(R = x \cap E)}{\Pr(E)} \right)
                + \Pr(\overline{E}) \cdot  \left( \sum_{x}
                        x \cdot \frac{\Pr(R = x \cap \overline{E})}
                        {\Pr(\overline{E})} \right) \\
        & = &   \sum_{x} x \cdot \left(
                        \Pr(R = x \cap E) + \Pr(R = x \cap \overline{E})
                        \right) \\
        & = &   \sum_{x} x \cdot \left(
                        \Pr((R = x \cap E) \cup (R = x \cap \overline{E}))
                        \right) \\
        & = &   \sum_{x} x \cdot \Pr(R = x) \\
        & = &   \Ex(R)
\end{eqnarray*}

The first step uses the definition of conditional expectation.  The
second step uses the definition of conditional probability.  The third
step is simplification.  The fourth step uses the fact that the
probability of a disjoint union of events is equal to the sum of the
event probabilities.  The fifth step is simplification, and the final
step uses the definition of expected value.}

%\problempart Compute the expected value of the product of the numbers
%rolled on two dice that are 6-sided, fair, and independent, given that
%the numbers rolled are distinct.
%
%\solution{Let the random variable $R$ be the product of the two dice,
%and let $E$ be the event that the two numbers rolled are {\em equal}.
%The following three quantities are easy to compute:
%
%\begin{eqnarray*}
%\Ex(R)         & = &   \Ex(\text{Die 1}) \cdot \Ex(\text{Die 2}) \\
%       & = &   \frac{7}{2} \cdot \frac{7}{2} \\
%       & = &   \frac{49}{4} \\
%\Pr(E) & = &   \frac{6}{36} \\
%       & = &   \frac{1}{6} \\
%\Ex(R \mid E)
%       & = &   \sum_{x \in \mathbb{N}} x \cdot \Pr(R = x \mid E) \\
%       & = &   1^2 \cdot \frac{1}{6} + 2^2 \cdot \frac{1}{6} +
%               3^2 \cdot \frac{1}{6} + 4^2 \cdot \frac{1}{6} +
%               5^2 \cdot \frac{1}{6} + 6^2 \cdot \frac{1}{6} \\
%       & = &   \frac{91}{6}
%\end{eqnarray*}
%
%We want to compute $\Ex(R \mid \overline{E})$, the expected value of
%the product of the two rolls, given that they are distinct.  From the
%identity in part(c), we have:
%
%\begin{eqnarray*}
%\Ex(R \mid \overline{E})
%       & = &   \frac{\Ex(R) - \Pr(E) \cdot \Ex(R \mid E)}{\Pr(\overline{E})} \\
%       & = &   \frac{\frac{49}{4} - \frac{1}{6} \cdot \frac{91}{6}}
%                       {\frac{5}{6}} \\
%       & = &   \frac{35}{3}
%\end{eqnarray*}
%}

\problempart
\emph{Optional problem:}
Suppose you are playing poker. You have the following chart of payoffs:
\begin{eqnarray*}
One \ Pair & : & \$10  \\
Two \ Pair & : & \$15  \\
Three \ of \ a \ Kind & : & \$30  \\
Full \ House & : & \$60  \\
All \ else & : & \$0
\end{eqnarray*}

Calculate the expected amount of money you will make on a hand, given
that the first two cards you are dealt are both Jacks.

\solution{
Note that $\binom{50}{3} = 19600$. We can compute the probabilities as follows:
\[
\begin{array}{rcllcl}
Two \ Pair & : & 12 \cdot \binom{4}{2} \cdot 44 & = 3168 & \longrightarrow & \frac{3168}{19600} \\
Four \ of \ a \ Kind & : & 48 \\
Three \ of \ a \ Kind & : & 2 \cdot \binom{48}{2} + 48 & = 2304 & \longrightarrow & \frac{2304}{19600} \\
Full \ House & : & 12 \cdot \binom{4}{3} & = 48  & \longrightarrow & \frac{48}{19600} \\
One \ Pair & : &  \binom{50}{3} - 3168 - 2304 - 48 & = 14080  & \longrightarrow & \frac{14080}{19600} \\
\end{array}
\]
The problem changes slightly if you did not count Four of a Kind as a valid
Three Pair, but by the payoffs given that is the optimal thing to do.

We thus get as the expectation:
\[
\frac{14080}{19600}(10) + \frac{3168}{19600}(15) + 
\frac{2304}{19600}(30) + \frac{48}{19600}(60) 
 = \$13.28
\]
}

\end{problemparts}


\end{problems}

\end{document}

