Algorithm Implementation/Simulation/Monty Hall problem/Usefulness

From Wikibooks, open books for an open world
Jump to: navigation, search
Clipboard

To do:
This article is a draft. Current content is ok, but it needs to be logically organized. For example, a proper introduction to the subject is missing.

Third version: a modification of the prior version, modeling the host opening a door and the player making the second choice, the same way the first version does. Even though the prior version is not a formal, proper or full modeling, it has the same effect in terms of computing, because we can check that the line "win += 1 if choice2 == car" is the same as "win += 1 if choice1 != car", making the choice2 information unnecessary.

In fact, given the first choice, the game is already decided for a switching player. This means that the full modeling (first, fourth and this version) is not necessary (or even concise) at all: if the player initially chooses the right door, for sure he loses after switching (because he is leaving the right door); if he chooses the wrong door, for sure he wins after switching (because the right door is the only one to switch to - the other one is opened by the host). As we already have the result of the current game after checking the first choice, we don't need to artificially compute it again by explicit simulation of the other events: it would be simply redundant.

This all means that the proper, full modeling of the Monty Hall problem can be abstracted to a more concise and simpler form. The full modeling becomes just an instance of the simplest one. Fifth version implements such a simplest abstraction, while the second and fourth ones work as intermediary simplifications. First and third versions even though proper descriptions of the scenario, are not computationally efficient in terms of good, non-redundant abstraction. In fact, refactoring of all the versions from first to fourth leads to the fifth one, because all versions are equivalent, differing only in the levels of abstraction and redundancy.

Another way to express the difference from the intermediary to the full modelings is that the full ones run a simulation from the player's perspective: he will only know whether his initial choice was right or not in the end of each game. However, we can run a more concise (even though abstracted, that is, not specifically describing the original scenario anymore) simulation using the host's perspective: we can take advantage of the fact that we can check if the first choice is correct, so that we can already know the result, without having to execute any additional steps. This may become clearer in the fourth example below.

Actually, if we think that the Monty Hall problem can be reduced to simply checking the success rate of many times picking up two elements out of three and checking them against an expected one, we can conclude that all the versions from first to fourth are redundant in some level, even if they are modeling the problem completely or correctly. Even in the simplest form, we can deduce that the more repetition and randomness we have, the more closer to 2/3 the result is inclined to be. From this point of view, any computer simulation of Monty Hall problem is pointless at all. Computer simulations are used where a complete enumeration of all possible states would be prohibitive or impossible[1], which is not the case of Monty Hall problem.

Note: the reason why the algorithms can't be reduced to a single "print 2/3" is because the output depends on the number of times the game is played, and on the randomness of either the right door, or the player's choice. For example, for only 10 games it is unlikely that the success rate will keep at 2/3 for all runnings of the simulation.


Full, proper modeling

wins = 0
car = 1
many times do
    choice1 = rand(1..3)     
    host = (1, 2, 3) - (car, choice1)
    choice2 = (1, 2, 3) - (host, choice1)    
    if choice2 == car   
        wins += 1  
end


Partial modeling (host's perspective)

wins = 0
car = 1 
many times do
    choice = rand(1..3)
    if choice != car    
        wins += 1
end


Abstracted modeling

wins = 0
many times do
    if rand(1..3) in 1..2
        win+= 1 
end


Ruby implementations

car = wins = 0
many = 100000
 
many.times do
    choice1 = rand(3)
    host_opts = [0, 1, 2] - [choice1, car]
    choice2 = [0, 1, 2] - [choice1, host_opts.first]
    wins += 1 if choice2 == [car] 
end
 
puts "#{(wins * 100) / many}%"



car = wins = 0
many = 1000 * 1000
 
many.times do |game|
    progress = ((game + 1) * 100) / many
    print("\b\b\b#{progress}%") 
    choice = rand(3) 
    wins += 1 unless choice == car    
end
 
puts "#{(wins * 100) / many}%"



many, wins = 1000 * 1000, 0
many.times { wins+= 1 if [0, 1].include? rand(3) }
puts "#{(wins * 100) / many}%"

References[edit]