2 Approximative optimal best choice solution

El e c t ro nic J

o f

Pr

ob a bi l i t y

Electron. J. Probab.17(2012), no. 54, 1–22.

ISSN:1083-6489 DOI:10.1214/EJP.v17-2172

Approximative solutions of best choice problems

Andreas Faller

Ludger Rüschendorf

Abstract

We consider the full information best choice problem from a sequenceX1, . . . , Xn

of independent random variables. Under the basic assumption of convergence of the corresponding imbedded point processes in the plane to a Poisson process we establish that the optimal choice problem can be approximated by the optimal choice problem in the limiting Poisson process. This allows to derive approximations to the optimal choice probability and also to determine approximatively optimal stopping times. An extension of this result to the bestm-choice problem is also given.

Keywords:best choice problem; optimal stopping; Poisson process.

AMS MSC 2010:60G40; 62L15.

Submitted to EJP on July 28, 2011, final version accepted on July 13, 2012.

1 Introduction

The best choice problem of a random sequenceX₁, . . . , X_n is to find a stopping time τ 6nto maximize the best choice probabilityP(Xτ =Mn), whereMn = max16i6nXi, under all stopping timesτ 6n. Thus we aim to find an optimal stopping time Tn 6n such that

P(XTn=Mn) = maxP(Xτ =Mn) (1.1) over all stopping timesτ 6n.

Gilbert and Mosteller (1966) [9] found the solution of the full information best choice problem, where X1, . . . , Xn are iid with known continuous distribution functionF. In this case the optimal stopping time is given by

Tn= min{k6n|Xk=Mk, F(Xk)>b_n−k} (1.2) whereb0= 0,Pi

j=1 i j

(b⁻¹_i −1)^jj⁻¹= 1, i= 1,2, . . .

The asymptotic behaviour ofbi is described bybi ↑ 1,i(1−bi)→c= 0.8043. . . The optimal probabilityvn =P(XT_n =Mn)does not depend on F, is strictly decreasing in nand has limiting valuev∞

v_n →v_∞= 0.580164. . . (1.3)

∗University Freiburg, Germany. On June 30, 2011, Andreas Faller died completely unexpected. He was an extraordinary talented young researcher.

†University Freiburg, Germany. E-mail:ruschen@stochastik.uni-freiburg.de

A continuous time version of the problem with random number of points given by a homogeneous Poisson process with intensityλwas studied in Sakaguchi (1976) [21].

Asλ→ ∞the same limitv_∞appears as limiting optimal choice probability as observed in Berezovski˘ı and Gnedin (1984) [1] and Gnedin and Sakaguchi (1992) [13]. In Gnedin (1996) [12] this limiting optimal choice probabilityv∞ was identified as optimal choice probability in an associated plane Poisson process on[0,1]×(−∞,0]with intensity mea- sureλ_[0,1]⊗λ_(−∞,0]. The link with the original problem was established by an explicit imbedding of finite iid sequences in the Poisson process. Multistop best choice prob- lems for Poisson processes were considered in Sakaguchi (1991) [22] and Saario and Sakaguchi (1992) [19].

The approach in Gnedin (1996) [12] was extended in [KR]¹(2000c) [16] to the best choice problem for (inhomogeneous) discounted sequencesX_i=c_iY_i, where(Y_i)are iid andc_iare constants which imply convergence of imbedded normalized point processes Nn=Pn

i=1E₍i n,^Xi−bn

an )to some Poisson processN in the plane. The proofs in that paper make use of Gnedin’s (1966) [12] result as well as of some general approximation re- sults in [KR] (2000a) [15]. The aim of this paper is to extend this approach to general inhomogeneous best choice problems for independent sequences under the basic as- sumption of convergence of the imbedded point processesNn to some Poisson process N in the plane. Subsequently we also consider an extension to them-choice problem, wheremchoices described by stopping times1 6T1 <· · ·< Tm 6nare allowed and the aim is to findmstopping timesT₁^m<· · ·< T_m^m6nwith

P(XT₁^m∨ · · · ∨XT_m^m=Mn) = supP(

m

_

i=1

XT_i =Mn) (1.4)

thesupbeing over all stopping timesT1<· · ·< Tm6n.

For the corresponding generalized Moser problem of maximizing E X_τ resp.

EWm

i=1X_τia general approximation approach has been developed in [KR] (2000a), [FR]

(2011) [7] form= 1, resp. in [KR] (2002) [18] and [FR] (2011) [6] form>1; see also Goldstein and Samuel-Cahn (2006) [14]. For a detailed history of this problem we refer to Ferguson (2007) [8] form= 1resp. to [FR] (2011) [6] in casem>1. Our results for (1.3) are in particular applicable to sequencesXi=ciZi+diwith iid random sequences (Z_i)and with discount and observation factorsc_i,d_i. The corresponding results for the Moser type problems for these sequences can be found in [FR] (2011) [6, 7].

There are further interesting types of choice problems as e.g. the expected rank choice problem (see Bruss and Ferguson (1993) [3], Saario and Sakaguchi (1995), [20]), multiple buying selling problems Gnedin (1981) [10], Bruss and Ferguson (1997) [4], Bruss (2010) [2] or multicriteria extensions Gnedin (1992) [11] which are not dealt with in this paper.

2 Approximative optimal best choice solution

We consider the optimal best choice problem (1.1) for a sequence (Xi)of indepen- dent random variables, i.e. to find optimal stopping timesTn 6nsuch that

P(X_Tn=M_n) = sup

τ6n

P(X_τ =M_n), (2.1)

1Kühne and Rüschendorf is abbreviated within this paper with [KR], Faller with [F], Faller and Rüschendorf with [FR].

over all stopping timesτ 6n. The basic assumption in our approach is convergence in distribution of the imbedded planar point process to a Poisson point processN,

N_n=

n

X

i=1

δ₍i n,X_iⁿ)

→d N (2.2)

onMc= [0,1]×(c,∞]. HereX_iⁿ= ^Xi_a^−bn

n is a normalization ofXitypically induced from a form of the central limit theorem for maxima wherea_n>0,b_n∈R^andc∈R∪ {−∞}. We consider Poisson processesN restricted onM_c which may have infinite intensity along the lower boundary[0,1]× {c}. We assume that the intensity measureµofN is a Radon measure on Mc with the relative topology induced by the usual topology on [0,1]×R^{and with}µ([0,1]× {∞}) = 0. Thus any subset ofMc bounded away from the lower boundary has only finitely many points ofNandN has no points with value∞.

Convergence in distribution ‘Nn

→d N onMc’ means convergence in distribution of the point processes restricted onMc. This convergence is defined on the Polish space of locally finite point measures supplied with the topology of vague convergence. Since the Poisson limitN has no points with infinite value this definition prevents that records of Nnmay disappear to infinity, whenNn

→d N. For some general conditions to imply this convergence and examples see [KR] (2000a,b) [15, 17] or [FR] (2011) [7]. The typical examples from extreme value theory concern the casec=−∞andc= 0. We generally assume that the intensity measure µis Lebesgue-continuous with density denoted as f(t, x). Thus the Poisson process

N=X

k>1

δ_(τk,Yk)onM_c (2.3)

does not have multiple points.

We consider also the best choice problem for the limiting continuous time Poisson process N. AnN-stopping time T : Ω → [0,1] is a stopping time w.r.t. the filtration At:=σ(N(· ∩[0, t]×(c,∞])),t∈[0,1]. For anN-stopping timeT we define

YT =Yk ifT =τk for somekandYT =−∞else.

For stopping problems with guarantee valuex≥cwe define the stopping valueYt=x forT = 1which corresponds to replacing all random variablesX_jⁿbyX_jⁿ∨xin the point processN_n.

AnN-stopping timeT is called ‘optimal best choice stopping time’ forNif P(YT = sup

k

Yk) = supP(YS = sup

k

Yk) (2.4)

the supremum being taken over all N-stopping timesS. This definition of optimality implies that only those stopping times are of interest, which stop in some time pointτk

of N.

In the following theorem we derive the optimal stopping timeT for the continuous time best choice problem for the Poisson process N. Further we show that the best choice problem forX1, . . . , Xn is approximated by the best choice problem forN. This allows us to get approximations of the best choice probabilitiesv_n=P(X_Tn=M_n)and to construct asymptotically optimal best choice stopping sequencesTˆ_n. Our approxima- tion result needs the following intensity condition, which is not necessary, when dealing only with the limiting best choice problem (see Section 3).

(I) Intensity Condition: For allt∈[0,1)letµ((t,1]×(c,∞]) =∞.

Theorem 2.1. Let the imbedded point processN_nconverge in distribution to the Pois- son processN onM_cand let the intensity condition (I) hold true. Then we get:

(a) The optimal best choice stopping timeT forNis given by T = inf{τk|Yk = sup

τ_j∈[0,τk]

Yj, Yk> v(τk)}, inf∅:= 1 (2.5) where the thresholdv: [0,1]→[c,∞)is a solution of the integral equation

Z 1 t

Z ∞ v(t)

eµ((r,1]×(v(t),y])µ(dr, dy) = 1 ∀t∈[0,1);

v(1) =c

(2.6)

v is monotonically nonincreasing and can be chosen right continuous. The optimal probability for the best choice problem forN is given by

s₁ := P(Y_T = sup

k

Y_k)

= Z 1

0

e−µ([0,r]×(c,∞])Z ∞ v(r)

e−µ((r,1]×(y,∞])µ(dr, dy) (2.7)

+ Z 1

0

Z v(r⁰) c

Z 1 r⁰

e−µ([0,r]×(y⁰,∞])Z ∞ y⁰∨v(r)

e−µ((r,1]×(y,∞])µ(dr, dy)µ(dr⁰, dy⁰).

(b) Approximation of the optimal best choice probabilities holds true:

n→∞lim v_n= lim

n→∞P(X_Tn =M_n) =s₁.

(c) Tˆn:= min{16i6n|Xi =Mi, Xi> anv(_nⁱ) +bn}defines an asymptotically optimal sequence of stopping times, i.e.

n→∞lim P(X_Tˆ

n=M_n) =s₁.

Proof. For (t, x) ∈ [0,1)×[c,∞) we consider the stopping problem after timetn with guarantee valuex. We want to determine optimal stopping timesTn(t, x)> tnforX_jⁿ, 16j6n, which maximize

P(X_τⁿ=x∨ max

tn<j6nX_jⁿ)

under all stopping timesτ > tn. For the proof of convergence properties we consider the stopping behaviour after timetnhere (and not only after time zero) in order to make use of the recursive structure of the optimal stopping times. Define fori > tn

Z_iⁿ(t, x) =P

X_iⁿ=x∨ max

tn<j6nX_jⁿ|X₁ⁿ, . . . , X_iⁿ . Then we have to maximize EZ_τⁿ(t, x) = P X_τⁿ =x∨maxtn<j6nX_jⁿ

. By the classical recursive equation for optimal stopping of finite sequences the optimal stopping times T_n(t, x)are given by (see e.g. Proposition 2.1 in [FR] (2011) [6])T_n(t, x) := T_n^>tn(t, x) whereT_n^>n(t, x) :=nand

T_n^>k(t, x) = min

k < i6n|P(X_iⁿ=x∨ max

tn<j6nX_jⁿ|X₁ⁿ, . . . , X_iⁿ)

> P(X_Tⁿ>i

n (t,x)=x∨ max

tn<j6nX_jⁿ|X₁ⁿ, . . . , X_iⁿ), X_iⁿ=x∨ max

tn<j6iX_jⁿ

= min

k < i6n|P(X_iⁿ> max

i<j6nX_jⁿ|X_iⁿ)

> P(X_Tⁿ>i

n (t,x)=X_iⁿ∨ max

i<j6nX_jⁿ|X₁ⁿ, . . . , X_iⁿ), X_iⁿ=x∨ max

tn<j6iX_jⁿ .

By backward induction inl = n−1, . . . ,btncwe obtain fortn < i 6 l that T_n^>l(t, x) = T_n^>l(_nⁱ, X_iⁿ)on {X_iⁿ = x∨max_tn<j6iX_jⁿ} and further that T_n^>l(t, x) is independent of σ(X₁ⁿ, . . . , X_btncⁿ . Thus

T_n(t, x) = min

tn < i6n|P(X_iⁿ> max

i<j6nX_jⁿ|X_iⁿ)

> P(X_Tⁿ

n(_nⁱ,X_iⁿ)=X_iⁿ∨ max

i<j6nX_jⁿ|X_iⁿ), X_iⁿ=x∨ max

tn<j6iX_jⁿ

= min

tn < i6n|h_n(_nⁱ, X_iⁿ)> g_n(_nⁱ, X_iⁿ), X_iⁿ=x∨ max

tn<j6iX_jⁿ where

gn(t, x) :=P(X_Tⁿ_n(t,x)=x∨ max

tn<j6nX_jⁿ) hn(t, x) :=P( max

tn<j6nX_jⁿ 6x). ^(2.8)

hn is monotonically nondecreasing in(t, x). As consequence we obtain from point pro- cess convergence thathnconverges uniformly in compact sets in[0,1]×(c,∞]to

h_∞(t, x) :=P(N((t,1]×(x,∞]) = 0) =e−µ((t,1]×(x,∞]).

To prove that gn(t, x) also converges uniformly on compact sets in [0,1]×(c,∞] we decomposegninto two monotone components.

g_n(t, x) = sup

τ >tn stopping times

P(X_τⁿ=x∨ max

tn<j6nX_jⁿ)

= sup

τ >tn stopping times

P(X_τⁿ=x∨ max

tn<j6nX_jⁿ, max

tn<j6nX_jⁿ> x)

= sup

τ >tn stopping times

P(X_τⁿ∨x= max

tn<j6n(X_jⁿ∨x), max

tn<j6nX_jⁿ> x)

= sup

τ >tn stopping times

P(X_τⁿ∨x= max

tn<j6n(X_jⁿ∨x))−P( max

tn<j6nX_jⁿ6x)

=: ˜g_n(t, x)−h_n(t, x). (2.9)

By assumption the pointprocessNhas only finitely many points in any subset bound- ed away from the lower boundaryc. In consequence point process convergenceNn

→d

N implies that ˜g_n(t, x)converges pointwise for all t, xto a limit ˜g_∞(t, x). A detailed argument for this convergence has been given for the related case of maximizingEX_τⁿ in [FR] (2011) [7, Theorem 4.1] resp. [F] (2009) [5, Satz 4.1]. This argument transfers to the optimal choice case in a similar way. Using monotonicity properties ofg˜n(t, x)in t, xwe next prove that˜g_∞is continuous which then implies uniform convergence. On one hand side we have fors < tandx > c

˜

g_n(s, x)6 sup

τ >sn stopping times

P(X_τⁿ∨x> max

tn<j6n(X_jⁿ∨x))

6 sup

τ >sn stopping times

P(X_τⁿ∨x> max

tn<j6n(X_jⁿ∨x), max

sn<j6tn(X_jⁿ∨x)6 max

tn<j6n(X_jⁿ∨x)) +P( max

sn<j6tn(X_jⁿ∨x)> max

tn<j6n(X_jⁿ∨x)) 6 g˜n(t, x) +P( max

sn<j6tnX_jⁿ> x).

On the other hand

˜

g_n(s, x) > sup

τ >sn stopping times

P(X_τⁿ∨x> max

sn<j6n(X_jⁿ∨x))

> sup

τ >sn stopping times

P(X_τⁿ∨x> max

tn<j6n(X_jⁿ∨x))

−P( max

sn<j6tn(X_jⁿ∨x)> max

tn<j6n(X_jⁿ∨x))

> ˜gn(t, x)−P( max

sn<j6tnX_jⁿ> x).

This implies

|˜g_n(s, x)−˜g_n(t, x)|6P( max

sn<j6tnX_jⁿ> x).

and thus using thatx > ccontinuity of˜g_∞(t, x)int. To prove continuity of˜g_∞inxletx < y. Then

0 6 g˜_n(t, y)−g˜_n(t, x)

6 sup

τ >sn stopping times

P(X_Tⁿ∨y= max

tn<j6n(X_jⁿ∨y), X_Tⁿ∨x < max

tn<j6n(X_jⁿ∨x)) 6 P(x < max

tn<j6nX_jⁿ6y).

In consequence ˜g_∞(t, x)is continuous andg_n → g_∞ uniformly on compact subsets of [0,1]×(c,∞). Point process convergence and the representation in (2.8) imply that

g_∞(t, x) =P Y_T(t,x)=x∨ sup

t<τ_k61

Y_k with theN-stopping time

T(t, x) = inf

τk > t|Yk =x∨ sup

t<τj6τ_k

Yj, h_∞(τk, Yk)> g_∞(τk, Yk) . The argument above also applies to the modified random variables

X˜_iⁿ:= sup

i−1 n <τ_k6_nⁱ

Yk.

Definingg_∞,h_∞as above we obtain in this casegn(t, x)↓g_∞(t, x)since the discrete stopping problems majorize the continuous time stopping problem. In consequence T(t, x)are the optimal stopping times forN, i.e.

g∞(t, x) = sup

τ >t N-stopping time

P Yτ =x∨ sup

t<τ_k61

Yk

,

Details of this approximation argument are given in [KR] (2000a) (proof of Theorem 2.5). As a result we get the following estimate

gn(t, x)>P(X_Tⁿ_ˆ

n(t,x)=x∨ max

tn<j6nX_jⁿ)→g_∞(t, x), with the stopping times

Tˆn(t, x) := min

tn < i6n|X_iⁿ=x∨ max

tn<j6iX_jⁿ, h_∞(_nⁱ, X_iⁿ)> g_∞(_nⁱ, X_iⁿ) . Thus the limitg∞(t, x)is the same for(X_iⁿ)and for( ˜X_iⁿ).

The arguments above in the casex > ccan also be extended to the casex=c. Note that forx > c

g_∞(t, x) 6 P Y_T(t,x)= sup

t<τ_k61

Y_k

6 sup

T >t N-stopping time

P YT = sup

t<τk61

Yk

6g_∞(t, x) +h_∞(t, x).

From the intensity assumption (I) and sinceh_∞(t, c) = 0we obtain g_∞(t, c) := lim

x↓cg_∞(t, x) =P Y_T(t,c)= sup

t<τk61

Yk

= sup

τ >t N-stopping time

P Yτ= sup

t<τ_k61

Yk

.

Since forx > c

gn(t, x)6gn(t, c)6gn(t, x) +hn(t, x) it follows that

n→∞lim g_n(t, c) =g_∞(t, c).

By assumption (I)P(N((t,1]×(c,∞])>1) >0fort∈[0,1). Thusg_∞(t, x)is mono- tonically nonincreasing inxwithg∞(t, c) >0and g∞(t,∞) = 0. Also by (I)h∞(t, x)is monotonically nondecreasing inxwithh_∞(t, c) = 0andh_∞(t,∞) = 1. In consequence there existsv(t)∈(c,∞)with

h_∞(t, v(t)) =g_∞(t, v(t)). (2.10) This implies the representation

T(t, x) = inf

τk > t|Yk =x∨ sup

t<τj6τ_k

Yj, Yk> v(τk) .

We next prove that v is monotonically nonincreasing. Since g∞(t, x)−h∞(t, x) is monotonically nonincreasing inxfor anytit is sufficient to show that fors < t

g_∞(s, v(t))−h_∞(s, v(t))>0. (2.11) To that aim we get fors < t

g_∞(t, x)−g_∞(s, x) 6 P(Y_T(t,x)=x∨sup

τ_k>t

Yk)−P(Y_T(t,x)=x∨ sup

τ_k>s

Yk) 6 P(x∨ sup

s<τk6t

Yk > Y_T(t,x)=x∨sup

τ_k>t

Yk) 6 P( sup

s<τ_k6t

Y_k> x)g_∞(t, x).

The first inequality results from definition ofg_∞(s, x), the second inequality is immedi- ate and the third inequality is a consequence from independence of the (Yk). On the other hand

h_∞(t, x)−h_∞(s, x) =P( sup

s<τk6t

Yk > x)h_∞(t, x).

Building the difference of these (in-)equalities and using (2.10) we obtain forx=v(t) the claim in (2.11).

Monotonicity ofvallows us to determineg_∞(t, x). Note that forx>v(t)

g_∞(t, x) := P ∃n0:∀n>n0:∃₂ⁱn ∈(t,1] :∃₂^jn > x: N((ⁱ⁻¹₂n,₂ⁱn]×(^j−1₂n ,₂^jn]) = 1, N((t,ⁱ⁻¹_2n]×(x,∞]) = 0,andN((₂ⁱ_n,1]×(₂^j_n,∞]) = 0

= Z 1

t

e−µ((t,r]×(x,∞])Z ∞ x

e−µ((r,1]×(y,∞])µ(dr, dy), and in casex6v(t)

g_∞(t, x) =P(∃n0:∀n>n0:∃₂ⁱn ∈(t,1] :∃₂^jn > x:

N((ⁱ⁻¹_2n ,₂ⁱ_n]×(^j−1_2n ,₂^j_n]) = 1for ₂^j_n > v(₂ⁱ_n), N((t,ⁱ⁻¹_2n]×(x,∞]) = 0, andN((₂ⁱn,1]×(₂^jn,∞]) = 0)

+P(∃n0:∀n>n0:∃t < ₂ⁱn⁰ <₂ⁱn 61,∃x < ₂^jn⁰ < ₂^jn : N((ⁱ⁻¹_2n ,₂ⁱ_n]×(^j−1_2n ,₂^j_n]) = 1for ₂^j_n > v(₂ⁱ_n), N((ⁱ⁰₂⁻¹n ,₂ⁱn⁰]×(^j0₂⁻¹n ,₂^jn⁰]) = 1for ₂^jn⁰ < v(₂ⁱn⁰),

N((t,ⁱ⁻¹_2n]×(₂^j_n⁰,∞]) = 0,andN((₂ⁱ_n,1]×(₂^j_n,∞]) = 0)

= Z 1

t

e−µ((t,r]×(x,∞])Z ∞ x∨v(r)

e−µ((r,1]×(y,∞])µ(dr, dy)

+

Z v⁻¹(x) t

Z v(r⁰) x

Z 1 r⁰

e−µ((t,r]×(y⁰,∞])Z ∞ y⁰∨v(r)

e−µ((r,1]×(y,∞])µ(dr, dy)µ(dr⁰, dy⁰).

This implies

g_∞(t, v(t)) = Z 1

t

e−µ((t,r]×(v(t),∞])Z ∞ v(t)

e−µ((r,1]×(y,∞])µ(dr, dy).

From condition (2.10) this is equal toh_∞(t, v(t)) =e−µ((t,1]×(v(t),∞]), and as consequence we obtain equality from (2.6).

Remark (triangular sequences) As remarked by a reviewer the proof of Theorem 2.1 extends in the same way to the optimal stopping of triangular sequences(X_iⁿ)and point process convergence as in (2.2). The asymptotically optimal sequence of stopping times in Theorem 2.1, (c) then is given by

Tˆn:= min

1≤i≤n|X_iⁿ =M_iⁿ, X_iⁿ > v _nⁱ (2.12) i. e. lim

n→∞P

Xⁿ_ˆ

Tn=M_n

=s₁. (2.13)

HereM_n= max

1≤i≤nX_iⁿandM_iⁿ= max

1≤j≤iX_jⁿ.

In general the optimal best choice probabilitys₁in (2.7) has to be evaluated numer- ically. Certain classes of intensity functions however allow an explicit evaluation.

Example 2.2. Consider densities of the intensity measureµof the form

f(t, y) =−a(t)F⁰(y), (2.14)

where a : [0,1] → [0,∞] is continuous and integrable, a is not identical zero in any neighbourhood of 1 andF : [c,∞] → Rmonotonically nonincreasing, continuous with lim_x↓cF(x) =∞andF(∞) = 0. DefiningA(t) :=R1

t a(s)ds, we obtain Z 1

t

Z ∞ x

eµ((r,1]×(x,y])µ(dr, dy) =

Z A(t)F(x) 0

e^y−1 y dy.

In consequencevsolves the equation

F(v(t)) = d

A(t), (2.15)

whered= 0.8043522. . . is the unique solution of Z d

0

e^y−1

y dy= 1. (2.16)

The asymptotic optimal choice probability can be obtained from (2.7)by some calcula- tion as

s1=e^−d+ (e^d−1−d) Z ∞

d

e^−y

y dy= 0.5801642. . .

This is identical to the asymptotic optimal choice probability in the iid case (see (1.3)). In particular in case of the three extreme value distribution typesΛ,Φα, andΨα, one gets for the limiting Poisson processes intensities with densitiesf(t, x)of the form f(t, x) =−F⁰(y)withF(x) =e^−x in caseΛ, F(x) =x^−α,x > 0in case Ψα,α > 0, and F(x) = (−x)^αforx60,F(x) = 0,x >0in caseΨα,α >0. Thus, these cases fit the form in (2.14). Also the example of a best choice problem forX_i=c_iY_ifor some iid sequence dealt with in [KR] (2000c) fits this condition.

3 Poisson processes with finite intensities

Gnedin and Sakaguchi (1992) [13] considered the best choice problem for iid se- quence (Yk)with distribution functions F arriving at Poisson distributed time points.

For continuous F this can be described by a planar Poisson process N with density f(t, y) = a(t)F⁰(y)wherea : [0,1]→[0,∞] is continuous integrable. N does not fulfill the infinite intensity condition (I) in Section 2. For the best choice problem in Pois- son processes our method of proof can be modified to deal also with the case of finite intensity.

Let N = P

k = δτ_k,Y_k be a Poisson process on[0,1]×(c,∞] with finite Lebesgue continuous intensity measure, i.e.µsatisfies

(If) Finite Intensity Condition: µ([0,1)×(c,∞])<∞.

Then the following modifications of the proof of Theorem 2.1 allow to solve this case.

Note that under condition(I_f)no longerh_∞(t, c) = 0and thus in general no longer one can find to anyt∈[0,1)anx > csuch thath_∞(t, x)< g_∞(t, x). This property holds true only in[0, t0)with

t0:= sup

t∈[0,1]| Z 1

t

Z ∞ c

eµ((r,1]×(c,y])µ(dr, dy)>1

. (3.1)

This can be seen as follows: Fort∈[0, t₀)and forxclose tocholds g_∞(t, x)>P(YT˜(t,x)= sup

τk>t

Yk∨x)> h_∞(t, x)

with stopping timeT˜(t, x) := inf{τk > t|Yk > x}. If for somet6∈[0, t0)there would exist somev(t)∈(c,∞)withh_∞(t, v(t)) =g_∞(t, v(t)), thenv(t) =cwould give a contradiction.

So far we have obtained optimality of the stopping timesT(t, x)forx > c. We next consider the casex=c. SinceN has only finitely many points in[0,1]×(c,∞)it follows that

g_∞(t, x) = P(Y_T(t,x)= sup

τ_k>t

Y_k> x)

−→x↓c P(Y_T(t,c)= sup

τ_k>t

Y_k > c) =P(Y_T(t,c)= sup

τ_k>t

Y_k)−h_∞(t, c).

The inequality sup

T >t N-stopping time

P(YT = sup

τ_k>t

Yk)

6 sup

τ >t N-stopping time

P(YT ∨x= sup

τk>t

Yk∨x) =g∞(t, x) +h∞(t, x)

then implies optimality ofT(t, c)and we obtain the following result.

Theorem 3.1. Let the Poisson process satisfy the finite intensity condition(I_f). Then the optimal choice stopping time forN is given by

T = inf

τk |Yk= sup

τ_j∈[0,τk]

Yj, Yk > v(τk) ,

wherev: [0,1]→[c,∞)is a solution of the integral equation Z 1

t

Z ∞ v(t)

eµ((r,1]×(v(t),y])µ(dr, dy) = 1 ∀t∈[0, t0), v(t) =c ∀t∈[t₀,1].

v is monotonically nonincreasing and can be chosen right continuous. The optimal choice probability is given by

s₁ := P(Y_T = sup

k

Y_k, T <1)

= Z 1

0

e−µ([0,r]×(c,∞])Z ∞ v(r)

e−µ((r,1]×(y,∞])µ(dr, dy)

+ Z t0

0

Z v(r⁰) c

Z 1 r⁰

e−µ([0,r]×(y⁰,∞])Z ∞ y⁰∨v(r)

e−µ((r,1]×(y,∞])µ(dr, dy)µ(dr⁰, dy⁰).

Example 3.2. In case of the finite intensity measureµwith densityf(t, y) =a(t)F⁰(y) as in Gnedin and Sakaguchi (1992) [13] let F(c) = 0 andA(t) := R1

t a(s)ds. Then we obtain

Z 1 t

Z ∞ x

eµ((r,1]×(x,y])µ(dr, dy) =

Z A(t)(1−F(x)) 0

e^y−1 y dy.

Thus we gett₀= 0andv≡cifA(0)6dwheredis the constant given in(2.16).

IfA(0)> d, thent0is the smallest point satisfyingA(t0) =d, and fort∈[0, to)v(t)is a solution of the equation

F(v(t)) = 1− d A(t),

Some detailed calculations yield in this case the optimal choice probabilitysas

s1=









 e^−A(0)

Z A(0) 0

e^y−1

y dy, ifA(0)6d,

e^−d+ (e^d−1−d) Z A(0)

d

e^−y

y dy, ifA(0)> d.

This coincides with the results obtained in Gnedin and Sakaguchi (1992) [13].

4 The optimal m -choice problem

In this section we consider the optimalm-choice problem (1.4) for independent se- quences(Xi). LetX_iⁿ= ^Xi_a^−bn

n denote the normalized version as in Section 2. Similarly we consider the optimalm-choice problem for continuous time Poisson processes in the plane defined by

P

m

_

i=1

Y_T^m

i = sup

k

Y_k

= sup

06T₁<···<T_m61 Ti,N-stopping times

P

m

_

i=1

Y_Ti = sup

k

Y_k

=:s_m (4.1)

and call(T_i^m) = (T_i^n,m)optimalm-choice stopping times. The conditiont 6T1 <· · ·<

T_m61means thatT_i−1< T_ion{Ti−1<1}andT_i= 1on{Ti−1= 1}.

The following lemma gives a characterization of optimalm-choice stopping times in the discrete case.

Lemma 4.1. Define for(t, x)∈[0,1)×[c,∞) g^m_n(t, x) := sup

tn<T₁<···<Tm6n stopping times

P(X_Tⁿ₁∨ · · · ∨X_Tⁿ_m =x∨ max

tn<j6nX_jⁿ) and

h¹_n(t, x) := P( max

tn<j6nX_jⁿ 6x), h^m_n(t, x) := g^m−1_n (t, x) +h¹_n(t, x).

Then

g^m_n(t, x) =P(X_Tⁿn,m

1 (t,x)∨ · · · ∨X_Tⁿn,m

m (t,x)=x∨ max

tn<j6nX_jⁿ) with optimal stopping times given by

T₁^n,m(t, x) := min{tn < i6n−m+ 1|

h^m_n(_nⁱ, X_iⁿ)> g_n^m(_nⁱ, X_iⁿ), X_iⁿ=x∨ max

tn<j6iX_jⁿ}, T_l^n,m(t, x) := min{T_l−1^n,m(t, x)< i6n−m+l|

h^m−l+1_n (_nⁱ, X_iⁿ)> g_n^m−l+1(_nⁱ, X_iⁿ), X_iⁿ=x∨ max

tn<j6iX_jⁿ}

(4.2)

for26l6m.

Proof. Lettn < S 6n−m+ 1be a stopping time andZ 6maxtn<j6SX_jⁿ be a random variable. Furthermore let for16i6n,M_iⁿbeσ(X_i+1ⁿ , . . . , X_nⁿ)measurable withM_iⁿ6 X_i+1ⁿ ∨M_i+1ⁿ andP(M_iⁿ =x) = 0for allx > c. In order to maximizeP(Z∨X_Tⁿ∨M_Tⁿ= x∨max_tn<j6nX_jⁿ)w.r.t. all stopping timesT,S < T 6n−m+ 1we define

Y_i :=P(Z∨X_iⁿ∨M_iⁿ =x∨ max

tn<j6nX_jⁿ|X₁ⁿ, . . . , X_iⁿ).

Thus we have to maximizeEYT =P(Z∨X_Tⁿ∨M_Tⁿ =x∨maxtn<j6nX_jⁿ). The optimal

stopping times are given byT_n(t, x) =T_n^>tn(t, x)with T_n^>k(t, x)

= min{k < i6n−m+ 1|P(Z∨X_iⁿ∨M_iⁿ=x∨ max

tn<j6nX_jⁿ|X₁ⁿ, . . . , X_iⁿ)

> P(Z∨X_Tⁿ>i

n (t,x)∨M_Tⁿ>i

n (t,x)=x∨ max

tn<j6nX_jⁿ|X₁ⁿ, . . . , X_iⁿ), X_iⁿ =x∨ max

tn<j6iX_jⁿ}

= min{k < i6n−m+ 1|P(X_iⁿ∨M_iⁿ =X_iⁿ∨ max

i<j6nX_jⁿ|X_iⁿ)

> P(X_Tⁿ>i

n (t,x)∨M_Tⁿ>i

n (t,x)=X_iⁿ∨ max

i<j6nX_jⁿ|X_iⁿ), X_iⁿ=x∨ max

tn<j6iX_jⁿ}.

For the second equality we use that P(X_iⁿ = X_jⁿ > c) = 0 for i 6= j and thusX_iⁿ = x∨max_tn<j6iX_jⁿ > xis strictly larger than Z. ThusZ can not be the maximum. In consequence we get fork>S

T_n^>k(t, x) = min{k < i6n−m+ 1|ˆhn(_nⁱ, X_iⁿ)>gˆn(_nⁱ, X_iⁿ), X_iⁿ=x∨ max

tn<j6iX_jⁿ} (4.3) where

ˆhn(t, x) := P(x∨M_btncⁿ =x∨ max

tn<j6nX_jⁿ)

= P(M_btncⁿ =x∨ max

tn<j6nX_jⁿ) +h¹_n(t, x), ˆ

gn(t, x) := P(X_Tⁿ

n(t,x)∨M_Tⁿ

n(t,x)=x∨ max

tn<j6nX_jⁿ).

By induction we obtain from (4.3) the representation in (4.2). Define form= 1: M_iⁿ:=

−∞, form= 2:M_iⁿ:=X_Tⁿ>i

n (t,x), etc.

Theorem 4.2(Approximative solution of the bestm-choice problem). LetNn

→d N on Mc = [0,1]×(c,∞]and letN satisfy the intensity condition (I).

a) The optimalm-choice stopping times forN are given byT₁^m(0, c), . . . , T_m^m(0, c), where T₁^m(t, x) = inf{τk > t|Y_k =x∨ sup

τj∈(t,τk]

Y_j, Y_k> v^m(τ_k)}, T_l^m(t, x) = inf{τk > T_l−1^m (t, x)|Yk=x∨ sup

τj∈(t,τ_k]

Yj, Yk > v^m−l+1(τk)}, for26l6m. The thresholdsv^m(t)are solutions of the equations

g^m_∞(t, v^m(t)) = h^m_∞(t, v^m(t)) fort∈[0,1) (4.4) v^m(1) = c,

with

g^m_∞(t, x) :=P(Y_T^m

1 (t,x)∨ · · · ∨Y_Tm

m(t,x)=x∨ sup

t<τ_k61

Yk) and

h¹_∞(t, x) := e−µ((t,1]×(x,∞]) form= 1, h^m_∞(t, x) := g_∞^m−1(t, x) +h¹_∞(t, x) form>2.

v^m: [0,1]→[c,∞)is monotonically nonincreasing and can be chosen right continu- ous. Furthermore,v^m(t)6v^m−1(t)fort∈[0,1] (m>2).

b) lim

n→∞P(X_T^n,m

1 ∨ · · · ∨X_Tm^n,m =M_n) =s_m=g_∞^m(0, c) c) The stopping timesTˆ_l^m= ˆT_l^n,mdefined by

Tˆ₁^n,m:= min{16i6n−m+ 1|Xi=Mi, Xi> anv^m(_nⁱ) +bn},

Tˆ_l^n,m:= min{Tˆ_l−1^n,m< i6n−m+l|Xi=Mi, Xi > anv^m−l+1(_nⁱ) +bn} ^(4.5) for26l6mare approximative optimalm-choice stopping times, i.e.

n→∞lim P(XTˆ₁^n,m∨ · · · ∨XTˆ_m^n,m =Mn) =sm. (4.6) Proof. The proof of b), c) is similar to the corresponding part in Theorem 2.1. We therefore concentrate on the proof of a).

As in the proof of Theorem 2.1 we obtain g_∞^m(t, x) = sup

t<T1,...,Tm61 N-stopping times

P(YT₁∨ · · · ∨YT_m =x∨ sup

t<τk61

Yk). (4.7)

Furthermore we note thatv^mis continuous in 1,limt↑1v^m(t) =c. If not, thenv^m(tn)→ d > cfor some sequencet_n↑1and thusg_∞^m(t_n, v^m(t_n))→0. The inequalityh^m_∞(t_n, v^m(t_n))

>h¹_∞(t_n, v^m(t_n))→e⁻⁰= 1>0then yields a contradiction.

We have to show that for m > 2, v^m 6 v^m−1. Using the characterization of v^m in (4.4) this inequality follows from

g^m_∞(t, x)−h^m_∞(t, x)6g_∞^m−1(t, x)−h^m−1_∞ (t, x). (4.8) forx=v^m(t). Form= 2we obtain from (4.7)

g²_∞(t, x)62g_∞¹ (t, x), which implies (4.8). Form>3(4.8) is equivalent to

g^m_∞(t, x)−g^m−1_∞ (t, x)6g_∞^m−1(t, x)−g_∞^m−2(t, x). (4.9) We prove (4.9) by induction. By induction hypothesis we assume thatv^m−16v^m−26 . . .6v¹and all of thevⁱare monotonically nonincreasing. Also we havelim_t↑1v^m(t) =c. Assume thatv^m(s)> v^m−1(s)for somes∈[0,1). Sincelim_t↑1v^m(t) = lim_t↑1v^m−1(t) =c and sincev^m−1is monotonically nonincreasing, there exists somet∈[s,1)withv^m(t)>

v^m−1(t)andv^m(t)>v^m(r)for allr>t. We establish (4.9) forx=v^m(t).

From the definition of the thresholds followsT_k^m(t, x)6T_k^m−1(t, x)6T_k^m−2(t, x)for all16k6m−2. We define the stopping time

Tˆ(t, x) := T₁^m(t, x)χ_{Tm

1 (t,x)<T₁^m−2(t,x)}

+

m−2

X

i=2

T_i^m(t, x)χ_{Tm

1 (t,x)=T₁^m−2(t,x)}∩···∩{T_i−1^m (t,x)=T_i−1^m−2(t,x)}∩{T_i^m(t,x)<T_i^m−2(t,x)}

+T_m−1^m (t, x)χ_{Tm

1 (t,x)=T₁^m−2(t,x)}∩···∩{T_m−2^m (t,x)=T_m−2^m−2(t,x)}.

Tˆ(t, x)only stops at time pointsT₁^m(t, x), . . . , T_m^m(t, x)but not at time pointsT₁^m−2(t, x),

. . . , T_m−2^m−2(t, x)when these are<1. We now obtain from (4.7) the inequality g_∞^m(t, x)−g^m−1_∞ (t, x)

6 P(Y_Tm

1 (t,x)∨ · · · ∨Y_Tm

m(t,x)=x∨ sup

t<τ_k61

Y_k)

−P(Y_T^m−2

1 (t,x)∨ · · · ∨Y_T^m−2

m−2(t,x)=x∨ sup

t<τ_k61

Yk)−P(YTˆ(t,x)=x∨ sup

t<τ_k61

Yk)

= P(YT₁^m(t,x)∨ · · · ∨YT_m^m(t,x)=x∨ sup

t<τ_k61

Yk, YT(t,x)ˆ < x∨ sup

t<τ_k61

Yk)−g_∞^m−2(t, x) 6 P(YT₁(t,x)∨ · · · ∨YT_m−1(t,x)=x∨ sup

t<τ_k61

Yk)−g^m−2_∞ (t, x) 6 g_∞^m−1(t, x)−g_∞^m−2(t, x),

with the stopping times

T₁(t, x) := T₁^m(t, x)χ_{Tm

1 (t,x)6= ˆT(t,x)}+T₂^m(t, x)χ_{Tm

1 (t,x)= ˆT(t,x)}

Ti(t, x) := T_i^m(t, x)χ_{Tm

1 (t,x)6= ˆT(t,x)}∩···∩{T_i^m(t,x)6= ˆT(t,x)}

+T_i+1^m (t, x)χ_{Tm

1 (t,x)= ˆT(t,x)}∪···∪{T_i^m(t,x)= ˆT(t,x)}

fori= 2, . . . , m−1.

Thus (4.9) holds true forx=v^m(t)and, therefore,v^m(t)6v^m−1(t), a contradiction.

This implies the statementv^m6v^m−1.

In the final step we prove thatv^m is monotonically nonincreasing. Sinceg^m_∞(t, x)− h^m_∞(t, x)is monotonically nonincreasing inxfor anyt, it suffices to prove that fors < t

g^m_∞(s, v^m(t))−h^m_∞(s, v^m(t))>0. (4.10) We define for(s, x)∈[0,1)×(c,∞]

A_(s,x) := {Y_T^m

1 (s,x)∨ · · · ∨Y_Tm

m(s,x)=x∨ sup

s<τk61

Yk, Y_Tm−1 1 (s,x)

∨ · · · ∨Y_Tm−1

m−1(s,x)< x∨ sup

s<τ_k61

Y_k}.

Then

g_∞^m(s, x)−g_∞^m−1(s, x) =P(A_(s,x)) and fors < t

P(A(t,x))−P(A(s,x))

= P(A_(s,x), N((s, t]×(x,∞]) = 0) +P(A_(t,x))P(N((s, t]×(x,∞])>1)

−P(A_(s,x))

= −P(A_(s,x), N((s, t]×(x,∞])>1) +P(A_(t,x))(1−e−µ((s,t]×(x,∞])) 6 P(A_(t,x))

h¹_∞(t, x)(h¹_∞(t, x)−h¹_∞(s, x)).

Withx=v^m(t)we obtain the inequality in (4.10) and thus monotonicity ofv^m. To calculate the optimal thresholds we need to calculate the densities of record stopping times with general thresholdv.

Lemma 4.3. Let v : [0,1] → [c,∞) be monotonically nonincreasing, right continuous withv > con[0,1). Define the record stopping time associated tov for(t, x)∈[0,1)× (c,∞)by

T(t, x) := inf{τk> t|Yk=x∨ sup

τ_j∈(t,τk]

Yj, Yk > v(τk)},