三门问题的程序解与解释

昨天在和同事吃饭时，同事提到了一个有趣的问题：

假设有三扇门，其中一扇门后面有奖，还有一个主持人，主持人知道哪扇门后面有奖。
你先随机选择一扇门，然后主持人会帮你打开另外两扇门中的一扇，可以确定的是，打开的这扇门肯定没有奖品。
现在，你有一个改变主意的机会，即在剩下的两扇门中，你可以坚持选择你本来选中的这扇门，也可以改变主意选择另外的一扇门。

问：你改变主意和不改变主意，中奖的概率分别是多少？

PS：我后来查了一下，这个问题叫做Monty Hall problem，也叫“三门问题”，最初来自于美国的一个电视游戏节目。

开始的时候，我一直觉得改变主意和不改变主意的概率是一样的，是一个二选一的问题，所以都是二分之一。

于是，后来，我写了个小程序验证：

#include <iostream>
#include <random>

typedef std::mt19937 EngineType;
typedef std::uniform_int_distribution<std::mt19937::result_type> GeneratorType;

bool GetIt(EngineType& engine, const GeneratorType& generator3, bool change) {
    int correct_door = generator3(engine);
    int first_choice = generator3(engine);

    if(change) {
        if(first_choice != correct_door) return true;
        else return false;
    } else {
        if(first_choice == correct_door) return true;
        else return false;
    }
}

int main() {
    EngineType eng;
    eng.seed(std::random_device()());
    GeneratorType dist3(1, 3);
    int change_sum = 0, unchange_sum = 0;
    long loop = 100000000;
    for(long i = 0; i < loop; ++i) {
        if(GetIt(eng, dist3, true))
            ++change_sum;
        if(GetIt(eng, dist3, false))
            ++unchange_sum;
    }

    std::cout << "Testing times: " << loop << std::endl;

    std::cout << "Always change choice, hit: " << change_sum
              << ", percentage: " << static_cast<double>(change_sum) / loop
              << std::endl;

    std::cout << "Always unchange choice, hit: " << unchange_sum
              << ", percentage: " << static_cast<double>(unchange_sum) / loop
              << std::endl;
}

程序中 GetIt() 函数用来模拟这个生成门以及选择门的过程，在主函数 main() 中跑一亿次之后进行结果统计，最后打印中改变主意的中奖情况，以及不改变主意的中奖情况。

由于涉及随机数，所以每次程序输出都不一样，下面是其中一次的输出结果：

Testing times: 100000000
Always change choice, hit: 66663376, percentage: 0.666634
Always unchange choice, hit: 33338904, percentage: 0.333389

可以清楚地看到，改变主意大概占了66.6%，不改变主意大概占了33.3%，分别接近2/3和1/3。

那么，为什么分别是2/3和1/3，而不是各占百分之五十呢？其实程序代码中的逻辑已经很清楚地解释了这个问题，来看程序中 GetIt() 函数的关键部分：

int correct_door = generator3(engine);
int first_choice = generator3(engine);

if(change) {
    if(first_choice != correct_door) return true;
    else return false;
} else {
    if(first_choice == correct_door) return true;
    else return false;
}

其中 generator3 是用来产生区间为 [1, 3] 的随机数， correct_door 表示有奖的门牌号， first_choice 表示第一次选择的门牌号， change 布尔变量表示在主持人打开一扇门后，是否改变主意， return true 表示中奖， return false 表示不中奖。

把中奖情况分为下面两种情况考虑：

我们改变主意(change == true)，然后中奖；
我们不改变主意(change == false)，然后中奖。

对于第一种情况，程序必须进入if分支中的if分支，条件是第一次没有猜中，很显然第一次没有猜中的概率是2/3；
对于第二种情况，程序必须进入else分支中的if分支，条件是第一次要猜中，事实上第一次没有猜中的概率是1/3。

个人觉得，这个问题最关键的是： 在主持人打开某扇门后，我们选择变或者不变，并不是一个二选一的概率问题，而是一个根据已有事实进行逻辑推断的问题。 就像上面程序所表示的一样，我们并没有用类似于 generator2 这样的函数来产生随机数表示是否改变主意，而是用 if...else... 分支来进行的分析。

所以，结果就是这样：改变主意，中奖的概率会是不改变主意的两倍。但现实中，我更相信，中奖是要靠人品的，公司的年终晚会也不远了，赶紧努力攒攒人品。。