4

A group of n people all have distinct heights. They are waiting in a straight line at the bank (one person in front of the other), with all orderings of the people equally likely. A person can see ahead to the front of the line if they are taller than everyone in front of them.

  • (a) What is the probability that the ith person in line can see to the front of the line (where the first person is at the front of the line, the second person is behind the first, etc.)?
  • (b) What is the expected number of people in line that can see to the front of the line? (Hint: Linearity of expectation.)

There are n! ways to arrange those people in line. For the first person to see in line: nC1, then for the ith person it is going to be nCi?

I am not sure how to approach (b)? Any hint or advice is helpful!

David G. Stork
  • 29,774
Dee Chantelle
  • 145
  • 2
  • 10

1 Answers1

2

Define indicator random variables $Y_1,Y_2,\dots, Y_n$ as follows. Let $Y_i=1$ if the $i$-th person can see all the way to the front of the line, and let $Y_i=0$ otherwise. Then $W=Y_1+\cdots+Y_n$ is the number of people who can see all the way to the front of the line. We want $E(Y_1+\cdots+Y_n)$, which by the linearity of expectation is $E(Y_1)+\cdots+E(Y_n)$. Note that the $Y_i$ are not independent. But linearity of expectation holds in all cases.

We have $\Pr(Y_i=1)=\frac{1}{i}$. For among the first $i$ people, the one in position $k$ is just as likely to be the tallest in the group as any other. So $$E(W)=1+\frac{1}{2}+\cdots +\frac{1}{n},$$ the $n$-th harmonic number.

André Nicolas
  • 507,029
  • Why is P(Yi=1)=1/i, and not 1/i! ? – Dee Chantelle Jul 20 '15 at 03:04
  • Your suggested $1/i!$ is the probability the first $i$ people are lined up exactly in order of increasing height. But for the $i$-th person to see all the way to the front, it doesn't matter whether the people in front of her can see, all that matters is that she is the tallest. And as I wrote in the answer, if you concentrate on the first $i$ people, the tallest is just as likely to be first as second as third and so on. Just like if you deal $5$ cards in a row, and you get a royal flush in spades, the Queen of spades is just as likely to be fist dealt, second dealt, and so on. – André Nicolas Jul 20 '15 at 03:15
  • Thank you for clarification. So essentially the answer to (a) is P( ith person can see to the front of the line) = 1/i ? – Dee Chantelle Jul 20 '15 at 03:26
  • Yes, I did not do (a) separately since that was dealt with in solving (b). – André Nicolas Jul 20 '15 at 03:28
  • You can also get the $\frac{1}{i}$ the slow way. The probability the second person can see is clearly $1/2$, For the third to see, the orders of height have to be $1,2,3$ or $2,1,3$, two possibilities out of $3!$, so $\frac{1}{3}$. For the fourth to see, any order for the first three is fine, as long as $4$ is tallest, probability $3!/4!=1/4$. And so on. I would rather do it the fast way. – André Nicolas Jul 20 '15 at 03:33
  • You are welcome. – André Nicolas Jul 20 '15 at 03:42