数理解析研究所講究録 1207 巻 2001 年 101-113101
最大値過程について
九州大学大学院経済学研究院
九州大学大学院経済学研究科

岩本 誠一
津留崎 和義Graduate School of Economics,
Kyushu Univ.

1

Introduction

In this paper we are concerned with amaximum process generated through independentand identically distributed random variables via its summation process. Both the i.i.d.
process and the summation process are Markov chains. The probabilistic behavior of bothis well known [12]. However, the maximum process is not Markov. We are interested
in how to make it Markov on suitable state spaces. Further we focus our attention on
arecursive computation of expected value, variance and probability distribution of the
maximum random variable.
We present anew method “Markovization”, which is astochastic realization of invariprogramming without optimization” [1,ant imbedding approach
$[9,
10]$
Chap.14].
[13,
,
[8,
p.23],We show that the computation
p. 115], [2, p.72], [4, p.203],is based upon the Markovization.
$[2-7, 9, 11]-” \mathrm{d}\mathrm{y}\mathrm{n}\mathrm{a}\mathrm{m}\mathrm{i}\mathrm{c}$2Profit Process

2.1

Random WalkLet

$X_{1}$,$X_{2}$,$\ldots$,$X_{i}$,$\ldots$

be independent and identically distributed with

$P(X_{i}=1)=p$ ,$(0\leq p\leq 1, p+q=1)$ .

$P(X_{i}=-1)=q$

In agame of flipping acoin–probability of head is –infinitely, $X_{i}=1(-1)$ denotes
awin (loss) at -th flipping. When aplayer wins (loses), he get (loses) one-unit.
Then we define the sum-tO-date as follows :
$p$

$i$

$\mathrm{Y}_{0}=0$,$\mathrm{Y}_{i}=\sum_{j=1}^{i}X_{j}$.

(1)

is arandom walk [12, p.143]. It is also called aprofit
The additive processprocess. In the game of coin flipping,denotes anet profit, which is equal to “thenumber of wins –the number of losses” up to flippings. It is adifference between wins
and losses.
Further we define the maximum-tO-date :$\{\mathrm{Y}_{i}, i\geq 0\}$$\mathrm{Y}_{i}$$i$$Z_{i}= \max_{1\leq j\leq i}\mathrm{Y}_{j}$.

102
The maximum process $\{Z_{i}, i\geq 1\}$ is called amaximum profit process. In the game,denotes the maximum value of differences between wins and losses up to flippings.
Let $N$ be any positive integer. We are concerned with the maximum profit random. Our problem is to find its expected value, variance andvariable over the $N$-stage
probability distribution :$Z_{i}$$i$$Z_{N}$$E[Z_{N}]$2.2,$V[Z_{N}]$,$P(Z_{N}=k)$ .

Profit Process

Let us take an integer $n(\geq 2)$ . We consider arandom variable
Binomial distribution $Bi(n;p)$ :$k=0,1$ ,$P(U=k)$ $={}_{n}C_{k}p^{k}q^{n-k}$$\ldots$$U$, which follows the

, .
$n$

It is easily shown that
$E[U]=np$ ,We return to the random variable$\mathrm{Y}_{n}=1\cdot$$k$$(n-k)$ ,$+(-1)\cdot$$k$$=0,1$ ,$V[U]=npq$ .

defined in (1). Let us consider the events, . Then we have$\mathrm{Y}_{n}$$n$$\ldots$$P(\mathrm{Y}_{n}=2k-n)={}_{n}C_{k}p^{k}q^{n-k}$.

Thus we see that $\mathrm{Y}_{n}=2U-n$ holds almost surely.
As asummary we obtain

Lemma 2.1.
(i)
(ii)
(iii)

Thus
$\{S_{n}\}$takes
as follows :$\mathrm{Y}_{n}$$\mathrm{Y}_{n}=2U-na.s$.
$k=0,1$ ,$P(\mathrm{Y}_{n}=2k-n)={}_{n}C_{k}p^{k}q^{n-k}$$E[\mathrm{Y}_{n}]=n(p-q)$$\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}\mathrm{s}-n$,$V[\mathrm{Y}_{n}]=4npq$, $-n+2$ , $-n+4$ ,$\ldots$$\ldots$

,

$n$

.

, $n-2$ ,$S_{n}:=\{-n, -n+2, -n+4, \ldots, n-2, n\}$$n$

. Let us define state spaces$n=0,1$ ,$\ldots$

(2)

where
$S_{0}=\{0\}$.

Therefore, the profit process $\{\mathrm{Y}_{n}, n=0,1, \ldots\}$ is aMarkov chain on the state spaces
with the transition probability $p=\{p_{n}(j|i)\}$ (Figure 1) :$\{S_{n}\}$if $j=i+1$$p_{n}(j|i)=\{$
if $j=i-1$0otherwise
$p$

$q$

Then the recursion$\mathrm{Y}_{n+1}=X_{n+1}+\mathrm{Y}_{n}$, $n=1,2$ ,$\ldots$$n=0,1$ ,$\ldots$.

together with i.i.d. property in(3)$\{X_{n}\}$103$\mathrm{Y}_{4}$$\mathrm{Y}_{3}\nearrow^{p}$$\mathrm{Y}_{2}\nearrow p$

43$\backslash _{q}$$\mathrm{Y}_{1}\nearrow p$

22$\nearrow p$$\backslash _{q}$11$\mathrm{Y}_{0}$$\nearrow p$$\nearrow^{p}$$\backslash _{q}$$\backslash _{q}$000$\backslash _{q}$$\nearrow^{p}$$\nearrow^{p}$$\backslash _{q}$-1-1$\nearrow p$$\backslash _{q}$$\backslash _{q}$-2-2$\nearrow p$$\backslash _{q}$-3$\backslash _{q}$-4$S_{4}$$S_{3}$$S_{2}$$S_{1}$$S_{0}$

Figure 1: Profit process$\mathrm{Y}=\{\mathrm{Y}_{n}\}$Lemma 2.2.
(i)$E[\mathrm{Y}_{n+1}]=p-q+E[\mathrm{Y}_{n}]$$E[\mathrm{Y}_{1}]=p-q$(i)$n=1,2$ ,$\ldots$.

$E[\mathrm{Y}_{n+1}^{2}]=1+2(p-q)E[\mathrm{Y}_{n}]+E[\mathrm{Y}_{n}^{2}]$$E[\mathrm{Y}_{1}^{2}]=1$$n=1,2$ ,$\ldots$.

Thus we have
$E[\mathrm{Y}_{n}]=n(p-q)$,$E[\mathrm{Y}_{n}^{2}]=n+n(n-1)(p-q)^{2}$.

This also implies $V[\mathrm{Y}_{n}]=Anpq$ .

3Maximum Process
has been calculated through
It is shown that expected value and variance of profit
expectedvalue and variance of
the Binomial distribution. In this section we consider.
maximum profit$\mathrm{Y}_{n}$$Z_{n}$

Lemma 3.1. (i) For $n=1,2$ ,$\ldots$,$\mathrm{Y}_{2n+1}>Z_{2n}$104is equivalent to$X_{2}+X_{3}+X_{4}+X_{5}+\cdots+X_{2n-4}+X_{2n-3}+X_{2n-2}+X_{2n-1}\geq 0$$X_{4}+X_{5}+\cdots+X_{2n-4}+X_{2n-3}+X_{2n-2}+X_{2n-1}\geq 0$..

$\cdot$$X_{2n-4}+X_{2n-3}+X_{2n-2}+X_{2n-1}\geq 0$$X_{2n-2}+X_{2n-1}\geq 0$$X_{2n}=X_{2n+1}=1$ .

(ii) For $n=1,2$ ,$\ldots$,$\mathrm{Y}_{2n+2}>Z_{2n+1}$

is equivalent to$X_{3}+X_{4}+X_{5}+X_{6}+\cdots+X_{2n-3}+X_{2n-2}+X_{2n-1}+X_{2n}\geq 0$$X_{5}+X_{6}+\cdots+X_{2n-3}+X_{2n-2}+X_{2n-1}+X_{2n}\geq 0$.
.

$\cdot$(4)$X_{2n-3}+X_{2n-2}+X_{2n-1}+X_{2n}\geq 0$$X_{2n-1}+X_{2n}\geq 0$$X_{2n+1}=X_{2n+2}=1$ .

In particular,$\mathrm{Y}_{2}>Z_{1}$is equivalent to$X_{2}=1$.

(iii) In either case we have$\mathrm{Y}_{n+1}-Z_{n}=1$$\mathrm{Y}_{n+1}^{2}-Z_{n}^{2}=2\mathrm{Y}_{n}+1$$n=0,1$ ,$\ldots$.

. Since (i) is shown, we first show (ii). We note that the inequality$Pro\mathrm{o}/$$\mathrm{Y}_{2n+2}>Z_{2n+1}$$=\mathrm{Y}_{1}\vee \mathrm{Y}_{2}\vee\cdots\vee \mathrm{Y}_{2n-1}\vee \mathrm{Y}_{2n}\vee \mathrm{Y}_{2n+1}$

is equivalent to the system of inequalities$\mathrm{Y}_{2n+2}>\mathrm{Y}_{2n+1}$$\Rightarrow X_{2n+2}>0$$\mathrm{Y}_{2n+2}>\mathrm{Y}_{2n}$$\Rightarrow X_{2n+2}+X_{2n+1}>0$$\mathrm{Y}_{2n+2}>\mathrm{Y}_{2n-1}$$\Rightarrow X_{2n+2}+X_{2n+1}+X_{2n}>0$$\mathrm{Y}_{2n+2}>\mathrm{Y}_{2n-2}$$\Rightarrow X_{2n+2}+X_{2n+1}+X_{2n}+X_{2n-1}>0$.
.

$\cdot$$\mathrm{Y}_{2n+2}>\mathrm{Y}_{2}$$\mathrm{Y}_{2n+2}>\mathrm{Y}_{1}$$\Rightarrow X_{2n+2}+X_{2n+1}+\cdots+X_{3}>0$$\Rightarrow X_{2n+2}+X_{2n+1}+\cdots+X_{3}+X_{2}>0$ .

(5)
(6)

105

$X_{2n+2}=1$$X_{2n+1}=1$$X_{2n}>-2$$X_{2n-1}+X_{2n}>-2$(7)$X_{2n-2}+X_{2n-1}+X_{2n}>-2$.

.
$\cdot$$X_{3}+X_{4}+\cdots+X_{2n-1}+X_{2n}>-2$$X_{2}+X_{3}+X_{4}+\cdots+X_{2n-1}+X_{2n}>-2$ .

Since eachtakes only two values -1, 1, we see that (7) is equivalent to (4). (iii) is
shown as follows. First we assume that
. Here$X_{m}$$\mathrm{Y}_{n+1}>Z_{n}$$\mathrm{Y}_{n}=\mathrm{Y}_{n-1}+X_{n}$(since $X_{n}=1$ )$>\mathrm{Y}_{n-1}$$\mathrm{Y}_{n}=\mathrm{Y}_{n-2}+X_{n-1}+X_{n}$$\geq \mathrm{Y}_{n-2}$$\mathrm{Y}_{n}=\mathrm{Y}_{n-3}+X_{n-2}+X_{n-1}+X_{n}$(since $X_{n-2}+X_{n-1}\geq 0$ )$>\mathrm{Y}_{n-3}$$\mathrm{Y}_{n}=\mathrm{Y}_{n-4}+X_{n-3}+X_{n-2}+X_{n-1}+X_{n}$$\geq \mathrm{Y}_{n-4}$.
.
$\cdot$

Then we have$Y_{n}\geq \mathrm{Y}_{m}$, $m=1,2$ ,$\ldots$, , which implies$n$$\mathrm{Y}_{n+1}-Z_{n}=\mathrm{Y}_{n+1}-\mathrm{Y}_{n}=X_{n+1}=1$.

Furthermore, this implies$\mathrm{Y}_{n+1}^{2}-Z_{n}^{2}=(\mathrm{Y}_{n+1}+Z_{n})(Y_{n+1}-Z_{n})$$=Y_{n+1}+Z_{n}$$=2\mathrm{Y}_{n+1}-1$$=2\mathrm{Y}_{n}+1$.
$\square$

Then we have the following recursion formulae :Lemma 3.2.
(i)$E[Z_{n+1}]=P(\mathrm{Y}_{n+1}>Z_{n})+E[Z_{n}]$$n=1,2$ ,$\ldots$$E[Z_{1}]=p-q$ .

(ii)$E[Z_{n+1}^{2}]=E[(2\mathrm{Y}_{n}+1)\cdot 1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}]+E[Z_{n}^{2}]$$E[Z_{1}^{2}]=1$.

$n=1,2$ ,$\ldots$

106
Proof. First we note the equality$1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}+1_{\{\mathrm{Y}_{n+1}\leq Z_{n}\}}=1$

where$1_{A}$

is the characteristic function of set$A$:$\in A$
1if
0otherwise.
$\omega$$1_{A}(\omega)=\{$

It holds that
$Z_{n+1}=Z_{n}\vee \mathrm{Y}_{n+1}$$=(Z_{n}\vee \mathrm{Y}_{n+1})\cdot(1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}+1_{\{\mathrm{Y}_{n+1}\leq Z_{n}\}})$$=\mathrm{Y}_{n+1}\cdot 1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}+Z_{n}\cdot 1_{\{\mathrm{Y}_{n+1}\leq Z_{n}\}})$(8)$=(Y_{n+1}-Z_{n})\cdot 1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}+Z_{n}$$Z_{n+1}^{2}=(Z_{n}\vee \mathrm{Y}_{n+1})^{2}$$=(Z_{n}\vee \mathrm{Y}_{n+1})^{2}\cdot(1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}+1_{\{\mathrm{Y}_{n+1}\leq Z_{n}\}})$$=\mathrm{Y}_{n+1}^{2}\cdot 1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}+Z_{n}^{2}\cdot 1_{\{\mathrm{Y}_{n+1}\leq Z_{n}\}})$.

(9)$=(\mathrm{Y}_{n+1}^{2}-Z_{n}^{2})\cdot 1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}+Z_{n}^{2}$

Prom (5) we see that
$E[(\mathrm{Y}_{n+1}-Z_{n})\cdot 1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}]=E[1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}]$$=P(\mathrm{Y}_{n+1}>Z_{n})$.

Taking the expectation of both sides in (8), we have
$E[Z_{n+1}]=E[(\mathrm{Y}_{n+1}-Z_{n})\cdot 1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}]+E[Z_{n}]$$=P(\mathrm{Y}_{n+1}>Z_{n})+E[Z_{n}]$.

Similarly, acombination of (6) and (9) yields$E[Z_{n+1}^{2}]=E[(\mathrm{Y}_{n+1}^{2}-Z_{n}^{2})\cdot 1_{\{\mathrm{Y}_{n+1}>Z_{\mathfrak{n}}\}}]+E[Z_{n}^{2}]$$=E[(2\mathrm{Y}_{n}+1)\cdot 1_{\{\mathrm{Y}_{n+1}>Z_{n}\}}]+E[Z_{n}^{2}]$.
$\square$

4Markovization
The profit process
is aMarkov chain, where the state spaces
and thetransition probability $p=\{p_{n}(j|i)\}$ are defined by (2) and (3), respectively. Now we
consider the maximum profit process $\{Z_{n}, n\geq 1\}$ , which is not necessarily Markov. We
are interested in some approach which makes the maximum process Markov on asuitablestate spaces. In the case, the state spaces are meaningful as far as it is small We call thisproblem aMarkovization of process. In this section the Markovization is performed
through an invariant imbedding method [1, p.82], [13, Chap.
$\{\mathrm{Y}_{n}, n\geq 0\}$$\{S_{n}\}$$\{Z_{n}\}$107
Let us define the past-value sets$\{\Omega_{n}\}$as follows :$\Omega_{n}:=\{\lambda_{n}|\lambda_{n}=(-1)\vee y_{1}\vee y_{2}\vee\cdots\vee y_{n-1}, y_{i}\in S_{i}, 1\leq i\leq n-1\}$$n=2,3$ ,$\ldots$.

the maximum-value-set to date . Then the past-value sets
In particular, we callsatisfy the forward recursive formula :$n$$\Omega_{n}$Lemma 4.1.
$\Omega_{2}=\{-1,1\}$$\Omega_{n+1}=${A$\vee y|\lambda\in\Omega_{n}$, $y\in S_{n}$ }$n=2,3$ ,$\ldots$.

In fact, we have$\Omega_{2}=\{-1,1\}$$n=3,4$ ,$\Omega_{n}=\{-1,0,1, \ldots, n-2, n-1\}$

Then$Z_{n}$

takes values on$\Omega_{n+1}$

for $n=1,2$ ,$\ldots$$\ldots$.

(Figure 2).
$Z_{4}$$Z_{3}$$Z_{2}$

333$Z_{1}$

22
1

1

$1$

\prime\prime\prime0\prime\prime\prime ’

0

0

-1

-1

-1

-1

$\Omega_{2}$$\Omega_{3}$$\Omega_{4}$$\Omega_{5}$Figure 2: Maximum profit process $Z=\{Z_{n}\}_{n\geq 1}$

Lemma 4.2. However the maximum profit process $Z=\{Z_{n}, n\geq 1\}$ is not Markov on. In fact, both transition probabilities
the state spaces$\{\Omega_{n+1}\}$$P(Z_{4}=2|Z_{2}=0, Z_{3}=1)=p$and$P(Z_{4}=2|Z_{2}=1, Z_{3}=1)=p^{2}$depend on the yesterday’s state and are not equal for $0<p<1$ .

108Proof. The following four equivalences axe easily shown.
,,,$Z_{2}=0$ , $Z_{3}=1$ , $Z_{4}=2\Leftrightarrow X_{1}=-1$ , $X_{2}=1,X_{3}=1$ , $X_{4}=1$$Z_{2}=0$ $Z_{3}=1\Leftrightarrow X_{1}=-1$ $X_{2}=1$ $X_{3}=1$,,$Z_{2}=1$ , $Z_{3}=1$ , $Z_{4}=2\Leftrightarrow X_{1}=1$ , $X_{2}=-1$ , $X_{3}=1$ , $X_{4}=1$ .
$Z_{2}=1$ $Z_{3}=1\Leftrightarrow X_{1}=1$ $X_{2}=-1$

The first two and the last two yield the former transition probability and the latter,
respectively. This completes the proof.

$\square$$(\mathrm{Y}_{4;}\lambda_{4})$(4; 3)(2; 3)$\mathrm{Y}_{1}$(2; 2)

1(0; 2)(2; 1)$\mathrm{Y}_{0}$(0; 1)

0(-2; 1)(0; 0)(-2; 0)-1(0;-1)(-2;-1)(-4;-1)$\tilde{S}_{0}$$\tilde{S}_{1}$$\tilde{S}_{2}$$\tilde{S}_{3}$Figure 3: Expanded profit process
First, by attachingas foUows :$\tilde{S}_{n}:=S_{n}$,$\Omega_{n}$, we expand the state space$\tilde{S}_{4}$$\tilde{\mathrm{Y}}=\{\tilde{\mathrm{Y}}_{n}, n\geq 0\}$$S_{n}$

to augmented state spaces$n=0,1$$\tilde{S}_{n}:=\{(y_{n};\lambda_{n})|yi_{\dot{l}}^{=x_{1}+x_{2}+\cdots+x_{\dot{l}}}\lambda_{n}=y_{1}\vee y_{2}\vee\cdots\vee y_{n-1}\in\{-1,1\},1\leq i\leq n$

Then the expanded state spaces$\{\tilde{S}_{n}\}$$\}\subset S_{n}\cross\Omega_{n}$$n=2,3$ ,are forwardly generated as follows$\ldots$, $N$ .

$\{\tilde{S}_{n}\}$

109
Lemma 4.3.
$\tilde{S}_{2}=\{(2;1), (0;1), (0;-1), (-2;-1)\}$$\tilde{S}_{n+1}=${ $(y+x$ ;A$\vee y$)$|(y;\lambda)\in\tilde{S}_{n},$$x\in\{-1,1\}$}$n=2,3$ ,, $N$ .

$\ldots$

Second we define anew transition law $q=\{q_{n}\}$ there by$p$$q_{0}(j|0):=\{$$q$

if $j=1$
if $j=-1$
if $j=i+1$
if $j=i-1$$p$$q_{1}((j;i)|i):=\{$$q$

if A $\vee i=\mu$
0otherwise$p_{n}(j|i)$$q_{n}((j;\mu)|(i;\lambda)):=\{$$n=2,3$ ,$\ldots$.

Finally we define asequence of random variables $\{\tilde{Y}_{n};n=0,1, \ldots\}$ by$n=0,1$ ;$\tilde{\mathrm{Y}}_{n}:=\mathrm{Y}_{n}$$n=2,3$ ,$\tilde{\mathrm{Y}}_{n}:=(Y_{n};\lambda_{n})$$\ldots$.

We callan expanded profit process. Thus
represents today’s profit, which$\lambda_{n}=(1)\veey_{1}\veey_{2}\vee\cdots\vee
y_{n-1}=z_{n-1}$
behaves stochastically. And
denotes the mcvximumtO-yesterday, which has been already determined. Thus
is deterministic. Every timerealizes avalue , the resulting pairyields the today’s maximum-value$\tilde{Y}=\{\tilde{Y}_{n}\}$$Y_{n}$$\{\lambda_{n}\}$$Y_{n}$$(y_{n};\lambda_{n})$$y_{n}$$\lambda_{n}\vee y_{n}=y_{1}\vee\cdots\vee y_{n-1}\vee y_{n}=z_{n}$under maximum operation V. In other words, the expanded profit process
generates the maximum process $Z=\{Z_{n}\}$ under the binary operation. Furthermore, wehave the following desired property.

$\tilde{\mathrm{Y}}=\{\tilde{\mathrm{Y}}_{n}\}$Lemma 4.4. The expanded profit process
is a Markov chain on the state$with$ the transition probability $q=\{q_{n}\}$ (Figure 3).
spaces$\{\tilde{\mathrm{Y}}_{n}, n\geq 0\}$$\{\tilde{S}_{n}\}$We define amapping$T_{n}$:$\tilde{S}_{n}arrow R^{1}$by$T_{n}(\tilde{y}_{n}):=\lambda_{n}\vee y_{n}$Then the sequence of mappings
sense :$\{T_{n}\}$$n=2,3$ ,transforms process$T_{n}(\tilde{Y}_{n})=Z_{n-1}\vee Y_{n}=Z_{n}$–$\{\tilde{\mathrm{Y}}_{n}\}$$n=2,3$ ,into$\ldots$$\{Z_{n}\}$in the following.

Thus the process
is aMarkovization of. Thus the Markovization is astochastic
version of the final state model [1, p.82], [13, p.71]$\{\tilde{\mathrm{Y}}_{n}\}$$\{Z_{n}\}$

110
4.1

Recursion for $E[Z_{N}]$Now let us take apositive integer $N(\geq 2)$ . We derive arecursive formula for the expected. We define aminal function
value of the maximum random variableby$T(\tilde{y}_{N}):=\lambda_{N}\vee y_{N}$Lemma 4.5.

$T:\tilde{S}_{N}arrow R^{1}$$te$$Z_{N}$.

holds that

$Jt$

$E[Z_{N}]=\tilde{E}_{\tilde{y}0}[T(\tilde{\mathrm{Y}}_{N})]$

where
state

$\tilde{E}_{\tilde{y}0}$

is the expectation operator induced from the transition law.

$q$and the initial$\tilde{y}_{0}=y_{0}=0$

Let us define the sequence of expected value functions$n=0,1$ ,$u_{n}(\tilde{y}_{n}):=\tilde{E}_{\tilde{y}_{n}}[T(\tilde{Y}_{N})]$$\{u_{n}\}$$\ldots$

as follows :, $N-1$$u_{N}(\tilde{y}_{N}):=\lambda_{N}\vee y_{N}$is the expectation operator induced from the transition law
where. We remark that takes the following values :initialstate
and an$\{q_{n}, q_{n+1}, \ldots, q_{N}\}$$\tilde{E}_{\tilde{y}_{n}}$$\tilde{y}_{n}\in\tilde{S}_{n}$$\tilde{y}_{0}=y_{0}=0$,$\tilde{y}_{n}$$\tilde{y}_{1}=y_{1}=-1$

or 1,$y\sim n=(y_{n};\lambda_{n})$$n=2,3$ ,$\ldots$, $N$ .

Then we have the backward recursive formula :Theorem 4.1.
$u_{0}(0)= \sum_{j\in S_{1}}u_{1}(j)q_{0}(j|0)$$i\in S_{1}$$u_{1}(i)= \sum_{j\in S_{2}}u_{2}(j;i)q_{1}(j|i)$

( ;A
$j$

$u_{n}(i; \lambda)=\sum_{j\in S_{n+1}}u_{n+1}$$u_{N}(i;\lambda)=\lambda\vee i$$\vee i$) $q_{n}(j|i)$$(i;\lambda)\in\tilde{S}_{N}$$(i;\lambda)\in\tilde{S}_{n}$, $n=2,3$ ,$\ldots$, $N-1$(10).

Thus, successively solving (10), we have the desired expected value of the maximum
profitover $N$-stage problem :$Z_{N}$$u_{0}(0)=E[Z_{N}]$.

Actually the recursive formula reduces as follows :Corollary 4.1.
$u_{0}(0)=pu_{1}(1)+qu_{1}(-1)$$u_{1}(i)=pu_{2}(i+1;i)+qu_{2}(i-1;i)$$u_{n}(i;\lambda)=pu_{n+1}$( $i+1$ ;A$\vee i$) $+qu_{n+1}(i-1;\lambda\vee i)$$(i;\lambda)\in\tilde{S}_{n}$$u_{N}(i;\lambda)=\lambda\vee i$$i=-1,1$$(i;\lambda)\in\tilde{S}_{N}$.

, $n=2,3$ ,$\ldots$, $N-1$

111
4.2

Recursion for$E[Z_{N}^{2}]$Now let us consider the expected value of the squared random variableof the terminal function we introduce the squared terminal function$T$$T^{2}(\tilde{y}_{N}):=(\lambda_{N}\vee y_{N})^{2}$.

$E[Z_{N}^{2}]=\tilde{E}_{\tilde{y}0}[T^{2}(\tilde{\mathrm{Y}}_{N})]$.

$Z_{N}^{2}$$T^{2}$. Here in place:$\tilde{S}_{N}arrow R^{1}$byThen we have

Lemma 4.6. It holds that

Let us define$\{v_{n}\}$as follows :$n=0,1$ ,$v_{n}(\tilde{y}_{n}):=\tilde{E}_{\tilde{y}_{n}}[T^{2}(\tilde{\mathrm{Y}}_{N})]$$v_{N}(\tilde{y}_{N}):=(\lambda_{N}\vee y_{N})^{2}$, $N-1$$\ldots$.

Then we have
Theorem 4.2.
$v_{0}(0)=pv_{1}(1)+qv_{1}(-1)$$i=-1,1$$v_{1}(i)=pv_{2}(i+1;i)+qv_{2}(i-1;i)$$v_{n}(i;\lambda)=pv_{n+1}$( $i+1$ ;A$\vee i$) $+qv_{n+1}$ ( $i-1$ ;A ), $n=2,3$ ,$(i;\lambda)\in\tilde{S}_{n}$$\ldots$$v_{N}(i;\lambda)=(\lambda\vee i)^{2}$(11)$\vee i$$(i;\lambda)\in\tilde{S}_{N}$, $N-1$.

Thus, the recursive computation of (11) yields the desired expected value:$v_{0}(0)=E[Z_{N}^{2}]$4.3.

Recursion for $P(Z_{N}=k)$

Now let us consider the probability distribution of. For each fixed
theprobability it takes value is calculated through invariant imbedding. We define theterminal function
by$Z_{N}$$k\in\Omega_{n\dagger 1}$$k$$T:\tilde{S}_{N}arrow R^{1}$$T(\tilde{y}_{N}):=\psi(\lambda_{N}\vee y_{N})$where$\psi(\cdot)$is the indicator function of aone-point set$\psi(z):=1_{\{k\}}(z):=\{$$\{k\}$:

1if $z=k$0otherwise

Then
Lemma 4.7. It holds that
$P(Z_{N}=k)=\tilde{E}_{\tilde{y}0}[T(\tilde{Y}_{N})]$.

112
Further we define$\{w_{n}\}$as follows :$n=0,1$ ,$w_{n}(\tilde{y}_{n}):=\tilde{E}_{\tilde{y}_{n}}[T(\tilde{Y}_{N})]$$w_{N}(\tilde{y}_{N}):=\psi(\lambda_{N}\vee y_{N})$$\ldots$, $N-1$.

Then

Theorem 4.3.
$w_{0}(0)=pw_{1}(1)+qw_{1}(-1)$$i=-1,1$$1;\mathrm{i})=pw_{2}(i+1;i)+qw_{2}(i-1;i)$$Wn(i;\lambda)=pw_{n+1}$( $i+1$ ;A$\vee i$) $+qw_{n+1}$ ( $i-1$ ;A, $n=2,3$ ,$\vee i$$(i;\lambda)\in\tilde{S}_{n}$$w_{N}(i;\lambda)=\psi(\lambda\vee i)$$(i;\lambda)\in\tilde{S}_{N}$

(12)

)

$\ldots$, $N-1$.

Thus, the recursion (12) yields the desired probability :$w_{0}(0)=P(Z_{N}=k)$.

References[1] R.E. Belman, Dynamic Programming, Princeton Univ. Press, NJ, 1957.
[2] R.E. Bellman, Some Vistas of Moderm Mathematics, University of Kentucky Press,
Lexington, KY, 1968.
[3] List of Publications :Richard Bellman, IEEE Transactions on Automatic Control,, 1213-1223.
AC-26(1981), No.
$5(\mathrm{O}\mathrm{c}\mathrm{t}.)$[4] R.E. Bellman, Eye of the Hurricane :an Autobiography, World Scientific, Singapore,

1984.

[5] R.E. Bellman (Ed. R.S. Roth), The Bellman Continuum :A Collection of the Worksof Richard Bellman, World Scientific, Singapore, 1986.
[6] R.E. Bellman and E.D. Denman, Invariant Imbedding, Lect. Notes in Operation
Research and Mathematical Systems, Vol. 52, Springer-Verlag, Berlin, 1971.
[7] R.E. Bellman and E.D. Denman, Invariant Imbedding :Proceedings of the Summer
Workshop on Invariant Imbedding Held at the University of Southerm California,
June -August 1970, Lect. Notes in Operation Research and Mathematical Systems,
Vol. 52, Springer-Verlag, Berlin, 1971.
[8] S. Iwamoto, Theory of Dynamic Program :Japanese, Kyushu Univ. Press, Fukuoka,

1987.

[9] S. Iwamoto, Maximizing threshold probability through invariant imbedding, Eds.
H F. Wang and U.P. Wen, Proceedings of The Eighth BELLMAN CONTINUUM,
Hsinchu, ROC, Dec.2000, pp. 17-22

113[10] S. Iwamoto, Fuzzy decision-making through three dynamic programming
proaches, Eds. H.F. Wang and U.P. Wen, Proceedings of The Eighth
CONTINUUM, Hsinchu, ROC, Dec.2000, pp.23-27.

$BEL\ovalbox{\tt\small REJECT}$[11] E.S. Lee, Quasilinearization and Invariant Imbedding, Academic Press, New$\urcorner$

1968.
[12] S. Ross, Stochastic Processes :second edition, Wiley&Sons, New York, 1996.

[13] M. Sniedovich, Dynamic Programming, Marcel Dekker, Inc. NY, 1992