A new article regarding the 2014/15 drawings will be available shortly is now available (see below). For now you can simulate the drawing process with my newly created Shiny App:
Champions League Drawings – Shiny App
or have a look at Dr. Martin Theus blog. The underlying R code and all the data will also be made available shortly can now be found here: code and all possible drawings as csv.
Note: The App is currently running on a low performance server (Amazon EC2 Micro Instance). Initial loading may take a bit.
The draw and its rules:
The are three rules for the the round of 16 drawing (see Wikipedia):
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 (league) cannot be drawn against each other.
Now these rules look fairly simple, and reasonable, but through the asymmetric nature of rule 3) this induces some interesting implications. This restriction only affects the leagues with more than one top team, like Barclay’s Premier League and the German Bundesliga. This is the reason why English vs. German matches are over-proportionally likely. For example FC Bayern München vs. FC Arsenal has a probability of 24% in this years draw, last year this was even higher at 30.8% (this was drawn in the end), if restriction 3) would not exist this probability would only be 14.3% (1 out of 7). This high likelihood is also true for the other German and English teams, e.g. FC Chelsea vs. Bayer 04 Leverkusen happens with a chance of 28.7% and thus is the single most likely match we will see.
The intuition behind this is somewhat hard to get, but i will try an explanation: The likelihood of each match is calculated as the fraction of draws in which this match occurs divided by the the number of all possible draws. If you account for all the restrictions you end up with just 4516 possible draws (see calculation below). Now consider two scenarios:
a) FC Bayern München is drawn against FC Arsenal (occurs in 1086 draws, i.e. 24%)
b) FC Bayern München is drawn against any single other possible opponent (occurs in 824 draws, i.e. 18.2% or 958 draws, i.e. 21.1% depending on the opponent)
So why is scenario a) much more likely? The main reason is that there must be a solution in the end, this means that every group-winner must have exactly on allowed opponent. Practically this is a fourth restriction. You will notice this in the live draw on Monday: Sometimes some matches will not be allowed in advance since this would lead to no solution. If FC Bayern München versus FC Arsenal is not drawn (scenario b)) there are fewer possibilities in the end for a solution, since the restriction has to be maintained for the later drawn matches.
This does not only hold for German and English teams, but for all teams with at least on group-winner and group runner-up. This time it is also France. This becomes pretty obvious once you play around a bit with the app, since the draw can be practically over after just four draws if only the unlikely matches are selected at first (there are actually several possibilities for this scenario), since then there remains just one solution. Consider this example where always the matches with the least conditionally probability are selected with ties broken at random: Atletico Madrid vs. FC Basel – Real Madrid vs. Juventus Turin – FC Barcelona vs. Shaktar Donetsk. For the moment we stop here. Now only 6 draws are possible (remember this is the just the third draw out of eight). The conditional probabilities look like this:
So now we have seven possibilities to end the draw with the next draw (all that occur with likelihood of 16.7%, i.e. in 1 out of 6). Of course these are only matches where we do not solve any restriction. If we would chose FC Bayern vs. FC Arsenal here, we could go on with a fifth draw. We proceed and choose AS Monaco vs. Manchester City. Voila we are done! This is the only possible solution in this case:
This is why:
Borussia Dortmund has to play against Paris St. Germain, (FC Schalke 04 and Bayer Leverkusen are not possible because of restriction 3), FC Arsenal is not possible because of restriction 2).
FC Bayern München has to face FC Arsenal since it also can’t play against FC Schalke 04 and Bayer Leverkusen, and we already know that Borussia Dortmund must face Paris St. Germain.
FC Chelsea has to face Bayer 04 Leverkusen, since FC Schalke 04 is not possible (restriction 2), same group) and all other possible opponents are already drawn.
FC Porto vs. FC Schalke 04 is clear now, since this is the only match that is left.
(Note that if we had not selected AS Monaco vs. Manchester City, and instead chosen FC Bayern München vs. FC Arsenal here, we could still get the same result, but would not be limited to this result.)
I hope this post clarifies at least a bit that the drawing mechanism induces a lot of bias though all its restrictions. Germany vs. England might stay the most likely matches in the near future for the round of 16. The draw might be over after just four draws, but it does not depend on chronologically order.
I encourage you to use the Shiny App to explore the drawing!.
How the calculation is implemented:
In principle all possible and allowed drawings are calculated. This is the fasted way i found:
1) calculate all possible group winner vs. group runner-up matches without respecting the latter two restrictions. This leads to 8×8 = 64 matches. Then employ all restrictions, i.e. remove all matches where two teams from the same group are drawn against each other and also remove all matches where two teams from the same league (association) are drawn against each other. This leads to 49 (notice there are 15 probabilities of zero in the plot) remaining possible matches.
2) calculate all possible draws (tuples of eight matches). At first ignore the restriction that one team can only be drawn once. Proceed as follows: Select one group winner and all possible matches that are possible for this team from the table created in step 1.
Example: There are 7 possible opponents for Atletico Madrid (all except Juventus Turin, since this team is from the same group). This leads to 7 possible matches in step 1. For Borussia Dortmund there are 5 possible opponents (FC Schalke 04 and Bayer Leverkusen are not possible because they are also from the German Bundesliga, FC Arsenal is not possible since this team is from the same group). This leads to 5 possible matches in step 1. Proceed like this for all group winners and calculate the cross product of all matches.
You end up with 7 (Atletico Madrid) x 7 (Real Madrid) x 6 ( AS Monaco) x 5 (Borissia Dortmund) x 5 (FC Bayern München) x 7 (FC Barcelona) x 5 (FC Chelsea) x 7 (FC Porto) = 1,800,750 Possibilities (a 1,800,750 x 16 (number of teams) matrix).
3) Remove all matches where one group second is selected more than once. This leads to 4516 possible draws.
4) To calculate the probabilities simply count all draws where the desired match occurs and divide by all possible draws.
It takes about 2 seconds to compute on my standard desktop machine and uses 300MB of memory. It is also possible to simulate the draw a drawing, but this is way slower (see last years post for (messy) code). It of course leads to the same result.
The App takes the pre-calculated table of drawings and just selects parts of it.
Schw4rzR0tG0ld 