数理解析研究所講究録
第 899 巻 1995 年 233-238$\sigma$233-集合体の行列表現と確率制御問題への応用
輝雄
Teruo Tanaka
広島市立大学情報科学部情報数理学科
田中$($$)$

Abstract
確率空間の 一集合体 (ここでは、集合体のみを扱う) の行列表現を用いて、離散時間の確率制$\sigma$

御問題、特に、最適停止問題、一般の制御問題、 Dynkin game を線形計画、 2 次計画、行列ゲームの問題に帰着できることを述べる。

1

集合体の行列表現 ([2], [4])を自然数、を満たすとする :$T$$(\Omega, \mathcal{F}, P)$.
.

を確率空間、 $\{\mathcal{F}_{t},t=1,2, \cdots,T\}$ を部分集合体の増大列とし、以下の 2 条件$\mathcal{F}=\mathcal{F}_{T}=\sigma(F_{1},$ $F_{2},$$\cdots,$ $F_{m})$$\mathcal{F}_{t}=\sigma(F_{1}^{t}, F_{2}^{t}, \cdots, F_{n_{t}}^{t})$,, $P(F_{i})>0(i=1,2,$$P(F_{i}^{t})>0(i=1,2, \cdots, n_{t})$そして、行列 $M_{t}(t=1,2, \cdots,T)$ ,$\bullet$$M_{t};=(m_{ij}^{t})_{m\cross n_{t}}$$\cdots,$$(t=1,2,$$m)$,,$F_{i}\cap F_{j}=\emptyset(i\neq j)$$F_{i}^{t}\cap F_{j}^{t}=\emptyset(i\neq j)$を次で定める :$M$$\cdots,$ $T)$$m_{ij}^{t};=\{\begin{array}{ll}1 ifF_{i}\subset F_{j}^{t}0 otherwise\end{array}$.

$M:=[M_{1}M_{2}\cdots M_{T}|:$

注意 11 集合体乙,例

.
.
.
.
.

確率空間

$\mathcal{F}$$(\Omega, \mathcal{F}, P)$$m\cross n$と、行列行列$M_{t},$ $M$

但し・$n:= \sum_{t=1}^{T}n_{t}$とする。

は 1 対 1 に対応する。

、増大列 $\{\mathcal{F}_{t},t=1,2,3,4\}$ として次のものを考える :$\Omega=\{(a_{1},$ $a_{2},$ $a_{3},$ $a_{4})$

:

$\{$

1, 2, 3, 4$\}$の permutation$\}$$P((a_{1}, a_{2}, a_{3}, a_{4}))= \frac{1}{4!}$$\mathcal{F}_{1}=\sigma(\Omega)$$\mathcal{F}_{2}=\sigma(\{a_{1}>a_{2}\}, \{a_{2}>a_{1}\})$$\mathcal{F}_{3}=\sigma(\{a_{1}>a_{2}>a_{3}\},$ $\{a_{1}>a_{3}>a_{2}\},$ $\{a_{3}>a_{1}>a_{2}\},$ $\{a_{2}>a_{1}>a_{3}\}$$\{a_{2}>a_{3}>a_{1}\},$ $\{a_{3}>a_{2}>a_{1}\})$

,

,

,

$\bigcup_{i}F_{i}.=\Omega$$\bigcup_{i}F_{i}^{t}=\Omega$

234

.

$\mathcal{F}=\mathcal{F}_{4}=\sigma(\{a_{1}>a_{2}>a_{3}>a_{4}\},$$\{a_{1}>a_{2}>a_{4}>a_{3}\},$ $\{a_{1}>a_{4}>a_{2}>a_{3}\}$$\{a_{4}>a_{1}>a_{2}>a_{3}\},$ $\{a_{1}>a_{3}>a_{2}>a_{4}\},$ $\{a_{1}>a_{3}>a_{4}>a_{2}\}$,,$\{a_{3}>a_{1}>a_{4}>a_{2}\},$ $\{a_{4}>a_{3}>a_{1}>a_{2}\},$ $\{a_{2}>a_{1}>a_{3}>a_{4}\}$ ,$\{a_{2}>a_{1}>a_{4}>a_{3}\},$ $\{a_{2}>a_{4}>a_{1}>a_{3}\},$ $\{a_{2}>a_{4}>a_{1}>a_{3}\}$ ,$\{a_{4}>a_{2}>a_{1}>a_{3}\},$ $\{a_{2}>a_{3}>a_{1}>a_{4}\},$ $\{a_{2}>a_{3}>a_{4}>a_{1}\}$ ,$\{a_{2}>a_{4}>a_{3}>a_{1}\},$ $\{a_{4}>a_{2}>a_{3}>a_{1}\},$ $\{a_{3}>a_{2}>a_{1}>a_{4}\}$ ,$\{a_{1}>a_{4}>a_{3}>a_{2}\},$ $\{a_{4}>a_{1}>a_{3}>a_{2}\},$ $\{a_{3}>a_{1}>a_{2}>a_{4}\}$$\{a_{3}>a_{2}>a_{4}>a_{1}\},$ $\{a_{3}>a_{4}>a_{2}>a_{1}\},$ $\{a_{4}>a_{3}>a_{2}>a_{1}\})$

各乙を生成する集合を、左から順番に$F_{i}^{t}$とする。

このとき、行列 $M(24\cross 33)$ は次のようになる :

,

235

命題 1.1 ([2], [4])$\mathcal{F}_{t}-stopp$

吻 time$\tau$と集合$X_{int}:=\{x\in\{0,1\}^{n}:Mx=1\}$の元は 1 対 1 に対応する。 実際、 その対応は$x_{j}^{t};=\{\begin{array}{l}1if F_{j}^{t}\subset\{\tau=t\}0 otherwise\end{array}$とおき、$x=(x_{1}^{1}, x_{2}^{1}, \cdots, x_{n}^{1_{1}}, x_{1}^{2}, x_{2}^{2}, \cdots, x_{n}^{2_{2}}, \cdots, x_{1}^{T}, x_{2}^{T}, \cdots, x_{n_{T}}^{T})$で与えられる。 1 はすべての成分が 1 であるベクトルとする。
命題 12 $E=\{c_{1}, c_{2}, \cdots, c_{r}\}$ を有限集合とする。 1 一可測関数 $U:\Omegaarrow E$ と集合$\mathcal{F}$$C_{int}^{t};=$$\{\{y^{c_{J}},j=1,2, \ldots, r\}:y^{c}j\in\{0,1\}^{n_{t}},\sum_{j=1}^{r}M_{t}y^{c_{j}}=1,\sum_{j=1}^{r}y^{c_{J}}=1 \}$の元は 1 対 1 に対応する。

2

離散時間確率制御問題への応用をそれぞれ有限集合、 $f$ を上の実数値関数、 を上の実数値関数とし、 を$F$-stopping time -値確率過程 $\{X_{t}, t=1,2, \cdots, T\}$ で状態変数を、 -値確率過程 $\{U_{t}, t=1,2, \cdots, T\}$で制御変数を表わすとする。
まず、次の確率制御問題 (SCP) を考える :$E,$ $S$$\{\mathcal{F}_{t}\}$、$S\cross E$

ma 幻 miZe

subject to

2.1

$g$

$S$

$\tau$$S$$E[ \sum_{k=1}^{\tau}f(X_{k},$$\tau,$$U_{k})+g(X_{r})]$$\{U_{k}\}$

最適停止問題(SCP) において $f=0$ とする。

定理 21([2]) 上記の問題は、次の整数計画問題と同値である :maximizesubject to
但し・ $t_{\beta}^{t}:=E[g(X_{t}):F_{\beta}^{t}]$ ,わすとする。

$x’L$$x\in x_{int}$$L;=[t_{1}^{1}, l_{2}^{1}, \cdots, l_{n_{1}}^{1}, l_{1}^{2}, l_{2}^{2}, \cdots, l_{n_{2}}^{2}, \cdots, l_{1}^{T}, l_{2}^{T}, \cdots, l_{n_{T}}^{T}]$とし、’ は転置を表236

定義 2.1 ([1], [4])あるという :

1.
2.

3.

$q_{t}\geq 0$$q_{t}$:$q=\{q_{t}, t=1,2, \cdots,T\}$が次の条件を満たすとき、 randomized stopping time で,t 一可測関数,$\mathcal{F}$$\sum_{t=1}^{T}q_{t}=1$.

定理 22([2], [4]) 定理 2.1 における整数計画問題を次の線形計画問題に修正する :maximize $x’L$
subject to $Mx=1,$ $x\geq 0$
このとき、 この問題は次の randomized 最適停止問題と同値である :ma ぬ mizesubject to22$\{X,$ $q \}:=E[\sum_{t=1}^{T}g(X_{t})q_{t}]$$q$

確率制御問題定理 23 上記の問題 (SCP りは、次の 2 次計画問題と同値である ;maximize $x’b+ \frac{1}{2}x’Ax$
subject to $x=[x,y]’,$ $y=[y_{1},y_{2},$$\cdots,y\tau|’$とするとき$x\in X_{int}$$y_{i}\in C_{int}^{t}$但し、行列$b,$ $A$は次で定める :$K(kt\alpha\beta c):=E[f(X_{k}, c):F_{\alpha}^{t}\cap F_{\beta}^{k}]$行列 $K_{(ktc)}$

は$(\alpha,\beta)$$\rangle$

成分を,$K(kt\alpha\beta c)$とする行列,$0$

$0$

$0$

,

.. ..... .... . .. .. ... .. ..... ..
$K_{(T-1,Tc_{r})}$$K_{(TTc_{1}})$$0$$K_{(TTc_{r})}$237$A=(0K’$,$0K$$b=(\begin{array}{l}L0\end{array})$.

定義 2.2 $\lambda^{t}=\{\lambda_{j}^{t},j=1,2, \cdots, r\}(t=1,2, \cdots,T)$ が次の条件を満たすとき、 mndomizedt 一可測$\mathcal{F}$関数であるという :1.

$\lambda_{j}^{t}\geq 0$:2.

$\lambda_{j}^{t}$3.

$\sum_{t=1}^{T}\lambda_{j}^{t}=1$

さらに、t 一可測関数$\mathcal{F}$を mndomized control という。

$\lambda=\{\lambda^{1}, \lambda^{2}, \cdots, \lambda^{T}\}$

定理 24 定理 23 における 2 次計画問題を次の問題に修正する :maximize$x’b+$ $\}x’Ax$

subject to $x=[x,y]’$ , $y=[y_{1}, y_{2}, \cdots,y\tau]’$ ,$Mx=1$ , $x\geq 0$$j \sum_{=1}^{r}M_{t}y_{t}^{c}j=1$,$y_{t}^{c}j\geq 0$,$y_{t}=[y_{t^{1}}^{c}, y_{t^{2}}^{c}, \cdots, y_{t^{\Gamma}}^{c}]’$$j \sum_{=1}^{r}y^{c}j=1$$t=1,2,$$\cdots,$とするとき$T$

このとき、 この問題は次の randomized 確率制御問題と同値である :maximize$\{X, \lambda,q\}$subject to

2.3$\lambda,$$:=E[ \sum_{t=1}^{T}\sum_{k=1}^{t}\sum_{j=1}^{r}f(X,c)\lambda_{j}^{t}q_{t}+\sum_{t=1}^{T}g(X_{t})q_{t}]$$q$

Dynkin game$\{X($ た $), k=1,2, \cdots, T\}$

実数値確率過程、$\tau_{1},$Find$\tau_{2}$を,$\{h($$(\tau_{1^{*}}, \tau_{2^{*}})$$J(\tau_{1^{*}},$

但し、た $), k=1,2, \cdots,T\}$ , $\{g($ た $), k=1,2, \cdots, T\}$ , $\{f($ ん $), k=1,2, \cdots, T\}$ を$\{\mathcal{F}_{t}\}$$\mathcal{T}2)$$\leq$-stopping time として、次の問題を考える :such that$J(\tau_{1^{*}},$$\mathcal{T}2^{*})$$J( \tau_{1}, \tau_{2})=E[\sum^{\tau_{1}}X\wedge\tau_{2} ($$\leq$$J(\tau_{1},$$\forall$$\tau_{2^{*}})$$(\tau_{1},$$\mathcal{T}2)$た $)+h(Tl)l\{\tau 1<\tau 2\}+g(\tau_{2})1_{\{\tau\}}\mathcal{T}2<1+f(\tau_{1})1_{\{\tau=\tau\}}12]$$k=1$

定理 25 上記の問題は次と同値である :Find$(x^{*}, y^{*})$

such that$F(x^{*}, y)\leq F(x^{*}, y^{*})\leq F(x, y^{*})$$\forall(x, y)\in X_{int}\cross X_{int}$

但し、 関数 $F$ は次で定める :行列 $A(s, t)$ は、 $(i$, の成分を k$\Sigma^{}=1^{E[X}\wedge t$(た) :$F_{i}^{s}\cap F_{j}^{t}]$行列且は、 ( , の成分を $A(s$ , のとする行列,$s$$r\nearrow\overline{\tau}F^{1J}B(s,t)$は、$\grave$とする行 1,

238

.
.
.

$s=t$ のとき、 (i, の成分を $E[f(t):F_{i}^{t}\cap F_{j}^{t}]$ とする行列$s>t$ のとき、色の成分を $E[g(t):F_{i}^{s}\cap F_{j}^{t}]$ とする行列$s<t$ のとき、砿の成分を E[ん (s):Fis F 哨とする行列$\cap$

行列 $B$ は、 ( , の成分を $B(s$ , りとする行列,として、$s$$F(x, y)=x’(A+B)y$とおく。

参考文献[1] J.R.Baxter and R.V.Chacon, Compactness of Stopping Times, Z.Wahrsch.Verw.Gebiete 40(1977), 169-181[2] R.Cairoli and R.C.Dalang, Sequential Stochastic optimization, Forthcoming (1993)[3] Y.S. Chow, H.Robbins and D.Siegmund, Great Expectations: The Theory of Optimal Stopping,Houghton-Mifflin, Boston, (1971)[4] R.C.Dalang, L.E.Trotter,JR and $D.oE.Werra$ , On Randomized Stopping Points and PerfectGraphs, J. Combin.Theory Ser. $B45$ (1988), 320-344[5] J.Neveu, Discrete-Parameter Martingale, North-Holland, (1975)