CathyInBlue
Grandmaster
I don't know what got me thinking about this again, but like so many influences, it got into my brain and wouldn't get back out unless exorcised through intense cogitation. We all know it, even if only vaguely. The problem goes something like this...
You're on the game show Let's Make a Deal, with your host, Monty Hall. You're presented with three doors, labelled 1, 2, and 3. Behind one of the doors is a new car, or bedroom set, or trip to Aruba, or whatever. It's a desirable prize. Behind the other two are goats. Might be of the barnyard variety, or a fake, wrecked car, or some other generic whammy, or no-prize. Your task is to pick one of the doors, the one you think leads to the prize.
After you've made your selection, with a one in three chance of selecting the car immediately, Monty selects one of the other doors not chosen and reveals the goat behind it. Here's where the fun begins. The question now is whether to take advantage of the opportunity Monty gives you to change your selection to the other door not yet revealed, or to stand pat with the choice you made originally.
I'd always said that it doesn't matter, because you have information for the second choice you didn't have for the first one, namely that the car was definitely NOT behind the door Monty revealed, the second choice is disconnected from the first one and is a brand new choice with its own probabilities, namely that the car is either A) behind the door you already chose, and you should stand pat, or B) behind the door you haven't chosen, and so you should change your selection. A or B, both with equal probability (1/3 each in the first case, 1/2 each in the second). Since both actions, staying, changing, had equal probability of being the action which yields the win of the car, it doesn't matter which action is chosen. The probabilities don't mitigate for a preference for either choice.
I was wrong.
I don't know specificly how I was wrong, why I was wrong, or how to correct myself so that I'm right, but I've come to accept that I was, indeed wrong.
Reading the Wikipedia page on the Monty Hall Problem, I saw one explanation of the solution that just went with straight forward empiracism. A Monte Carlo simulation of 30 games with completely random choices. Of the times the player won, twice as many wins came as the result of changing as came as a result of staying with the original choice. "No way," I thought. I gotta do this myself.
So I did.
Yeah, my programming language of choice is the Bourne-Again Shell. Big whoop! Wanna fight about it? I even went to the trouble of making it count the doors starting from 1, instead of from the computer-friendly 0, and to make it generic for any number of doors, not just the default of 3.
The code is straight forward and there are no errors with regard to the decisions that have to be made and how they are permitted to be made. Some examples of the output of the program:
The Monte Carlo simulation from the Wikipedia article only used 30 games. I figured if I'm gonna convince myself of this, I need to do just a few more than that. I did it for a million, carved off just the last summary line, which classifies the nature of the game simulated, and then collate the results and count the number of each class of game that randomly occurred... a million times.
I've been so, so wrong. I just don't know how.
You're on the game show Let's Make a Deal, with your host, Monty Hall. You're presented with three doors, labelled 1, 2, and 3. Behind one of the doors is a new car, or bedroom set, or trip to Aruba, or whatever. It's a desirable prize. Behind the other two are goats. Might be of the barnyard variety, or a fake, wrecked car, or some other generic whammy, or no-prize. Your task is to pick one of the doors, the one you think leads to the prize.
After you've made your selection, with a one in three chance of selecting the car immediately, Monty selects one of the other doors not chosen and reveals the goat behind it. Here's where the fun begins. The question now is whether to take advantage of the opportunity Monty gives you to change your selection to the other door not yet revealed, or to stand pat with the choice you made originally.
I'd always said that it doesn't matter, because you have information for the second choice you didn't have for the first one, namely that the car was definitely NOT behind the door Monty revealed, the second choice is disconnected from the first one and is a brand new choice with its own probabilities, namely that the car is either A) behind the door you already chose, and you should stand pat, or B) behind the door you haven't chosen, and so you should change your selection. A or B, both with equal probability (1/3 each in the first case, 1/2 each in the second). Since both actions, staying, changing, had equal probability of being the action which yields the win of the car, it doesn't matter which action is chosen. The probabilities don't mitigate for a preference for either choice.
I was wrong.
I don't know specificly how I was wrong, why I was wrong, or how to correct myself so that I'm right, but I've come to accept that I was, indeed wrong.
Reading the Wikipedia page on the Monty Hall Problem, I saw one explanation of the solution that just went with straight forward empiracism. A Monte Carlo simulation of 30 games with completely random choices. Of the times the player won, twice as many wins came as the result of changing as came as a result of staying with the original choice. "No way," I thought. I gotta do this myself.
So I did.
Code:
#!/bin/bash
# Monty Hall Problem
declare -A Door
declare -a Door_indices
declare -i num_doors=${num_doors:-3}
declare -i car pick reveal
echo "Monty Hall Problem with $num_doors doors."
[[ ${num_doors} -lt 3 ]] && echo "Need at least 3 doors." >&2 && exit 0
# Set all doors to goats.
for i in $(seq ${num_doors}); do
Door[${i}]='goat'
done
# Except the one with the car.
car=$((RANDOM % ${#Door[@]} + 1))
Door[${car}]='car'
# Pick a random door.
pick=$((RANDOM % ${#Door[@]} + 1))
# Reveal a random door, not the one picked, or the one with the car.
Door_indices=(0 "${!Door[@]}")
unset Door_indices[${pick}]
unset Door_indices[${car}]
Door_indices=("${Door_indices[@]:1}")
reveal=${Door_indices[$((RANDOM % ${#Door_indices[@]}))]}
# Flip a coin to decide whether to switch.
switch=$((RANDOM % 2))
echo "Picked door ${pick}."
echo "Revealed door ${reveal} to have a ${Door[${reveal}]}."
case ${switch} in
0) echo 'Staying with first door.' ;;
1)
# Pick another random door, not the first one picked, or the one revealed.
Door_indices=(0 "${!Door[@]}")
unset Door_indices[${pick}]
unset Door_indices[${reveal}]
Door_indices=("${Door_indices[@]:1}")
pick=${Door_indices[$((RANDOM % ${#Door_indices[@]}))]}
echo "Switching to door $pick."
;;
esac
# Report the out doors.
for i in $(seq ${num_doors}); do
echo -n "Door ${i} hid a ${Door[${i}]}. "
done
echo
# Case summary.
case ${switch} in
0) if [ ${Door[${pick}]} == 'car' ]; then
echo 'Case A: Stayed and won.'; else
echo 'Case B: Stayed and lost.'; fi ;;
1) if [ ${Door[${pick}]} == 'car' ]; then
echo 'Case C: Switched and won.'; else
echo 'Case D: Switched and lost.'; fi ;;
esac
The code is straight forward and there are no errors with regard to the decisions that have to be made and how they are permitted to be made. Some examples of the output of the program:
Code:
Monty Hall Problem with 3 doors.
Picked door 2.
Revealed door 3 to have a goat.
Staying with first door.
Door 1 hid a goat. Door 2 hid a car. Door 3 hid a goat.
Case A: Stayed and won.
Code:
Monty Hall Problem with 3 doors.
Picked door 2.
Revealed door 3 to have a goat.
Staying with first door.
Door 1 hid a car. Door 2 hid a goat. Door 3 hid a goat.
Case B: Stayed and lost.
Code:
Monty Hall Problem with 3 doors.
Picked door 3.
Revealed door 2 to have a goat.
Switching to door 1.
Door 1 hid a car. Door 2 hid a goat. Door 3 hid a goat.
Case C: Switched and won.
Code:
Monty Hall Problem with 3 doors.
Picked door 3.
Revealed door 1 to have a goat.
Switching to door 2.
Door 1 hid a goat. Door 2 hid a goat. Door 3 hid a car.
Case D: Switched and lost.
Code:
$ for i in $(seq 1000000); do monty | tail -1 ; done | sort | uniq -c
166885 Case A: Stayed and won.
333611 Case B: Stayed and lost.
333329 Case C: Switched and won.
166175 Case D: Switched and lost.
Last edited: