In a permutation a1.....an of n distinct integers, an inversion is a pair (ai,…
2003
In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1.....n ?
- A.
n(n - 1)/2
- B.
n(n - 1)/4
- C.
n(n + 1)/4
- D.
2n[log2 n]
Attempted by 1 students.
Show answer & explanation
Correct answer: B
Solution (indicator variable method):
For each pair of positions i and j with i < j, define an indicator variable X_{ij} that equals 1 if the pair forms an inversion (the element in position i is greater than the element in position j) and 0 otherwise.
Because all permutations are equally likely, for any fixed pair i < j the two relative orders are equally likely, so P(X_{ij} = 1) = 1/2 and therefore E[X_{ij}] = 1/2.
There are exactly n(n - 1)/2 distinct pairs i < j. The total number of inversions is the sum of the X_{ij}, so by linearity of expectation the expected total is
E[number of inversions] = (number of pairs) × E[X_{ij}] = [n(n - 1)/2] × 1/2 = n(n - 1)/4.
Quick check: for n = 3 there are 6 permutations with inversion counts 0,1,1,2,2,3; the average is (0+1+1+2+2+3)/6 = 9/6 = 3/2, which matches n(n - 1)/4 = 3·2/4 = 1.5.