Ten songs on shuffle: how many pairs are out of order?

Question

An album has 10 songs in a fixed intended order. You put the 10 songs on shuffle, giving a completely random play order. A pair of songs is "out of order" if the shuffle plays them in the opposite order to the album.

On average, how many out-of-order pairs does the shuffle produce?

Accepted Answer

Put one indicator on each pair of songs and add. There are \binom{10}{2} = 45 pairs. Fix one pair. In a random shuffle the two songs are equally likely to play in either relative order, so the pair is out of order with probability 	frac12: P(	ext{a given pair is out of order}) = \frac12. Summing over all 45 pairs, E[	ext{out-of-order pairs}] = \binom{10}{2} 	imes \frac12 = 45 	imes \frac12 = \frac{45}{2} = 22.5. Takeaway. A random shuffle inverts each of the \binom{n}{2} pairs with probability 	frac12, so the expected number of out-of-order pairs is 	frac12\binom{n}{2}. For 10 songs th…

Ten songs on shuffle: how many pairs are out of order?

Your answer

Discussion

Learn the concepts

Related questions