Random queue: how many taller-behind-shorter pairs?

Question

Five people, all of different heights, line up in a completely random order from front to back. Consider every pair of people: the pair is "misordered" if the taller person is standing somewhere behind the shorter one.

On average, how many misordered pairs are there in the line of 5?

Accepted Answer

Put one indicator on each pair of people and add. There are \binom{5}{2} = 10 pairs. Fix one pair. In a random line the taller person is equally likely to stand ahead of or behind the shorter one, so the pair is misordered with probability 	frac12: P(	ext{a given pair is misordered}) = \frac12. Summing over all 10 pairs, E[	ext{misordered pairs}] = \binom{5}{2} 	imes \frac12 = 10 	imes \frac12 = 5. Takeaway. "Taller behind shorter" is just an inversion relative to height order: each pair qualifies with probability 	frac12, so the expected count is 	frac12\binom{5}{2} = 5.

Random queue: how many taller-behind-shorter pairs?

Your answer

Discussion

Learn the concepts

Related questions