数学ガール 乱択アルゴリズム 〜P≠NP予想と乱択クイックソート

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

数学ガールシリーズの第4巻。今回は確率、線型代数、計算量、NP問題（充足可能性問題）、乱択アルゴリズム、といった内容。
過去3冊を含めて一番楽に読めたのは、仕事柄というやつだろう。

第4章の「確率の定義」あたりを読んでいて、大学1年の時、統計学基礎の第1回目の講義で公理的確率の話を聞かされたのを思い出した。数式の示すところは間違っていないようなのだが、何を言っているのか得心がいかず、しばらく頭を捻ったのでした。

そのへんは、さすがにすっきり書いてあります。

公理的確率は、＜確率の公理＞によって定めた確率だ。確率の性質を公理という形で定め、その公理を満たすものを確率として定義する。現代数学では、これこそが確率の定義になる。
古典的確率は、＜場合の数の比＞によって定めた確率だ。同じ確からしさを持つ出来事とは何であるかを前もって決め、＜注目している場合の数＞を＜すべての場合の数＞で割った値、すなわち＜場合の数の比＞が確率を表すとする。高校までに学ぶ確率はこれになる。公理的確率と矛盾しないし、直感的にも分かりやすいが、適用範囲は限られている。
統計的確率は、＜発生頻度の比＞によって定めた確率だ。注目している出来事が実際に何回起きたかを調べたものを確率として考える。全体の内何回起きたか、つまり＜発生頻度の比＞を実際に調べ、過去をもとに未来を予測する。これは、出来事の原因を理論的に考えにくいときでも使える。(pp.116-117)

そのうえで、＜同じ確からしさ＞で出るの意味を

• 公理的確率の立場では、各目に与えられた確率が等しいことを＜同じ確からしさ＞という。つまり、公理で定義された確率という概念を使って＜同じ確からしさ＞とはなにかを定義する。ゆがんでいないサイコロをモデル化していることになる。
• 古典的確率の立場では、ゆがんでいないサイコロの目が＜同じ確からしさ＞で出ることは議論の前提だ。＜同じ確からしさ＞がどういう場合のことをいうかに対しては、答えを与えない。
• 統計的確率の立場では、何度も投げたとき、それぞれの目がほぼ等しい頻度で出たら＜同じ確からしさ＞で出るという。

とまとめている。

私も、これくらいすっきりまとめて説明ができればなあ、と感心しながら読んでました。

同様に、いつも困っている確率変数の話も、こんな例で示している。

• サイコロを1回投げたときに、出る目を確率変数Xとする
• コインを10回投げたときに、表が出る回数を確率変数Yとする
• 当たり籤を引くまでの、くじ引きの回数を確率変数Zとする

そのうえで、

100倍ゲーム（確率変数の例）
サイコロを投げて出た目を100倍した賞金が貰えるゲームをしよう。確率変数を使って、賞金をX(ω)円とする。ωは出た目である。
確率変数X(ω）は、標本空間Ω＝{1,2,3,4,5,6}から実数Rへの関数として表せる。

として、「確率変数は標本空間から実数への関数である」ということの説明をしている。

終盤は、乱択アルゴリズムの例として、乱択クィックソートを細かく説明している。これできちんと「乱択を使うことで計算量を下げる」話まで解説している。

数学の話というと真偽のはっきりする話というイメージが強いが、本書で扱うトピックには「どのくらい」という観点が何度も出てくる。計算量も期待値もそう。このへんの「数学」という言葉のイメージを広げることについて、結城先生がどの程度狙っているのかなとかもちょっと思った。

ちょっと不思議だったのが、リサ。わざわざコンピュータに詳しい新キャラを出してきたから、てっきり乱数生成の話をすると思っていたので、読み終わったときに「あれ、出てこなかったな」とちょっと思った。

あと、コンピュータに詳しいリサって新キャラが出てきたら、やっぱりアレを連想してしまうわけでして、「姉キャラじゃないのか」と叫んだ小飼弾先生の気持ちもわからなくはない。

アナログゲームを作る人に

すべての目が出るまで、サイコロを繰り返して投げる。
このとき、投げる回数の期待値を求めよ。(p.171)

この問題は、非常に頻繁に目にする。この問題をきちんと解く方法を、分かりやすく説明してくれているので、そういう方面の方にもお薦め。（ちなみに、6面ダイスだと約14.7回です。）
この説明に必要な「和の期待値は、期待値の和」がきちんと前の時点で説明してある。伏線があとから回収されていく謎解きものを読む面白さも（これは、本シリーズずっとだけど）ある。