\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer} \&
Dr.~Radhika~Nagpal}

\renewcommand{\reading}{
\href{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln11-12.pdf}
{Week 11-12 Notes}}

\begin{document}
\problemset{11-12}

%%-----------------------------------------------------------------------%%

% \problemdata     
% {new}           
% {independence theory}              
% {Albert R. Meyer} 		
% {}
% {}

\begin{problem} Prove that
\bparts

\ppart $\prcond{A}{B} = \prcond{A}{\bar{B}}$ iff $A$ and $B$ are independent.

\solution{\begin{proof}
($\rightarrow$): Assuming $\prcond{A}{B} = \prcond{A}{\bar{B}}$,
\begin{align*}
\pr{A} = & \prcond{A}{B}\pr{B} + \prcond{A}{\bar{B}}\pr{\bar{B}}
             & \text{(Law of Total Probability)}\\
       = & \prcond{A}{B}\pr{B} + \prcond{A}{B}\pr{\bar{B}}
             & \text{(assumption)}\\
       = & \prcond{A}{B}(\pr{B} + \pr{\bar{B}})
             & \text{(distributivity)}\\
       = & \prcond{A}{B} \cdot 1 = \prcond{A}{B} & \text{(Complement Rule)},
\end{align*}
so $A$ is independent of $B$ by definition.

($\leftarrow$): Assuming $A$ and $B$ are independent, we know that $A$ and
$\bar{B}$ are also independent, so
\begin{align*}
\prcond{A}{B} = & \pr{A} &  \text{(independence of $A$ and $B$)}\\
              = &\prcond{A}{\bar{B}} &  \text{(independence of $A$ and $\bar{B}$)}.
\end{align*}

For the record, here's  the proof that $A$ and $\bar{B}$ are independent:
\begin{align*}                                     
\prcond{A}{\bar{B}} = & \frac{\pr{A \intersect \bar{B}}}{\pr{\bar{B}}} 
                        & \text{(definition of conditional probability)}\\
                    = & \frac{\pr{A - B}}{\pr{\bar{B}}} 
                        & \text{(definition of set difference)}\\
                    = & \frac{\pr{A} - \pr{A \intersect B}}{\pr{\bar{B}}}
                        & \text{(Difference Rule)}\\
                    = & \frac{\pr{A} - \pr{A}\pr{B}}{\pr{\bar{B}}}
                        & \text{\text{(independence of $A$ and $B$)}}\\
                    = & \frac{\pr{A}(1 - \pr{B})}{\pr{\bar{B}}}
                        & \text{(distributivity)}\\
                    = &  \frac{\pr{A}\pr{\bar{B}}}{\pr{\bar{B}}}
                        & \text{(Complement Rule)}\\
                    = &  \pr{A}.
\end{align*}

\end{proof}
} \ppart If $A,B,C$ are mutually independent events, then $A$ and $B
\union C$ are independent.

\solution{
\begin{proof}
To show independence of the event $A$ and the event $B \union C$, it suffices to 
show that the probability of both events happening is equal the the product of
the probabilities that each event happens.  That is, we need only show that
the 
\begin{equation}\label{need}
\pr{A \intersect (B \union C)} = \pr{A}\pr{B \union C}
\end{equation}

But
\begin{align*}
\pr{A \intersect (B \union C)} = & \pr{(A \intersect B) \union (A \intersect C)}
       & \text{(distributivity of $\intersect$ over $\union$)}\\
  = & \pr{A \intersect B} + \pr{A \intersect C} - \pr{(A \intersect B)
       \intersect (A \intersect C)} & \text{(Inclusion-exclusion)}\\
  = & \pr{A \intersect B} + \pr{A \intersect C} - \pr{A \intersect B
       \intersect C} & \text{(since $A \intersect A = A$)}\\
  = & \pr{A}\pr{B} + \pr{A}\pr{C} - \pr{A}\pr{B}\pr{C} &
       \text{(mutual independence)}\\
  = & \pr{A}(\pr{B} + \pr{C} - \pr{B}\pr{C}) & \text{(distributivity of
       multiplication)}\\
  = & \pr{A}\pr{B \union C}  & \text{(Inclusion-exclusion)},
\end{align*}
which proves~(\ref{need}).
\end{proof}
}
\eparts
\end{problem}


% \problemdata     
% {Spring 02 In class}           
% {conditional probability \& independence}
% {Albert R. Meyer} 		
% {}
% {}

\begin{problem}
There is a course---not 6.042, naturally---in which \emph{10\% of the
assigned problems contain errors}.  If you pick a random problem and send
an email to your TA and your Lecturer asking whether the problem has an
error, then \emph{the TA's reply will be correct 80\% of the time}.  This
80\% accuracy holds regardless of whether or not a problem has an error.
Likewise, \emph{the Lecturer's reply will be correct with only 75\%
accuracy}.\footnote{This is consistent with the view that Lecturers are chosen
for their theatrical personalities, not their mastery of the material.
\texttt{:-)}}

Furthermore, the TA and Lecturers tend to be confused by different kinds
of problems.  The net result of this is that \emph{the correctness of the
lecturers' answer and the TA's answer are independent of each other,
regardless of whether there is an error}.

For the following parts, designate events as follows:
\begin{eqnarray*}
T & \eqdef & \mbox{``the TA's email says the problem has an error,''}\\
L & \eqdef & \mbox{``the Lecturer's email says the problem has an error.''}\\
E & \eqdef & \mbox{``the problem has an error,''}
\end{eqnarray*}

%We verify this informal argument by actually calculating the probability
%of each of these events and their intersection, and then observing that
%the probability that the two events occur is different from the product of
%the probabilities.

\begin{problemparts}

\problempart Using $T$, $L$ and $E$ translate the sentences in italics
into probability notation.  For example, ``the correctness of the
lecturers' answer and the TA's answer are independent of each other,''
could translate into some equations involving terms such as
$\prcond{T}{E}$ and $\prcond{T \intersect L}{E}$.

\solution{
%The assumptions above tell us:

10\% of the assigned problems contain errors:
\begin{equation}
\pr{E} =  \frac{10}{100} = \frac{1}{10}.\label{E10}
\end{equation}

the TA's reply will be correct 80\% of the time \dots regardless of whether
or not a problem has an error:
\begin{equation}
\prcond{T}{E} = \prcond{\bar{T}}{\bar{E}} = \frac{80}{100} =
     \frac{4}{5}.\label{TE}
\end{equation}

the Lecturer's reply will be correct with only 75\% accuracy:
\begin{equation}
\prcond{L}{E} = \prcond{\bar{L}}{\bar{E}} = \frac{75}{100} =
       \frac{3}{4}\label{LE}.
\end{equation}

the correctness of the lecturers' answer and the TA's answer are
independent of each other, regardless of whether there is an error:
\begin{align}
\prcond{T \intersect L}{E}  = & \prcond{T}{E} \prcond{L}{E}\label{TLE}\\
\prcond{T \intersect L}{\bar{E}}  = & \prcond{T}{\bar{E}}
                      \prcond{L}{\bar{E}}  \label{TLbarE}. 
\end{align}

%COMMENT FOR EDITING:  Seems like a better translation than~(\ref{TLbarE})
%would be
%\[
%\prcond{\bar{T} \intersect \bar{L}}{\bar{E}} = \prcond{\bar{T}}{\bar{E}}
%                      \prcond{\bar{L}}{\bar{E}}.
%\]
%I think they are equivalent, but I don't have time to check now -- ARM
%11/12/02 9:30PM.}

%Note that while we know that $T$ and $L$ are independent \emph{given} $E$
%or \emph{given} $\bar{E}$, we will show that they are not independent by
%themselves.  In fact, we will show:

%%\begin{claim*}
%\[
%\pr{L \intersect T} > \pr{L}\pr{T}.
%\]
%%\end{claim*}


\problempart What is the probability that \emph{both} the Lecturer and TA
report an error?

\solution{
\begin{align*}
\pr{L \cap T} = & \prcond{L \cap T}{E} \pr{E} + \prcond{L \cap T}{\bar E} \pr{\bar E}
        & \text{(Law of Total Probability)}\\
= & \prcond{L}{E}      \prcond{T}{E}       \pr{E} + 
      \prcond{L}{\bar{E}} \prcond{T}{\bar{E}} \pr{\bar E} &
        \text{(by~(\ref{TLE}) and~(\ref{TLbarE}))}\\
= & \frac{3}{4} \cdot \frac{4}{5} \cdot \frac{1}{10}
        + (1 - \frac{3}{4}) (1 - \frac{4}{5}) (1 - \frac{1}{10}) =
        \frac{105}{1000} = 0.105. & \text{(by~(\ref{LE}) and~(\ref{TE}))}
\end{align*}
}

\ppart Is the event that ``the TA says that there is an error'',
independent of the event that ``the lecturer says that there is an
error''?  Prove it.

\solution{
\begin{align*}
\pr{T}  = & \prcond{T}{E} \pr{E}  + \prcond{T}{\bar{E}} \pr{\bar{E}}
        & \text{(Law of Total Probability)}\\
 = & \prcond{T}{E} \pr{E}  + (1- \prcond{\bar{T}}{\bar{E}})(1- \pr{E})
        & \text{(Complement Rule)} \\
 = & \prcond{T}{E} \pr{E}  + (1- \prcond{T}{E})(1- \pr{E})
        & \text{(by~(\ref{TE}))} \\
 = & \frac{4}{5} \frac{1}{10} + (1 - \frac{4}{5})(1 - \frac{1}{10})
        = \frac{13}{50}, & \text{(by~(\ref{TE}) and~(\ref{E10}))}
\end{align*}

A similar argument proves that
\begin{equation}
\pr{L} =  \pr{L \cap E} + \pr{L \cap \bar{E}}
  = \frac{3}{4} \frac{1}{10} + (1 -\frac{3}{4})(1 - \frac{1}{10}) = \frac{3}{10}.
\end{equation}

Finally,
\[
\pr{L}\pr{T} = \frac{3}{10} \cdot \frac{13}{50} = .078 >  0.105 = \pr{L
\intersect T},
\]
so $L$ and $T$ are not independent.

There is a simple intuitive argument supporting this conclusion.  Suppose
you receive an email from your TA that says the problem has an error.
Then the odds that the Lecturer's email will now say that the problem has
an error are higher than before the email.  That is, $\prcond{L}{E} >
\pr{L}$.  The reason is that
\begin{itemize}

\item Because the TA is usually right, when the TA says that the problem
has an error, the likelihood that there really is an error is increased.

\item But the lecturer is also usually right, so increasing the likelihood
of there \emph{being} an error also increases the likelihood that the
lecturer will \emph{report} an error.
\end{itemize}
}

\end{problemparts}
\end{problem}

\iffalse
\problemdata     
{S01-PS8-3}           
{probability-intro}              
{Joshua A. Tauber} 		
{F98-PS9, S01-PS8}
{S01 Karger}
\begin{problem}

Three friends, $A$, $B$, and~$C$, plan to fight a three-cornered
paint-ball duel. They will shoot one at a time in the sequence
$ABCABC\dots$. On her turn, a shooter may target either of the other
two, or may fire harmlessly at a tree to enjoy the splat of the paint.
Once a duelist is hit, she must retire from the field to clean the
paint off her goggles and let the other two finish the duel.  Assume
it is common knowledge that each of the three friends want to maximize
her probability of being the only one left standing and that all three
can compute probabilities without error.\footnote{Informally, a fact
$F$ is common knowledge if it we can truthfully assert an infinite
sequence of statements of the form ``$A$ knows $F$. $B$ knows that $A$
knows $F$.  $A$ knows that $B$ knows that $A$ knows $F$, \dots''.}
Furthermore, they all know that $A$'s chance of hitting her target is
$0.3$, $B$~never misses, and $C$'s chance of hitting is~$0.5$.  What
should duelist $A$~do on her first shot and what probability of
winning does this give her?

\solution{
%FIX SOLUTION
First note that the optimal strategy for~$B$ is to shoot the most accurate
gunfighter. So, if $B$~gets to shoot and both $A$ and~$C$ are still alive,
$B$~will shoot~$C$---this gives him a $1-0.3 = 0.7$ chance of survival---and
not~$A$---that would only give him a $1-0.5 = 0.5$ chance of survival.
 
Suppose that $A$ shoots into the air. Then $B$ shoots~$C$, and $A$~gets one
shot to kill~$B$ before he himself is killed. Therefore $A$~has a $0.3$~chance
of survival.
  
Suppose that $A$ shoots at~$B$. If he hits, then he enters a duel with~$C$,
where $C$ gets the first shot. In this case, let $p$~be the probability that
$A$~wins the duel. For this to happen, either $C$~must miss and $A$~must hit
(probability $0.5 \cdot 0.3$) or else $C$~must miss, $A$~must miss, and then
$A$ must win a duel of the same type as before (probability $0.5 \cdot 0.7
\cdot p$).  As an equation: \begin{displaymath} p = \frac{1}{2} \cdot
\frac{3}{10} + \frac{1}{2} \cdot \frac{7}{10} p, \end{displaymath} which has
the solution $p = 3 /13$.
  
Thus, If $A$ hits~$B$, his odds of survival are lower than if he fires into the
air! If he does not hit, his probability of survival is the same as if he had
started by firing in the air. Since $A$~hits with probability~$0.3$, the
probability that $A$~survives when he begins with shooting at~$B$ is $0.3 \cdot
3 / 13 + 0.7 \cdot 0.3 = 363 / 1300 < 0.28$.
  
On the other hand, suppose that $A$ shoots at~$C$. If he hits, then
$B$~immediately kills him. If he does not hit, his probability of survival is,
again, the same as if he had started by firing in the air. Thus, his
probability of survival in this case is $0.3 \cdot 0 + 0.7 \cdot 0.3 = 0.21$.
  
To conclude, $A$'s best strategy is to fire into the air; this gives him a
$0.3$ chance of survival.}

\end{problem}
\fi


%%%%%%%%%%%%%%% EXPECTATION %%%%%%%%%%%%%%

% \problemdata     
% {S01-PS10-7}           
% {expectation}              
% {} 		
% {S01-PS10}
% {S01 Karger}

\begin{problem}
In the board game Monopoly, the number of squares that a player
advances in a single turn is determined by up to three rolls of a pair
of dice as follows.

\begin{itemize}
\item Initially, the player rolls two dice, sums the results, and
advances that many squares.

\item If the same number comes up on both dice---this is called
\emph{rolling a double}---then the player rolls the dice a second time,
sums the results, and advances that many additional squares.

\item If the player rolled on double on the second roll, then the player
rolls the dice a third time, sums the results, and advances that many
additional squares.

\item However, if third roll was a double, then the player ``goes to
jail''.  We will treat this as though he had to reset his position to
where he was just before the first roll, so the total number of squares
advanced by the player in this case is zero.
\end{itemize}

Assume that the dice are fair and six-sided and that rolls are
mutually independent.

We want to calculate the expected number of squares that a player
advances in a single turn. Here is one approach to the problem.  Lets
assume that the pair of dice are \emph{always} rolled three times,
with the player simply ignoring results of any roll which was preceded
by a non-double roll.

Let the random variable $R_i$ be the sum of the two dice on the $i$th
roll, and let $I_i$ be an indicator for the event that the $i$th roll
was a double.

\begin{problemparts}

\problempart Let the random variable $R$, be the number of squares
advanced by the player. Express $R$ is terms of $R_i$ and $I_i$.

\solution{ 
We can express the random variable $R$, the number of squares advanced
by the player, as follows:
\[
R = R_1 + I_1 R_2 + I_1 I_2 R_3 - I_1 I_2 I_3 (R_1 + R_2 + R_3)
\]
}

\problempart Calculate $\expect{R}$. You will almost surely use some
assumptions about independence. Be sure to indicate where you do so.

\solution{ Since the dice rolls are independent, we know that $R_i$'s and
$I_j$'s at different rolls are independent.  For example, knowing the value of
the first roll has no effect on the probability that the second or third roll
is a double.  We can take expectations of both sides and reason as follows:
\begin{align*}                                     
\expect{R}  = &   \expect{R_1 + I_1 R_2 + I_1 I_2 R_3  
                                - I_1 I_2 I_3 (R_1 + R_2 + R_3)}
              & \text{definition of R}\\
            = &   \expect{R_1 + I_1 R_2 + I_1 I_2 R_3  
                                 - I_1 I_2 I_3 R_1
                                 - I_1 I_2 I_3 R_2
                                 - I_1 I_2 I_3 R_3}
              & \text{distributivity}\\
            = &   \expect{R_1}
                 + \expect{I_1 R_2}
                 + \expect{I_1 I_2 R_3}
               & \text{linearity of expectation}\\
              & \mbox{}
                 - \expect{I_1 I_2 I_3 R_1}
                 - \expect{I_1 I_2 I_3 R_2}
                 - \expect{I_1 I_2 I_3 R_3}\\
            = &   \expect{R_1}
                 + \expect{I_1} \cdot \expect{R_2}
                 + \expect{I_1} \cdot \expect{I_2} \cdot \expect{R_3}\\
              &\mbox{}
                - \expect{I_2} \cdot \expect{I_3} \cdot \expect{I_1 R_1} 
                - \expect{I_1} \cdot \expect{I_3} \cdot \expect{I_2 R_2} 
                - \expect{I_1} \cdot \expect{I_2} \cdot \expect{I_3 R_3}
\end{align*}
The last step follows because mutual independence of the rolls implies
that each the following sets of random variables are independent:
$\{I_1, R_2\}$, $\{I_1, I_2, R_3\}$, $\{I_1, I_2, R_3\}$,
$\{I_2, I_3, (I_1 R_1)\}$, $\{I_1, I_3, (I_2 R_2)\}$, and
$\{I_1, I_2, (I_3 R_3)\}$.

Note that the expectation of $R_i$ is $7$, and the expectation of $I_i$ is
$1/6$.  Finally, note that $\expect{I_i R_i} = 7/6$ by direct calculation.
Substituting into the formula above gives:
\begin{eqnarray*}
\expect{R}      & = &   \frac{595}{72}.
\end{eqnarray*}
}

\end{problemparts}
\end{problem}

% Wald's Theorem.
% Spring 99 Final. 
\begin{problem}
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{problem}



%% old problem
%% like cool stickers 
\begin{problem} 

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

Suppose that I choose a permutation 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 permutation 4, 2,
1, 5, 3, the numbers 4 and 5 are greater than all preceding
entries (Hint: What's the probability that the
first entry is greater than all the preceding entries? What about the
second one?)

\solution{We can solve this problem in a similar manner to the cool
stickers problem from class. Let $i_k$ be an indicator for the event
that the $k$-th entry is greater than the preceding $k-1$ entries. The
$I_k$ are not independent, however independence is not required for
using linearity of expectation

\begin{eqnarray*}
\expect{\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. Consider a $k$-permutation selected from $n$ elements. One of
the elements in the permutation must be the largest, since all the
elements are distinct. However by symmetry, the largest number is
equally likely to be in the first or second or third ... $k$
position. Therefore, $\Pr(i_k = 1) = \frac{1}{k}$.  

Substituting this into the equation above gives:

\begin{eqnarray*}
\expect{\text{\# new maxima}}
    & = &   \sum_{k=1}^n \Pr(i_k = 1) \\
    & = &   \sum_{k=1}^n \frac{1}{k} \\
    & = &   H_n
\end{eqnarray*}
}

\end{problem}


% \problemdata     
% {S01-PS10-6}           
% {RV's, expectation}              
% {} 		
% {S01-PS10}
% {S01 Karger}


\begin{problem}
% modified from spring 97 Pset 13, 3
There are $n$ MIT students who are taking 6.042 and 6.003 this term.  To
make it easier on themselves, the professors in charge of these classes
have decided to randomly permute their class lists and then assign
students grades based on their rank in the permutation\footnote{\dots just
as many students have long suspected \texttt{:-)}}.  Assume all permutations
are equally likely and that the ranking in each class is independent of
the other.

\bparts

\ppart
What is the expected number of students that have a higher rank
in 6.042 than 6.003?

\solution{

Let $X$ be a random variable whose value is the number of students whose ranks
are higher in 6.042.  Let $X_i$ be a random variable whose value is 1 if
student i has higher rank in 6.042 than 6.003 and 0 otherwise.  By the Law of
Total Probability, the probability that student $i$ has higher rank in 6.042 is
\begin{eqnarray}
\prob{X_i = 1} &=& \sum_{1\leq r \leq n} 
                       \prob{\text{6.033 rank } < r \mid \text{6.042 rank = r}}
\label{totalrank}
\end{eqnarray}
Since there are $n$ possible rankings and $r-1$ rankings lower than $r$, the
probability that student $i$ has higher rank in 6.042 than in in 6.003 is
$(r-1)/n$.  The probability that student $i$ has rank $r$ in $6.042$ is $1/n$.
Thus, \ref{totalrank} becomes


\[
\prob{X_i = 1} = \sum_{1\leq r \leq n} \frac{1}{n} \frac{r-1}{n} = \frac{n-1}{2n}.
\]

Since $X = \sum_{1\leq i \leq n} X_i$, we use linearity of expectation to
compute that the expected number of students with a higher rank on 6.042 is
rank on 6.042 is
\[
\expect{X} = \expect{X_1}+\expect{X_2}+\dots+\expect{X_n} = \frac{n-1}{2}.
\]

Another way to solve this problem is to observe that students with higher
rank in one class have lower rank in the other class, so by symmetry, the
expected number of higher- and lower-ranked students in either class is
the same.  The expected number of students with the same rank equals 1 by
linearity of expectation, since probability student  ranked the same in
both schools is $1/n$.  These observations now yield same answer as above.
}

\ppart
What is the expected number of students that have a ranking at
least $k$ higher in 6.042 than in 6.003?

\solution{

This part can be done in the same way as the previous one.  Let $X$ be a random
variable whose value is the number of students who are ranked at least $k$
higher in 6.042 thank 6.003.  Let $X_i$ be the random variable whose value is 1
if student $i$ is ranked at least $k$ higher in 6.042 than 6.003 and 0
otherwise.  By the Law of Total Probability, the probability that student $i$
has at least $k$ higher rank in 6.042 is 
\begin{eqnarray}
\prob{X_i = 1} &=& \sum_{k+1\leq r \leq n} 
                       \prob{\text{6.033 rank } \leq r-k \mid \text{6.042 rank = r}}
\label{totalkrank}
\end{eqnarray}

%COMMENT FOR EDITING: Why are we summing from $k+1$ to $n$ rather than
%$1$ to $n-k$?  Does ``higher rank'' mean higher number or lower number?


(Notice that the $\prob{X_i = 1 \mid i \leq k} = 0$.) Since there are $n$
possible rankings and $r-k$ rankings no higher than $r-k$, the probability that
student $i$ has $k$ higher rank in 6.042 than in in 6.003 is $(r-k)/n$.  The
probability that student $i$ has rank $r$ in $6.042$ is $1/n$.  Thus,
\ref{totalkrank} becomes
\[
\prob{X_i=1} = \sum_{k+1\leq r\leq n} \frac{1}{n} \frac{r-k}{n} 
             = \frac{(n-k)(n-k+1)}{2n^2}.
\]

Since $X = \sum_{1\leq r \leq n} X_i$, we use linearity of expectation to
compute that the expected number of students with a $k$ higher rank on 6.042 is
\[
\expect{X}=\expect{X_1}+\expect{X_2}+\dots+\expect{X_n} = \frac{(n-k)(n-k+1)}{2n}.
\]

}

\eparts
\end{problem}

\iffalse
% \problemdata     
% {new}           
% {conditional probability; intransitivity}
% {Albert R. Meyer} 		
% {from F02, cp10F prob 3}
% {}

\begin{problem}
Do Week 10, Friday, Class Problem 3 with ``\texttt{HHH}'' replacing
``\texttt{HTT}''.

\solution{Josh/Karen complete the soln; similar to the solution given for
Week 10, Friday, Class Problem 3.  If you can figure it out, prove the
general result that any sequence $abc$ is beaten by $\bar{b}ab$, so will
be an intransitive beating cycle $abc, \bar{b}ab, \bar{a}\bar{b}a,
b\bar{a}\bar{b}, ab\bar{a}, \bar{b}ab$.}

\end{problem}
\fi

\begin{problem} 
\begin{problemparts}
\problempart Suppose we flip a fair coin until two heads in a row come up.  What
is the expected number, $F$, of flips we perform?

\hint Let
$F_{\text{T}}$ be the expected number of further flips until two heads
comes up, given that the previous flip was T, and likewise let
$F_{\text{H}}$ be the expected number of further flips until two heads
comes up given that the previous flip was H.  Argue that $F_{\text{T}}$
will equal 1 plus the average of $F_{\text{T}}$ and $F_{\text{H}}$.

\solution{
$F=F_{\text{T}}$, since the initial condition has no chance
of achieving two heads on the first flip and is thus the same as if the
previous flip had been tails. 

To calculate the expected number of flips, we take $1$ for the first 
flip and then consider the two equally-likely outcomes: the first flip
is tails, or the first flip is heads. The remaining flips we can expect
are simply $F_{\text{T}}$ and $F_{\text{H}}$, respectively.
This gives us a total expectation of:
\[
F_{\text{T}} = 1 + \frac{1}{2}F_{\text{T}} + \frac{1}{2}F_{\text{H}}
\]
If the previous flip was heads, we get a similar calculation. The biggest
difference is that if the first flip is heads, we have no more flips
beyond the current one (we are done).
\[
F_{\text{H}} = 1 + \frac{1}{2}F_{\text{T}}+ \frac{1}{2}(0)
\]
Solving for $F_{\text{T}}$ (by substitution) yields $F=6$.

This can also be solved using a single equation formed by examining
that cases for the first and second flips, but it is not as clean.

%Clearly $F=F_{\text{T}}$.  Assuming the hint
%\[
%F_{\text{T}} = 1 + \frac{F_{\text{T}}+ F_{\text{H}}}{2}.
%\]
%Similarly,
%\[
%F_{\text{H}} = 1 + \frac{F_{\text{T}}+ 0}{2}.
%\]
%Solving for $F_{\text{T}}$ yields $F=6$.

}

\problempart Suppose we flip a fair coin until a head followed by a tail come
up.  What is the expected number, $G$, of flips we perform?

\solution{
Clearly $G=G_{\text{T}}$.  As above
\begin{eqnarray*}
G_{\text{T}} &=& 1 + \frac{G_{\text{T}}+ G_{\text{H}}}{2},\\
G_{\text{H}} &=& 1 + \frac{0+G_{\text{H}}}{2}.
\end{eqnarray*}
So $G=G_{\text{T}}=4$.
}

\problempart Suppose we now play a game: flip a fair coin until either HH or HT
first occurs.  You win if HT comes up first, lose if HH comes up first.
What odds should you offer an opponent to make this a fair game?

\solution{
Even money odds.  Although the expected time for HH is larger
than for HT, the game of waiting for one or the other to come up first is
fair!

To prove this, let W be the probability of winning.  Clearly,
\[
W = (1/2)\prob{W \mid \text{first roll is }T} + (1/2)\prob{W \mid \text{first
roll is }
H} = (1/2)W + (1/2)(1/2)
\]
so $W = 1/2$.

By the way, an even more dramatic contrast comes up if we consider longer
sequences, where the sequence with the longer waiting time may be
\emph{more} likely to appear first.  For example, the expected waiting
time for HHH is 14, while the expected waiting time for TTHH is 16, as can
be shown by reasoning about conditional expectations as in the previous
problem parts.  However, the probability that HHH appears before TTHH is
only 1/3, which can be shown by reasoning about conditional probabilities
as above (see also, \href
{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/miscellaneous/cp10F.pdf}
{Friday Week 10, Class Problem 3}).

This surprising result reflects the unexpected \texttt{:-)} technical
properties of expectation.  A simple intuitive explanation of this
phenomenon is that although one pattern may usually occur before a second
one, it may be that when the second pattern does appear earlier, the time
for the first pattern to appear later is very large, so that overall, the
expected time for the more likely first pattern is much larger.

A simpler, contrived example crystallizes this idea: consider an
experiment which begins by flipping a coin biased 3 to 1 in favor of
Tails.  If a Head comes up, then continue flipping a two-Headed coin
forever.  If a Tail comes up, then flip a two-Tailed coin once, and then
continue flipping a two-Headed coin forever.

So an occurrence of TT is 3 times as likely to appear before HH than
vice-versa, because TT appears before HH precisely when the first flip
comes up Tails.  But HH is guaranteed to appear in at most 4 flips in
either case, so its expectation is obviously at most 4 (actually it's
$(1/4)2 + (3/4)4 = 3.5$).}  On the other hand, when the first flip comes
up Heads, TT \emph{never} appears.  Since this happens with probability
1/4, the expected time for TT to appear is infinite!
\end{problemparts}

\end{problem}


\iffalse
% \problemdata                                                             
%         {gambling game} % latex-friendly label for the prob.
%         {expected values} % The topic(s) of the problem content.  
%         {Peter Winkler Seminar 2001} % Source (if known)         
%         {S01 Tutorial 13, 1} % Usage (list ones you are aware of). 
%         {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Consider the following game.  I start with $X$ dollars, you start with $Y$
dollars.  In a round, we each wager any amount of dollars up to what we have.
Then we flip a biased coin.  If I wager $x$ and you wager $y$, then I win with
probability $\frac{x}{x+y}$, while you win with probability
$\frac{y}{x+y}$. Whoever wins a coin flip gets all the money wagered on that
flip.  The game ends when someone goes broke.  Calculate the probability that I
win.

(Hint: This question does not specify a particular wagering strategy.)

\solution{
In a particular round, I win $y$ dollars with probability $\frac{x}{x+y}$ and
lose  $x$ dollars with probability $\frac{y}{x+y}$.  Therefore, my expected 
return on a particular wager is 
\[
\Ex[\mathrm{Return\ on\ 1\ wager}] =\Pr[\mathrm{win}] \cdot \mathrm{profit} -
\Pr[\mathrm{loss}] \cdot \mathrm{loss} =
\frac{x}{x+y}\cdot y - \frac{y}{x+y}\cdot x = 0
\]
Therefore, after each wager, I expect to have the same number of
dollars as I had before it.  Intuitively, if our expected profit is
invariantly 0 for every wager, we can use linearity of expectations to
conclude that the expected profit for the whole game is 0.

However, a game will continue for a random number of rounds before concluding.
So formalizing this intuition becomes slightly more complicated.
Let $Q$ be a random variable for the length of the game in rounds.
($Q$ will depend on a number of things including the players'
strategies and the results of each wager until the game ends.)

Let $X_i$, be a random variable for the number of dollars I have before
round $i$.  Let $p_i$ be the profit for round $i$. So
$X_i = X + p_1 + p_2 + \ldots p_{i-1}$
and my profit at the end of the game is
\[
X_{Q+1} - X = \sum_{i=1}^Q p_i
\]
By the law of total probability, my expected profit is 
\[
\Ex[X_{Q+1}] - X = \Ex \left [\sum_{i=1}^Q p_i \right ] = \sum_{q=1}^\infty \left(\Ex \left[
\sum_{i=1}^q p_i \biggm| \{Q=q\} \right ] \Pr[Q=q] \right)
\]
But we just proved above that
\[ \Ex \left[ \sum_{i=1}^q p_i \biggm| \{Q=q\} \right ] = 0 \]
(this follows since we proved above that the expected return on any
wager is 0 given that the game is still running before the wager is
made).  So the whole sum and, thus, my total expected profit, is equal
to~0.

We can now use the expected return on the game to calculate the probability of
winning. If I win the game, I win $Y$ dollars.  If I lose the game, I lose $X$
dollars.  So, by the definition of expectation
\[\Ex[\mathrm{Return\ on\ game}] = \Pr[\mathrm{win}] \cdot
\mathrm{profit} - \Pr[\mathrm{loss}] \cdot \mathrm{loss} = 
 p \cdot Y - (1-p) \cdot X = 0.
\]
Solving for $p$ yields my probability of winning: $p = \frac{X}{X+Y}$.
}
\end{problem}
\fi

                                                                  
\end{document}

