Monty Hall Problem
Tags: statistics, bayesian, datascience, python
Published: 2019-09-27 19:28:50

**Monty Hall Problem** is a famous probability puzzle in statistics. It is named after Monty, the host of the television game show "Let's Makes a Deal". The brain teaser loosely replicates the game show concept and it goes like this:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/dppd3jokklf3jbhb1sk0.png)

>There are 3 doors. You will have to choose a door, and you will win whatever behind it. There is one door with a car. Each remaining door has a goat. First, you are asked to pick one of the doors. Next, Monty, who knows what's behind each of the doors, opens up one of the two doors you didn’t pick and reveal a goat. Finally, you are given the opportunity to either “stay” with your original choice, or “switch” to the remaining door. What is the best strategy to win the car? 

I first encountered this problem 4 years ago in a statistics class. It was hard enough that I spent the whole day thinking about it and still insist on 1/2 for both strategies. My explanation was: there are 3 doors, 1 door has a car. If the host opens one door that has the goat, one out of two remaining doors must have the car. So regardless of "switching" or "staying", the probability should be 1/2!   

I was wrong. The tricky part of this problem is Monty knows what behind those doors so his decision has an influence on the outcome. Take a minute for yourself to think if this is true.

## 1) Intuitive answer
Assuming that the three doors are: 1, 2, and 3
Since probability = Event/Sample space we just need to find these variable and plug in the equation.
Sample space here is the total of different ways that we choose the door and where the car actually is. There are 6 possibilities which are illustrated in the following table:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/fpeijsqol07658x42ow6.png)

Note that in this table, Monty has already eliminated the door with the goat. 
As you can see, the probability of winning for "staying" strategy is 1/3 while "switching" is 2/3.

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/2izk7doe64ai0ndyzo6w.gif)

## 2) Bayes formula method
This is another approach for people who loves Bayes! 
Let P(A|B) denote the probability of event A given that event B already happened 

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/jpcf6pe6q8bsy5dysusl.png)

If we know how to translate the problem into events, then everything becomes straight forward. Let:
* A be the event that is choosing the door with the car on the first choice. 
* B be the event that Monty eliminates one door that has a goat. 
So we are looking for P(A|B), the "staying" strategy.

Let write down things that we know: 
* P(B|A) = 1, since Monty always choose the right door regardless of any given condition
* P(A) =1/3, there is a 1/3 chance of opening the car door, without knowing anything. 
* 
To understand how to find P(B), let's look at the diagram:
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/44rb00z0z8ybzekknog0.png)

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/t11nr5ugso3dqxm5j4az.png)

There are only 2 possible strategies, either stay or switch. Thus, "switching" probability is the complement of staying, which is 1-1/3=2/3.

**If** Monty does not know which door has the goat. This is equivalent to P(B|A)=1 and P(B|¬A)=1/2. Plug them back to the equation and it returns P(B|A)=1/2. This is the part that I was confused. 

## 3) Simpler answer
With the "staying" strategy, you can only win if you choose the door with a car at first. Since there are 3 doors, the probability of choosing a door with a car is 1/3. So the "switching" strategy is 2/3. This provide us a general observation for more than 3 doors Monty Hall problem. 

## 4) What if?
What if Monty Hall decides to reveal k doors out of n doors where the maximum number of k is n-2, will it affect the strategy at all?

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/xs7yzx0m7cvotz7868kf.jpg)


"Switching" in this case means not keeping the original choice
#### Case A: k=n-2
This case is similar to the original problem. Note that you cannot switch to the door that you chose. So "Staying" win rate is always 1/n and switching win rate, in this case, is (n-1)/n

#### Case B: k<n-2
The probability of choosing the door with a car at the beginning is still 1/n. Thus "staying" = 1/n
In the "switching" strategy, your final choice cannot be your first choice. Thus, you don't want to choose the first door which has the car at the beginning. The probability of not choosing it is (n-1)/n. The k-th switch is also when your pick, there are n-k door(s) left but you must exclude your first door. Thus, the probability of picking the prized door in the last step is 1/(n-k-1). Together we have: 

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/iu2vgqi7fofsskwhgg0k.png)

It shows that the "switching" strategy is always better than "staying" strategy.

## 5) Simulation

Let run it on python to see if our formula work. Let n be the number of doors and r is the number of door Monty wants to reveal

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/9ohcnr66xuc4nnu14670.jpg)
 
The graph shows that the statistical result getting close to our actual answer when increasing the number of iteration. 

So, you know what you should do if you play a similar game like this next time.

***
For more information about the code, please visit my [Githup repository](https://github.com/williamhuybui/Monty_Hall_problem).