Monty hall problem and monte carlo method

Posted on | In ,

There is a famous problem known as “Monty hall problem”. There are three doors. One of the door has a car and others have a goat. If a person selects a door, host will open one door with a goat. Now, person gets one chance to change the selection or not. So the question is which one is better in between changing it or not? If there is nothing psychological relations, it is proven that changing the selection makes better decision.

It can be easily extended to $n$ door problem. Let’s assume that $A$ is an event that chooses the right door at the first trial which $P(A) = \frac{1}{n}$. If a person choosed the right door, then change makes the selection wrong. If a person choosed the wrong door, then change may make the right selection between $n - 2$ doors. As a result, if a person changes a door it will be $\frac{1}{n} \times 0 + \frac{n - 1}{n} \times \frac{1}{n-2} = \frac{n-1}{n \times (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 monte-carlo method. It just tries the change and check wheter it is price or not. Collect the data and guess 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.