数学ガール読書メモ

4. 乱択アルゴリズム

概要: 後半に登場する乱択アルゴリズム(特に3SATとクイックソート)を理解するためのあれこれ(ビッグオー記法, ランダムウォーク, 確率と線形性)を前半に説明する感じ。前半はあっちこっちに話が飛ぶなあと思うけど、後半になるとそれがつながっているという構成なので、二度目に読んだ方が納得感があるように思う。以下 記憶に残ったトピックをざっくり

モンティは濃縮操作をしたと考える: 最初の選択では 1/3 の当たりの確率。残りの 2/3 の確率が残り2枚に分布しているのを モンティが濃縮して 1枚に濃縮した。手元は 1/3、もう片方は濃縮された 2/3。どっちを選択すべきかは自明。

番兵/sentinelで線形探索高速化: 探索対象を走査対象の末尾にわざと配置することでコードがスッキリして少しだけ早くなる。番兵法と呼ばれる。

標本空間を忘れるという考え方: 「標本空間と確率分布」を考える代わりに「確率変数の値と確率分布」を考えて議論することが多い。つまり、賞金(確率変数の値)と確率（確率分布）さえわかるなら、サイコロの目（標本空間の元）を捨象できるということ。

期待値の線形性を生かすための確率変数の選び方: 問い「二項分布に従うときn回の試行で事象が起こる回数の期待値は？」には、i回目の試行で事象が起こるときに1そうでないときには0をとる確率変数Xiを考えると、線形性からE[X]=ΣE[Xi]となりnpと簡単に答えが求まる。なお、ある事象が起きるときに 1, そうでないときに 0 を取るような確率変数を インディケータ確率変数と呼ぶらしい。期待値が確率になる。

比較ソートの計算オーダー: 比較木およびその高さという概念を導入することで、（バブルソートなどの）具体的な手続きに依存しない形で計算のオーダーを見積もれる。

NP問題のNはnotのNでない: Pは解の構成が多項式時間で終わるタイプの問題群。NPは解の検証が多項式時間で終わるタイプの問題群。PならNPなのは知られているが、NPならPかは知られていない。一般に P≠NP であるという予想がされているが、それを立証するためには NPだがPでない問題を一つでも挙げればよい。

3SATでの乱択はハミング距離空間におけるランダムウォークに対応: 現在検討中の割り当て と正解の割り当てとの「近さ」はハミング距離として定量化できる。3SAT乱択アルゴリズムにおけるフリップはハミング距離が1縮まるか1遠ざかるかのランダムウォークというわけ。1回の乱択によって近づく確率は少なくとも 1/3 で遠ざかる確率は 高々 2/3 という点から「表が1/3以上 裏が2/3未満の確率なコインを何回も投げて目的地まで行ける確率」というようなアナロジーになる。