Shuffled numbers: how many pairs are out of order?

Question

The numbers 1 through 8 are shuffled into a completely random order. A pair of numbers is "out of order" if the larger number appears before the smaller one.

On average, how many out-of-order pairs are there?

Accepted Answer

Put one indicator on each pair of numbers and add. There are \binom{8}{2} = 28 pairs. Fix one pair. In a random shuffle, the larger number is equally likely to appear before or after the smaller one, so the pair is out of order with probability 	frac12: P(	ext{a given pair is out of order}) = \frac12. Summing over all 28 pairs, E[	ext{out-of-order pairs}] = \binom{8}{2} 	imes \frac12 = 28 	imes \frac12 = 14. This is exactly the expected number of swaps a sorting algorithm like bubble sort would need to fix the shuffle. Takeaway. Each of the \binom{n}{2} pairs is out of order with probabi…

Shuffled numbers: how many pairs are out of order?

Your answer

Discussion

Learn the concepts

Related questions