## 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.

## Don’t buy a Tesla!

Written on 8 December 2018, 10:02pm

Tagged with: ,

TL;DR: The Model S is a great car and it offers you an extraordinary driving experience. Tesla customer service in Europe (more specifically in Belgium) is dreadful. Tesla doesn’t take security seriously and the Model S doesn’t seem to be very mature yet. I am still loving my Model S.

The statements above are not mutually exclusive. I’m loving it, but I don’t recommend buying one. Not for the moment at least. Customer care is part of the experience of owning a car, and Tesla does it badly here in Europe.

More details about my statements above:

• if you plan to call your customer service, expect waiting times in the region 1-2 hours. Yes, you read that right. Freaking hours, on the phone.
• if you get in touch with someone from support, there’s no guarantee that they will actually do something to help. Recent example: called to report a problem with the left mirror. After an hour of waiting, I am told to send an email to the technical team, and they will reach back to me. That was 2 weeks ago. Nobody called.
• the Model S is not mature enough. As a technical guy, I am used to technical issues. I see my Model S as a computer on wheels, so a few non-safety related bugs are tolerable. Resetting your car to fix the air conditioning flow or the internet connectivity is fine for me. But when these things start to happen on a regular basis, things can get annoying. Especially when Tesla doesn’t seem to care about it.
• the Model S’s produced before June 2018 have a known vulnerability that can lead to the car being stolen with minimal effort. The solution is simple: upgrade the chip on the key fobs and re-link them with your car. Tesla fixed this problem for the cars produced after June 2018, but is asking the existing owners (pre-June 2018) to pay for the fix from their own pocket (about 250 EUR). The alternative recommended by Tesla is to disable the Passive Entry. Because that’s the normal thing to do after you sell a \$100k+ car with a security hole in it: ask the customer to disable a feature for which he already paid. But hey, they take security seriously…

All that being said, I still love to drive my Model S. But I don’t recommend  anyone buying one. There are other electric car producers out there. Look for one that actually gives a s*it about you. Unfortunately Tesla is not one of them. Yet.

## Secure your Tesla Model S!

Written on 26 October 2018, 10:45pm

Tagged with: , ,

Update 8 December 2018: Don’t buy a Tesla!

Even if it has wheels and wipers, your Model S is ultimately a computer. A very good looking one if you ask me, but, as any other computer, it can be pwned. The recent news shows an increased incidence of Model S thefts across Western Europe, and apparently the thieves are exploiting a vulnerability in the way the car communicates with the key fob:

Like most automotive keyless entry systems, Tesla Model S key fobs send an encrypted code, based on a secret cryptographic key, to a car’s radios to trigger it to unlock and disable its immobilizer, allowing the car’s engine to start. After nine months of on-and-off reverse engineering work, the KU Leuven team discovered in the summer of 2017 that the Tesla Model S keyless entry system, built by a manufacturer called Pektron, used only a weak 40-bit cipher to encrypt those key fob codes.

Wired:  Hackers Can Steal a Tesla Model S in Seconds by Cloning Its Key Fob

Long story short, it only takes about \$600-worth of equipment, a decent computer and less than 2 seconds to crack the 40-bit cipher. According to Wired, the vulnerability was responsibly disclosed in August 2017, and after about a year, Tesla reacted by addressing the root cause (upgrading the key fobs) in addition to implementing the PIN-to-drive feature.
But this leaves a lot of room for the bad guys: there must be plenty of Model S manufactured before June 2018 and without the PIN-to-drive enabled. So what should you to secure your Tesla Model S and avoid a situation like this?

### 1. Disable passive entry

I don’t really like this option because you trade functionality for
security. The passive entry is a nice feature and Tesla should make it work securely, by upgrading the key fobs. But until then, this is a solid option to improve the existing security posture.

### 2. Enable PIN-to-drive

Again, an option that gets the job done, but leaves massive room for improvement. There are two major inconveniences: first, you must type your PIN in an environment where you cannot properly hide your keyboard. Second, your fingers leave traces when typing, and unless you are wiping the screen after every PIN entry, you are leaving a potential door open. This is simply not good enough, and I did not even mention how inconvenient is to input your PIN every time you start your car.
Tesla can do better – how about FaceID-to-drive?

FaceID just proved how it can address the most security concerns while providing a seamless user experience. With time, software and hardware updates, it will get even better, and we will see FaceID on other computing devices like tablets or laptops.
And from there it’s easy to imagine a keyless future. How long until you unlock your car by looking at it?

A post that I wrote back in November 2017: FaceID: convenience and security

### 3. Additional measures

• If your car was produced before June 2018, contact Tesla to replace your key fob so that the communication between the car and the key fob is properly encrypted
• Get a Faraday pouch if you would like to keep the Passive Entry active. Store your key inside the pouch when you’re not using the car, but make sure that you don’t leave the key inside the pouch inside the car 🙂 Oh, and get another pouch for the second key
• Install a hidden GPS tracker on your car. This will help locate the stolen car even when the bad guys would destroy the embedded connectivity module. Tesla won’t be able to remotely control your car, but, if you react quickly, you should be able to tell the police where it is
• Just use common sense when parking your car. Would you park your nice car in a shady, cheap and isolated area?
• Think defense-in-depth: implement not one, but more security measures to protect your asset 🙂