18.5. Linearity of Expectation 785
then assign students grades based on their rank in the permutation—just as many
students have suspected:-). Assume all permutations are equally likely and that
the ranking in each class is independent of the other.
(a)What is the expected number of students that have a higher rank in Math for
CS than in Signal Processing?
Hint:If a student ranksrth in Math for CS, then the probability that this rank is
higher than their rank in Signal Processing is.r 1/=n. LetXibe the indicator
variable for studentihaving higher rank in Math for CS than Signal Processing.
(b)What is the expected number of students that have a ranking at leastkhigher
in Math for CS than in Signal Processing?
Problem 18.25.
Justify each line of the following proof that ifR 1 andR 2 areindependent, then
ExŒR 1 R 2 çDExŒR 1 çExŒR 2 ç:Proof.
ExŒR 1 R 2 ç
DX
r 2 range.R 1 R 2 /rPrŒR 1 R 2 DrçD
X
ri 2 range.Ri/r 1 r 2 PrŒR 1 Dr 1 and R 2 Dr 2 çD
X
r 12 range.R 1 /X
r 22 range.R 2 /r 1 r 2 PrŒR 1 Dr 1 andR 2 Dr 2 çD
X
r 12 range.R 1 /X
r 22 range.R 2 /r 1 r 2 PrŒR 1 Dr 1 çPrŒR 2 Dr 2 çD
X
r 12 range.R 1 /0
@r 1 PrŒR 1 Dr 1 çX
r 22 range.R 2 /r 2 PrŒR 2 Dr 2 ç1
A
D
X
r 12 range.R 1 /r 1 PrŒR 1 Dr 1 çExŒR 2 çDExŒR 2 çX
r 12 range.R 1 /r 1 PrŒR 1 Dr 1 çDExŒR 2 çExŒR 1 ç: