Expected number of out-of-order pairs

Question

You shuffle the numbers 1, 2, \dots, 100 into a uniformly random order. An inversion is a pair of positions i < j where the earlier position holds the larger number (they are out of sorted order). What is the expected number of inversions?

Accepted Answer

Do not try to count inversions permutation by permutation, use indicators and symmetry. For each unordered pair of values, define I = 1 if that pair appears out of order in the shuffle, else 0. Pick any two positions i < j. The two numbers landing there are equally likely to be in increasing or decreasing order (a random permutation is symmetric under swapping any two elements), so P(	ext{pair inverted}) = \frac{1}{2}. There are \binom{100}{2} = \frac{100 \cdot 99}{2} = 4950 pairs of positions. By linearity of expectation, E[	ext{inversions}] = \binom{100}{2}\cdot \frac{1}{2} = 4950 	imes …

Expected number of out-of-order pairs

Your answer

More Probability questions