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



          


\begin{problem}




% modifed 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 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_i$ be random variable whose value is 1 if student i has higher rank
in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$ for
6.042 than the probability that student $i$ has higher rank on 6.042,
given that the student has rank $r$ in 6.042, is $(r-1)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the
probability that student $i$ has higher rank in 6.042 is
\[
\sum_{1\leq r \leq n}  \frac{1}{n} \frac{r-1}{n} = \frac{n-1}{2n}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x} = \expect{x_1}+\expect{x_2}+...+\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_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.  If student $i$ has rank of $r$
$(r>k)$ for 6.042 than the probability that student $i$ has at least $k$
higher rank in 6.042 given student ranked $r$ in 6.042 is $(r-k)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the probability
that student $i$ has at least $k$ higher rank in 6.042 is
\[
\sum_{k+1\leq r\leq n} \frac{1}{n} \frac{r-k}{n} = \frac{(n-k)(n-k+1)}{2n^2}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x}=\expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{(n-k)(n-k+1)}{2n}.
\]

}

\eparts
\end{problem}
