跳转到内容

算法实现/模拟/蒙提霍尔问题/有用性

来自维基教科书,开放世界中的开放书籍
Clipboard

待办事项
本文档是草稿。目前的内容还不错,但需要进行逻辑上的整理。例如,缺少对主题的适当介绍。


第三个版本:是对先前版本的修改,对主持人打开一扇门和玩家进行第二次选择进行了建模,与第一个版本的方式相同。尽管先前版本不是正式的、适当的或完整的模型,但它在计算方面具有相同的效果,因为我们可以检查“win += 1 if choice2 == car”这一行与“win += 1 if choice1 != car”相同,因此 choice2 信息不必要。

事实上,在第一次选择之后,对于一个切换玩家来说,游戏的结果就已经决定了。这意味着完整的模型(第一个、第四个和这个版本)完全没有必要(甚至简洁):如果玩家最初选择了正确的门,那么在切换之后他一定会输(因为他离开了正确的门);如果他选择了错误的门,那么在切换之后他一定会赢(因为正确的门是唯一可以切换到的门——另一扇门是由主持人打开的)。由于我们在检查第一次选择之后已经有了当前游戏的結果,我们不需要通过显式地模拟其他事件来人工地再次计算它:这将是多余的。

所有这些都意味着蒙提霍尔问题的适当、完整的模型可以抽象成一个更简洁和更简单的形式。完整的模型仅仅成为最简单模型的一个实例。第五个版本实现了这样一个最简单的抽象,而第二个和第四个版本则作为中间简化形式。第一个和第三个版本虽然是对场景的适当描述,但在良好的、非冗余抽象方面的计算效率不高。事实上,所有版本从第一个到第四个的重构都导致了第五个版本,因为所有版本都是等价的,只是抽象和冗余程度不同。

另一种表达中间模型与完整模型之间差异的方式是,完整模型从玩家的角度进行模拟:他只有在每局游戏结束时才能知道他最初的选择是否正确。但是,我们可以利用主持人的角度进行更简洁(尽管是抽象的,即不再具体描述原始场景)的模拟:我们可以利用我们可以检查第一次选择是否正确的事实,这样我们就可以提前知道结果,而不必执行任何额外的步骤。这在下面的第四个例子中可能更清楚。

实际上,如果我们认为蒙提霍尔问题可以简化为简单地检查多次从三个元素中取出两个元素并将其与预期元素进行比较的成功率,那么我们可以得出结论,从第一个到第四个的所有版本在某种程度上都是冗余的,即使它们是完全或正确地对问题进行建模。即使是最简单的情况,我们也可以推断出,重复和随机性越多,结果越倾向于接近 2/3。从这个角度来看,任何对蒙提霍尔问题的计算机模拟都是毫无意义的。计算机模拟被用于所有可能的狀態的完整枚举是禁止的或不可能的,[1] 这在蒙提霍尔问题中并非如此。

注意:算法不能简化为一个简单的“打印 2/3”的原因是,输出取决于游戏进行的次数以及正确门或玩家选择的随机性。例如,对于只有 10 局游戏,成功率不太可能在模拟的所有运行中保持在 2/3。

完整的、适当的模型

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

部分模型(主持人的视角)

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

抽象模型

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

Ruby 实现

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}%"

参考文献

[编辑 | 编辑源代码]
华夏公益教科书