Monty Hall Problem

Solution: Monte Carlo Simulation

function montyHallSimulation(numTrials) {
    let stayWins = 0;
    let switchWins = 0;

    for (let trial = 0; trial < numTrials; trial++) {
        // Randomly place the car behind one of 3 doors (0, 1, or 2)
        const carDoor = Math.floor(Math.random() * 3);

        // Player randomly picks a door
        const playerChoice = Math.floor(Math.random() * 3);

        // Host opens a door that:
        // - Is not the player's choice
        // - Does not have the car behind it
        let hostOpens;
        for (let door = 0; door < 3; door++) {
            if (door !== playerChoice && door !== carDoor) {
                hostOpens = door;
                break;
            }
        }

        // Find the remaining door (not player's choice, not host's open)
        let remainingDoor;
        for (let door = 0; door < 3; door++) {
            if (door !== playerChoice && door !== hostOpens) {
                remainingDoor = door;
                break;
            }
        }

        // Check outcomes
        if (playerChoice === carDoor) {
            stayWins++;
        }

        if (remainingDoor === carDoor) {
            switchWins++;
        }
    }

    return {
        trials: numTrials,
        stayWins: stayWins,
        switchWins: switchWins,
        stayWinRate: (stayWins / numTrials * 100).toFixed(2) + '%',
        switchWinRate: (switchWins / numTrials * 100).toFixed(2) + '%'
    };
}

// Run simulation
console.log(montyHallSimulation(10000));

/* Expected output:
{
  trials: 10000,
  stayWins: ~3333,
  switchWins: ~6667,
  stayWinRate: ~33.33%,
  switchWinRate: ~66.67%
}
*/

Cleaner Python Version

import random

def monty_hall_simulation(num_trials):
    stay_wins = 0
    switch_wins = 0

    for _ in range(num_trials):
        # Setup
        doors = [0, 1, 2]
        car_door = random.choice(doors)
        player_choice = random.choice(doors)

        # Host opens a door with goat
        available_doors = [d for d in doors
                          if d != player_choice and d != car_door]
        host_opens = random.choice(available_doors)

        # Remaining door after host opens
        remaining_door = [d for d in doors
                         if d != player_choice and d != host_opens][0]

        # Count wins
        if player_choice == car_door:
            stay_wins += 1
        if remaining_door == car_door:
            switch_wins += 1

    return {
        'stay_wins': stay_wins,
        'switch_wins': switch_wins,
        'stay_rate': f'{stay_wins/num_trials*100:.2f}%',
        'switch_rate': f'{switch_wins/num_trials*100:.2f}%'
    }

# Run with different sample sizes
for n in [100, 1000, 10000, 100000]:
    result = monty_hall_simulation(n)
    print(f"n={n}: Stay: {result['stay_rate']}, "
          f"Switch: {result['switch_rate']}")

Expected Output

n=100: Stay: 32.00%, Switch: 68.00%
n=1000: Stay: 33.40%, Switch: 66.60%
n=10000: Stay: 33.21%, Switch: 66.79%
n=100000: Stay: 33.35%, Switch: 66.65%

As sample size increases, rates converge to theoretical 1/3 and 2/3.

Mathematical Proof

Using Bayes' Theorem:

P(Car behind Door 1 | Host opened Door 3) =
    P(Host opens Door 3 | Car behind Door 1) × P(Car behind Door 1) /
    P(Host opens Door 3)

Let's say you chose Door 1, host opened Door 3:

• Car behind Door 1: P = 1/3, host can open Door 2 or 3 (1/2 chance he picks 3)
• Car behind Door 2: P = 1/3, host MUST open Door 3 (probability 1)
• Car behind Door 3: P = 0, host would never open the car door

P(Door 1 has car | host opened 3) = (1/3 × 1/2) / (1/3 × 1/2 + 1/3 × 1 + 0) = 1/3
P(Door 2 has car | host opened 3) = (1/3 × 1) / (1/3 × 1/2 + 1/3 × 1 + 0) = 2/3

Switching gives you 2/3 probability of winning!

Visualization Function

function visualizeMontyHall() {
    const trials = 1000;
    let stayCounts = [];
    let switchCounts = [];
    let stayRunning = 0;
    let switchRunning = 0;

    for (let i = 1; i <= trials; i++) {
        const result = montyHallSimulation(1);
        stayRunning += result.stayWins;
        switchRunning += result.switchWins;

        stayCounts.push((stayRunning / i * 100).toFixed(2));
        switchCounts.push((switchRunning / i * 100).toFixed(2));
    }

    console.log("TrialtStay%tSwitch%");
    for (let i = 0; i < trials; i += 100) {
        console.log(`${i+1}t${stayCounts[i]}t${switchCounts[i]}`);
    }
}

Complexity Analysis

Time Complexity: O(n) where n is number of trials

Space Complexity: O(1) - only tracking counters

Common Mistakes

1. Host opens random door: Host knows where car is and never opens that door
2. Not enough trials: Need 10,000+ to see clear 33/67 split
3. Confusing conditional probability: The host's action provides information
4. Assuming 50/50: Two doors remaining doesn't mean equal probability

Variations

1. 100 doors: You pick one, host opens 98 goat doors. Switch probability = 99/100!
2. Host doesn't know: If host opens random door and happens to show goat, then switching gives 50/50
3. Multiple switches: If you can switch multiple times, probability changes

Real-World Applications

• A/B testing: Understanding conditional probability in experiments
• Bayesian inference: Updating beliefs with new information
• Game theory: Optimal strategy when opponent has information
• Medical testing: Understanding false positive rates

Related Problems

• Red Marbles, Blue Marbles - Probability theory
• Getting a fair result with an unfair coin - Probability transformation
• Coin Rolls - Expected value
• Probability Distribution Function - Statistical reasoning