Monty Hall Afterthoughts
(Last Mod: 04 November 2010 18:10:44 )
Now that you have implemented the Monty Hall problem - and understand the results (hopefully) - it is useful to discuss some of the different ways in which some of the key elements could have been approached.
As you should already be aware, random selections had to be made at a number of different points - but the constraints on the selection varied. The purpose of this treatment is to show some of the ways that a problem like this can be looked at and simplified by looking for and noticing patterns and relationships.
1) Pick a door to put the prize behind.
Description: This involved returning one of three possible random numbers.
Input: None.
Output: A door number. One of three possible random numbers - {0,1,2} or {1,2,3} are perhaps the most reasonable sets.
2) Pick a door as the initial user selection.
Description: This also involved returning one of three possible random numbers with no restrictions and hence the same function used for the prior case could be reused for this one.
3) Pick a door to open.
This actually breaks down into two sub-problems:
3a) Pick a door to open if the User chose the winning door.
Description: Randomly pick one of the two remaining doors
Input: The number of the door the user chose - is the same as the number of the winning door..
Output: A door number. The number of the door to be opened
3b) Pick a door to open if the User chose a non-winning door.
Description: Open the other non-winning door.
Input: The number of the door the user chose and the number of the winning door.
Output: A door number. The number of the door to be opened
4) Decide whether to switch or stay.
Description: Randomly pick from among two possible choices.
Input: None:
Output: A logic value. (either 0 and 1 or two other numbers that are interpreted properly by the calling function).
We have a few basic strategies to approach the problems above:
1) We could certainly write four different functions to cover these five cases (since the first two have already been identified as being the same). Each function could use the specific constraints associated with that particular problem in order to generate its output. This could be done use selection statements such as if()/else and switch() constructs very readily: As an inefficient but quickly coded alternative we could do pick-and-check - simply pick one of three possible numbers randomly and then test to see if that selection satisfies the constraints - if it doesn't then we repeat the process and continue picking random numbers until we happen to pick one that is acceptable. This approach would permit us to get our code up and running very quickly and then, if the performance turned out to be unacceptable, we could rewrite these functions to make them faster.
2) We could evaluate the common traits of the four functions and see if at least a couple of them can be combined and performed by a single function. This is what we want to explore here.
Notice that in each case, we want to randomly pick one of three values subject to the constraint that the number returned is NOT equal to specific values. In the case of Problems #1 and #2, there are no values that are not allowed. In the case of Problems #3a and #4 there is one disallowed value - in Problem #3a it is the number of the door the user chose and in Problem #4 it is simply one of the three possible values so that we are picking one of the two remaining possibilities. Finally, in Problem #3b, we want to exclude two of the three possible values - namely the door that the user chose and the winning door.
At this point, notice that we can reword the problem statement so that Problems #3a and #3b collapse back into a single problem - if we pick a door at random after excluding both the winning door and the chosen door, then we have covered both cases. The fact that, if the user chose the winning door, we are excluding the same door twice is immaterial.
As a possible function prototype, we could have something like this:
int PickAnyDoorOtherThan(int NotDoor1, int NotDoor2, int DoorsToExclude);
where DoorsToExclude tells us how many doors are excluded from possible selection such that:
| DoorsToExclude | Meaning |
| 0 | Pick any door |
| 1 | Pick any door except NotDoor1 |
| 2 | Pick any door except NotDoor1 and NotDoor2 |
Thus, our function calls for the five original problems could become:
1) Pick a door to put the prize behind.
Description: This involved returning one of three possible random numbers.
Input: None.
Output: A door number. One of three possible random numbers - {0,1,2} or {1,2,3} are most reasonable sets..
Function Call: PrizeDoor = PickAnyDoorOtherThan(0,0,0);
2) Pick a door as the initial user selection.
Description: This also involved returning one of three possible random numbers and hence the same function used for the prior case could be reused for this one.
Function Call: ChosenDoor = PickAnyDoorOtherThan(0,0,0);
3) Pick a door to open (now covers both #3a and #3b).
Description: Randomly pick a remaining door that is neither the Chosen door nor the Winning door.
Input: The number of the door the user chose and the number of the winning door.
Output: A door number. The number of the door to be opened
Function Call: OpenDoor = PickAnyDoorOtherThan(ChosenDoor, PrizeDoor,2);
4) Decide whether to switch or stay.
Description: Randomly pick from among two possible choices.
Input: None:
Output: A logic value. (either 0 and 1 or two other numbers that are interpreted properly by the calling function).
We could use the same function for this problem as well, something along the lines of:
Function Call: Switched = (DOOR1 = = PickAnyDoorOtherThan(DOOR3, 0, 1));
The above function call assumes that three constants, DOOR1, DOOR2, and DOOR3, have been appropriately #defined. This will work but it is not very readable code. Basically we are using a trick - randomly picking either DOOR1 or DOOR2 and saying that we will switch if DOOR1 gets chosen and that we will stay if DOOR2 gets chosen. It will work, but it is rather convoluted logic. For readability, we should either use a more obvious approach (randomly pick either a 0 or a 1 using something like rand()%2 for instance) or imbed the "trick" inside of a function - perhaps named WillSwitch() - so that the "trick" is not visible unless the user actually looks up the code for the function (and where this "trick" should be well documented).
Assuming we have decided to treat Problem #4 separately (at least by embedding it into its own function) then we are left with just two potential calls to our generic door picking function:
PickAnyDoorOtherThan(0,0,0);
PickAnyDoorOtherThan(ChosenDoor, PrizeDoor, 2);
The strategies discussed previously - using selection statements and pick-and-check - are still perfectly viable methods of actually implementing this function. We are interested in looking at other possible methods, but before we do let's see if we can't pare down our function a bit more.
Notice that the first two arguments are door numbers and that it only makes sense to exclude them from selection if they are door numbers that actually represent doors. For instance, if our doors are numbered {1,2,3} then if Chosen Door is 15 we are still allowed to pick any of the doors as acceptable return values. This opens the door for us to get rid of the third argument - we simply note that the function returns the number of a legal door that does not match either of the arguments and that using an illegal door number as an argument simply doesn't exclude any doors from consideration. So now our prototype might look like this (along with some #define constants that will come in handy shortly).
#define NODOOR (0)
#define DOORS (3)
int PickAnyDoorOtherThan(int NotDoor1, int NotDoor2);
One implementation of this function could be nothing more than:
#define NODOOR (0)
#define DOORS (3)
int PickAnyDoorOtherThan(int NotDoor1, int NotDoor2);
{
int door;
do
{
door = (rand()%DOORS) + (NODOOR+1);
} while ((door == NotDoor1) || (door == NotDoor2));
return(door);
}
Notice that the #define constants are interpreted as meaning that we have DOORS legal doors and that they are numbered from (NODOOR+1) to (NODOOR+DOORS).
In theory, this implementation could get stuck for an indefinite period of time if it kept repeatedly picking a door that has been excluded. Using a series of selection statements could eliminate this problem. But let's explore another possible approach.
Let's specify that NODOOR is going to be equal to zero and that we are going to have three doors. We can then write down all of the possible function calls and what they can return in a simple table and then look for ways to group them:
| NotDoor1 | NotDoor2 | Possible Return Values |
| 0 | 0 | {1,2,3} |
| 0 | 1 | {2,3} |
| 0 | 2 | {1,3} |
| 0 | 3 | {1,2} |
| 1 | 0 | {2,3} |
| 1 | 1 | {2,3} |
| 1 | 2 | {3} |
| 1 | 3 | {2} |
| 2 | 0 | {1,3} |
| 2 | 1 | {3} |
| 2 | 2 | {1,3} |
| 2 | 3 | {1} |
| 3 | 0 | {1,2} |
| 3 | 1 | {2} |
| 3 | 2 | {1} |
| 3 | 3 | {1,2} |
We can now regroup this table according to the possible return values and look for patterns:
| NotDoor1 | NotDoor2 | Possible Return Values |
| 0 | 0 | {1,2,3} |
| 0 | 3 | {1,2} |
| 3 | 0 | {1,2} |
| 3 | 3 | {1,2} |
| 0 | 2 | {1,3} |
| 2 | 0 | {1,3} |
| 2 | 2 | {1,3} |
| 0 | 1 | {2,3} |
| 1 | 0 | {2,3} |
| 1 | 1 | {2,3} |
| 2 | 3 | {1} |
| 3 | 2 | {1} |
| 1 | 3 | {2} |
| 3 | 1 | {2} |
| 1 | 2 | {3} |
| 2 | 1 | {3} |
We can definitely see a pattern and, even at this point, could greatly reduce the number of selection statement that we need. But now let's look at some simple arithmetic and logical combinations of NotDoor1 and NotDoor2 and see if they reveal even better patterns.
| NotDoor1 | NotDoor2 | NotDoor1 + NotDoor2 | Possible Return Values |
| 0 | 0 | 0 | {1,2,3} |
| 0 | 3 | 3 | {1,2} |
| 3 | 0 | 3 | {1,2} |
| 3 | 3 | 6 | {1,2} |
| 0 | 2 | 2 | {1,3} |
| 2 | 0 | 2 | {1,3} |
| 2 | 2 | 4 | {1,3} |
| 0 | 1 | 1 | {2,3} |
| 1 | 0 | 1 | {2,3} |
| 1 | 1 | 2 | {2,3} |
| 2 | 3 | 5 | {1} |
| 3 | 2 | 5 | {1} |
| 1 | 3 | 4 | {2} |
| 3 | 1 | 4 | {2} |
| 1 | 2 | 3 | {3} |
| 2 | 1 | 3 | {3} |
Notice that just by adding them together, we have almost solved the problem - now we only need to between a few of the cases above. Also notice that in all of the cases where we have to make any kind of a random selection, either the two arguments are the same or at least one of the NotDoor arguments is equal to zero - and that in the cases where we do not have to make any random picks, neither of the NotDoor arguments are equal to zero and they are not equal to each other.. Since we also know that a zero is a logic FALSE and anything else is a logic TRUE, we can exploit this using the logical AND operator:
| NotDoor1 | NotDoor2 | NotDoor1 + NotDoor2 | NotDoor1 && NotDoor2 | Possible Return Values |
| 0 | 0 | 0 | 0 | {1,2,3} |
| 0 | 3 | 3 | 0 | {1,2} |
| 3 | 0 | 3 | 0 | {1,2} |
| 3 | 3 | 6 | 1 | {1,2} |
| 0 | 2 | 2 | 0 | {1,3} |
| 2 | 0 | 2 | 0 | {1,3} |
| 2 | 2 | 4 | 1 | {1,3} |
| 0 | 1 | 1 | 0 | {2,3} |
| 1 | 0 | 1 | 0 | {2,3} |
| 1 | 1 | 2 | 1 | {2,3} |
| 2 | 3 | 5 | 1 | {1} |
| 3 | 2 | 5 | 1 | {1} |
| 1 | 3 | 4 | 1 | {2} |
| 3 | 1 | 4 | 1 | {2} |
| 1 | 2 | 3 | 1 | {3} |
| 2 | 1 | 3 | 1 | {3} |
Now notice that, if we restrict ourselves to the cases where the logical AND is FALSE and take the logical OR of the two computed columns, we find that if the result is FALSE we have to return one of three values while if the result is true we have to return one of two values and the value we can't return is the value of the sum of the two doors.
Looking at the cases where the logical AND resulted in a TRUE result, notice that we can build a direct arithmetic expression for the final return value - since no random element is included - by solving the following:
f(5) = 1
f(4) = 2
f(3) = 3
If you plot these three points, you see that they lie on a straight line with the equation:
f(n) = 6 - n
Let's see if we can't play a similar game with the case where we want to pick one of two doors:
|
NotDoor1 + NotDoor2 |
rand()%2 | Return Value |
| 3 | 0 | {1,2} |
| 3 | 1 | (the other) |
| 2 | 0 | {1,3} |
| 2 | 1 | (the other) |
| 1 | 0 | {2,3} |
| 1 | 1 | (the other) |
Notice that, within a pair, we are free to pick which value we return if rand()%2 is zero as long as we return the other value if it is equal to one. This gives us some flexibility since we can perform some arithmetic or logic on the above values and if we get duplicate results we may still be okay provided we can return the same value for all of those duplicates. So, after playing with this for just a little bit, we can come up with something like:
|
NotDoor1 + NotDoor2 |
rand()%2 |
NotDoor1 + NotDoor2 + rand()%2 |
Return Value |
| 3 | 0 | 3 | 1 |
| 3 | 1 | 4 | 2 |
| 2 | 0 | 2 | 3 |
| 2 | 1 | 3 | 1 |
| 1 | 0 | 1 | 2 |
| 1 | 1 | 2 | 3 |
Using the third column as out independent variable, we need a function that does the following:
f(1) = 2
f(2) = 3
f(3) = 1
f(4) = 2
Notice that, while we don't have a linear mapping, we do have a cyclical one. In particular, note that:
f(1) = 1 + 1 = 2
f(2) = 2 + 1 = 3
f(3) = 0 + 1 = 1
f(4) = 1 + 1 = 2
The first term in each equation above is simply the modulo 3 remainder of the argument. Hence we can write our return value as simply:
door = ( (NotDoor1 + NotDoor2 + rand()%2) % 3 ) + 1;
So our function, at this point, could be implement as follows:
#define NODOOR (0)
#define DOORS (3)
int PickAnyDoorOtherThan(int NotDoor1, int NotDoor2);
{
int door;
switch(NotDoor1 && NotDoor2)
{
case FALSE : switch(NotDoor1 && NotDoor2)
{
case 0: return( 1 + rand()%3 );
case 1: return( 1 + (rand()%2 + NotDoor1 + NotDoor2)%3 );
}
case TRUE : return(6 - (NotDoor1 + NotDoor2));
}
return(-1); /* Should never reach this return statement */
}
If you note the similarities between the expressions in the two case expressions for the nested switch() statement, you can pretty readily reduce them to a single statement by noting that:
a) (3 - (NotDoor1 && NotDoor2)) results in 3 if the && is FALSE and 2 if the && is TRUE.
b) (rand()%3 + ANY_INTEGER)%3 is still a random integer between zero and three.
So we can further "simplify" our code to:
int
PickAnyDoorOtherThan(int NotDoor1, int NotDoor2);
{
if(NotDoor1 && NotDoor2)
return( 6 - (NotDoor1 + NotDoor2) );
else
return( 1 + (rand()%(3-(NotDoor1 && NotDoor2)) + NotDoor1 + NotDoor2)%3 );
return(-1); /* Should never reach this return statement */
}
The above code is quite efficient, although a bit cryptic - hence it should be well documented. It turns out that, if you are willing to push just a bit harder, you can reduce the entire function into a single, very cryptic, expression.
int
PickAnyDoorOtherThan(int NotDoor1, int NotDoor2);
{
return((NotDoor1&&NotDoor2)*(6-(NotDoor1+NotDoor2))
+ !(NotDoor1 && NotDoor2)*(1+(rand()%(3-(NotDoor1&&NotDoor2))+NotDoor1+NotDoor2)%3) );
}