The best choice problem for random number of objects
with a refusal probability
Masayuki Horiguchi,
Masami Yasuda
November 21, 2009
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),Siryaev(1973) 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 theoptimal rule by using the sum-the-odds theorem. Refer to Ferguson(2006), Bruss(2003), Tamaki(2001),Hsiau/Yang(2000) etc. It would be prefered 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 theproblem on Markov processes.
Firstly the formulation of stopping problem for Markov processes are given and its optimal equationof 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. Someequivalence relation is shown between the decision-theoretic form of the optimal equation and thetransition probability with refusal.
In the last, by a translation from the case of random number of objects to the standard form ofoptimal stopping problem, we could obtain the optimal value in the cited case of title. Also a variation
for the selection is considered.

1 Formulation and Notations
The optimal stopping problem is a special case of Markov decision processes and the decision makercan either select to stop so as receiveing rewards, or to pay costs and continue observing the state. Let
xn , n = 0, 1, 2, · · · be a Markov Chain with a transition probability P = P(i, j), i, j ∈ S over a state space
S in R1 . We assume that S is countable, but this is inessential and for our discussion so that the scaling
limit case of problems with the random numbers can be treated. For a stopping time τ, the aim is tomaximize the expectation of payoff v(i; τ ) starting at i and its optimal value v(i ) defined by[]τv(i ) = sup v(i, τ ) = sup E r ( xτ − ∑ c( xn )
τ <∞

τ <∞

n =01x0 = i , i ∈ S(1.1)

where r (i ) and c(i ) (i ∈ S) mean an immediate reward and a paying cost respectively. Refer toChow/Robbibs/Siegmund(1971), Siryaev(1973) etc.
The relation between Markov potential theory and Dynamic Programming or Markov decision processes is well known. The optimality equation is reduced as follows.
v(i ) = max{r (i ), Pv(i ) − c(i )}, i ∈ S.

(1.2)

Consider the set of states for which stopping immediately is at least as gppd as stopping after exactly
one more period. Denote this set by
B = {i ∈ S | r (i ) ≥ Pr (i ) − c(i )}(1.3)

where Pr (i ) = ∑ j∈S P(i, j)r ( j). The policy, defined by hitting time of this set B, is called a One-stage Loog
Ahead(abridged as OLA) policy, refer to Ross(1983). It is sufficient that the OLA policy is optimal if B isclosed and eventually hits to the set. That the set is closed means if
P(i, j) = 0 fori ∈ B, j ∈ B(1.4)

where B denotes the complement of the set B.
There are many discussions on Markov stopping theory excellently as the excessive function, themartingale theory and so on, however the general framework does not cover for specific solution in
the exploit structure or interesting features. The aim of this note is to obtain the explicit optimal value
associated with OLA policy and various problems in the asymptotic form. Firstly the motivated case forthe classical secreraly choise problem and then for the variation of the case with the refusal probability.
The odd-theorem by Bruss(2000) and Ferguson(2008) will be applied also as the optimal stopping rule.

2 Markov Potential
Let PA denote the restriction to a subset A of S for the transition probability P, that is,PA (i, j) = P(i, j)1 A (i )(2.5)

where the indicator of A is 1 A (i ) = 1/0(i ∈ A)/(i ∈/ A). We shall use the notation of a potential as[]
N f (i ) = lim { I + P + P2 + · · · + Pk } f (i ) i ∈ S.
nTheorem 2.1 If we assume that[]limk ( PB )k r (i ) = 0[]
NB ( PB r − c) (i ) < ∞(2.6)

for i ∈/ B, then(i) the OLA policy τB is optimal,(ii) the optimal value v(i ), i ∈ S is given by{v(i ) = r (i ) + N ( Pr − r − c)+ (i ) =r (i )NB ( PB r − c)(i )

onon

B
B

(2.7)

where + is the positive part of the function, and N and NB are potentials with respect to P and PB
respectively.
23 The best choice Problem
3.1 Classical Problem
The secretary problem is an optimal stopping problem based on relative ranks for objects for objects
arriving in a random fashion. The objective is to find the stopping rule that maximizes the probabilityof stopping at the best object among the sequence. The formulation of the problem as Markov processes
is given by Dynkin/Yushkevitch(1969).
The state space is S = {1, 2, 3, · · · , n} and the reward, its win of probability is r (i ) = i/n, thei, 1 ≤ i < j ≤ n. The optimal value v(i ), istransition probability is P(i, j) =j ( j − 1)v(i ) = max{i/n,ni∑ j( j − 1) v( j)},i = 1, 2, · · · , n − 1,v(n) = 1.

(3.8)

j = i +1

Taking a scale limit of i/n → x as i, n → ∞, it becomes thatv( x ) = max{ x, x

∫ 1xv(y)dy},y2x ∈ S = [0, 1],v(1) = 1.

where the state space is S = [0, 1]. The solution is well known as{e−1 on [0, e−1 ],v( x ) =xon [e−1 , 1].

(3.9)(3.10)

By extending the reward r ( x ) in general, that is,v( x ) = max{r ( x ), x

∫ 1xv(y)dy},y2x ∈ S = [0, 1],v(1) = 1.

(3.11)

it is also the OLA policy is still optimal.
Assumption 3.1 The functionh( x ) = r ( x ) − x∫ 1xr (y)dyy2

is finite on [0, 1] for a given r ( x ) and it changes its sign from − to + only once as x increases 0 to 1.
So there exists a unique solution α of the equation h( x ) = 0.
Theorem 3.1 Using this solution, the assumption 3.1 implies that{r (α) on [0, α],v( x ) =r ( x ) on [α, 1].

(3.12)

Because the result of the equation (2.7) is calculated asx
PB r ( x ) = r (α) ,α(by using the notation (1.3).
Note also that

−xPB)n(α)
xPB r ( x ) = r (α) logn/n!,αx()+d v( x )= r ( x ) − v( x ) ,dx
3x ∈ [0, 1].

NB PB r ( x ) = r (α)

3.2 Problem with a refusal probabilityA variant for the classical best choice problem is considered by Smith(1975) inducing a refusal probability. A given p means the probability of not refused case and the quality 1 − p is a probability of therefusal. When there occues no refusal, that is, the usual standard problem corresponds to p = 1. The
asymptotic form of the transition probability is given as{py−1 ( x/y) p dy 0 < x < y < 1,P( x, dy) =(3.13)0otherwise
Similarly before
Assumption 3.2 The function
h p (x) = r(x) − p∫ 1xr (y)( x/y) p dyyis finite on [0, 1] for a given r ( x ) and it changes its sign from − to + only once as x increases 0 to 1. Its uniquesolution is denoted by α p of the equation h p ( x ) = 0.
Theorem 3.2 Using this solution α p , the assumption 3.2 implies that{r (α p ) on [0, α p ],v( x ) =r(x)on [α p , 1].

(3.14)

It is also known the technique of using a differential equation by Mucci(1973). We could apply thecase by this technique. Let∫ 1V (x) = pxr (y)( x/y) p dy,ywhich means a contditional optimal value. This satisfies() − x dV ( x ) = p r ( x ) − V ( x ) + ,dx
V (1) = 0.

x ∈ [0, 1]x ∈ [0, 1],(3.15)The optimal value at the begining v∗ = V (0) = r (α p ). Confirming that the case of r ( x ) = x, theequation h p ( x ) = 0 solves x = α p = p1/(1− p) which consist with the result by Smith(1975).

4 Random number of objects
4.1 Formulation for random number of objects
The discussion on the stopping choice problem with a random number of objects is firstly by Presman/Sonin(1972). Then Rasmussen/Robbins(1975), Tamaki(1979), Irle(1980), Petruccelli(1983) etc.
If we restrict ourselves that the support of distribution for a number of objects is bounded, the technique of the previous scaling limit could be applied.
Assumption 4.1 A random number of objects N is bounded and let
n = inf{k ≥ 1; P( N > k) = 0}.
4

By using the notation of pi = P( N = i ) and πi = P( N ≥ i ) = ∑k≥i pi , the transition probability matrix
for this case is as follows:
i πj, 1 ≤ i < j ≤ n,j ( j − 1) πini pk, 1 ≤ i < n, p(n, n) = 1,p(i, n) = ∑k πi
k = i +1ni pk
r (i ) = ∑,c(i ) = 0, ∀i.
k πi
k =ip(i, j) =(4.16)

If we denote the distribution by Φ( x ), x ∈ [0, 1] of its random number for objects, and taking the scale
limit of k, n → ∞ with k/n = x, then v(i ) → V ( x ) andpk /πk → dΦ( x )/(1 − Φ( x )),i n pkxi pk=→ R( x ) =∑k πiπi k =i k
1 − Φ( x )k =inr ( k + 1) = ∑∫ 1x

the resulting the differential equation is given as − x dV ( x ) + x V ( x ) dΦ( x ) = ( R( x ) − V ( x ))+ dx,
1 − Φ( x )V (1) = 0wherexR( x ) =1 − Φ( x )∫ 1x

y−1 dΦ(y),x ∈ [0, 1]

y−1 dΦ(y).

(4.17)(4.18)The details refer to Yasuda(1984).
Assumption 4.2 We assume that dΦ satisfies the conditions:
1. (1 − Φ( x ))−1
∫ 1

2. xx

∫ 1x

y−1 dΦ(y) → 1

y−1 dΦ(y) → 0

asasx → 1,x → 0.

This assumtion implies that R( x ) → 0 ( x → 0) and → 1( x → 1). In the usual non-random case,∫ 1
1R( x ) = x, these conditions are satisfied since
y−1 dΦ(y) = 1 for x ̸= 1.
1 − Φ( x ) x
Typical example of a random number N is the uniformly distributed case on a partial interval {n −m, n − m + 1, · · · , n − 1, n} of {1, 2, · · · , n} provided that (1 ≤ m ≤ n). Letting θ = m/n is fixed forn, m → ∞, Φ( x ) = 0, (0 < x < 1 − θ ), = ( x − 1 + θ )/θ, (1 − θ < x < 1).

1 − θ ≥ e −2α: threshold√1 − θe−1

1 − θ ≤ e −2e −2casev∗ :optimal value√1−θ
log(1 − θ )e−1−
θ
2e−2 /θ

If θ → 1 it tend to 2e−2 as discussed in Presman/Sonin(1972) etc. Alternatively, if θ → 0, this reduces
to the non-random classical problem and it tend to e−1 as is well known. However it is interesting thatthe threshold α = e−2 does not depent on θ in case of 1 − θ ≈ 0, that is, case of the ambiguity is beingin spread.
5

4.2 Random number of objects with refusal
Here we would like to impose a refusal probability for the model. As it had been shown that, from theoptimal equation of classical problem to one with a refusal in section 3,V (x)Instead of V ( x ) in the optimality equation (4.17), consider dv( x ) = dV ( x ) −dΦ( x ). Then,1 − Φ( x )it holds that{}∫ 1x−2v( x ) = max R( x ),(1 − Φ(y))y v(y) dy(4.19)
1 − Φ( x ) xwith R( x ) in (4.18).
In a general consideration of decision for ”stop”, there exist some possibility of ”continuity” in therefusal problem. So for given transition matrix P and reward r, the optimality equation of stopping
problem: v( x ) = max{ R( x ), Pv( x )}, 0 ≤ x ≤ 1 have a modification with a refusal probability p( x ), 0 ≤x ≤ 1 becomesv( x ) = max{ p( x ) R( x ) + (1 − p( x )) Pv( x ), Pv( x )},0 ≤ x ≤ 1.

(4.20)

1x(1 − Φ(y))y−2 v(y) dy,
1 − Φ( x ) x∫ 1(∫ 1)q( x ) = exp
y−1 (1 − p( x )) dy
and h( x ) =y−1 dΦ(y),(4.21)

By letting∫

Pv( x ) =xx

the following assumtion assures Theorem 4.1.
Assumption 4.3 Assume thatH p ( x ) = h( x ) − q( x )∫ 1xh(y) p(y)dyy q(y)(4.22)

changes its sign once from − to + as x increase.
Theorem 4.1 If Assumption (4.3) is satisfies, the solution is given as the value{inf{ x; H p ( x ) ≥ 0}∗αp =1 i f empty(4.23)

determine its threshold policy and so the optimal value v(0+) in (4.20) .
However in order to display the above assertion or explicit form, it is not easy for us. Even thesimplest case of p( x ) = p (0 < p < 1) and Φ( x ) = x (0 ≤ x ≤ 1), it needs the discussion on Lambert
W function.

References[1] Bruss,F.T.(2000); Sum the odds to one and stop, Ann.Prob. 28(3), 1384-1391.
[2] Bruss,F.T.(2003); A note on Bounds for the Odds-Theorem of Optimal stopping, Ann. Prob. 32,1859-1861.

6

[3] Bruss,F.T., Samuels,S.M.(1987); A unifies approcah to a class of optimal selection problem s withan unknown number of options, Ann.Prob.15(2) 824-830.
[4] Chow,Y.S., Robbibs,H. and Siegmund,D.(1971): Great Expectations: The Theory of Optimal Stopping, Houghton Mifflin, Boston.
[5] Darling,D.A.(1985):Contribution to the optimal stopping problem, Z. Wahr. verw.Gebiete 70, 525533.
[6] Dubins,L.E. and Savage,L.J.(1965): How to Gamble if you must: Inequalities for Stochastic Processes, McGrow-Hill, New York.
[7] Dynkin,E.B. and Yushkevitch,A.A.(1969): Theorems and Problems on Markov Processes, Translation: Plenum Press, New York.
[8] Ferguson, T.S.(2008); The sum-the-Odds theorem with application to a stopping game of Sakaguchi, http://www.math.ucla.ucls.edu/ tom/
[9] Ferguson, T.S.(1989); Who solved the secretary problem? Statistical Science, 4 ,282-296.
[10] Ferguson, T.S.(2004);Selection by Committee, in Advances in Dymnamic Games, A.S.Nowak andK.Szajowski eds., 183-188, Birkhauser.
[11] Hordijk,A.(1974); Dynamic Programming and Markov Potential Theory, Mathematisch Centrum,Amsterdam.
[12] Hsiau, Shoou-Ren and Yang Jiing-Ru(2000);A natural variation of the standard secretary problem,Statistica Sinica, 10, 639-646.
[13] Irle,A.(1980);On the best choice problem with random population size, Z.Oper.Res. 24, 177-190.
[14] Kawai,M. and Tamaki,M.(2003); Choosing either best or the second best when number of applicants is random, Computers and Mathematics with Applications, 46, 1065-1071.
[15] Mucci,A.G.(1973); Differential equations and optimal choice problem, Ann.Statist.,1, 104-113.
[16] Prabhu,N.U.(1974); Stochasitic control of quequing systems, Nav. Res. Logist.Q. 21, 411-418.
[17] Presman,E.L.,Sonin,I.M.(1972); The best choice problem for a random number of objects,
Theo.Prob.Appli. 4 , 657-668.
[18] Presman, E. L.; Sonin, I. M.(1972): The problem of best choice in the case of a random number ofobjects. (Russian) Teor. Verojatnost. i Primenen. 17 (1972), 695–706.
[19] Ross,S.M.(1983); Introduction to Stochastic Dynamic Programming, Academic Press, New York.
[20] Rasmussen, W.T., Robbins,H.(1975); The candidate problem with unknown population size,J.Appl.Prob. 12, 692-701.
[21] Samuels,S.M.(1991);Secretary problem, in Handbook of Sequential Analysis, B.K.Ghosh andP.K.Sen, eds. Dekker, New York.

7

[22] Shiryaev,A.N.(1973); Statistical Sequential Analysis, Translation: American Mathematical Society,Providence.
[23] Smith,M.H.(1975); A secretary problem with uncertain employment, J.Appl.Prob., 12, 620-624.
[24] Tamaki,M.(1979);[25] Tamaki,M.(2001);Optimal stopping on trajectories and the ballot problem, J.Appl.Prob., 38, 946959.
[26] Tamaki,M.(2002);Recent developments in the secretary problem. (Japanese) Development of theoptimization theory for the dynamic systems and their applications (Japanese, Kyoto, 2002). RIMS
No.1263, 131–150.
[27] Yasuda,M.(1984); Asymptotic results for the best-choice problem with a random number of objects,J.Appl.Prob. 21, 521-536.
[28] Yasuda,M.(1988); On the value for OLA-optimal stopping problem by potential theoretic method,
Lecture Notes in Math 1299 Springer-verlag, 517-580.

8