One Draw Can Change Everything – UEFA CL Round of 16 Drawings

Today the UEFA Champions League Round of 16 matchups were drawn. The rather simple rules for drawing the matchups lead to quite interesting results. There are three rules (s. http://en.wikipedia.org/wiki/2013%E2%80%9314_UEFA_Champions_League):

1. The group winners will be drawn against the group runners-up, with the group winners hosting the second leg.
2. Teams from the same group cannot be drawn against each other.
3. Teams from the same association cannot be drawn against each other.

group winners: Manchester United (MAN), Real Madrid (REA), Paris St. Germain (PSG), FC Bayern (BAY), FC Chelsea (CHL), Borussia Dortmund (BVB), Atletico Madrid (ATL) and FC Barcelona (BAR). (from group A to H)

group runners-up: Bayer 04 Leverkusen (B04), Galatasaray (GAL), Olympiacos (PIR), Manchester City (MAC), Schalke 04 (S04), FC Arsenal (FCA), Zenit St. Petersburg (ZEN), AC Milan (ACM). (from group A to H)

The question that arises here is: how do these restrictions influence the “random” drawing. To answer that question i wrote a function in R that simulates 1 million random draws to make sure that in the end i get all possible drawings. (Ex ante i did not know how many simulations had to be done. Now i know far less than 1 million are actually needed.) This took about 40 minutes. In the end one gets the result that only 3497 different matchups are actually possible:

One can clearly see that matchups of Bundesliga vs. Barclays Premier League are much more likely than any other matches. That is because there are less restrictions for the other matches if one of these matches drawn (restriction 2 and 3). The probability for FC Bayern vs. FC Arsenal (30.8%) is nearly twice as high as any other single matchup. The same is true for the other possible Bundesliga vs. Barclays Premier League matchups. To get a little more behind the logic of these probabilities we can now have a closer look at the conditional probabilies given the first draw, second draw etc. In the first draw of todays lottery the matchup FC Barcelona vs. Manchester City has been drawn by Luis Figo. The probabilities changed in the following way:

FC Bayern vs. FC Arsenal got even more likely. After the first matchup is now fixed there are only 605 possibilities left. After the next draw: Manchester United vs. Olypiakos F.C. the probabilities changed to the following:

At this stage there are no restrictions in the drawing process except the three restrictions from above (this will change in the next draws). The thrid matchup drawn is Atletico Madrid vs. AC Milan.

Now only only 11(!) draws are possible. Real Madrid vs. Schalke 04 gets a probaility of more than 50%, so does FC Bayern vs. FC Arsenal. Borussia Dortmund basically has a 50:50 chance of getting Galatasary. In the next draw the less likely Paris Saint-Germain vs. Bayer 04 Leverkusen is drawn (18.2%). This leads to the following conditional probabilities:

Leaving us with just 2(!) (remember next is the fifth draw from eight) possibilities. FC Bayern vs. Arsenal is fixed now without even being drawn, so is Real Madrid vs. Schalke 04! Galatasary is now selected to get ist oppenent. Why cant its opponent be FC Bayern? Lets check two examples:

1. GAL-BAY gets drawn here, in the next draw ZEN-BVB is selected. But this would lead to a dead end. Since then there are only two matches left to be decided, either FCA-CHL and S04-REA, which is not possible because FCA and CHL are from the same association (restriction 3), or FCA-REA and S04-CHL, which is also not possible because S04 and CHL were from the same group (restriction 2).
2. GAL-BAY gets drawn here, in the next draw FCA-REA is selected. This would also lead to a dead end since there is no possible opponent left for S04. CHL is not possible (from same group, restriction 2). BAY and BVB are not possible (same association, restriction 3)

If one checked all other possibilities, all but two final drawings would lead to a dead end. That is the reason why in the drawings the above two teams were not allowed to be selected by Luis Figo (green dot = allowed, grey dot = not allowed):(Source: http://www.youtube.com/watch?v=moDwj6pHSPg at 5:35) The chance of Galatasaray getting Chealsea or Borussia Dortmund is now 50:50. Thats the only decision left here. Chelsea is being selected. From now on everything else is clear.

Now Gianni Infantino selected Schalke 04 to get its opponent. The opponent is clear now. It cant be Borussia Dortmund because they are both from the Bundesliga (restriction 3). It cant get FC Bayern for the same reason. So now we are only left with FC Bayern, Borussia Dortmund, Zenit St. Petersburg and FC Arsenal. FC Bayern cannot face Borussia Dortmund, since they both are group winners (and from the same association, restrictions 1 and 3). FC Bayern cannot face Zenit St. Pertersburg because then Borussia Dortmund would have to face Arsenal FC, which is not possible due to restriction 2 (from same group). So now we are done 😉 The last draws are just pro froma. Nothing changes, as one can see here (just for completeness):

Schalke 04 vs. Real Madrid has been selected before. Now Zenit St. Petersburg is drawn. We already know its opponent: Borussia Dortmund.

Now we are only left with FC Bayern and FC Arsenal. Probability is of course 100%:

So this is the final result.

So in the end these rather simple rules reduced the number of possible matchups quite substantially. After only three draws we were left with just 11 possibilities, after four draws only two and after five draws everything was clear.

In the end it is rather hard to get all the complete logic behind all the probabilities, since there are many possibilities, and also a lot unsymmetrical restrictions. The only easy rule of thumb probably is, that if two teams that have more than restriction 1 and 2 get drawn against each other this leads to less restrictions for the other matches, allowing more possibilities in the end, which vice versa makes this drawing (ex ante) more likely. A draw of MAC-BVB in the first draw for example leads to 1077 matchups, whereas the draw of MAC-BAR led to only 605 possible matchups. Or in the other way round as seen in draw 4 and 5: If none of these likely draws (picture one) happen at the beginning, they must happen in the end (FCA-BAY).

Code for the simulations and plots can be found here: http://pastebin.com/wngGBkTZ. R 3.0.2, with packages: data.table, plyr and ggplot2 was used. A .csv file with all possible drawings can be found here: http://pastebin.com/DGVcj0E2.