《最適停止》

【さいてきていし (optimal stopping)】

　逐次に観測される確率変数列に基づき, 期待利得を最大化したり期待費用を最小化するためにある行動を取る時刻を選ぶ問題を最適停止問題という. 最適停止は次の2つの要素を持つ. (i) 結合分布が既知である確率変数列: $X_{1},X_{2},\cdots \,$, (ii) 実数値利得関数列: $y_{0},\ y_{1}(x_{1}),\ y_{2}(x_{1},x_{2}),\cdots ,\,$ $\ y_{\infty }(x_{1},x_{2},\cdots )\,$. 逐次に確率変数列$X_{1}\,$, $X_{2}\,$, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \cdots\, } を観測し, 最初の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 段階において構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X_1=x_1,X_2=x_2, \cdots, X_n=x_n\, } を観測後に観測を停止して利得構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y_n(x_1, \cdots, x_n)\, } を得るか, 継続して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X_{n+1}\, } を観測するかの決定を下す. 全く観測しないならば構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y_0\, } , 決して停止しないならば$y_{\infty }(x_{1},x_{2},\cdots )\,$の利得を得る.このとき, 利得を最大にするタイミングである停止時刻を求めるのが最適停止問題である.要素の(ii)は, $Y_{n}=y_{n}(X_{1},\cdots ,X_{n})\,$としたとき, (ii') 結合分布が既知である利得を表す確率変数列: $Y_{0},\ Y_{1},\ Y_{2},\ \cdots ,\ Y_{\infty },\,$ としてもよい. このとき, $E(Y_{N})\,$を最大にする停止時刻$N\,$を求めるのが最適停止問題であるとも記述できる. $Y_{N}\,$を利得ではなく何らかの費用や損失と解釈すると, 費用ないし損失を最小にする停止規則(時刻)$N\,$を求める問題となる.

　より一般的には, 最適停止問題は次の様に記述されている. 確率空間 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\Omega, {\mathcal F}, P)\, } が与えられ, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal F}_n\, } を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X_1, \cdots, X_n\, } によって生成される 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal F\, } の部分 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sigma\, } 集合, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal F}_0=\{\Omega, \phi\}, {\mathcal F}\, } を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \cup {\mathcal F}_n\, } によって生成される 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sigma\, } 集合とし, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal F}_0 \subset {\mathcal F}_1 \subset \cdots\subset {\mathcal F}_n \subset \cdots\subset {\mathcal F}_{\infty} \subset {\mathcal F}\, } とする. (i)(ii) にかわり(i') 増加部分構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sigma\, } 集合列:${\mathcal {F}}_{0}\subset {\mathcal {F}}_{1}\subset \cdots \subset {\mathcal {F}}_{\infty }\subset {\mathcal {F}}\,$, (ii") 結合分布が既知な利得を表す確率変数列: $Y_{0},Y_{1},\cdots ,Y_{n},\cdots ,Y_{\infty }\,$,とし, $Y_{n}\,$は${\mathcal {F}}_{n}\,$-可測, $n=0,1,\cdots ,\infty \,$とする. $\{N=n\}\in {\mathcal {F}}_{n}\,$である非負整数値確率変数$N\,$を停止規則と定義する. (この定義は, いつ停止するかの決定は今までの観測のみに基づき, 将来の観測には基づかないと解釈するとわかりやすい.) このとき 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle E(Y_N)\, } を最大にする停止規則構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } を求めるのが最適停止問題である. 一般に全ての最適停止問題を解くことは難しいが, 有限期間問題と単調問題(monotone problem)は解くことができる. 確率変数列 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X_1, X_2, \cdots, X_n, n<\infty\, } を観測後に必ず停止しなければならないとき, 有限期間問題と呼ぶ.有限期間問題は基本的に後向きの帰納法 (backward induction) によって解かれる. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 期では停止しなければならないので, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V_n^{(n)}\, } を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V_n^{(n)}(x_1, \cdots, x_n)=y_n(x_1, \cdots, x_n)\, } と定義する. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (n-1)\, } 期では, ここで停止したときの利得 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y_{n-1}(x_1, \cdots, x_{n-1})\, } と, 継続して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 期で停止したときの期待利得 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{E} (V_n^{(n)}(x_1, \cdots, x_{n-1}, X_n)|X_1 = x_1, \cdots, X_{n-1}=x_{n-1})\, } を比較すれば, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (n-1)\, } 期で停止すべきか継続すべきかが判明する. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V_{n-1}^{(n)}(x_1, \cdots, x_{n-1})\, } を次のように定義する. $V_{n-1}^{(n)}(x_{1},\cdots ,x_{n})=\max\{y_{n-1}(x_{1},\cdots ,x_{n-1}),{\mbox{E}}(V_{n}^{(n)}(x_{1},\cdots ,x_{n-1},X_{n})|X_{1}=x_{1},\cdots ,X_{n-1}=x_{n-1})\}.\,$同様に 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j=n-2, n-3, \cdots, 0\, } と後ろ向きに構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V_j^{(n)}(x_1, \cdots, x_j)\, } を定義し,

${\begin{array}{ll}V_{j}^{(n)}(x_{1},\cdots ,x_{j})=&\max\{y_{j}(x_{1},\cdots ,x_{j}),\\&\quad {\mbox{E}}(V_{j+1}^{(n)}(x_{1},\cdots ,x_{j},X_{j+1})|X_{1}=x_{1},\cdots ,X_{j}=x_{j})\}\end{array}}\,$

とする. このように定義された 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V_j^{(n)}(x_1, \cdots, x_j)\, } は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X_1=x_1, \cdots\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X_j=x_j\, } を観測して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j\, } 期から始めたときの最大期待利得を表し, 上式は最適方程式と呼ばれる. これは動的計画の最適性の原理によって得られる関数再帰方程式に他ならず, DP(ダイナミック構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \cdot\, } プログラミング)方程式とも呼ばれる. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j\, } 期においては, 停止して得られる利得$y_{j}(x_{1},\cdots ,x_{j})\,$が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j\, } 期より継続して得られる最大期待利得構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{E}(V_{j+1}^{(n)}(x_1, \cdots, x_j, X_{j+1})|X_1 = x_1, \cdots, X_j=x_j)\, } より良ければ停止し, 逆ならば継続するのが良い. それゆえに, 有限期間問題の最適停止規則構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } は, 初めて構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V_j^{(n)}(x_1, \cdots, x_j)=y_j(x_1, \cdots, x_j)\, } となる構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j\, } で停止することである. 有限期間問題の最大期待利得は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V_0^{(n)}\, } となる.

　最適停止問題において, 事象構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_n=\{Y_n\ge E(Y_{n+1}|{\mathcal F}_n)\}\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n=0, 1, 2, \cdots\, } が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle A_0 \subset A_1 \subset \cdots \subset;\ {\bigcup}_1^{\infty} A_n=\Omega \, } (almost surely) を満たしているとき単調問題とよぶ. 単調問題では, ある条件の下で([1]参照) OLA (one-stage look-ahead) 停止規則構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N:=\min\{n\ge 0: Y_n\ge E(Y_{n+1}|{\mathcal F}_n)\}\, } が最適停止規則となる. OLA 停止規則とは, もう1期だけ継続してから停止するよりも, 今停止するほうがよいときに停止することを要求する規則である.

　独自のクラスを形成してきたといえる確率最大化最適停止問題に秘書問題がある. 秘書問題は結婚問題とも呼ばれ, 最も基本となる古典的秘書問題は次のように記述される. 1人の秘書を雇いたい. 面接した応募者には同ランクはなくランク付けが可能とする. 1人ずつ面接する毎に, 今までに面接した応募者の相対ランクに基づき採用するか否かを決めなければならず, 一度不採用にした応募者を採用することはできない. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 人の応募者があり, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 人の面接の順列の一つが実現する確率が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1/n!\, } のとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 人中のベストランクを得る確率を最大にする最適停止規則を求めたい. 最適停止規則は, $r^{\ast }-1\,$番目までの応募者は全て採用を見送り, それ以降に最初に面接する相対的ベストの応募者を採用しなさい, となり, ここで, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle r^{\ast}=\min\{i\ge 1:\sum_{j=i}^{n-1}(1/j) \le 1\}\, } により構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r^{\ast}\, } は与えられる. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\to \infty\, } のとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r^{\ast}/n \to 1/{\rm e} \approx 0.3678\, } となる. 大まかに言うと, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } が十分大きいとき, 36.8%まではパスしてそれ以 降に到着する相対的ベストの応募者を採用するのが最適である.

---

参考文献

[1] Y. S. Chow, H. Robbins and D. Siegmund, Great Expectations: The Theory of Optimal Stopping, Houghton Mifflin Company, Boston, 1971.

[2] T. S. Ferguson, "Who Solved the Secretary Problem?," Statistical Science, 4 (1989), 282-289.

[3] A. N. Shiryaev, Optimal Stopping Rules, Springer-Verlag, New York, 1978.

[4] J. L. Snell, ""Applications of Martingale System Theorems," Trans. Amer. Math. Soc., 73 (1952), 293-312.

[5] S. M. Ross, Applied Probability Models with Optimization Applications, Holden - Day, San Francisco, 1970.