最適停止問題の諸相が、簡潔に解説されている。取り上げられている問題は、 次の通り。
本書を読んで難渋したことを述べる。 まず、各種の最適停止問題の標題がわからない。 たとえば、Googol という最適停止問題がある。なぜこの名前なのか、 わからない。調べてみたら、google は 10 の 100 乗を表す、 Google 社のもとになった、などの情報は出てきたが、 なぜ Googol と、この最適停止問題が結び付くのか、わからない。 だから、著者も説明を諦めたのだろうか。 なお、Googol は、マーティン・ガードナーの発案になるゲーム。 内容は、たとえば、 数学の答え、結婚相手、 そして食べる場所を効果的に見つける方法 (現在リンク切れ、plnet.jp) にある。
同様の例をもう一つ。One-Armed-Bandit という問題がある。 この英語もわからない。調べたら、スロットマシンという意味だが、 なぜこの最適停止問題とつながるのか、わからない。
Success Run という問題がある。これも、 英語だけ出されて意味の解説がないのがつらい。 連続成功の問題だと思うが、どうか。
この本では、a.s. という略語が多く使われている。 これがわからない。調べてみると、 a.s. は、「殆ど確実に」(Almost Surely) の意味だとわかった。 ある資料によると、次の通りである。
たとえば、ある確率的な命題が確率 1 で成立するとき、 その命題は殆ど確実に成立する (または P-a.s. に成立する) という。 例えば、確率変数 `X` に対し、`P(X in E) = 1` ならば
`X in E quad "P-a.s."`
とあらわす。
この本では、P-a.s. を略して a.s. と書いているようだ。 最初にこの解説があると楽だった。
他にも馴染みの薄いことばがあった。たとえば、 確率変数に対する「結合分布」ということばが出てくるが、 すぐにはわからなかった。調べてみて、 これは「同時分布」と同義であることがわかった。 結合分布を知らない俺の問題だろうか。
実際にどんな問題が取り上げられているか。実例を挙げる。 多少自分のことばで書き直している。
ソフトウェアのリリース前の最終検査を考える。 このソフトウェアには、最終検査前に `M` 個のバグがあることがわかっている。 ただし、`M` の分布は既知とする。 バグの検査1回にかかる費用を `c_1 gt 0` とする。 発見されたバグは直ちに修正されるが、 バグが未発見の場合、 リリース後に生じる品質不良に伴う費用が生じる。 このときの費用をバグ1個につき `c_2 gt 0` とする。
`n` 回目の検査で発見されるバグ数を確率変数 `X_n` とし、 `X_1, X_2, cdots ` の同時分布はバグ個数 `M` が与えられたとき既知とする。 `n` 回目の検査後に残るバグの個数は、 `M - sum_(i=1)^nX_i` となる。 `n` 回めの検査後に出荷する時の費用 `Y_n` の期待値を最小にする 最適なソフトウェアのリリースタイミング `N` をみつけたい。ここで、
`Y_n = n c_1 + (M - sum_(i=1)^n X_i)c_2, quad n = 0, 1, cdots, Y_oo = oo`
この解答は次の通り。
`N = min {n gt 0 : E(X_(n+1) | X_1, cdots, X_n) le c_1/c_2}.`
現実にはバグ数 `M` もわからないし、バグの同時分布もわからない。 だから役には立たないといえばそれまでなのだが、 ものにはタイミングというものがある、ということはわかる。
最適停止問題で最も有名なものは、結婚問題(秘書問題、お見合い問題) であろう。本書でも結婚問題は詳細に記述されている。 ところで、結婚問題の結論が「37%ルール」という名前になっているとは、 知らなかった。37%という数字は、結婚問題の厳密解が、 `1 // e` (`e` は自然対数の底)で表されていることから来るのだが、 近似値として堂々と記述されているので、驚いたのだった。 なお、結婚問題については、上記でもリンクしているが、 数学の答え、結婚相手、 そして食べる場所を効果的に見つける方法 (現在リンク切れ、plnet.jp) の「最適停止問題」の項にある。
ところで、結婚問題を最初に教えてくれたのは友達の S くんである。 どんな答だと思う?と聞かれて、思い付きで `1 // e` と答えたら、 その通り、と驚かれた。これは、ただの自慢である。
このページの数式記述は ASCIIMathML で 表現はMathjaxを用いている。
書 名 | タイミングの数理 最適停止問題 |
著 者 | 穴太 克則 |
発行日 | 2000年3月10日 |
発行元 | 朝倉書店 |
定 価 | 3000円(本体) |
サイズ | A5判166ページ |
ISBN | 4-254-12618-2 |
まりんきょ学問所 > 数学の部屋 > 数学の本 > 穴太 克則:タイミングの数理 最適停止問題