Borussia M’Gladbach, PSG’s most likely opponent in the round of 16

As every year, the draw for the knockout stages of the Champions League is shaking up the football world. The supporters wonder: against whom can my favorite team fall? With what probabilities? And, like every year, the table of these probabilities raises many questions: how is it that some opponents of PSG are more likely than others? Why do the odds vary so much? How are they calculated?

Group winners (written in column, from group A to group H) can only meet runners-up (written in line, in the same order). However, they cannot be drawn against the second in their group, so the diagonal is filled with zeros. In addition, two clubs from the same country cannot compete against each other: the zeros outside the diagonal correspond to this constraint.

How to calculate the probabilities for all the remaining boxes? Take the example of PSG, the only French club still in the running after the inglorious eliminations of OM and Stade Rennes. PSG can fall against seven teams: all second in the group, except Leipzig, which PSG faced in Group H. One would therefore think that PSG has a one in 7 chance (14.3%) of being drawn against each of the 7 possible opponents, for example Borussia Mönchengladbach.

However, if we follow this logic, the probability of PSG-M’Gladbach should also be worth 20%, seen from M’Gladbach, since the latter has only five possible opponents. Obviously, the probability of a PSG-M’Gladbach clash cannot be worth both 14.3% and 20%. In reality, both of these figures are wrong.

Algorithm of ” backtracking “

We could also be tempted to reason as follows: we list all the possible complete results of the draw, that is to say those which satisfy all the constraints (there are 3,305 this year), and we calculate the proportion of draws for which PSG meet M’Gladbach (there are exactly 624). We would then arrive at the probability 624/3 305 = 18.9%. But this figure is still not the right one! It would be correct if the Union of European Football Associations (UEFA) were to shoot one ball at random among 3,305, each ball representing a possible full draw.

To calculate the true odds, you have to look in detail at how UEFA proceeds in the draw. A second from the group is drawn, then an algorithm, called “backtracking”, provides the list of possible opponents. Be careful, it’s more complicated than it sounds, because you have to make sure that the draw does not end in a dead end!

Computer will list Real Madrid as the only possible opponent, to prevent the draw ending with a Real-Barcelona

For example, if at the end of the draw, Barcelona and Lazio are the two second in groups remaining to be drawn, if Bayern Munich or Real Madrid are the two group winners still available, and if Lazio is drawn in first, so although it can a priori play against Bayern and Real, the computer will list Real Madrid as the only possible opponent, in order to prevent the draw from ending with a Real-Barcelona, ​​a forbidden match since it opposes two Spanish teams.

For each second of the group drawn at random, once the list of possible opponents has been drawn up, one of these opponents is drawn at random, uniformly. The procedure is repeated until all the matches have been decided. Thus, we avoid having to shoot a ball among 3,305!

From single to triple

But we also modify the probabilities of the draw; the 3,305 possible outcomes of the complete draw are in fact not equally likely! A simple and robust way to calculate the true odds is to simulate the draw a very large number of times, following UEFA’s procedure exactly, and to measure the frequency of matches.

Thus, the true probability of PSG-M’Gladbach (except for the sampling error, which is here very low since I have simulated a million prints) is 19.3%, i.e. 0.4 point higher than if all possible draws were equally likely. Porto are the least likely opponents of PSG (10.9%). The other opponents of PSG all have probabilities between 13% and 15%.

The odds vary from single to triple: 10.6% for Liverpool-Porto and Chelsea-Porto, against 30.4% for Real Madrid-Leipzig, the most likely match of the round of 16. Note that Bayern Munich are Barcelona’s most likely opponents, and vice versa (this match would be a hell of a poster!).

But this is not automatic: if M’Gladbach is PSG’s most likely opponent, M’Gladbach’s most likely opponent is Juventus. An extreme case is funny: While Porto are Real Madrid’s least likely opponent, Real are Porto’s most likely opponent. Ah! when football invites questions and ecstasies in front of the beauty of mathematics!