Sunday 7 March 2010

Info content of the FA cup draw

For the semi-final draw they dramatically select each of the four balls for the four clubs, but in fact there's only log2(3) = 1.58 bits of information, and it could be done with a single draw. Since both matches play at Wembley, there's no 'home' or 'away', so there's only three possibilities:

A - B and C - D
A - C and B - D
A - D and B - C

During the draw:

- first team out of the box: gives no information
- second team out, select one from the three remaining, and gives all of the information
- third and fourth teams out, tell us nothing, because we already knew they were to play each other

Unless I suppose it makes a difference which match is played first, in which case there are six possibilities, adding one bit of information, 2.58 bits. (log2(6) = 2.58)

A - B then C - D
A - C then B - D
A - D then B - C
C - D then A - B
B - D then A - C
B - C then A - D

- first team out. Tells us that team plays in the first match. That is a selection from two equal possibilities (that team could have played in the first or second match), so contributes 1 bit of information
- second team out. This is a selection of one from three (the three teams still in the hat) so is 1.58 bits of information. This is now all the information, because we know the other two teams play each other in the second match. Information adds, so total information is 2.58 bits.
- third and fourth teams out contribute no information.

No comments: