Solution
Expected Disorder
Show the problem again
The numbers 1, 2, ..., 10 are arranged in a uniformly random order. An inversion is a pair of numbers i < j such that j appears before i. What is the expected number of inversions? Give an exact value (a fraction or decimal).
Worked solution
The answer is 45/2 = 22.5. There are C(10,2) = 45 pairs of numbers. For any one pair, the two relative orders are equally likely by symmetry (swap the two values), so each pair is an inversion with probability 1/2. By linearity the expected number of inversions is 45/2. In general a random permutation of n items has n(n − 1)/4 inversions on average, which is also the average number of swaps bubble sort performs on random input.
Source: Standard exercise on inversions of permutations; no single originator. Statement written for AxiomIQ.