## Tuesday, December 1, 2009

### Three doors problem

There is very interesting problem which solution seems unintuitive, but indeed is correct. Also problem is called Monty Hall paradox. Problem definition is this:
-------------------------------------------------------------
Suppose you're on a game show and you're given the choice of three doors. Behind one door is a car; behind the others, goats [that is, booby prizes]. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you have chosen a door, the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one randomly. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door. Imagine that you chose Door 1 and the host opens Door 3, which has a goat. He then asks you "Do you want to switch to Door Number 2?" Is it to your advantage to change your choice?
-------------------------------------------------------------
Now what is probability that switching to last remaining door will reveal a car ?
This probability is 2/3. I will not explain it here, because it is very well explained in wikipedia site. It is more interesting to note that problem solution gets somewhat different when one must taken into account host bias. That is - what if host will have freedom to offer (or not) switching door ? If we define probability of host offering door switch when one looses (chooses door with goat) as Pol, and probability of host offering door switch when one wins (chooses door with car) as Pow. Then we can relate these two probabilities as
Pow=1-Pol
and define host bias, which is bias=Pol-Pow.
So now we have required information and we can conduct experiment/simulation which will reveal host bias impact on probability that door switching wins.

Experiment algorithm is as follows -
1. Take some bias from the range [-1;1]
2. Calculate Pow,Pol according this bias.
3. Simulate 500 000 games with this bias.
3a. According to these probabilities Pow,Pol - offer (or not) door change to player.
3b. If switch was offered and switching win the car - increase won games.
4. Calculate win probability when switching doors, with current host bias.
5. Repeat everything from 1. until bias range is covered.

Code which did these measurements is this (this time coded in plain good C):

#include <stdio.h>#include <stdlib.h>#include <time.h>struct Game { int PrizeDoor; int ChosenDoor; int RevealDoor; int OtherDoor;};// Reveal one empty door and calculate what door left for changingvoid OpenDoor(struct Game *gm) { for (int i=0; i!=3; ++i) {  if (i!=gm->ChosenDoor && i!=gm->PrizeDoor ) {   gm->RevealDoor = i;   gm->OtherDoor = 3 - (gm->ChosenDoor + gm->RevealDoor);   break;  } }}// Calculate probability that changing door wins a prize.// This probability is dependent on host bias towards the fair play.// Bias +1 - host only offers to change door when one looses.// Bias  0 - host offers to change door when one looses or wins.// Bias -1 - host only offers to change door when one wins.float ProbabilityChangeWins(float bias, int games) { float Pol, Pow, Prob, ProbChangeWins ; int TotalWins = 0, gamesWithOffers = 0; struct Game gm; Pol = (bias+1.0)/2.0; Pow = 1.0-Pol; srand(time(NULL)); // Main game test loop. The doors are numbered as 0,1,2. for (int i=0; i!=games; ++i) {  gm.PrizeDoor  = rand()%3;  gm.ChosenDoor = rand()%3;  Prob = (gm.PrizeDoor == gm.ChosenDoor) ? Pow : Pol;   // host offers to change doors based on his bias.  if (((float)rand()/RAND_MAX) < Prob) {   gamesWithOffers++;   OpenDoor(&gm);   TotalWins += (gm.OtherDoor == gm.PrizeDoor);  } } ProbChangeWins = ((float)TotalWins)/gamesWithOffers; return ProbChangeWins;}int main(void){ for (float i = -1.0; i < 1.05; i+=0.05)  printf("Bias = %1.2f | ProbabilityOfChangeWins = %1.2f\n",      i,ProbabilityChangeWins(i,500000));  return 0;}

Results of this experiment is graph plotted as switch win probability dependence on host bias:

Results is interesting and can be seen that host bias can shift "standard" problem solution very much.

Conclusions
1. Host can affect game outcome in such a way that switching doors always looses game or always wins game - in the case of marginal host bias values -1/+1.
2. If host is neutral (bias=0) then problem solution becomes the same as in "standard" way - swithing doors wins with the 2/3 probability.
3. Even if host is slightly shifted toward negative bias, that is bias > -0.3, switching doors is still beneficial.
4. What is more interesting that host bias can be established from the probability of win when switching doors. This means that from people who participated in that game and switched doors we can deduce host bias and tell if the game was fair or in what "amount" it was fair.

Have fun with probabilities and three door problem !