タイミングの数理最適停止問題

作成日 : 2007-01-16
最終更新日 :

概要

最適停止問題の諸相が、簡潔に解説されている。取り上げられている問題は、 次の通り。

ことばについて

本書を読んで難渋したことを述べる。 まず、各種の最適停止問題の標題がわからない。 たとえば、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%ルール」という名前になっているとは、 知らなかった。37%という数字は、結婚問題の厳密解が、 `1 // e` (`e` は自然対数の底)で表されていることから来るのだが、 近似値として堂々と記述されているので、驚いたのだった。 なお、結婚問題については、上記でもリンクしているが、 数学の答え、結婚相手、 そして食べる場所を効果的に見つける方法 (現在リンク切れ、plnet.jp) の「最適停止問題」の項にある。

ところで、結婚問題を最初に教えてくれたのは友達の S くんである。 どんな答だと思う?と聞かれて、思い付きで `1 // e` と答えたら、 その通り、と驚かれた。これは、ただの自慢である。

数式記述

このページの数式記述は ASCIIMathML で 表現はMathjaxを用いている。

書誌情報

書 名タイミングの数理 最適停止問題
著 者穴太 克則
発行日2000年3月10日
発行元朝倉書店
定 価3000円(本体)
サイズA5判166ページ
ISBN4-254-12618-2

まりんきょ学問所数学の部屋数学の本 > 穴太 克則:タイミングの数理 最適停止問題


MARUYAMA Satosi