パターン認識と機械学習 上を読み進める前に確率の基礎がわかる本を探したら、プログラミングのための確率統計という本がわかりやすそうなので読み始めた。
例題として
モンティ・ホール問題 - Wikipedia
がでてきたので、理解を深めるために(というか興味本位で)
モンテカルロ法でモンティ・ホール問題を解いてみた。
次のようなCのプログラムで、10万回試行して、
プレイヤーが選択を変更しなかった場合と
変更した場合の正解の確率を計算した。
#include <stdio.h> #include <Windows.h> bool game(bool is_change) { // 正解の選択 int correct = rand() % 3; // プレイヤーの最初の選択 int pick = rand() % 3; // 司会者が開く扉 int opendoor; if (correct == pick) { // プレイヤーが正解だった場合 opendoor = (correct + rand() % 2 + 1) % 3; } else { // プレイヤーが不正解だった場合 opendoor = 3 - (correct + pick); } if (pick == correct) { return !is_change; } else { return is_change; } } double try_many_time(bool is_change) { const int max_count = 100000; int correct_count = 0; for (int i = 0; i < max_count; i++) { correct_count += game(is_change) ? 1 : 0; } // 正解率 double rate = double(correct_count) / max_count; return rate; } int main() { unsigned int seed = GetTickCount(); srand(seed); double rate; // プレイヤーが変更しなかった場合 rate = try_many_time(false); printf("correct rate if not change => %.5f\n", rate); // プレイヤーが変更した場合 rate = try_many_time(true); printf("correct rate if change => %.5f\n", rate); return 0; }
実行結果は、
プレイヤーが選択を変更しなかった場合:0.33011
プレイヤーが選択を変更した場合 :0.66835
プレイヤーが選択を変更しなかった場合の正解率は約1/3
プレイヤーが選択を変更した場合の正解率は約2/3という結果が得られた。
なお、モンテカルロ法で、C言語のrand()を使うのは本当は良くないらしい。
今回は精度は大して求めてないのでrand()を使用した。