Use cryptographically secure pseudo-random numbers to verify that the solution to the Monty Hall problem is not 50%

What is the Monty Hall problem?

The Monty Hall problem is a problem of probability as follows.

There are three closed doors.

Beyond one of the doors is a new prize car, and beyond the other two doors is a goat, which means lost. Players can get a new car by opening the door with the new car.

When the player chooses one door, the moderator Monty Hall opens one of the remaining two doors with the goat to show the goat.

Here the player can change from the first door he chooses to another door that hasn't been opened yet.

Now, should the player change the door? (Which one is more likely to hit a new car?)

Monty Hall Problem-Wikipedia

Those who thought, "Since the moderator opened the door of the lost goat, there are only two doors left, and the probability is 1/2 with or without changing the door?" Actually, this is an incorrect answer.

The correct answer is, "The more you change the door, the more likely you are to win." If you do not change the door, you have a 1/3 chance of hitting, and if you change the door, you have a 2/3 chance of hitting.

The following video explains why this is the result.

Twitter survey has surprising results! "Monty Hall Problem Modified Version"

Let's verify

Now, even if you know the answer, some may still not be convinced that it really is.

So, I tried 1 million times with and without changing the door in the middle, and wrote a program to verify whether the result really meets that probability.

If you want to know only the result, please jump to "Verification result".

program

The program I actually wrote is as follows. Implemented in Ruby.

monty_hall_problem.rb


# frozen_string_literal: true

require 'optparse'
require 'securerandom'

options = {}
OptionParser.new do |opt|
  opt.on('-d NUMBER', '--doors=NUMBER') { |v| options[:doors_count] = v }
  opt.on('-t NUMBER', '--trials=NUMBER') { |v| options[:trials] = v }
  opt.parse!(ARGV)
end

DOORS_COUNT = options[:doors_count].to_i >= 3 ? options[:doors_count].to_i : 3
TRIALS      = options[:trials].to_i      >= 1 ? options[:trials].to_i      : 100

def main
  correct_count = { changed: 0, never: 0 }

  TRIALS.times do
    correct_count[:changed] += 1 if try(changed: true)
  end

  TRIALS.times do
    correct_count[:never] += 1 if try(changed: false)
  end

  puts "Number of doors:  #{DOORS_COUNT} doors"
  puts "Number of trials: #{TRIALS} times each"
  puts
  puts "Changed: #{correct_count[:changed]} times (Actual: #{((correct_count[:changed].to_f / TRIALS.to_f) * 100).round(2)}%, Expected: #{(((DOORS_COUNT - 1).to_f / DOORS_COUNT.to_f) * 100).round(2)}%)"
  puts "Never:   #{correct_count[:never]} times (Actual: #{((correct_count[:never].to_f / TRIALS.to_f) * 100).round(2)}%, Expected: #{((1.0 / DOORS_COUNT.to_f) * 100).round(2)}%)"
end

def try(changed:)
  doors = Array.new(DOORS_COUNT, false)
  doors[SecureRandom.random_number(DOORS_COUNT)] = true
  first_choice = SecureRandom.random_number(DOORS_COUNT)

  doors = reveal(doors, first_choice)

  doors[second_choice(doors, first_choice, changed: changed)]
end

def reveal(doors, first_choice)
  if doors[first_choice] # the first choice is correct
    leftover = nil

    loop do
      leftover = SecureRandom.random_number(DOORS_COUNT)
      break if leftover != first_choice
    end

    doors.map.with_index { |door, index| door if door || index == leftover }
  else # the first choice is incorrect
    doors.map.with_index { |door, index| door if door || index == first_choice }
  end
end

def second_choice(doors, first_choice, changed:)
  return first_choice unless changed

  second_choice = nil
  doors.each_with_index do |door, index|
    unless door.nil? || index == first_choice
      second_choice = index
      break
    end
  end

  second_choice
end

main

The original Monty Hall problem is 3 doors, but it is a program like [^ 1] that can be verified even if it is 10 doors or 100 doors. DOORS_COUNT represents the number of doors. The default is 3.

[^ 1]: If there are 100 doors, the moderator will open the door with the remaining 98 goats after the player chooses one.

You can also change the number of trials. TRIALS represents the number of trials. The default is 100.

You can change the number of doors by putting -d NUMBER in the argument. NUMBER is a number. You can also change the number of trials by entering -t NUMBER. For example, -t 100000 will try 100,000 times.

main It is a method that outputs the result of trying several times separately when the door is changed and when it is not changed in the middle.

Put the result (the number of hits subtracted) in correct_count. correct_count [: changed] is the number of hits when the door is changed in the middle, and correct_count [: never] is the number of hits when the door is not changed in the middle.

try The method to try. If you pull the winning door, it will return true, and if you pull the lost door, it will return false.

Prepare an array doors with all elements false, and randomly put true somewhere in it. true is the door with the new car and false is the door with the goat.

Randomly put the possible subscript values ​​of the array doors into first_choice. This is the state in which the player has selected one door. Of course, the player doesn't know the answer, so he gets the value randomly.

reveal A method in which the moderator opens the remaining door with the goat.

Returns an array with all but the door chosen by the player (the element specified by first_choice) and the door with the new car (the element of true) as nil.

However, if the player has selected the door with the new car (the element of true) from the beginning, it does not matter if all the doors are opened, so in that case the unselected doors (all) Randomly choose one of the (goat doors) doors, leave that element alone, and leave all other elements (except, of course, the player's chosen door) as nil.

The element containing nil means the [^ 2] door where the moderator has revealed that there is a goat (missing).

[^ 2]: "reveal" means "reveal".

second_choice A method that returns the door the player chooses for the second time. Returns the possible subscript values ​​of the array doors.

The changed received as an argument can be true or false. true means that you changed the door in the middle, and false means that you did not change the door.

If you do not change the door, it is the same as first_choice, so the value of first_choice is returned as it is.

If you change the door, it is an element that is not nil and returns a different value than first_choice. After the moderator opens the door with the goat, there are only two doors, one that he chose first and one that hasn't been opened yet, so it's unique to change.

inspection result

Let's actually verify it. I will try it a million times.

$ ruby monty_hall_problem.rb -t 1000000
Number of doors:  3 doors
Number of trials: 1000000 times each

Changed: 666764 times (Actual: 66.68%, Expected: 66.67%)
Never:   333181 times (Actual: 33.32%, Expected: 33.33%)

The table below is easy to understand.

If you change the door on the way If you do not change the door on the way
Number of hits(1 million times) 666,764 times 333,181 times
Correct answer rate(Round to the third decimal place) 66.68% 33.32%
Real probability(Round to the third decimal place) 66.67% 33.33%

If you changed the door, there was almost a 2/3 chance that you would get it right, and if you didn't change the door, you had a good chance of getting it right about 1/3.

So, it turns out that the probability of 50% with or without changing the door is wrong, and that changing it does increase the accuracy rate.

Bonus: Reasons for using cryptographically secure pseudo-random numbers

There are two types of most languages: (just) pseudo-random numbers and cryptographically secure pseudo-random numbers.

Ruby, of course, has both.

Pseudo-random number


irb(main):001:0> rand
=> 0.3204722194100945

Cryptographically secure pseudo-random numbers


irb(main):001:0> require 'securerandom'
=> true
irb(main):002:0> SecureRandom.rand
=> 0.6596803273103891

In this program, we used cryptographically secure pseudo-random numbers (SecureRandom.random_number) instead of just pseudo-random numbers. The reason is ** [^ 3] because there is a possibility of bias if it is just a pseudo-random number.

That doesn't mean that cryptographically secure pseudo-random numbers are truly unbiased random numbers, but because they are used in cryptography, they are unpredictably unbiased random numbers. That said.

This time, it was a verification to find the mathematical probability, so I decided that it would be better to use random numbers that are not biased as much as possible, so I used cryptographic pseudo-random numbers.

Reference: How to make really safe random numbers in each language

[^ 3]: Pseudo-random numbers-Wikipedia

Recommended Posts

Use cryptographically secure pseudo-random numbers to verify that the solution to the Monty Hall problem is not 50%
About the solution to the problem that the log of logback is not output when the web application is stopped
Use stream to verify that SimpleDateFormat is thread unsafe
How to solve the problem that the website image is not displayed after deploying to heroku on Rails 5
About the problem that the image is not displayed after AWS deployment
How to fix the problem that Aptana Studio does not start
After verifying the Monty Hall problem with Ruby, a story that I could understand well and did not understand well
I want to solve the problem that JS is not displayed properly unless reloaded when transitioning with Turbolinks: link_to
A quick look at the Monty Hall problem
How to fix the problem that the upper half is cut off when using UITabBar