Sunday, June 23, 2013

The Monty Hall Problem

OK. This is an entirely non-Infosec related post, but it was a fun thing to do this weekend so I thought I'd post it.

I was discussing the "Monty Hall Problem" with a friend last week and despite my attempts at explaining why the "Always Switch Doors" technique gives you the best chance of winning he simply had a gut reaction that there must be some flaw in the explanation. After all, this is such a non-intuitive answer that mathematicians debated for years over the solution. Although there now exist formal mathematical proofs of the solution, that's not very fun and doesn't give me an excuse to play in PowerShell.

So, I decided to write a game simulation.

For those not familiar with the problem, it goes like this:

On the old game show, "Let's Make a Deal," the host, Monty Hall, would present a contestant with three doors. The contestant -we'll call her Betty- wins whatever is behind the door she chooses. One door hides a good prize and the other two doors hide booby prizes. For ease of explanation, we'll use the example of a car and two goats.

Betty chooses the door she thinks the car is behind. Monty Hall then reveals what's behind one of the other doors -he always reveals one with a goat. Betty is left with two doors to choose from. Monty Hall then asks Betty if she wants to switch her choice to the other door or stick with her original choice.

At first glance, it appears to be a 50/50 proposition. The car is either behind one door or the other. Because of that, contestants tend to stick with their original choice.

The thing is, do you really think the producers of the show would willingly host a game they thought they had a 50/50 chance of losing? Of course not -for the exact same reason that the odds of every game in a casino are in the house's favor.

The real odds are ~33% if you always stick with the original door and ~66% if you always switch doors. That's because, when you made your original choice, you only had a 33.3(repeating)% chance of being correct and a 66.6(repeating)% chance of being wrong. You're not choosing between Door 1 and Door 3, for example; you're choosing between Door 1 and the combination of Door 2 and Door 3.

It becomes more obvious if you think about the same game being played with 100 doors. Betty chooses a door, then Monty Hall reveals 98 doors with goats behind them. Betty's original choice only had a 1% chance of being correct, but all the other doors put together have a 99% of holding the car. Do you think she should switch her choice to the remaining door? Remember, it's her original choice up against the totality of other doors, not just the one that remains hidden.

The simulation script below can run as many iterations as you choose (by modifying the $numrounds variable at the top of the script). Playing the game 1000 times, you can definitely see the pattern. If you never switch, the simulation demonstrates your winning percentage is ~33%. If you always switch, you win ~66% of the time. Interestingly, if you randomly choose whether to switch or not, your odds are actually 50/50. That's better than always sticking with the original choice, but not the best odds you can achieve.

Summary of Results:

Play Mode: NeverSwitch
Rounds: 1000
Switches: 0
Switch Percentage: 0 %
Wins: 323
Losses: 677
Win Percentage: 32 %

Play Mode: AlwaysSwitch
Rounds: 1000
Switches: 1000
Switch Percentage: 100 %
Wins: 660
Losses: 340
Win Percentage: 66 %

Play Mode: RandomlySwitch
Rounds: 1000
Switches: 468
Switch Percentage: 47 %
Wins: 479
Losses: 521
Win Percentage: 48 %

If you don't believe the results, check out the code below and run the simulation yourself.

Here's the process the simulation goes through in non-code speak.

The script is run in one of three modes; Never Switch, Always Switch, and Randomly Switch. This is selected by modifying the $mode variable at the top of the script.

1. A car and two goats are randomly assigned to each of three doors.
2. The contestant randomly selects a door.
3. Monty Hall reveals one of the remaining doors; it's always a goat.
4. The contestant decides whether to switch his choice.
     a. If running in "Never Switch" mode, he sticks to his guns and keeps the first choice.
     b. If running in "Always Switch" mode, he switches his choice to the remaining door.
     c. If running in "Randomly Switch" mode, he randomly decides whether to switch his choice.
5. If the door he ultimately chose contains the car he wins. If not, he loses.
6. The details of the game round are written to a CSV file.
7. The simulation repeats steps 1 - 6 as many times as specified.
8. A summary of the entire run is displayed on-screen and also written to a TXT file.

The script definitely could be made more elegant but it was just for fun so there wasn't any point in putting TOO much work into it.

Have fun!

#Set $numrounds to how many rounds you want to run
$numrounds = 1000

#Set $mode = "NeverSwitch" to run as "Never Switch My Choice"
#Set $mode = "AlwaysSwitch" to run as "Always Switch My Choice"
#Set $mode = "RandomlySwitch" = 2 to run as "Randomly Switch My Choice"
$mode = "NeverSwitch"

# Set initial variables and stuff
$content = "C","G","G"
$doors = "","",""
$possiblechoices = 0,1,2

$detailfile = "c:\temp\MontyHallSim-Details-$mode-$numrounds.csv"
$summaryfile = "c:\temp\MontyHallSim-Summary-$mode-$numrounds.txt"

    "NeverSwitch" {$shouldISwitch = $false}
    "AlwaysSwitch" {$shouldISwitch = $true}
    "RandomlySwitch" {$shouldISwitch = $true,$false}
} #End switch($mode)
$i = 1
$wins = 0
$losses = 0
$switches = 0
$percentwins = 0
$percentswitches = 0

add-content $detailfile "Round,Door1,Door2,Door3,Choice,ChoiceContent,Revealed,RevealedContent,NewChoice,NewChoiceContent,Mode,DidISwitch,Result,TotalSwitches,SwitchPercentage,TotalWins,TotalLosses,WinPercentage"

#Run the simulation
while($i -le $numRounds){
    $doors[0] = $content | get-random

        "C" {$doors[1] = "G"
            $doors[2] = "G"}
        "G" {$doors[1] = $content | get-random
                "C" {$doors[2] = "G"}
                "G" {$doors[2] = "C"}
            } #End Switch($doors[1])
    } #End Switch($doors[0])
    $door1 = $doors[0]
    $door2 = $doors[1]
    $door3 = $doors[2]

    $choice = $possiblechoices | get-random
    $choicecontent = $doors[$choice]
    $remaining = $possiblechoices | where{$_ -ne $choice}
    $goatFound = 0
    $remaining | foreach{
        if($doors[$_] -eq "G" -and $goatFound -eq 0){
            $revealed = $_
            $goatfound = 1
            $revealedcontent = $doors[$_]
        } # End ($doors[$_] -eq "G" -and $goatFound -eq 0)
    } #End foreach
    $willSwitch = $shouldISwitch | get-random
        $false {
            $DidISwitch = "No"
            $newchoice = $choice
            $newchoicecontent = $doors[$choice]}
        $true {
            $DidISwitch = "Yes"
            $remaining | foreach{
                if($_ -ne $revealed){
                    $newchoice = $_
                    $newchoicecontent = $doors[$_]
                } # End if($_ -ne $revealed)}
            } #End Foreach
            $switches = $switches + 1
    } #End switch($willSwitch)
    if($newchoicecontent -eq "C"){
        $result = "Win"
        $wins = $wins + 1
        $result = "Lose"
        $losses = $losses + 1
    } #End if($newchoicecontent -eq "C")
    $percentwins = $wins / $i
    $percentwins = "{0:P0}" -f $percentwins
    $percentswitches = $switches / $i
    $percentswitches = "{0:P0}" -f $percentswitches
    add-content $detailfile "$i,$door1,$door2,$door3,$choice,$choicecontent,$revealed,$revealedcontent,$newchoice,$newchoicecontent,$mode,$DidISwitch,$result,$switches,$percentswitches,$wins,$losses,$percentwins"
    $i = $i + 1
} #End while($i -le $numRounds)

# Display Results and Write to Summary file
"Play Mode: $mode"
add-content $summaryfile "Play Mode: $mode"
"Rounds: $numrounds"
add-content $summaryfile "Rounds: $numrounds"
"Switches: $switches"
add-content $summaryfile "Switches: $switches"
"Switch Percentage: $percentswitches"
add-content $summaryfile "Switch Percentage: $percentswitches"
"Wins: $wins"
add-content $summaryfile "Wins: $wins"
"Losses: $losses"
add-content $summaryfile "Losses: $losses"
"Win Percentage: $percentwins"
add-content $summaryfile "Win Percentage: $percentwins"

No comments:

Post a Comment

One rule: Don't be a jerk.

You can correct me or other commenters all you want, just be cool about it. Of course, I mean "cool" in the nerdiest way possible.