EPL Predictions and Derangements

I was reading this article the other day about making predictions about the final position of league tables. Guardian said that they managed to get 4 teams in the right position. People didn't think that that was really a big deal, and they were asking, if people were to make predictions about the positions of teams at random, what is the average number of teams that people would predict in the correct position?

How would you go about doing this? First, we assume that all permutations are equally possible? One way is to partition the set of 20! permutations on the 20 element set. There are permutations which keep i number of elements in the right place, but scramble the (20-i) other elements such that none of those (20-i) elements are in the correct order. We say that this is a derangement. The number of derangements is fortunately easy to calculate: we will just use the approximation that the number of derangements on set of n elements is

Lets call the set of permutations which keep i elements in place but scramble the other (20-i) as P_i. Note that the various P_i are non-overlapping, and they sum up to 1. Therefore the P_i are a partition on the n! permutations. The expected value of r, the number of correct guesses, is

What is the size of P_i? There are i number of elements preserving their order. So there is a 20 choose i number of ways of picking the i elements. The rest of the elements have to be shuffled around in a derangement, so that no other elements preserve their order. From the earlier given formula for the number of derangements,


So we have

This works out to approximately 1. To see why, when you expand 20 choose i and expand, you get







And by the time you get to 20, all the other terms in that expansion are really small. So in the end, on average a randomly chosen prediction will have 1 correct guess. After doing my calculations on the spreadsheet, I find that there is a 99.6% chance that a random guess will get 4 predictions right.

Obviously the Guardian was working on a search space which was much smaller than 20! : People knew the rough strengths and weaknesses of all the teams. But the commentators seemed to think that on average a guess picked at random will have around 4 teams in the right position, and that estimation is way way off.