The Monty Hall Problem and Monte Carlo Method

Posted on | In ,

There is a famous problem known as the “Monty Hall problem.” There are three doors. One door hides a car and the other two hide goats. After a person selects a door, the host opens one of the remaining doors to reveal a goat. The person then gets one chance to either keep their original choice or switch doors. The question is: which strategy is better — switching or staying? Setting aside psychological considerations, it is proven that switching leads to a higher probability of winning.

This generalizes easily to an $n$-door problem. Let $A$ be the event of choosing the correct door on the first pick, so $P(A) = \frac{1}{n}$. If the person chose the correct door, switching makes the selection wrong. If the person chose the wrong door, switching wins among the remaining $n - 2$ doors. Therefore, the probability of winning after switching is $\frac{1}{n} \times 0 + \frac{n - 1}{n} \times \frac{1}{n-2} = \frac{n-1}{n(n-2)}$.

Which means it results in a better probability to win.

It can be simulated by code below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <time.h>
#include <iostream>

int main(){
    using namespace std;

    int numDoor;
    int numIteration;
    int success = 0;
    int failed = 0;
    int price, selected, changed;
    srand(time(NULL));

    cout << ("Enter the trial number: ");
    cin >> numIteration;
    cout << ("Enter the number of doors: ");
    cin >> numDoor;

    bool door[numDoor];
    for (int i = 0; i < numIteration; i++){
        for (int j = 0; j < numDoor; j++){
            door[j] = false;
        }

        price = rand() % numDoor;
        door[price] = true;

        selected = rand() % numDoor;

        int hostSelected = rand() % numDoor;
        while(hostSelected == selected || door[hostSelected]){
            hostSelected = rand() % numDoor;
        }

        changed = rand() % numDoor;
        while((changed == selected) || (changed == hostSelected)){
            changed = rand() % numDoor;
        }

        if (door[changed]){
            success++;
        }
        else{
            failed++;
        }
    }
    cout << "# success " << success << ", # failed " << failed << ", Percentage " << success / float(numIteration) * 100 << std::endl;
    return 0;
}

This is close to the Monte Carlo method. It simply tries the switch and checks whether the result is a prize or not. Collecting enough trials allows us to estimate the actual probability.

# trial # door # success # fail Probability(From experiment) Probability(From theory)
10000 3 6703 3297 67.03 $\frac{2}{3} \cdot \frac{1}{1} \cdot 100 = 66.\dot{6}$
10000 4 3768 6232 37.68 $\frac{3}{4} \cdot \frac{1}{2} \cdot 100 = 37.5$
10000 5 2608 7392 26.08 $\frac{4}{5} \cdot \frac{1}{3} \cdot 100 = 26.\dot{6}$
10000 6 2028 7972 20.28 $\frac{5}{6} \cdot \frac{1}{4} \cdot 100 = 20.8\dot{3}$

Here is one more example to compute the area of circle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <time.h>

int main(){
    using namespace std;
    constexpr int numIteration = 1000000;
    srand(time(NULL));

    int inSide = 0;
    for(int i = 0; i < numIteration; ++i){
        float x = rand() % 10000 / float(5000) - 1; // -1 ~ 1
        float y = rand() % 10000 / float(5000) - 1; // -1 ~ 1
        if(x * x + y * y <= 1){
            ++inSide;
        }
    }
    cout << "Inside of circle : " << inSide << ", circle area may be " << 4 * inSide/float(numIteration) << std::endl;
}

It is known to be $\pi r^2$. Circle area is $3.14082$ with $r = 1$ from the experiment. Which means it works pretty well.