三门问题
三门问题,亦称为蒙提霍尔问题,出自美国的电视游戏节目Let’s Make a Deal。问题的名字来自该节目的主持人蒙提·霍尔(Monty Hall)。游戏规则是:参赛者会看见三扇关闭了的门,其中一扇后面有一辆汽车,选中后面有车的那扇门就可以赢得该汽车,而另外两扇门后面则各藏有一只山羊。当参赛者选定了一扇门,但未去开启它的时候,节目主持人会开启剩下两扇门的其中一扇,露出其中一只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。
关于换不换的问题,就是计算换了之后能不能增加获得汽车的概率。答案是可以, 不换的话获得汽车的概率是1∶3,但是换了之后的概率将提高到2∶3。关于理论上的证明有很多种方式,这里就不再一一介绍。下面直接看怎么用Python来模拟这个过程并得出结论,在这之前建议有点思路的读者先自己尝试一下看能不能写出来,这里给出一个参考程序。
首先是进行一次游戏,根据规则和做出的策略来看是否能赢。
# 计算在第二次采取不同策略时,是否在游戏中获胜(选中汽车)
def game(strategy):
win = 0
# 假定汽车在0号门(参赛者并不了解这一事实)
doors = [0, 1, 2]
# 因为事先并不知道任何信息,所以第一次随机选取一扇门
first_choice = rnd.choice(doors)
# 根据第一次的选择情况的不同,第二次决策面临两种不同的备选组合
# 如果第一次选择了0号门,那么在主持人打开另外两扇门中的其中一扇门后
# 第二次将在0号门和未打开的空门(1或 2)中作出选择
if first_choice == 0:
doors = [0, rnd.choice([1, 2])]
# 如果第一次没有选中0,那么此时被打开的必然是另一扇有山羊的门,那么
# 在第二次选择时,将在0和自己现在所处的门(first_choice)作出选择
else:
doors = [0, first_choice]
# 采取不同的策略进行第二次选择
# 保持原来位置不变
if strategy == 'stick':
second_choice = first_choice
# 排除一扇空门后,放弃原来的选择,直接选择另一扇门
else:
doors.remove(first_choice)
second_choice = doors[0]
# 记得,奖品在0号门
if second_choice == 0:
win = 1
return win
之后进行一定次数的模拟,并计算不同策略获胜的概率,如下所示。
# 对特定策略进行的一定次数的模拟
def MC(strategy, times):
wins = 0
for i in range(times):
wins += game(strategy)
# 计算获奖的概率值
p = wins / times
print('第二次选择采用' + strategy + '方法,
获奖的概率为:' + str(p) + '(模拟次数为' + str(times) + ')')
模拟10000次,如下所示。
if __name__ == '__main__':
MC('stick', 10000)
MC('switch', 10000)
运行输出如下。
第二次选择采用stick方法,获奖的概率为:0.3438(模拟次数为10000)
第二次选择采用switch方法,获奖的概率为:0.6658(模拟次数为10000)
可以清楚地看到转换的概率提升到了三分之二。该程序再次见证了蒙特卡罗方法的强大,我们不需要去理解问题本身深刻的机理,只需要将现象在一定的规则下进行尽量多的随机模拟,即可得到解决问题的办法。Python还可以利用现有的第三方库来解决较为复杂的优化问题,下面介绍LP、QP问题的解决。