Shocked that I've never written about this.
I just searched my entire blog history since 2017 and I'm very surprised to see that I've never written about the Monty Hall problem. It's just one of those math/gambling/statistics riddles that feels like I would have mentioned within the last 8 years, but I guess not. So to give an extremely quick overview we require some background context for another variant of this problem that seems borderline impossible and paradoxical.
Monty Hall Problem:
You are on a gameshow and in front of you lies three distinct doors. Behind one of the doors is a prize you want (say a car) and behind the other two doors is either nothing or a prize you don't really want that much (like a goat). Your chance of winning this game is one in three. There are three doors and you choose one of them, pretty simple.
However, after you choose your door and get your 1/3rd chance, the host of the gameshow throws in a twist. He removes one of the doors you didn't pick, and also guarantees that the one he removed was not the winning door. And thus, either the door you picked is the winning door, or the one door that's left is the winning door. The host asks you if you'd like to change your mind or stick with what you picked. What should you do?
Logistically it feels like in this situation it wouldn't really matter if you switched your bet or not, but it very much does matter. The door that you picked has a one in three chance of being right, while the door that remains has a one in two chance of being right due to a losing door being removed from the game. In this case you should always change your mind for the optimal pot odds and higher estimated value play.
A few days ago I found a problem that's a hundred times crazier.
The answer is so weird that it feels like it can't be true mathematically, but somehow it works. I don't like the way the problem is framed, so I'm going to explain the original and then reframe it to another gambling example.
- There are 100 prisoners, each with a number from 1 to 100.
- The prisoners are told they will all be freed if they can all independently go into a room full of boxes and find their number.
- The room has 100 boxes, all labeled from 1 to 100, but the box contains a random prisoner number from 1 to 100.
- If all the prisoners find their number in 50 attempts (coin flip) they get set free.
- But if even one prisoner gets it wrong they'll all be executed.
- What are the chances the prisoners can pull it off with ideal conditions?
Here's the crazy part:
The professor that wrote this problem in a dissertation did not know the answer. He was actually just using this problem to show how crazy non-polynomial (exponential) math can be. In this case one would assume that each prisoner independently has a 50% chance of finding their number, and the chance of all of them finding it would be one in 2^100, which is 1,267,650,600,228,229,401,496,703,205,376.
So the chance of the prisoners winning this bet is essentially zero. It would be the same as trying to crack 100-bit encryption on the first try, which is what the author was trying to imply... that there's a better chance of two prisoners picking the same grain of sand on a beach than winning this bet... and yet there is a technique that can increase the chance of success from almost-literal zero to over 30%, which tends to baffle mathematicians.
But before we get into that.
I'm going to reframe it from prisoners to lottery/gambling.
Because risking your life is too high stakes and ridiculous.
- So instead of 100 prisoners it's 100 lottery tickets.
- Each person needs to find their lottery ticket in 50 tries to win.
- Each person pays $100 to play but will get a payout of $1M if they win.
In this case the casino does not realize that there's a way to get a 30% chance of winning, so they are about to lose a lot of money. The players only have to play three or four times in order to win a game on average... which means they'll lose like $310 but then make $1M on the win, and the casino will go bankrupt thinking there was no way they could lose this game.
Ring theory.
In order to crack this problem with heuristics, each player must stick to a very specific plan. Luckily, the plan is very simple so hopefully nobody messes it up.
- If your lottery number is 47, go to box 47.
- If box 47 contains number 47, you win.
- If box 47 contains number 25, go to box 25 and try again.
- If box 25 contains 47, you win, if not go to the next box it points to.
- Eventually you find your number (47) which will point back to box 47 and close the loop.
- The only question is whether or not you'll find the number in 50 tries or not.
It sounds insane, but if the players of the game follow this strategy they will ALL find their lottery ticket 30%+ of the time and win the game. However, if they lose, they will lose big as well. If one of these rings is of size 51 or greater, everyone in that ring will lose... but that doesn't matter, because if one person loses they all lose anyway.
This ring strategy works because it exploits the fact that if one person loses they all lose. By forcing everyone into the same ring of choices it means that everyone is going to win or lose together. And the crazy thing is that it doesn't matter how many players you add. 1000 players have 500 guesses? That's also a 30% win rate. A million players get 500k guesses? Same thing. The limit approaches around 30% win-rate no matter how many players are playing by combining the fates of all the players inside the ring together.
None of this should really make sense to you fully.
I watched the 18 minute video and it still seemed like bullshit to me until I really started thinking about it. This is the response that most mathematicians have as well, which is why the solve is so damn interesting.
Interesting notes:
Because the same box cannot appear in multiple rings, it is possible to give the players a 100% win rate using this strategy just by swapping the contents of two different boxes. This is because if there's a ring of size 51+ there can't be another ring of size 51+ because that many boxes do not exist. Thus, the person who swaps for the 100% victory just takes the ring of 51+ boxes and splits it up into 2 smaller rings of less than 50; guaranteeing the win.
However, if a malicious actor gets to swap boxes and try to force them to lose, the players can prevent this from happening. Imagine the bad actor (casino in this case) organizes the boxes to create a ring of size 51+... this can be avoided by the players with a virtual swap of the numbers. The example given in the video was extremely simple: just add +5 to the box numbers and this will do a full shuffle of the rings and create a completely random outcome.
A lesson in heuristics
The reason why a brain teaser like this is so interesting is that it's one of those rare examples in which an insurmountable non-polynomial problem with a nearly infinite fail rate is 'magically' simplified into a something that can be solved instantly. The importance of this is huge, because if something like this were to happen to cryptography (like quantum computing) then all of a sudden most crypto implementations are no longer secure and we have to figure out quantum resistant solutions (which are more expensive and resource-heavy but they'd at least be secure).
This is also how AI works. When I was a kid computers were actually quite bad at chess. Grandmasters and computer scientists alike were on record as saying that a computer could never beat the best humans. This is because there were no heuristics to guide the computer algorithm. Every move was considered just as valid as any other move.
This meant that the computer thinking even 7 moves ahead was insanely difficult and took a long time to compute all the possibilities. Now that the computer has an idea of which terrible moves can be completely pruned from the decision tree all computer chess players are top grandmasters and essentially unbeatable by any human opponent. That on top of computers just being a lot faster today than they were 30 years ago (another example of exponential growth)
Conclusion
If you have the time and the interest watch the 18 minute video on this problem. While it might seem that stuff like this doesn't have any real world applications, the concept of simplifying exponential problems down to solvable ones definitely does. In fact it is the foundation of AI, which we can all see has been making leaps and bounds in recent years with a ton of potential value that hasn't been realized yet.