How many pairs land out of order in a random ranking?

Question

Six items have a true best-to-worst order. A reviewer, knowing nothing, ranks them in a completely random order. An "inversion" is any pair of items that the reviewer places in the opposite order to the truth.

On average, how many inversions does the random ranking contain?

Accepted Answer

Do not try to count inversions by how tangled the ranking is. Put one indicator on each pair of items and add. There are \binom{6}{2} = 15 pairs of items. Fix one pair. In a random ranking, the two items are equally likely to appear in either order, so the pair is inverted with probability 	frac12: P(	ext{a given pair is inverted}) = \frac12. Let X{ij} = 1 if pair \{i,j\} is inverted; E[X{ij}] = 	frac12. Summing over all 15 pairs, E[	ext{inversions}] = \binom{6}{2} 	imes \frac12 = 15 	imes \frac12 = \frac{15}{2} = 7.5. Takeaway. Count "how many pairs are out of order" with one indicator…

How many pairs land out of order in a random ranking?

Your answer

Discussion

Learn the concepts

Related questions