Thursday, November 26, 2009

Monty Hall Problem and Intuitive Solutions

Classical Problem

There are three doors. Two hide nothing. One hides a car. In phase 1, you pick a door. Monty (knowing where the car is) opens a door that does not hide a car and that you did not pick. In phase 2, you may stay with your chosen door (StayStrategy) or you may change your guess to the one remaining door (SwapStrategy). If you've picked the door that hides the car, you win the car.

The Truth

In the Classical Monty Hall problem, the StayStrategy succeeds with 1/3 probability, and the SwapStrategy succeeds with 2/3 probability.

Hand Wavy Justification

Imagine that there are 100 doors. You choose one. Knowing where the car is, Monty Hall opens 98 doors (other than your pick) that don't have the car. It is intuitively clear that your door has low probability of success, while the swap door has high probability of success.

Modified Problem

Imagine the same game, except Monty Hall doesn't know where the car is. After you pick a door in phase 1, he randomly reveals one of the remaining two doors. Now consider the situation where (by chance) he does not reveal the car. Should you stay or swap? Note: this problem only considers the situation when Monty Hall (by chance) has opened a door that does not hide the car.

The Truth

In the Modified Monty Hall problem, the StayStrategy succeeds with 1/2 probability, and the SwapStrategy succeeds with 1/2 probability.

A False Hand Wavy Argument

Imagine that there are 100 doors. You choose one. Not knowing where the car is, Monty Hall opens 98 doors (other than your pick) that don't have the car. This situation is highly unlikely, but possible. Originally, you knew that your door had a 1/100 probability of hiding the car, so it must reasonably be true that all the other doors combined had a 99/100 probability of hiding the car, and since they have been narrowed to one selection, the swap door must have a higher probability of success.

Proof For The Classical Problem

The Classical Monty Hall problem is exactly equivalent to the following problem. You pick a door with a 1/3 probability of success. There is a 2/3 probability that one of the other two doors hides the car. You are given the option of opening and winning the contents of just your selected door (StayStrategy) or both the other doors (SwapStrategy). Because Monty Hall never reveals the car, the (SwapStrategy) is exactly equivalent to having both the other doors, and therefore 2/3 probability of success. It is important to remember that there are only two possible outcomes to this game: the stay door hid the car or the swap door hid the car. The Monty door never hides the car. This proof is particularly evident when examining the source code for a simulation of the game. In the simulation it is not necessary to determine which door Monty reveals. All you need to do is randomly generate a car on [1..3] and randomly generate a guess on [1..3]. If the car equals the guess then the (StayStrategy) wins, otherwise the (SwapStrategy) wins.

Proof For The Modified Problem

The Modified Monty Hall problem is actually three problems considered in isolation. It is true that your original pick has 1/3 probability of success. It is true that Monty Hall is not allowed to reveal your door. This does not change the fact that the door Monty Hall picks has a 1/3 probability of hiding the car. Since neither your nor Monty have knowledge of which door hides the car, regardless of the picks, each door has a 1/3 probability of hiding the car. Hence in the millions of times that the game is played, 1/3 of the games end with Monty Hall accidentally revealing the car. In the remaining 2/3 of the games played there is a 50% probability that the (StayStrategy) wins, and a 50% probability that the (SwapStrategy) wins. That is to say that 1/3 of all games end with Monty Hall accidentally revealing the car, 1/3 of all games end with your original pick hiding the car, and 1/3 of all games end with the remaining door (picked by neither you nor Monty) hiding the car.

Java Simulation Source Code

import java.util.Random;
public class Sim 
{
  /**
   * A static number generator.
   */
  private static Random rn = new Random();

  public static void main(String args[])
  {
    long inner_loop = 10000000;
    long outer_loop = Long.MAX_VALUE/(inner_loop+1);
    long know_stay = 0;
    long know_swap = 0;
    long unkn_stay = 0;
    long unkn_swap = 0;
    long bad_monty = 0;
    long loops = 0;
    int result = 0;
    
    for (long i=0; i<outer_loop; i++)
    {
      for (long j=0; j<inner_loop; j++)
      {
        if (playKnown()) { know_stay++; }
        else { know_swap++; }
        result = playUnknown();
        if (result == -1) { bad_monty++; }
        else if (result == 1) { unkn_stay++; }
        else { unkn_swap++; }
      }
      loops++;
      System.out.println("with knowledge:    " + (inner_loop*loops) + " tries, stay wins " + know_stay + " times, swap wins "  + know_swap + " times");
      System.out.println("without knowledge: " + (inner_loop*loops) + " tries, stay wins " + unkn_stay + " times, swap wins "  + unkn_swap + " times, and we didn't count "  + bad_monty + " games because monty opened the car with the door.");
    }
  }

  /**
   * return true if the stay stratgey wins
   * false if the swap strategy wins
   */ 
  public static boolean playKnown()
  {
    int car = randomInt(1,3);
    int guess = randomInt(1,3);
    
    return (car == guess);
  }    
  
  /**
   * return 1 if the stay stratgey wins
   * 0 if the swap strategy wins
   * -1 if monty uncovered the car
   */ 
  public static int playUnknown()
  {
    int car = randomInt(1,3);
    int guess = randomInt(1,3);
    
    int[] not_guess = new int[2];
    if (guess == 1)
    {
      not_guess[0] = 2;
      not_guess[1] = 3;
    }
    else if (guess == 2)
    {
      not_guess[0] = 1;
      not_guess[1] = 3;           
    }
    else // guess == 3
    {
      not_guess[0] = 1;
      not_guess[1] = 2;           
    }
    int monty = not_guess[randomInt(0,1)];
    
    if (monty == car) { return -1; }        
    else if (car == guess) { return 1; }
    else { return 0; }
  }
  
  /**
   * Generate a random int bounded by lo and hi.
   * 
   * @param   lo  The lower bound for the generated random int.
   * @param   hi  The upper bound for the generated random int.
   * @return  A random int bounded by lo and hi.
   */
  public static int randomInt(int lo, int hi)
  {
    int n = hi - lo + 1;
    int i = rn.nextInt() % n;
    if (i < 0) { i = -i; }
    return lo + i;
  }
}

Results:

with knowledge:     10000000 tries, stay wins  3334274 times, swap wins  6665726 times
without knowledge:  10000000 tries, stay wins  3332947 times, swap wins  3332175 times, and we didn't count  3334878 games because monty happened to open the door that hides the car.
with knowledge:     20000000 tries, stay wins  6669429 times, swap wins 13330571 times
without knowledge:  20000000 tries, stay wins  6666620 times, swap wins  6666379 times, and we didn't count  6667001 games because monty happened to open the door that hides the car.
with knowledge:     30000000 tries, stay wins 10002452 times, swap wins 19997548 times
without knowledge:  30000000 tries, stay wins 10000691 times, swap wins  9998688 times, and we didn't count 10000621 games because monty happened to open the door that hides the car.
with knowledge:     40000000 tries, stay wins 13337424 times, swap wins 26662576 times
without knowledge:  40000000 tries, stay wins 13335449 times, swap wins 13331927 times, and we didn't count 13332624 games because monty happened to open the door that hides the car.
with knowledge:     50000000 tries, stay wins 16668431 times, swap wins 33331569 times
without knowledge:  50000000 tries, stay wins 16669002 times, swap wins 16665316 times, and we didn't count 16665682 games because monty happened to open the door that hides the car.
with knowledge:     60000000 tries, stay wins 20001372 times, swap wins 39998628 times
without knowledge:  60000000 tries, stay wins 20003117 times, swap wins 20000776 times, and we didn't count 19996107 games because monty happened to open the door that hides the car.
with knowledge:     70000000 tries, stay wins 23336691 times, swap wins 46663309 times
without knowledge:  70000000 tries, stay wins 23337282 times, swap wins 23330969 times, and we didn't count 23331749 games because monty happened to open the door that hides the car.
with knowledge:     80000000 tries, stay wins 26671522 times, swap wins 53328478 times
without knowledge:  80000000 tries, stay wins 26669341 times, swap wins 26665020 times, and we didn't count 26665639 games because monty happened to open the door that hides the car.
with knowledge:     90000000 tries, stay wins 30006648 times, swap wins 59993352 times
without knowledge:  90000000 tries, stay wins 30001021 times, swap wins 30000035 times, and we didn't count 29998944 games because monty happened to open the door that hides the car.
with knowledge:    100000000 tries, stay wins 33338997 times, swap wins 66661003 times
without knowledge: 100000000 tries, stay wins 33336749 times, swap wins 33330848 times, and we didn't count 33332403 games because monty happened to open the door that hides the car.
with knowledge:    110000000 tries, stay wins 36670433 times, swap wins 73329567 times
without knowledge: 110000000 tries, stay wins 36670423 times, swap wins 36664718 times, and we didn't count 36664859 games because monty happened to open the door that hides the car.
with knowledge:    120000000 tries, stay wins 40002402 times, swap wins 79997598 times
without knowledge: 120000000 tries, stay wins 40004144 times, swap wins 39996302 times, and we didn't count 39999554 games because monty happened to open the door that hides the car.
with knowledge:    130000000 tries, stay wins 43336203 times, swap wins 86663797 times
without knowledge: 130000000 tries, stay wins 43337738 times, swap wins 43327772 times, and we didn't count 43334490 games because monty happened to open the door that hides the car.
with knowledge:    140000000 tries, stay wins 46669017 times, swap wins 93330983 times
without knowledge: 140000000 tries, stay wins 46673344 times, swap wins 46661949 times, and we didn't count 46664707 games because monty happened to open the door that hides the car.
with knowledge:    150000000 tries, stay wins 50000488 times, swap wins 99999512 times
without knowledge: 150000000 tries, stay wins 50006909 times, swap wins 49995306 times, and we didn't count 49997785 games because monty happened to open the door that hides the car.

Java Simulation Executable Jar File

{ "loggedin": false, "owner": false, "avatar": "", "render": "nothing", "trackingID": "UA-36983794-1", "description": "Intuitive Solutions to the Monty Hall Problem, including Java simulation source, executable and results.", "page": { "blogIds": [ 15 ] }, "domain": "holtstrom.com", "base": "\/michael", "url": "https:\/\/holtstrom.com\/michael\/", "frameworkFiles": "https:\/\/holtstrom.com\/michael\/_framework\/_files.4\/", "commonFiles": "https:\/\/holtstrom.com\/michael\/_common\/_files.3\/", "mediaFiles": "https:\/\/holtstrom.com\/michael\/media\/_files.3\/", "tmdbUrl": "http:\/\/www.themoviedb.org\/", "tmdbPoster": "http:\/\/image.tmdb.org\/t\/p\/w342" }