Optimal Stoppingとは何？わかりやすく解説 Weblio辞書

索引トップ用語の索引ランキングカテゴリー

最適停止

概要

結合分布が既知である確率変数列 $X_1, X_2, \cdots \,$ ,と実数値利得関数列 $y_0, \ y_1(x_1), \,$ $\ y_2(x_1, x_2), \,$ $\cdots, \ y_{\infty}(x_1, x_2,\dots) \,$ に対して, 逐次に確率変数列 $X_1 \,$ , $X_2 \,$ , $\cdots \,$ を観測し, 各 $n \,$ 段階において $X_1=x_1, X_2=x_2, \cdots, X_n=x_n \,$ を観測後に観測を停止して利得 $y_n(x_1, \dots, x_n) \,$ を得るか, 継続して $X_{n+1} \,$ を観測するかを決定を下す.このとき, 期待利得を最大にする(もしくは期待費用を最小化する)停止時刻を求めるのが最適停止問題である.

詳説

　逐次に観測される確率変数列に基づき, 期待利得を最大化したり期待費用を最小化するためにある行動を取る時刻を選ぶ問題を最適停止問題という. 最適停止は次の 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\,$ , $\cdots\,$ を観測し, 最初の $n\,$ 段階において $X_1=x_1,X_2=x_2, \cdots, X_n=x_n\,$ を観測後に観測を停止して利得 $y_n(x_1, \cdots, x_n)\,$ を得るか, 継続して $X_{n+1}\,$ を観測するかの決定を下す. 全く観測しないならば $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\,$ を求める問題となる.

　より一般的には, 最適停止問題は次の様に記述されている. 確率空間 $(\Omega, {\mathcal F}, P)\,$ が与えられ, ${\mathcal F}_n\,$ を $X_1, \cdots, X_n\,$ によって生成される $\mathcal F\,$ の部分 $\sigma\,$ 集合, ${\mathcal F}_0=\{\Omega, \phi\}, {\mathcal F}\,$ を $\cup {\mathcal F}_n\,$ によって生成される $\sigma\,$ 集合とし, ${\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') 増加部分 $\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\,$ を停止規則と定義する. (この定義は, いつ停止するかの決定は今までの観測のみに基づき, 将来の観測には基づかないと解釈するとわかりやすい.) このとき $E(Y_N)\,$ を最大にする停止規則 $N\,$ を求めるのが最適停止問題である. 一般に全ての最適停止問題を解くことは難しいが, 有限期間問題と単調問題(monotone problem)は解くことができる. 確率変数列 $X_1, X_2, \cdots, X_n, n<\infty\,$ を観測後に必ず停止しなければならないとき, 有限期間問題と呼ぶ.有限期間問題は基本的に後向きの帰納法 (backward induction) によって解かれる. $n\,$ 期では停止しなければならないので, $V_n^{(n)}\,$ を $V_n^{(n)}(x_1, \cdots, x_n)=y_n(x_1, \cdots, x_n)\,$ と定義する. $(n-1)\,$ 期では, ここで停止したときの利得 $y_{n-1}(x_1, \cdots, x_{n-1})\,$ と, 継続して $n\,$ 期で停止したときの期待利得 $\mbox{E} (V_n^{(n)}(x_1, \cdots, x_{n-1}, X_n)|X_1 = x_1, \cdots, X_{n-1}=x_{n-1})\,$ を比較すれば, $(n-1)\,$ 期で停止すべきか継続すべきかが判明する. $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})\}.\,$ 同様に $j=n-2, n-3, \cdots, 0\,$ と後ろ向きに $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}\,$

とする. このように定義された $V_j^{(n)}(x_1, \cdots, x_j)\,$ は, $X_1=x_1, \cdots\,$ , $X_j=x_j\,$ を観測して $j\,$ 期から始めたときの最大期待利得を表し, 上式は最適方程式と呼ばれる. これは動的計画の最適性の原理によって得られる関数再帰方程式に他ならず, DP(ダイナミック $\cdot\,$ プログラミング)方程式とも呼ばれる. $j\,$ 期においては, 停止して得られる利得 $y_j(x_1, \cdots, x_j)\,$ が $j\,$ 期より継続して得られる最大期待利得 $\mbox{E}(V_{j+1}^{(n)}(x_1, \cdots, x_j, X_{j+1})|X_1 = x_1, \cdots, X_j=x_j)\,$ より良ければ停止し, 逆ならば継続するのが良い. それゆえに, 有限期間問題の最適停止規則 $N\,$ は, 初めて $V_j^{(n)}(x_1, \cdots, x_j)=y_j(x_1, \cdots, x_j)\,$ となる $j\,$ で停止することである. 有限期間問題の最大期待利得は, $V_0^{(n)}\,$ となる.

　最適停止問題において, 事象 $A_n=\{Y_n\ge E(Y_{n+1}|{\mathcal F}_n)\}\,$ , $n=0, 1, 2, \cdots\,$ が $\textstyle A_0 \subset A_1 \subset \cdots \subset;\ {\bigcup}_1^{\infty} A_n=\Omega \,$ (almost surely) を満たしているとき単調問題とよぶ. 単調問題では, ある条件の下で([1]参照) OLA (one-stage look-ahead) 停止規則 $N:=\min\{n\ge 0: Y_n\ge E(Y_{n+1}|{\mathcal F}_n)\}\,$ が最適停止規則となる. OLA 停止規則とは, もう1期だけ継続してから停止するよりも, 今停止するほうがよいときに停止することを要求する規則である.

　独自のクラスを形成してきたといえる確率最大化最適停止問題に秘書問題がある. 秘書問題は結婚問題とも呼ばれ, 最も基本となる古典的秘書問題は次のように記述される . 1人の秘書を雇いたい. 面接した応募者には同ランクはなくランク付けが可能とする. 1人ずつ面接する毎に, 今までに面接した応募者の相対ランクに基づき採用するか否かを決めなければならず, 一度不採用にした応募者を採用することはできない. $n\,$ 人の応募者があり, $n\,$ 人の面接の順列の一つが実現する確率が $1/n!\,$ のとき, $n\,$ 人中のベストランクを得る確率を最大にする最適停止規則を求めたい. 最適停止規則は, $r^{\ast}-1\,$ 番目までの応募者は全て採用を見送り, それ以降に最初に面接する相対的ベストの応募者を採用しなさい, となり, ここで, $\textstyle r^{\ast}=\min\{i\ge 1:\sum_{j=i}^{n-1}(1/j) \le 1\}\,$ により $r^{\ast}\,$ は与えられる. $n\to \infty\,$ のとき, $r^{\ast}/n \to 1/{\rm e} \approx 0.3678\,$ となる. 大まかに言うと, $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.

「OR事典」の他の用語

動的・確率・多目的計画：

完全情報の期待価値対話型解法最短最長ルート問題最適停止最適性の原理期待値最適化木の総容量

Weblio日本語例文用例辞書

索引トップ用語の索引ランキング

「optimal stopping」の例文・使い方・用例・文例

『filling（お腹が一杯になる）』のくだけた英国英語表現は『stopping』である

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。

>> 「Optimal Stopping」を含む用語の索引
Optimal Stoppingのページへのリンク


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

Optimal Stoppingとは？わかりやすく解説

最適停止

概要

詳説

「optimal stopping」の例文・使い方・用例・文例

「Optimal Stopping」の関連用語

Optimal Stoppingとは？ わかりやすく解説

最適停止

概要

詳説

「optimal stopping」の例文・使い方・用例・文例

「Optimal Stopping」の関連用語

Optimal Stoppingとは？わかりやすく解説