% Lecture Notes in Mathematics, 1299, 
% Probability Theory and Mathematical Statistics, 
% S.Watanabe and Yu.V.Prokhorov(Eds.), Springer-Verlag, Berlin, 1988.

\documentclass[11pt,final]{article}

\evensidemargin=0.15in \oddsidemargin=0.15in \textwidth=6.25in
\topmargin=0.0in \headheight=0.0in \headsep=0.0in
\textheight=8.75in

\renewcommand{\baselinestretch}{1.2}

%
\newcommand{\Sessiontitle}[1]
 {
  \noindent \textbf{\large Session Title: {#1} \\}
 }

\newcommand{\Presentingauthor}[1]
 {\noindent \textbf{{#1}}}

\newcommand{\Talktitle}[1]
 {\noindent \textbf{\large Title: {#1}} \\}

\newcommand{\Affiliation}[1]{{#1}}
\newcommand{\email}[1]{{#1} \\}

\newcommand{\Coauthor}[1]
 {\noindent {\textbf{#1}}}

\renewcommand{\abstract}[1]
 {\noindent \textbf{Abstract: }{#1} \\}

\iftrue %%%%%%% If you do not have the "amsmath" or "amsfonts" package:
% \iffalse %%%%   Comment out the "iftrue" line, uncomment the "iffalse" line
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{verbatim}
%
% Definitions in case you do have the ams packages
%
\newcommand{\field}[1]{\mathbb{#1}}
\DeclareMathOperator{\PR}{\field{P}}             % Probability
\DeclareMathOperator{\E}{\field{E}}              % Expectation
\def\N{\field{N}}                                % nonnegative integers
\def\R{\field{R}}                                % Blackboard R - Reals
\def\F{\field{F}}                                % Functions/stationary policies
\def\A{\field{A}}                                % Action space
\def\X{\field{X}}                                % State space

\def\Z{\field{Z}}
%
% Definitions in case you do not have the ams packages
%
\else
\def\PR{\mathop{\rm I\kern -0.20em P}\nolimits}  % Probability
\def\E{\mathop{\rm I\kern -0.20em E}\nolimits}   % Expectations
\def\N{\mathop{\rm I\kern -0.20em N}\nolimits}   % Nonnegative integers
\def\R{\mathop{\rm I\kern -0.20em R}\nolimits}   % Blackboard R - Reals
\def\F{\mathop{\rm I\kern -0.20em F}\nolimits}   % Functions/stationary polices
\def\A{{A}}                                      % Action space
\def\X{{X}}                                      % State space
\fi
\def\r{C}
% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small

\begin{document}
  \Talktitle{
%%
The best choice problem for random number of objects 
 with a refusal probability
%%
}
  \Presentingauthor{Masayuki Horiguchi}, 
  \Affiliation{Kanagawa University, Japan}, 
  \email{horiguchi@kanagawa-u.ac.jp}
  \Coauthor{Masami Yasuda}, \email{yasuda@math.s.chiba-u.ac.jp}
% \Coauthor{Uptown Jones}, \email{jack.in.the.box.u@rapmusic.com}
  \abstract{
In this note, we will consider the best choice problem for random number of 
objects with a refusal probability. There are many papers and books on this 
subject from 
Chow/Robbibs/Siegmund(1971)\cite{cho-rob-sie71}
, 
Siryaev(1973)\cite{sir71}
downward.  These problems has been close relations with the martingale theory, 
the potential theory, the optimality principle in the mathematical programming.
And now it is derived the optimal rule by using the sum-the-odds theorem. 
Refer to 
Ferguson(2006)\cite{fer06}
, 
Bruss(2003)\cite{bru03}
, 
Tamaki(2001)\cite{tam01}
, 
Hsiau/Yang(2000)\cite{hsu-yan00}
etc. It would be preferes to call it the odds-theorem rather than 
the secretary problem or the best choice nowdays.  
Here we adapt a classical analysis to obtain its optimal value 
for the problem on Markov processes.

Firstly the formulation of stopping problem for Markov processes are given and 
its optimal equation of the value are designated. Since the secretary problem 
has a special transition probability, we show the optimal value is calculated 
as 
One-Look ahead policy or monotone stopping problem. Then it is treated 
asymptotically and solve the value in the explicitly form by a differential 
equation. 
Some equivalence relation is shown between the decision-theoretic form of the 
optimal equation and the transition probability with refusal. 

In the last, by a translation from the case of random number of objects to the 
standard form of optimal stopping problem, we could obtain the optimal value 
in the cited case of title. Also a variation for the selection is considered.
% (Not more than 250 words.)
}

\section{Formulation and Notations}
\label{sec:1}
%1. Introduction. 

The optimal stopping problem is a special case 
of Markov decision processes. The decision maker can either select to stop, in 
which case he receives reward and the process terminates, or to pay cost and 
continue observing the state. If the decision is made to continue, then he 
proceeds to the next state according to the given transition probability. 
The objective is to choose the policy which maximizes the expected value. 
A policy for the decision process means to take the adaptation of a stopping 
time of the process. 

Let $x_n, n=0,1,2,..$ be a Markov chain over a state space $S$ in $R^1$. 
We assume that $S$ is countable, but this is inessential for our discussion.. 
In the last section \ref{sec:3} the cases of the unit interval are considered. 
The optimal stopping problem is to find a stopping time l' which maximizes 
the expectation of payoff $v(i;t)$ starting at $i$. 
Let us denote the optimal value by 

\label{eq:(1.1)} 	
v(i) = sup_{\tau} v(i;\tau) 
                   
          = sup_{\tau} E[r(x_{\tau}) - \sum c(X_n) \vert x_0=i], i \in S


where r(i) means an immediate reward and c(i) a paying cost. The admissible class of the policies is the set of all finite stopping times. 
The detai led analyses are discussed by many authors such as 
Chow/Robbins/Siegrnund\cite{cho-rob-sie71}, Shiryaev\cite{shi73} and so on. 

Consider the set of states for which stopping immediately is at 
least as good as stopping after exactly one more period. Denote this 
set by 

\label{eq:(1.2)} 
B = {ie: S ;' r ( i ) ~ Pr (i) -c ( i) }

where Pr(i) = r. S P(i,j)r(j) and P(i,j), i,je:S, is a stationary
transition probal;>ility. The policy, defined by the hitting time of this set B, is called a "One-stage Look Ahead"(abridged by OLA) policy by Ross\cite{ros83}, since it compares stopping immediately with stopping after one period. Under certain conditions, He shows that the OLA policy is optimal. The OLA policy is 
useful for many problems and also extended to the continuous parameter process
by Prabhu\cite{pra74}. 

Our aim of this note is to obtain, by applying the potential operator, the explicit optimal value associated with the OLA policy for stopping problems. With this result, we will give, in the section \ref{sec:3}, the explicit solution of the various versions for the best choice problem in the asymptotic form. The first is the classical problem and the second is the case wi th the refusal probabi I ~ ty. Also the solution for the case of random number of objects is calculated. The last case was reduced to a functional optimality equation by an ad hoc method in Yasuda\cite{yas84}. The motivation for this approach arose in connection with the results of Darling\cite{dar85} and that of Hordijk\cite{hor74}. The former gave the upper bound of the optimal value by a potential operator and the latter gave a sufficient condition to find an optimal stopping time. 


\section{Markov Potential}
\label{sec:2}
%2. Markov potential and the optimal value. 

For a transition probability p=p(i,j) ,i,je:S, a function f=f(i), ie:S, is called a charge if lim [{I+P+ ??? +pk}f] (i) for each ie:S, exists and is finite-valued. Function g=g(i),ie:S is a potential if there exists a charge f such that g(i) = lim [{I+P+ ??? +pk}f] (i), ie:s. We shall use the notation g ( i ) = N f ( i), i e:s ? 
The relation between Markov Potential Theory and Dynamic programming or Markov Decision Process is discussed by Hordijk\cite{hor74}. Since, as in the section 1, the optimal stopping problem is a special case of Markov Decision Process, the optimality equation of the stopping problem is reduced as follows. 

\label{eq:(2.1)} 
v (i) = max {r (i), Pv (i) -c ( i) } , i \in S


Fundamental in such an investigation of Dynamic programming is the uniqueness 
of the equation \ref{sec:(2.1)} and the determination of the optimal policy and the 
optimal value. 

In this note we consider the optimal stopping problem, for which the OLA policy is optimal. To give a sufficient condition, we prepare 
the next two propositions. 
The subset B of S in \ref{eq:(1.2)} is closed if

\label{eq:(2.2)} 
P(i,j) = @ for i EB, j Ea 

where a denotes the complement of the set B. Thed process is stable 
if the sequence defined by 

v0{i)=r{i), 

v (i) = max{r (i), Pv lei) -c(i)} for n~l,
n n-

converges uniformly and limn )00 vn(i) = veil for iES. 
" 
\label{pro:2.1}
Proposition 2.1 (Ross\cite{ros83}). If the process is stable and the set B is 
closed, then the OLA policy is optimal. 

Although this situation occurs in many applications and is useful to determine the stopping region, the proposition does not state the optimal value. The stability is somewhat less satisfactory to check in" the appl ication because the optimal value is unknown. So we impose assumption on a potential of the chain. Our aim is to calculate the optimal expected value under the closedness and the following equalization assumption in stead of the stability assumption, and express it explicitly by using a potential. We call the problem where the OLA policy is optimal as the OLA-optimal stopping problem. 

\label{pro:2.2}
Proposition 2.2 (Hordijk\cite{hor74}). 

Suppose that 

\label{eq:(2.3)} 
v ( i ) = Pv ( i) -c ( i ) when it. r = { i ES ; V ( i) = r ( i) } ? 

If the value function is a potential, then the hitting time of set r becomes optimal. 

Proof. This is a special case in Theorem 4.1 of Hordijk\cite{hor74}. Q.E.D. 

Let" PA denote the restr iction to a subset A of the trans i tion probability P, i.e., 

\label{eq:(2.4)} 
PA(i,j) = P(i,j)lA(j) if i,je:s, 

where lA denotes the indicator of set A. 

     When the stability is dropped, as Ross shows, a stopping problem does not imply the optimality of the OLA policy. So we must impose a condition so as to preserve the OLA principle. The condition of equalizing for the reward function due to a potential notion is considered. 


Assumption 2.1. 
\label{ass:2.1}

We assume that 
\label{eq:(2.5)} 
  limk )oo[ (Ps)kr ] (i) = 0 for iEa 

where B denotes the complement of the set B defined by \ref{eq:(1.2)}, and that the potential for PBr-c is finite-valued with respect to P ' that is, 

\label{eq:(2.6)}
 [N -(P r -c) ] (i) < co for IEB. 

The assumption of the equation \ref{eq:(2.5)} is equivalent to 

 limk )co E[r(~k)l{T>k};xntB,n=l, ?? ,k-l] = 9 

where T is the hitting time of B. The property limk ) co (Pa)kV = 0 for the optimal value is called equalizing 
in Optimal Gambling(Dubins /Savage\cite{dub-sav65} or Hordijk\cite{hor74}). 
One might say that here the actually received in the time period up to Nand the promised earnings equalize as N tends,to infinity. If the optimal value satisfies this property, the assumption \ref{eq:(2.5)} holds since v ( i). > r ( i), i E S by (2 ? l) ? 
= 

Theorem 2.1. 
\label{thm:2.1}

Under the assumptions \ref{eq:(2.5)} and \ref{eq:(2.6)} 
the OLA policy 
sa 
TB is optimal, that is, the optimal policy is the hitting. time of B. The optimal value veil = v(i;T) is given by

\label{eq:(2.7)} 
v(i) = rei) + N(pr-r-c)+(i) = 
-
r(i) on B 
Na(PBr-c) (i) on B 

where + is the positive part of the function, and Nand NB are potentials with respect to P and P respectively.
a 

Proof. The proof for the optimality of the OLA policy is similar to 
Ross\cite{ros83} and Hordijk\cite{hor74}. In generally if veil, iE S is 
a solution of the optimality equation \ref{eq:(2.1)}, then v(i) > r(i) and v(i) > pv(i) -c(i)
= = 
for iES. So 
0-1 veil ~ pnr(l) -L pkc(i) for each n. 
-
k=9 
It yields that v(i) ~ v(i; T) for any policy T < co.
-
Therefore it is sufficient to assert the followings to show the optimality. One is that, for the OLA policy TB, its value equals the right hand side of 
\ref{eq:(2.7)}, that is, 
v(i;T B) = rei) on B and NB(PBr
-
c) (i) on B, and the second is that it satisfies 
the optimality equation \ref{eq:(2.1)}. 

Because of the definition 
OLA policy, v(i) = r(i) on Band 
. 
v(i) = Pv(i)-c(i) = PBv(i) + 
-c ( I) on B. Hence we get the 

first assertion immediately. Nextly we show that it satisfies 
the optimality equation \ref{eq:(2.1)}. 
From P f ( i ) = P B f ( i), iE B for any f=f(i), we have pv(i) -c(i) = PBv(i) -c(i) = PBr(i) -c(i) = Pr ( i) -c ( i) on B. Hence 

max {r (i), Pv (i) -c (i) } = max{r(i), Pr(i) -c(i)} = rei) for iEB. 
On the other 	hand, by substitution of (2.7), 
Pv ( i) -c ( i) 	= Psv (i) + P B v ( i) -c ( i) = [PsNa(PBr-c?) (i) + PBr(i) -c(i) = [Na(PBr-c?)(i), iES. 
On id~, that 
rei) < Pr(i) -c(i) = Par(i) + PBr(i) -c(i) implies rei) -Par(i) < PBr(i) -c(i). And, by the assumption (2.6), rei) ~ [Na(PBr -c?) (i) for iEa. Combining the above assertions, 
max{r(i), Pv(i) -c(i)} = max{r(i), [Na(PBr-c?)(i)} = [N(PBr-c?) (i) for iE a. 
a Thus the value v(i)=v(i;~B) satisfies the optimality equation. It now remains to calculate the potential N(pr-r-c)+(i), iES. From the definition of the set B in (1.2), we have (pr-r-c)+(i)=9 on 
B. 	So the support of charge is the complement of B and hence 
                     N(Pr-r-c)+(i)=9 on B. On other hand, since (Pr-r-c) + (i) = (Pr-r-c) (i) for iEa, we have that 
P (Pr-r-c) + (i) = P (Pr-r-c) (i)
a 	. 
= ?P-) 2r+p_p r-P-r-P-c) (i), 	lEB.
B 	B B B B 
?
Repeatlng this procedure to take the expectation up to k times and adding these, ., {I+P+p2+ ??? +pk } (pr-r-c)+(i) k'. [{ k-l k-2 } ) . . 
= (P) r(l) + 	(P) +(P) + ?? +I (PBr-c) (1) -rei), lEB. 
         a aaa Hence 
. .. 	
N(pr-r-c)+(i) = [Na(PBr-c?) (1) -r(l), lEB follows immediately 
from the assumptions \ref{eq:(2.5)} and \ref{eq:(2.6)}. Q.E.D. 


We remark that the upper bound on the optimal value in Theorem 
3.6 of Darling\cite{dar85} equals exactly the optimal value in this case. That is, the bound holds with equality when the OLA policy is optimal and it is , equalizing. This explicit solution and 
the proposition \ref{pro:2.1}, \ref{pro:2.2} determine the optimal value 
and policy completely in the OLA-optimal stopping problem. 

\section{The best choice Problem}
%3. The Best Choice Problem. 
\label{sec:3}

In this section we apply the previous method to the typical stopping problem 
known as the best  
choice problem. By taking a scale limit, the asymptotic form of the problem is considered in order to get an analytical explicit solution. In the asymptotic form the state space of the problem is not countable but the unit interval. However immediately the previous method can be applied to the case. Some of results are well known and the optimal values are already obtained by some method, for example, by using differential equation. Here we intend to illustrate it for the application which optimal value can be determined by the unified previous me,thod. Each of these are cases whose problem is the OLAoptimal stopping one. 

 \subsection{Classical Problem}
%3.1. The Classical Secretary problem. 
\label{sec:3.1}

The secretary problem, variously called dowry problem or Googol, is an optimal stopping problem based on relative ranks for objects arriving in a random fashion; the objective is to find the stopping rule that maximizes the probability of stopping at the? best object of the sequence. The optimality equation for the optimal value veil, iES, the maximal probability of win, on the state space S={1,2, ?? ,n} is as follows. 
n v ( i) = rna x{i/ n, i L v ( j ) I ( (j-1) j) } , iE{1,2, ??? ,n-l}, v(n)=l j=i+l 
where there are no costs. This formulation of the problem as Markov Process is given by Dynkin and Yushkevitch\cite{dyn-yus69}. Also refer to 
Chow/Robbins/Siegmund\cite{cho-rob-sie71} or Shiryaev\cite{shi73}. 
To consider the problem in the asymptotic form, take the scale 1imit by i In --> x as i, n --> co. It becomes that 

\label{eq:(3.1)}
 	vex) = max{ x , x f 1 v(y)y-2 dyl, xES=[G,l]. x 
The solution of (3.1) is well known as 
-1 	[n -l]
e 	on '0, e . , 

\label{eq:(3.2)} 	
v (x) = -1 
x 	on [e ,1]. 

Now we extend the problem by changing the reward function r(x)=x, which means probabili ty of choosing the best object in the classical secretary problem, to a general reward r(x). To ensure the OLA policy is still optimal, we assume, for a function hex) defined by 

\label{eq:(3.3)}
 	hex) =r(x)-x f1 r(y)y-2 dy on [13,1] , 
x 

that 


i) each term of the function h(x) is finite-valued on [0,1], and ii) it changes its sign from -to + only once as x increases 0 to 1 and so the equation h(x)=0 has a unique solution a. The optimality equation \ref{eq:(3.1)} with the reward function r(x) is 

\label{eq:(3.4)} 	
v (x) = rna X { r (x) , x f v(y)y-dy}, x?(0,l] ? x 

provided that the underlying Markov chain is unchanged. The solution of this equation \ref{eq:(3.4)} is given by 

\label{eq:(3.5)}
        r(a) 	on [0,a], 
 	v (x) = 
r (x) 	on [a,l] 

where a is defined by \ref{eq:(3.3)}. 

In fact, one can show this \ref{eq:(3.5)} by applying the previous result. Straightforward calculation yields that the set B becomes [a ,1] and it is closed with respect to the transition probability: 

-2
xy dy 	for 0<x<y<1,
. 
P(x,dy) = 
otherwise. 
r(a) (x/a) 10gn(a/x)/n! for x?[0,a], n=0,1,2,... Hence 

We have PBr (x) = r (a) (x/a) and 
-1 	2
NaPBr(X) = r(a) (x/a) {1+10g(a/x)+2 log (a/x)+ ??? 
-1 	n
+(nl) log (a/x)+ ??? } 
= r (a) 

for x?[0,a] and thus the assumption \ref{eq:(2.6)} is satisfied. 
Also we can check the condition of \ref{eq:(2.5)}: 
n 	. 
f a 	-2 n-1
(P) r(x) = x 	{r(y)y log (y/x)/(n-1)1}dy
a 
x 

tends to zero as n -~> co for X? [0, a]. 


 \subsection{Problem with a refusal probability}
%3.2. A Problem with Refusal Probability.
\label{sec:3.2}
 
A variant of the best choice problem is a case with a refusal probability discussed by Smith\cite{smi75}. We can also formulate the problem as optimal stopping on a Markov chain. The asymptotic form of the transition probabi1ity is obtained immediately and we have 

-1 	p
py (x/y) dy 	0<x<y<1, 
P(x,dy) = 
otherwise 

where p is a given parameter o < p 5 1, which quantity 1-p means a
probability of the refusal. 	When there is no refusal, i.e., p=l, it 
reduces to the classical secretary problem discussed 
in the section \ref{sec:3.1}. 

Similar1y as before, the optima1 i ty equation for the stopping problem 
with refusal probability p is 
1 1 

\label{eq:(3.6)}
 	v (x ) = rna x {r (x) , f py-(x/y)Pv(y)dy}, x?[0,1) ? x 

Define a function hex) by 
1 1 	" 
"

\label{eq:(3.7)}
 , hex) = rex) -f {py-(x/y)Pr(y) ldy, x?[0,1) ? x 

Under the same assumptions as \ref{eq:(3.3)}, we obtain the optimal value with refusal probability as follows. 
rea) 	on [0,a), 

\label{eq:(3.8)}
 	v (x) = r (x) on [a, 1 ) 

where 	is a unique solution of h(x)=0 in \ref{eq:(3.7)}. 
Another method to solve the best choice problem is given by Mucci\cite{muc73}, 
which method reduces the value to the solution of a differential equation. 
Let 
1 	1 

v(x) = f {py-(x/y)Pr(y)}dy, xe:[0,1] x 

which means a conditional optimal value. This satisfies 
-1 	+

\label{eq:(3.9)} 
dV(x)/dx = -px (r(x)-V(x? , xe:[0,1] 
V(1)=0. * 

The optimal value at the beginning v = V(0) equals rea). 


 \subsection{Random number of objects}
%3.3. A Problem with Random Number of Objects. 
\label{sec:3.3}

The discussion of the problem for variant on the random number of objects is given by Presman/Sonin\cite{pre-son72}. The random environment in the problem means that there is a distribution ~(x) over x e:[0,1] which denotes the random number of objects. 
If we adapt the approach by the differential equation \ref{eq:(3.9)}, 
the following functional equation is obtained by Yasuda\cite{yas84}. 
For xe:(0,1], 

\label{eq:(3.10)} 
1 . -1 	+
dV(x) = Vex) [1-~(x)]-d ~(x) -x (R(x)-V(x? dx, Vel) = 0 

where we set 	, 

\label{eq:(3.11)}
 	R (x) = x ( 1-~(x) )-1 

When the distribution is absolutely continuous, \ref{eq:(3.10)} 
reduces to a differential equation such as \ref{eq:(3.9)}. Let us define 
1 1 

g (x) = 
and hex) = g(x) -f y-g(y)dy for x?[0,l]. x 

We assume conditions on the distribution ~(x) so that these functions R(X), g(x) and hex) are well defined. The following result is obtained already by 
Yasuda\cite{yas84}. 
If hex) changes its sign only once from -to + as x varies from 0 to 1, and if !flex) is continuous for 0 < x < 1, then the optimal value * 
at the beginning v 	= V(0) is given by 

\label{eq:(3.12)}
 	v * = (l-~(a?V(a) = ag(a) 
. 
where a is a unique solution of h(x)=0 for x?[0,l]. 
�@�@�@This can be also obtained by applying the previous method. Since the optimality equation with random number of objects in the asymptotic form is, for x?[0,l], 
-1 
.

\label{eq:(3.13)}
 vex) = rnax {R (x) , . x. (1-~ (x) ) f1 (l-t(y?y-2 v(y)dy), x 

we have 


\label{eq:(3.14)}
 	v (x) = 
R(a) 	on [0,a], 
R (x) 	on {a, 1] ? 

In fact, it is equivalent to the classical secretary problem 
w ( x ) = rna x { r (x) , x f1 y-2 w(y)dy} x 
with the function 

\label{eq:(3.15)}
 w(x) 	= (l-~(x?v(x) 

and 	with the reward function . 1 

\label{eq:(3.16)}
 	rex) = x f y-1d!fl(y). x 


Hence the solution \ref{eq:(3.14)} is immediately obtained by the result 
of \ref{eq](3.5)}. 
This method is simpler than the ad hoc treatment of the 
functional equation \ref{eq:(3.10)}.


\section{Random number of objects with refusal}



\section{Remarks}



%References 
\begin{thebibliography}{99}
%\bibitem{bell57} 
%R.E.~Bellman, {\em Dynamic Programming}, 
%Princeton Univ. Press, NJ,  1957.

\bibitem{bru00} 
Bruss,F.T. ``Sum the odds to one and stop", Ann. Prob. 28 (2000), 1384-1391.

\bibitem{bru03} 
Bruss,F.T. ^^' ^^'A note on Bounds for the Odds-Theorem of Optimal Stopping", 
Ann. Prob. 32 (2003), 1859-1861.

\bibitem{cho-rob-sie71} 
%[1]
Chow,Y.S., Robbins,H. and Siegmund,D.: Great Expectations: 
The Theory of Optimal Stopping, Houghton Mifflin, Boston (1971). 

\bibitem{dar85} 
%[2]
Darling, D.A. : Contribution to the optimal stopping problem, 
Z. Wahr. verw. Gebiete 70 (1985), 525-533. 

%\bibitem{dub-sav65}
%[3]
%Dubins,L.E. and Savage,L.J. : How to Gamble if You Must: 
%Inequalities for Stochastic Processes, McGrow-Hi11, New York (1965). 

\bibitem{dyn-yus69} 
%[4]
Dynkin,E.B. and Yushkevitch,A.A. : 
Theorems and Problems on Markov Processes, 
Translation: Plenum Press, New York (1969). 

\bibitem{fer00} 
Ferguson, T.S. 
The sum-the Odds theorem with application to a stopping game of Sakaguchi,
http://www.math.ucla.edu/~tom/

\bibitem{fer89} 
Ferguson, T.S. 
Who solved the secretary problem? 
Statistical Science, 4(1989), 282-296.
 
\bibitem{fer04} 
Ferguson, T.S. 
Selection by Committee, in Advances in Dynamic Games, 
A.S. Nowak and K. Szajowski eds., (2004) 183-188, Birkhauser.
(also refer to http://www.math.ucla.edu/~tom/).


\bibitem{hor00} 
%[5]
Hordijk, A.: Dynamic Programming and Markov Potential Theory, 
Mathematisch Centrum, Amsterdam (1974). 

\bibitem{hsu-yan00} 
Hsiau, Shoou-Ren and Yang Jiing-Ru, A natural variation of the standard 
secretary problem, Statistica Sinica, 10 (2000), 639-646. 

\bibitem{kaw-tam03} 
Kawai,M. and Tamaki,M. Choosing either best or the second best  
when number of applicants is random,
Computers and Mathematics with Applications, 46, (2003), 1065-1071.


%\bibitem{kme76} 
%[6]
%Kemeny,J.G., Sne11,J.L. and Knapp,A,W. : 
%Denumerable Markov Chains, 2nd eds., Springer-Verlag, Berlin (1976). 

\bibitem{muc73} 
%[7]
Mucci, A. G. : Differential equations and optimal choice problem, 
Ann. Statist. 1 (1973), 104-113. 

%\bibitem{pra74} 
%[8]
%Prabhu, N.U. : Stochastic control of queueing systems, 
%Nav. Res. Logist. Q. 21 (1974), 411-418. 

\bibitem{pre-son72} 
%[9]
Presman,E.L. and Sonin,I.M. : 
The best choice problem for a random number of objects, 
T. Probe App1. 17 (1972), 657-668. 

\bibitem{ros83} 
%[10]
Ross, S.M.: Introduction to Stochastic Dynamlc Programmlng, 
Academic Press, New York (1983). 

\bibitem{sam91} 
Samuels,S.M. Secretary problems, In Handbook of Sequential Analysis, 
(B.K.Ghosh and P.K. Sen, eds.) Dekker, New York. 1991

\bibitem{shi73} 
%[11]
Shiryaev, A.N.: Statistical Sequential Analysis, Translation: 
American Mathematical Society, Providence (1973).


\bibitem{smi75} 
%[12]
Smith, M.H. : A secretary problem with uncertain employment, 
J. App1. Probe 12 (1975), 620-624. 

\bibitem{tam01} 
Tamaki,M. Optimal stopping on trajectories and the ballot problem,
J. Appl. Prob. 38, (2001), 946-959.


\bibitem{yas84} 
%[13]
Yasuda, M. : Asymptotic results for the best-choice problem 
with a random number of objects, 
J. App1. Prob. 21 (1984), 521-536.


\bibitem{yas88} 
Yasuda,M. : On the value for OLA-optimal stopping problem by potential 
theoretic method, 
Lecture Notes in Math, 571-580, 1299, Springer-Varlag, (1988) 


\end{thebibliography}

\end{document}


 Lecture Notes in Mathematics, 1299, 
 Probability Theory and Mathematical Statistics, 
 S.Watanabe and Yu.V.Prokhorov(Eds.), Springer-Verlag, Berlin, 1988.

On the value for OLA-optimal stopping problem by potential 
 theoretic method, Lecture Notes in Math, 571-580, 1299, 
 Springer-varlag, (1988) 


Masami Yasuda 

Summary. The stopping problem on Markov process with OLA(One-stage Look Ahead) 
policy is considered. Its associated optimal value could be expressed explicitlyby a potential for a charge of the positive part of the difference between the immediate reward and the oneperiod-after reward. As appl icat i on to the best cho ice problem, the optimal value of three problems: the classical secretary problem, the problem with a refusal probability and the one with random number of objects are calculated. 








