モンティ・ホール問題で遊ぶ
有名な数学問題なので知ってる人も多いと思うけど一応解説すると，「モンティ・ホール問題」というのは Monty Hall という人が司会をつとめるアメリカの番組 “Let’s make a deal” 内で行われたゲームに関する問題である。
簡単にルールを紹介する。
- プレイヤーの前に閉まった3つのドアがある。1つのドアの後ろには景品の新車が，2つのドアの後ろには（はずれを意味する）ヤギがいる
- プレイヤーが1つのドアを選択
- 司会者が残りのドアのうちヤギがいるドアを開けてヤギ（＝はずれ）を見せる
- プレイヤーは最初に選んだドアを変更してもよい
このときプレイヤーは最初に選択したドアを変更したほうが得（つまり当たる確率が高い）かどうか，というのが「モンティ・ホール問題」のあらましである。
この問題について「ドアを変更したほうが当たる確率が高い」と示した女性がいて，これに対して猛烈な反発が起こり大論争になったらしい（女性蔑視な発言もあったそうで，今なら確実にハラスメント案件だよなw）。
ポイントは3番目の「はずれのドアを開ける」部分で（司会者はどのドアが当たりかあらかじめ知っている），残りの2つのドアのどちらかが当たりなのだからというので多くの人が直感的に「当たる確率は半々」だと思った，博士号保持者も含めて。
この問題は事後確率（posterior probability）と呼ばれるものの一種である1。 最初の選択で当たる確率は $1 / 3$ なので後半に変更しなければ $1 / 3$ のままだが，「はずれのドアを開ける」ことにより選択肢が既に選択したドアともうひとつのドアの2つになるため，ドアを変更した場合の当たる確率が $2 / 3$ （つまり半々より確率値が大きい）になるのである。
「モンティ・ホール問題」は直感と論理との乖離を示す好例として挙げられることが多く，また簡単な確率シミュレーションとしてプログラミングの演習問題に使われることもあるようだ。
というわけで「モンティ・ホール問題」をシミュレートするコードを Go 言語で組んでみよう（Go 言語で書くことに特に意味はない。皆さんはお好きな言語でどうぞ）。
package main
import (
"fmt"
"math/rand"
"time"
)
func selectDoor(limit, max int) <-chan int {
ch := make(chan int)
go func() {
defer close(ch)
rand.Seed(time.Now().UnixNano())
for i := 0; i < max; i++ {
ch <- rand.Intn(limit)
}
}()
return ch
}
func challenges(shuldChange bool, max int) int {
doors := []bool{true, false, false}
ch := selectDoor(len(doors), max)
count := 0
for n := range ch {
result := doors[n]
if shuldChange {
result = !result
}
if result {
count++
}
}
return count
}
func main() {
max := 10000
fmt.Println("nochange:", float64(challenges(false, max))/float64(max))
fmt.Println(" change:", float64(challenges(true, max))/float64(max))
}
Go 言語的に面白いトピックはないので詳細は省くが，ざっくり説明すると selectDoor() 関数は（疑似乱数を使って）ドアを選択する関数で選択したドアを指定回数だけ channel で返す。
challenges() 関数は「モンティ・ホール問題」を指定回数だけ試行するもので，当たりの回数を返している。
ドアを変更するか否かは引数 shuldChange で指定する。
変数 doors がプレイヤーが選択するドアで，当たりが true に相当する。
for-range 構文の中身が実際に「モンティ・ホール問題」を試行している部分で
for n := range ch {
result := doors[n]
if shuldChange {
result = !result
}
if result {
count++
}
}
ドアを変更しない場合はそのまま，変更する場合は真偽が反転する。 これは「はずれのドアを開ける」と当たりとはずれのドアが 必ず ひとつづつになるため，最初に選択したドアとそうでないドアで真偽が反対になるからである。
では実際にコードを実行してみる。
$ go run monty-hall-problem.go
nochange: 0.3464
change: 0.6675
というわけで，それっぽい値になった。 めでたし。
「モンティ・ホール問題」は確かに直感に反するが2，こうやって具体的なコードで記述していくと「何故そうなるのか」が何となく分かってくる。 どうせプログラミング教育をやるのならこういう感じでやっていただきたいものである（笑）
おまけ：N個のドアでモンティ・ホール問題
応用として $n$ 個のドアで「モンティ・ホール問題」を検証してみよう。 ルールはこんな感じ。
- プレイヤーの前に閉まった $n$ 個のドアがある（$n \ge 3$）。当たりのドアは $1$ つ。残り $n-1$ 個ははずれ
- プレイヤーが $1$ つのドアを選択
- 司会者が残りのドアのうち $n-2$ 個のはずれドアを開ける
- プレイヤーは最初に選んだドアを変更してもよい
まず先ほどのコードのうち challenges() 関数と main() 関数を以下のように変更する。
func challenges(shuldChange bool, dct, max int) int {
doors := make([]bool, dct, dct) //initialized by false
doors[0] = true
ch := selectDoor(len(doors), max)
count := 0
for n := range ch {
result := doors[n]
if shuldChange {
result = !result
}
if result {
count++
}
}
return count
}
func main() {
dct := 3
max := 10000
fmt.Println("nochange:", float64(challenges(false, dct, max))/float64(max))
fmt.Println(" change:", float64(challenges(true, dct, max))/float64(max))
}
これで最初のコードとまったく同じ機能になる。
ここで main() 関数内の dct を 100 にして実行してみる。
$ go run monty-hall-problem.go
nochange: 0.0114
change: 0.9785
何故こういう値になるか考えてみませう。 簡単だよね。
おまけ2：有理数表現
Go 言語では math/big パッケージを使った有理数表現 big.Rat が使える。
これを使って main() 関数を書き直すと
func main() {
dct := 3
max := 10000
fmt.Println("nochange:", big.NewRat(int64(challenges(false, dct, max)), int64(max)).FloatString(4))
fmt.Println(" change:", big.NewRat(int64(challenges(true, dct, max)), int64(max)).FloatString(4))
}
てな感じになる。 math/big パッケージを使うと，計算コストは高くなるが，浮動小数点数型特有の計算誤差を緩和できるメリットがある。 まぁ，今回はあんまり関係ないけどね。
おおっ。 なんか Go 言語 っぽい（笑）
参考図書
- プログラマの数学 第2版
- 結城 浩 (著)
- SBクリエイティブ 2018-01-16 (Release 2018-02-08)
- Kindle版
- B079JLW5YN (ASIN)
- 評価
タイトル通りプログラマ必読書。第2版では機械学習に関する章が付録に追加された。
- プログラミング言語Go
- アラン・ドノバン (著), ブライアン・カーニハン (著), 柴田芳樹 (著)
- 丸善出版 2016-06-20 (Release 2021-07-13)
- Kindle版
- B099928SJD (ASIN)
- 評価
Kindle 版出た！ 一部内容が古びてしまったが，この本は Go 言語の教科書と言ってもいいだろう。感想はこちら。