UEFA CL draw probabilities – 2018 edition

Written on 19 December 2018, 06:44pm

Tagged with: , , , ,

This is a follow up to https://colorblindprogramming.com/round-probabilities-before. Last year I stopped after discovering that the only correct way to calculate the odds is to look at the probability trees. This year I took this one step forward and created a script that would calculate the correct probabilities. I intend to reuse this script for the future draws, and a year it’s a long time for my memory so I am adding some notes here.

The incorrect approach: the big-bowl

The first approach last year was to calculate all the possible pairs, eliminate the invalid ones and then calculate the associated percentages for each pair. In hindsight, this approach was obviously wrong, because it doesn’t replicate the actual draw. This approach would only be accurate if the draw consisted of a single draw – from a very big bowl of all the valid options. This is obviously not how the actual draw works, so even if the final numbers were pretty close to the correct ones, it was not the correct approach.  

The correct approach, using conditional probabilities

The correct way to look at this is by understanding that we are talking about dependent events. Each draw depends on the actual result of the previous draw. It’s identical to this process, beautifully explained on MathIsFun.com:

So how do we actually do it?

There are two approaches:
The first one is a bit more complicated and implies creating the tree above for the 16 teams and 16 steps (each team pick is a step). It has the advantage of producing accurate results, but it’s a bit more difficult to implement.
The second one consists of simulating the draw process and repeating it a lot of times. I found this approach easier, here is the pseudo-code of the draw process:

  1. for each unseeded team
  2. if there is a mandatory draw (starting from the 5th unseeded team)
    1. then automatically create the pair and add it to the draw
  3. otherwise, pick a random unseeded team
    1. get the list of available seeded teams
    2. randomly pick a seeded team from the list above
    3. add pair to the draw
  4. end

Repeating this process a few millions of times would lead to millions of possible draws, and based on that we can calculate the percentages.

But there are 2 catches:
1. Checking both sides of the draw. Have a look at the step 2 above, checking if there is a mandatory draw: let’s say you are left with 4 unseeded teams and 4 seeded teams. It’s not enough to look at the unseeded teams options, you also need to look the other way around. Example:
Unseeded teams: Liverpool, United, Shalke, Lyon
Seeded teams: PSG, City, Real, Barcelona
Liverpool has 2 options, United 3, Shalke 4 and Lyon 2. But if you randomly pick Shalke and you pair it with any of PSG, Real or Barcelona, then you leave an impossible draw for City (which cannot be drawn against any of the 3 English teams left). So the solution is to count the number of options for both unseeded and seeded teams. If there is a single option, pick it.

2. Go back if needed. Even with the above safety mechanism in place things can still go wrong. Example:
Unseeded teams: Roma, Liverpool, Shalke, Lyon
Seeded teams: Porto, Barcelona, PSG, City
Options for the unseeded teams: Rome -4, Liverpool -2, Shalke -4, Lyon -2.
Options for the seeded teams: Porto -3, Barcelona -4, PSG -2, City -2. 
The safety mechanism above (counting the number of options for both seeded and unseeded teams) tells us that everything is fine. So we go ahead and pair Rome with Porto. We are now left with:
Unseeded: Liverpool -1, Shalke -3, Lyon -1
Seeded: Barcelona -3, PSG -1, City -1.
The problem is that both PSG and City have an option, and that option is Shalke. So this leads to an impossible draw, so the solution in this case is to go back one step and pick another draw instead of Roma v Porto.
According to my calculations this could happen in about 0.4% of cases, and I am really curious how UEFA would handle it if it happened on stage. In the scenario above, if Roma was selected as unseeded team, I expect that the computer will only allow PSG and City to be one of the seeded teams, but I am really curious to hear the hosts explanation about this constraint (since both Porto and Barcelona are, at first sight, also valid options for Roma) 🙂

Using the algorithm above, I ran the simulation 2 million times. These are the results:

Checking the results

The nice thing about being both a geek and a football lover is that you get to know smart persons at the intersection of science and football. Two of them are Julien Guyon and Emmanuel Syrmoudis. They also spent time thinking about this topic. Julien came up with a great explanation of the draw process and probabilities, while Emmanuel went one step forward and actually created an interactive draw simulator.  

My results come pretty close to theirs, so I’m quite confident that my method is decent enough. I plan to reuse it again next year and, perhaps, also try to create the actual probability tree to get the exact percentages.  

Tesla road trip through Europe

Written on 1 September 2018, 11:53am

Tagged with: ,

Here are a few notes on the road trip I recently took through the Central Europe with my Tesla Model S 75D.

The route along with the superchargers data points
The trip segments
  • The Tesla superchargers infrastructure is ready to support road trips through the Central Europe (Belgium, Netherlands, Germany, Austria, Italy, Switzerland, France, Luxembourg)
  • Free supercharging is awesome 🙂
  • In order to avoid waiting times to pay road tolls, I highly recommend alternatives like this 
  • Trip segments longer than 2-2.5 hours are really difficult to manage for families with kids, which makes it perfect for stopping and re-charging
  • The Supercharger locations are really nice. Ranging from nice hotels to commercial centers, they completely change your long trip experience (no more crowded and dirty toilets in gas stations)
  • Supercharging is really fast. It happened several times that the car had to charge more than needed to continue because we were not ready
  • The Superchargers are conveniently located along the highway. 5 to 10 minutes is the average detour
  • The Superchargers are not clearly marked, and that’s one of the few annoying bits. The Tesla navigation brings you in front of the hotel / commercial center, but I only saw indication panels on few locations. Maybe it’s on purpose to avoid non-EV to occupy the space?
  • Still on negative points: the Arlon supercharger was marked as ‘Reduced capacity’, making it unclear if I should use it or not. Fortunately a phone call to the hotel cleared things up
  • Charging your car on top of the Grossglocker road is awesome
  • Seeing your range increase when you come down the mountain is  satisfying
  • The luggage load does not have a big impact on the autonomy. But going 170km/h in Germany certainly does 😀
Charging at 2369 meters, on top of the road offering a view to the spectacular Grossglockner peak
After coming down the mountain – negative consumption for 42 kilometers!

Overall, I was really impressed with the trip. I had to spend more time planning, but I enjoyed a completely changed road trip experience, with smooth and silent driving and no range anxiety.
The future of transportation is here, and I am happy to be part of it!

Tuscany sunset

PS: In case you plan to order a Tesla, you can use my referral code … 

8 December 2018: scratch that. I cannot recommend buying a Tesla. Not for the moment at least.

Unexpected ways the technology gets intrusive

Written on 10 January 2017, 09:27pm

Tagged with: , , , , ,

Just a quick, did-you-know type of post written because the technology below is way to cool not to share 🙂

1. Did you know that the wi-fi routers can be used to identify faces, recognize keys that you type or read lips?

Researchers from the Northwestern Polytechnical University in China used WiFi signals to identify people. This identification was made based on the shape of people that was read as radio waves bounced back and forth, as well as by the specific way in which people moved. The success ratio was 88.9% to 94.5% in a domestic environment. One potential application is that of having a super custom-made smart home which adjusts lighting, temperature and even music based on the person(s) gait walking through the room. Or you can just use it to spy.
[…]
A system developed at the University of Berkeley uses distortions and reflections in Wi-Fi signals made by moving mouths to essentially lip-read. This setup was used to tell which words a single person was speaking with 91 percent accuracy. The accuracy was 74 percent when three people were speaking at the same time.
http://www.zmescience.com/science/news-science/wifi-routers-for-spying/

(more…)