Introduction
Let X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n be independent random scores sampled from some continuous distribution. The scores are observed sequentially, with the aim to select one of them using a nonanticipating stopping rule τ \tau τ with values in [ n ] : = { 1 , … , n } [n]:=\{1,\ldots,n\} [ n ] := { 1 , … , n } . With each score X k X_k X k we associate its final rank among all n n n scores,
R k , n : = # { i ∈ [ n ] : X i ≤ X k } . (1) R_{k,n}:=\#\{i\in[n]:X_i\le X_k\}. \tag*{(1)} R k , n := # { i ∈ [ n ] : X i ≤ X k } . (1)
In ‘secretary problems’ the loss for selecting X k X_k X k depends on the scores ( X 1 , … , X n ) (X_1,\ldots,X_n) ( X 1 , … , X n ) through the ranking permutation ( R 1 , n , … , R n , n ) (R_{1,n},\ldots,R_{n,n}) ( R 1 , n , … , R n , n ) [24 ] . This includes in the first turn stopping problems with objectives of the form
E q ( R τ , n ) → min , (2) \mathbb{E}\,q(R_{\tau,n})\to\min, \tag*{(2)} E q ( R τ , n ) → min , (2)
where q ( r ) q(r) q ( r ) is a nondecreasing function on the integers; the classical best-choice objective being q ( r ) = 1 ( r > 1 ) q(r)=1(r>1) q ( r ) = 1 ( r > 1 ) . The nature of a selection problem largely depends on the type of information allowed in stopping rules.
In rank-information problems one considers the family of stopping rules adapted to the sequence ( I k , k ∈ [ n ] ) (I_k,k\in[n]) ( I k , k ∈ [ n ]) of initial ranks
I k : = # { i ∈ [ k ] : X i ≤ X k } , (3) I_k:=\#\{i\in[k]:X_i\le X_k\}, \tag*{(3)} I k := # { i ∈ [ k ] : X i ≤ X k } , (3)
where I 1 , … , I k I_1,\ldots,I_k I 1 , … , I k encode the ranking permutation of the first k k k scores. Adopting the terminology of extreme-value theory, we say that X k X_k X k is an i i i -record if I k = i I_k=i I k = i , and just a record if i = 1 i=1 i = 1 . By exchangeability, the sequence of final ranks is a uniformly random permutation of [ n ] [n] [ n ] , the initial ranks are independent with I k I_k I k uniformly distributed on [ k ] [k] [ k ] , and R k , n R_{k,n} R k , n is independent of I 1 , … , I k − 1 I_1,\ldots,I_{k-1} I 1 , … , I k − 1 . For problems (2) this implies that the optimal decision at stage k k k depends on the observed scores through I k I_k I k , which makes the stopping problems efficiently solvable by backward induction, as the continuation value only depends on k k k and n n n . The structural clarity underlies the large-sample theory developed for (2) and related problems in the framework of a continuous-time infinite-arrivals model [9 ] , where the value function is determined from a piecewise differential equation [21 ] . Closed-form asymptotic solutions are available, in particular, for the problem of choosing one of the m m m best with q ( r ) = 1 ( r > m ) q(r) = \mathbf{1}(r > m) q ( r ) = 1 ( r > m ) [8 , 10 , 20 , 21 ] , and Lindley’s minimum rank problem with the linear loss q ( r ) = r q(r) = r q ( r ) = r [4 , 16 , 21 ] .
In full-information problems the optimum is sought within the larger family of all stopping rules adapted to ( X k , k ∈ [ n ] ) (X_k, k \in[n]) ( X k , k ∈ [ n ]) . The term ‘full-information’ was coined in [10 ] to stress that the observer knows exactly the source distribution (which may be assumed uniform), and can use the score values in the selection strategies. The informational advantage makes the optimisation problem much more complex, because the global ranking couples the observed and future scores, thus forcing history dependence of the continuation value and decisions. To date the sole completely understood instance is the best-choice problem, reducible to optimal stopping of the univariate Markovian sequence of records [12 , 13 , 18 ] . For problems (2) with general q q q , in particular for the linear loss – known in this full-information setting as the Robbins problem – one should not expect a closed-form solution, since the continuation value at stage k k k depends on all k k k past scores [1 , 6 ] , and the full history dependence persists in the limit [14 ] . The present paper aims to illustrate how the complexity grows with the dimension, by focusing on truncated loss structures, where only a small number m m m of the i i i -record processes, i ≤ m i \le m i ≤ m , is relevant. Concretely, we consider two loss structures:
A n , m : the loss for selecting an i -record X k is min ( i , m + 1 ) + # { k < j ≤ n : X j < X k } , (4) A_{n,m}\colon\text{the loss for selecting an }i\text{-record }X_k\text{ is }\min(i,m+1)+\#\{k<j\le n:X_j<X_k\}, \tag*{(4)} A n , m : the loss for selecting an i -record X k is min ( i , m + 1 ) + # { k < j ≤ n : X j < X k } , (4)
B n , m : q ( r ) = 1 ( r > m ) for the final rank r . (5) B_{n,m}\colon\qquad q(r)=\mathbf{1}(r>m)\text{ for the final rank }r. \tag*{(5)} B n , m : q ( r ) = 1 ( r > m ) for the final rank r . (5)
In problem A n , m A_{n,m} A n , m the loss is the capped initial rank plus the number of later smaller scores. This objective was employed in [2 ] to compute numerical lower bounds for the value in Robbins’ problem. We will show that problem A n , 1 A_{n,1} A n , 1 has a simple asymptotic solution, very much in line with the best-choice problem B n , 1 B_{n,1} B n , 1 , both are treated here by a novel sliding window approach. We further consider A n , 2 A_{n,2} A n , 2 and B n , 2 B_{n,2} B n , 2 , which require keeping track of the 1- and 2-record processes. For B n , m B_{n,m} B n , m the best of the explored single-curve rules has the failure probability within 7.5% (m = 2 m=2 m = 2 ) and about 20% (m = 3 m=3 m = 3 ) of the optimum computed in [19 ] , and two- or three-parameter rules reduce the excess to below 1%. This suggests that for problems with rank-dependent loss the complexity of the exactly optimal strategies is not matched by the gain over simple low-parameter rules, in accord with our findings on the best-choice problem [17 ] .
In [12 , 13 , 18 ] the full-information best-choice problem and some of its versions were embedded in a planar Poisson process (PPP) – an infinite-arrivals model providing a natural framework for the asymptotic analysis. In [14 ] this connection was extended to problems with objective (2) where the stopping value remains bounded as n → ∞ n \to\infty n → ∞ . In [17 ] we applied the PPP as a tool to compare the optimal best-choice strategy against a memoryless rule, which stops at the first arrival below a precommitted time-dependent threshold. Here we continue this line by using the self-similarity of the PPP to eliminate the time variable from the integro-differential optimality equation, to reveal the structural patterns of the optimal adaptive threshold, and to evaluate the limits in (4) and (5) .
The rest of the paper is organised as follows. In § 2 we connect the discrete-time problems (4) , (5) with their PPP counterparts A m A_m A m , B m B_m B m , show the convergence of the optimal stopping values, and analyse the optimality equation for the value function. The central optimality result, Theorem 2.4 , is proved for more general loss structures; we need a special argument using self-similarity and an embedded Markov chain with a finite number of steps, since the PPP setting, with infinitely many arrivals and a rank-dependent loss, is not covered verbatim by the standard theorem. Proposition 2.7 describes the pathwise behaviour of the adaptive acceptance threshold: we show that this is a nondecreasing process drifting continuously between arrivals, jumping up at some arrival times, and staying flat once it reaches a past score. § 3 presents explicit solutions for m = 1 m=1 m = 1 . § 4 describes the geometric boundaries of the two-dimensional stopping sets, and § 5 and § 6 give the solutions of $A_2 and B2 _2 2 . Section 7 explores the performance of simple strategies, especially for B m B_m B m . Section 8 presents numerical evaluation of optimal and suboptimal stopping strategies.
The planar Poisson process framework
Scores, ranks and losses
Let Π \Pi Π be a unit rate PPP on [ 0 , 1 ] × [ 0 , ∞ ) [0,1]\times[0,\infty) [ 0 , 1 ] × [ 0 , ∞ ) . We view Π \Pi Π as a random scatter of points, where an atom ( t , x ) ∈ Π (t,x)\in\Pi ( t , x ) ∈ Π is interpreted as a score x x x observed at time t t t , smaller scores being preferred. The natural filtration is generated by the restrictions of Π \Pi Π to [ 0 , t ] × [ 0 , ∞ ) [0,t]\times[0,\infty) [ 0 , t ] × [ 0 , ∞ ) , t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] . An admissible selection strategy (sometimes referred to as rule) is a stopping time τ \tau τ with respect to this filtration, which is either the arrival time of an atom or τ = 1 \tau=1 τ = 1 (no selection); the latter happens with positive probability for the optimal strategies. See [23 ] for measure-theoretic aspects of optimal stopping for planar point processes, with objectives depending on ( t , x ) (t,x) ( t , x ) alone.
For an atom ( t , x ) (t,x) ( t , x ) we define its final rank r r r to be one plus the number of atoms of Π \Pi Π with scores smaller than x x x , and its initial rank i i i to be one plus the number of earlier atoms with scores smaller than x x x . When the atom arrives, x x x and i i i are observed, and the conditional distribution of r − i r-i r − i is Poisson(ξ \xi ξ ), with the mean equal to the area of the south-east window ( t , 1 ] × ( 0 , x ) (t,1]\times(0,x) ( t , 1 ] × ( 0 , x ) , where
ξ : = t x ˉ , t ˉ : = 1 − t . \xi:= t\bar{x}, \qquad\bar{t} := 1-t. ξ := t x ˉ , t ˉ := 1 − t .
We call ξ \xi ξ the box coordinate of the atom.
For m = 1 , 2 , … m=1,2,\ldots m = 1 , 2 , … we consider two types of the adapted loss from stopping at an atom with initial rank i i i and box coordinate ξ \xi ξ , given the observed information:
A m : Q ( ξ , i ) = min ( i , m + 1 ) + ξ , (6) \begin{aligned}
A_m:\qquad&Q(\xi,i)=\min(i,m+1)+\xi, \tag*{(6)}
\end{aligned} A m : Q ( ξ , i ) = min ( i , m + 1 ) + ξ , (6)
B m : Q ( ξ , i ) = 1 − ∑ j = 0 m − i e − ξ ξ j j ! , (7) \begin{aligned}
B_m:\qquad&Q(\xi,i)=1-\sum_{j=0}^{m-i}\frac{e^{-\xi}\xi^j}{j!}, \tag*{(7)}
\end{aligned} B m : Q ( ξ , i ) = 1 − j = 0 ∑ m − i j ! e − ξ ξ j , (7)
where the sum in (7) is empty for i > m i>m i > m . The PPP problems with these loss structures are infinite-arrivals counterparts of the full-information problems (4) , (5) from the Introduction. In both cases Q ( ξ , i ) Q(\xi,i) Q ( ξ , i ) is nondecreasing in ξ \xi ξ and in i i i . For the event { τ = 1 } \{\tau=1\} { τ = 1 } we assume the loss
Q ∞ = m + 1 in A m , Q ∞ = 1 in B m . Q_\infty=m+1\text{ in }A_m,\qquad Q_\infty=1\text{ in }B_m. Q ∞ = m + 1 in A m , Q ∞ = 1 in B m .
This convention is the limit form of the terminal loss in the finite-n n n problems (4) , (5) , where the observer must stop at stage n n n : by exchangeability, the last score has rank of order n n n with high probability, and the loss for being forced to accept it tends to Q ∞ Q_\infty Q ∞ . Clearly, it can only be optimal to stop at observations with initial rank i ≤ m i\le m i ≤ m , since otherwise the loss is at least Q ∞ Q_\infty Q ∞ ; this may lead to missing all opportunities and ending at t = 1 t=1 t = 1 . The minimal achievable expected losses are denoted a m a_m a m and b m b_m b m for problems A m A_m A m and B m B_m B m , respectively. For B m B_m B m the loss is the conditional probability of failure , which is the choice of an atom of final rank above m m m ; the complementary probability 1 − b m 1-b_m 1 − b m is the probability of successful choice of one of the m m m best scores.
Here is the link to the discrete-time fixed-n n n problems. Split the time range [ 0 , 1 ] [0,1] [ 0 , 1 ] in n n n equal slots ( ( k − 1 ) / n , k / n ] ((k-1)/n,k/n] (( k − 1 ) / n , k / n ] , k ∈ [ n ] k\in[n] k ∈ [ n ] , and suppose that the arrival times of the n n n slot-wise minima M 1 , … , M n M_1,\ldots,M_n M 1 , … , M n belong to the prior information of the observer. Then the selection is reduced to an n n n -step problem for M 1 , … , M n M_1,\ldots,M_n M 1 , … , M n , which are independent and share the same exponential distribution. With the further advantage that only unobserved minima contribute to the final rank of the selected observation, the problem becomes equivalent to A n , m A_{n,m} A n , m , respectively B n , m B_{n,m} B n , m . This shows that the Poisson values a m , b m a_m,b_m a m , b m are upper bounds for the values of the discrete problems. In problem [5 ] the values increase with n n n to b m \mathbf{b}_m b m [14 ] . For problem [4 ] the same holds, but requires a separate proof, since the loss is not a function of the final rank.
Proposition 2.1. Let a n , m a_{n,m} a n , m be the value of problem [4 ] . For every m ≥ 1 m \ge1 m ≥ 1 the sequence a n , m a_{n,m} a n , m , n ≥ m n \ge m n ≥ m , is nondecreasing and converges to a m \mathbf{a}_m a m .
Proof. The loss for selecting a score is min ( i , m + 1 ) + N \min(i,m+1)+N min ( i , m + 1 ) + N , where i i i is its initial rank and N N N is the number of later scores below it. It depends on the scores only through their order, hence the common continuous distribution of the scores does not matter for the stopping problem.
Monotonicity in n n n follows by a familiar coupling argument. Take n + 1 n+1 n + 1 independent uniform scores, n ≥ m n \ge m n ≥ m , and let the observer be told in advance the value u u u of the largest one; the advantage can only lower the minimal expected loss. If u u u is the k k k -th score, selecting it costs min ( k , m + 1 ) + ( n + 1 − k ) ≥ m + 1 \min(k,m+1)+(n+1-k) \ge m+1 min ( k , m + 1 ) + ( n + 1 − k ) ≥ m + 1 , while the last of the other scores costs at most m + 1 m+1 m + 1 , so u u u may be declined. Discarding u u u does not impact ranking of the other scores, and given u u u the other scores are independent and uniform on [ 0 , u ] [0,u] [ 0 , u ] . Thus the problem is reduced to n n n scores, and a n , m ≤ a n + 1 , m a_{n,m} \le a_{n+1,m} a n , m ≤ a n + 1 , m .
Upper bound follows by the slot argument above: a n , m ≤ a m a_{n,m} \le\mathbf{a}_m a n , m ≤ a m . The rest of the proof deals with a lower bound.
Fix n n n , a level A > 0 A>0 A > 0 and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , and let M 1 , … , M n M_1,\ldots,M_n M 1 , … , M n be the minima of Π \Pi Π over the slots ( ( k − 1 ) / n , k / n ] ((k-1)/n,k/n] (( k − 1 ) / n , k / n ] , as above; they are independent and P [ M k > x ] = e − x / n \mathbb{P}[M_k>x]=e^{-x/n} P [ M k > x ] = e − x / n . Let ρ \rho ρ be the optimal strategy for the n n n -step problem with the scores M 1 , … , M n M_1,\ldots,M_n M 1 , … , M n , i.e. ρ \rho ρ is adapted to G k : = σ ( M 1 , … , M k ) \mathcal{G}_k:=\sigma(M_1,\ldots,M_k) G k := σ ( M 1 , … , M k ) , k ∈ [ n ] k \in[n] k ∈ [ n ] , and incurs some loss L ρ L_\rho L ρ satisfying E L ρ = a n , m \mathbb{E}L_\rho=a_{n,m} E L ρ = a n , m . At stage k k k the strategy ρ \rho ρ accepts any score below some threshold depending on history M 1 , … , M k − 1 M_1,\ldots,M_{k-1} M 1 , … , M k − 1 . The latter follows from the opposite directions of monotonicity of the expected loss of stopping at score x x x , given by min ( i , m + 1 ) + ( n − k ) ( 1 − e − x / n ) \min(i,m+1)+(n-k)(1-e^{-x/n}) min ( i , m + 1 ) + ( n − k ) ( 1 − e − x / n ) with i i i the initial rank of x x x , and the value function, which is nonincreasing in the state (the coupling of Lemma 2.6(i)). Consider a stopping time τ \tau τ for Π \Pi Π defined as follows: τ \tau τ stops at an atom ( t , x ) (t,x) ( t , x ) of the k k k -th slot if and only if x < A x<A x < A , no earlier atom of this slot has score below A A A , and ρ \rho ρ applied to the sequence M 1 , … , M k − 1 , x M_1,\ldots,M_{k-1},x M 1 , … , M k − 1 , x stops at stage k k k with score x x x . At any time t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] the minima of the earlier slots are known, so τ \tau τ is a legitimate stopping time for Π \Pi Π . Let L τ L_\tau L τ be its loss, equal to m + 1 m+1 m + 1 if no atom is selected, and let N A = d Poisson ( A ) N_A \stackrel{d}{=} \operatorname{Poisson}(A) N A = d Poisson ( A ) count the number of atoms of Π \Pi Π with score below A A A .
Let G G G be the event that every slot contains at most one atom with score below A A A , and let D = { M ρ ≥ A } D=\{M_\rho\ge A\} D = { M ρ ≥ A } . Suppose τ \tau τ stops at an atom x x x of the k k k -th slot. Then x ≥ M k x \ge M_k x ≥ M k , and ρ \rho ρ applied to M 1 , … , M k − 1 , x M_1,\ldots,M_{k-1},x M 1 , … , M k − 1 , x stops at the stage k k k and not before; then M k ≤ x M_k \le x M k ≤ x belongs to the acceptance interval for the same history, hence ρ = k \rho=k ρ = k . Thus τ \tau τ stops only in the slot ρ \rho ρ , at the first atom of this slot with score below A A A (which is not later than the atom M ρ M_\rho M ρ in time), or makes no selection. On G ∖ D G \setminus D G ∖ D we have L τ = L ρ L_\tau=L_\rho L τ = L ρ , since the slot ρ \rho ρ contains exactly one atom below A A A , which has the score M ρ M_\rho M ρ selected by τ \tau τ ; every atom below M ρ M_\rho M ρ is the minimum of its slot, so the initial rank of M ρ M_\rho M ρ and the number of later atoms below it are the same in Π \Pi Π as among the slot minima. On G ∩ D G \cap D G ∩ D the slot ρ \rho ρ has no atom below A A A , thus τ \tau τ makes no selection and L τ = m + 1 L_\tau=m+1 L τ = m + 1 . On the complement of G G G the selected atom may differ from the slot minimum, but still L τ ≤ m + 1 + N A L_\tau\le m+1+N_A L τ ≤ m + 1 + N A . Since L ρ ≥ 0 L_\rho\ge0 L ρ ≥ 0 , we obtain
E L τ ≤ E [ L ρ 1 ( D c ) ] + ( m + 1 ) P [ D ] + E [ ( m + 1 + N A ) 1 ( G c ) ] = a n , m + E [ ( m + 1 − L ρ ) 1 ( D ) ] + E [ ( m + 1 + N A ) 1 ( G c ) ] . (8) \begin{aligned}
\mathbb{E}L_\tau\le\mathbb{E}[L_\rho\mathbf{1}(D^c)] +(m+1)\mathbb{P}[D] + \mathbb{E}[(m+1+N_A)\mathbf{1}(G^c)] \\
&= a_{n,m}+\mathbb{E}[(m+1-L_\rho)\mathbf{1}(D)] + \mathbb{E}[(m+1+N_A)\mathbf{1}(G^c)]. \tag*{(8)}
\end{aligned} E L τ ≤ E [ L ρ 1 ( D c )] + ( m + 1 ) P [ D ] + E [( m + 1 + N A ) 1 ( G c )] = a n , m + E [( m + 1 − L ρ ) 1 ( D )] + E [( m + 1 + N A ) 1 ( G c )] . (8)
The term with D D D . Since D ∈ G ρ D \in\mathcal{G}_\rho D ∈ G ρ and, conditionally on G ρ \mathcal{G}_\rho G ρ , the later minima are independent of the past, on D D D we have
E [ L ρ ∣ G ρ ] = min ( i ρ , m + 1 ) + ( n − ρ ) ( 1 − e − M ρ / n ) ≥ min ( i ρ , m + 1 ) + ( n − ρ ) ( 1 − e − A / n ) , \mathbb{E}[L_\rho\mid\mathcal{G}_\rho]=\min(i_\rho,m+1)+(n-\rho)(1-e^{-M_\rho/n}) \ge\min(i_\rho,m+1)+(n-\rho)(1-e^{-A/n}), E [ L ρ ∣ G ρ ] = min ( i ρ , m + 1 ) + ( n − ρ ) ( 1 − e − M ρ / n ) ≥ min ( i ρ , m + 1 ) + ( n − ρ ) ( 1 − e − A / n ) ,
where i ρ i_\rho i ρ is the initial rank of M ρ M_\rho M ρ . If ρ ≤ ( 1 − δ ) n \rho\le(1-\delta)n ρ ≤ ( 1 − δ ) n , the right side is at least δ n ( 1 − e − A / n ) \delta n(1-e^{-A/n}) δ n ( 1 − e − A / n ) , which tends to δ A \delta A δ A as n → ∞ n \to\infty n → ∞ , so it exceeds m + 1 m+1 m + 1 for large n n n when A ≥ 2 ( m + 1 ) / δ A \ge2(m+1)/\delta A ≥ 2 ( m + 1 ) / δ . If ρ > ( 1 − δ ) n \rho> (1-\delta)n ρ > ( 1 − δ ) n , then on D D D every minimum M k M_k M k with k ≤ ( 1 − δ ) n k \le(1-\delta)n k ≤ ( 1 − δ ) n and M k < A M_k < A M k < A is below M ρ M_\rho M ρ and arrives earlier, thus i ρ ≥ m + 1 i_\rho\ge m+1 i ρ ≥ m + 1 unless fewer than m m m such minima exist. Let H H H be the event that fewer than m m m of the minima M k M_k M k , k ≤ ( 1 − δ ) n k \le(1-\delta)n k ≤ ( 1 − δ ) n , are below A A A . Then, for large n n n , ( m + 1 − E [ L ρ ∣ G ρ ] ) 1 ( D ) ≤ ( m + 1 ) 1 ( H ) (m+1-\mathbb{E}[L_\rho\mid\mathcal{G}_\rho])1(D) \le(m+1)1(H) ( m + 1 − E [ L ρ ∣ G ρ ]) 1 ( D ) ≤ ( m + 1 ) 1 ( H ) , which yields
E [ ( m + 1 − L ρ ) 1 ( D ) ] ≤ ( m + 1 ) P [ H ] . \mathbb{E}[(m+1-L_\rho)1(D)] \le(m+1)\mathbb{P}[H]. E [( m + 1 − L ρ ) 1 ( D )] ≤ ( m + 1 ) P [ H ] .
The number of minima M k M_k M k , k ≤ ( 1 − δ ) n k \le(1-\delta)n k ≤ ( 1 − δ ) n , which fall below A A A is binomial with success probability 1 − e − A / n 1-e^{-A/n} 1 − e − A / n , hence P [ H ] → P [ N ≤ m − 1 ] \mathbb{P}[H] \to\mathbb{P}[N \le m-1] P [ H ] → P [ N ≤ m − 1 ] as n → ∞ n \to\infty n → ∞ , where N N N is Poisson with mean ( 1 − δ ) A (1-\delta)A ( 1 − δ ) A .
The term with G c \mathcal{G}^c G c . Let N k N_k N k be the number of atoms with score below A A A in the k k k -th slot; these are independent Poisson with mean A / n A/n A / n , and N A = ∑ k N k N_A=\sum_k N_k N A = ∑ k N k , G c = ⋃ k { N k ≥ 2 } \mathcal{G}^c=\bigcup_k\{N_k\ge2\} G c = ⋃ k { N k ≥ 2 } . Therefore P [ G c ] ≤ n ( A / n ) 2 / 2 = A 2 / ( 2 n ) \mathbb{P}[\mathcal{G}^c] \le n(A/n)^2/2=A^2/(2n) P [ G c ] ≤ n ( A / n ) 2 /2 = A 2 / ( 2 n ) , and
E [ N A 1 ( G c ) ] ≤ ∑ j ≠ k E N j P [ N k ≥ 2 ] + ∑ k E [ N k ( N k − 1 ) ] ≤ n 2 A n A 2 2 n 2 + n A 2 n 2 = A 3 2 n + A 2 n , \begin{aligned}
\mathbb{E}[N_A1(\mathcal{G}^c)] \le\sum_{j\ne k}\mathbb{E}N_j\mathbb{P}[N_k\ge2]+\sum_k\mathbb{E}[N_k(N_k-1)] \\
&\le n^2\frac{A}{n}\frac{A^2}{2n^2}+n\frac{A^2}{n^2}=\frac{A^3}{2n}+\frac{A^2}{n},
\end{aligned} E [ N A 1 ( G c )] ≤ j = k ∑ E N j P [ N k ≥ 2 ] + k ∑ E [ N k ( N k − 1 )] ≤ n 2 n A 2 n 2 A 2 + n n 2 A 2 = 2 n A 3 + n A 2 ,
since N ≤ N ( N − 1 ) N\le N(N-1) N ≤ N ( N − 1 ) for N ≥ 2 N\ge2 N ≥ 2 for the diagonal terms j = k j=k j = k . Therefore for the term in focus E [ ( m + 1 + N A ) 1 ( G c ) ] → 0 \mathbb{E}[(m+1+N_A)1(\mathcal{G}^c)]\to0 E [( m + 1 + N A ) 1 ( G c )] → 0 as n → ∞ n\to\infty n → ∞ .
Finally, given the past, the number of later atoms below a selected atom is Poisson with mean equal to its box coordinate, so E L τ \mathbb{E}L_\tau E L τ is the expected loss (6) of the strategy τ \tau τ , and a m ≤ E L τ a_m\le\mathbb{E}L_\tau a m ≤ E L τ . Passing to the limit in (8) we obtain for every A ≥ 2 ( m + 1 ) / δ A\ge2(m+1)/\delta A ≥ 2 ( m + 1 ) / δ
a m ≤ lim n → ∞ a n , m + ( m + 1 ) P [ N ≤ m − 1 ] , a_m\le\lim_{n\to\infty}a_{n,m}+(m+1)\mathbb{P}[N\le m-1], a m ≤ n → ∞ lim a n , m + ( m + 1 ) P [ N ≤ m − 1 ] ,
and letting A → ∞ A\to\infty A → ∞ gives a m ≤ lim n a n , m a_m\le\lim_n a_{n,m} a m ≤ lim n a n , m (the limit exists by monotonicity). Taken together with the upper bound, this implies the desired convergence a n , m ↑ a m a_{n,m}\uparrow a_m a n , m ↑ a m .
Self-similarity and the state
For every t > 0 t>0 t > 0 the number of atoms arrived before time t t t is infinite. However, since the ranks above m m m can be ignored, the past data relevant for the future decisions is the ordered vector y = ( y 1 , … , y m ) \mathbf{y}=(y_1,\ldots,y_m) y = ( y 1 , … , y m ) , where y i y_i y i is the i i i -th lowest score observed before t t t . We call y \mathbf{y} y the history; this statistic takes the role of the state in a Markovian stopping problem. Along the path of PPP, the history is a monotonic jump Markov process; the marginals y i y_i y i are the (minimal) i i i -record processes, coming down from infinity at t = 0 + t=0+ t = 0 + [15 ] . In the sequel under time-0 history we shall mean a finite state of this m m m -dimensional process; the stopping problem initialised this way can be interpreted in terms of Palm conditioning of the PPP on m m m arrivals at time 0.
Lemma 2.2. The decision problem at time t t t with the history y \mathbf{y} y is equivalent to the problem at time 0 with the initial history t ˉ y = ( t ˉ y 1 , … , t ˉ y m ) \bar{t}\mathbf{y}=(\bar{t}y_1,\ldots,\bar{t}y_m) t ˉ y = ( t ˉ y 1 , … , t ˉ y m ) .
Proof. Given the observations up to time t t t , the restriction of Π \Pi Π to ( t , 1 ] × [ 0 , ∞ ) (t,1]\times[0,\infty) ( t , 1 ] × [ 0 , ∞ ) is a PPP. The map ( s , x ) ↦ ( ( s − t ) / t ˉ , t ˉ x ) (s,x)\mapsto((s-t)/\bar{t},\bar{t}x) ( s , x ) ↦ (( s − t ) / t ˉ , t ˉ x ) preserves the Lebesgue measure and sends this restriction to a PPP on [ 0 , 1 ] × [ 0 , ∞ ) [0,1]\times[0,\infty) [ 0 , 1 ] × [ 0 , ∞ ) . It sends the history y \mathbf{y} y to t ˉ y \bar{t}\mathbf{y} t ˉ y , preserves all ranks, and the box coordinate t ˉ x \bar{t}x t ˉ x of an atom ( t , x ) (t,x) ( t , x ) is the same in both settings.
Thus it suffices to consider the stopping–continuation dilemma at time 0, for the generic state x = ( x 1 , … , x m ) \mathbf{x}=(x_1,\ldots,x_m) x = ( x 1 , … , x m ) , where x i x_i x i is the i i i -th lowest of the scores in box coordinates, x i = t ˉ y i x_i=\bar{t}y_i x i = t ˉ y i . To avoid confusion, we keep the notation y \mathbf{y} y for the history in the original PPP coordinates at a given time t > 0 t>0 t > 0 . Let S = { x : 0 ≤ x 1 ≤ ⋯ ≤ x m < ∞ } \mathcal{S}=\{\mathbf{x}:0\le x_1\le\cdots\le x_m<\infty\} S = { x : 0 ≤ x 1 ≤ ⋯ ≤ x m < ∞ } be the set of finite states. For x ∈ S \mathbf{x}\in\mathcal{S} x ∈ S and ξ < x m \xi<x_m ξ < x m we write x ∪ ξ \mathbf{x}\cup\xi x ∪ ξ for the vector of the m m m lowest values among x 1 , … , x m , ξ x_1,\ldots,x_m,\xi x 1 , … , x m , ξ ; this is the updated state upon arrival at the box coordinate ξ \xi ξ . The initial rank of such an arrival is i ( x , ξ ) : = 1 + # { j ∈ [ m ] : x j < ξ } i(\mathbf{x},\xi):=1+\#\{j\in[m]:x_j<\xi\} i ( x , ξ ) := 1 + # { j ∈ [ m ] : x j < ξ } . An atom with box coordinate above x m x_m x m has initial rank larger than m m m ; it is never worth accepting (its loss is at least Q ∞ Q_\infty Q ∞ ) and does not change the history.
The value function and the optimal strategy
The optimality results below apply to a general loss Q ( ξ , i ) ≥ 0 Q(\xi,i) \ge0 Q ( ξ , i ) ≥ 0 , provided it is nondecreasing in ξ ≥ 0 \xi\ge0 ξ ≥ 0 and i ≥ 1 i \ge1 i ≥ 1 and satisfies Q ( ξ , i ) ≥ Q ∞ Q(\xi,i) \ge Q_\infty Q ( ξ , i ) ≥ Q ∞ for i > m i > m i > m , where Q ∞ < ∞ Q_\infty< \infty Q ∞ < ∞ is the loss of no selection, and also Q ( 0 + , 1 ) < Q ∞ Q(0+,1) < Q_\infty Q ( 0 + , 1 ) < Q ∞ . These properties hold for the losses (6) and (7) . We require further that
lim inf ξ → ∞ Q ( ξ , 1 ) ≥ Q ∞ , (9) \liminf_{\xi\to\infty} Q(\xi,1) \ge Q_\infty, \tag*{(9)} ξ → ∞ lim inf Q ( ξ , 1 ) ≥ Q ∞ , (9)
which holds in both cases: Q ( ξ , 1 ) = 1 + ξ Q(\xi,1) = 1+\xi Q ( ξ , 1 ) = 1 + ξ in A m A_m A m , and Q ( ξ , 1 ) = 1 − e − ξ ∑ j < m ξ j / j ! → 1 Q(\xi,1) = 1-e^{-\xi}\sum_{j<m}\xi^j/j! \to1 Q ( ξ , 1 ) = 1 − e − ξ ∑ j < m ξ j / j ! → 1 in B m B_m B m . Condition (9) is used only for the attainment of the value for the empty history, see Remark 2.5. Lemma 2.6 below uses further properties of A m A_m A m and B m B_m B m .
The expected loss of an admissible strategy τ \tau τ in the problem which starts at time 0 with the history x x x is
L x ( τ ) = E [ Q ( ξ τ , i τ ) 1 { τ < 1 } + Q ∞ 1 { τ = 1 } ] , L_x(\tau)=\mathbb{E}\left[Q(\xi_\tau,i_\tau)1\{\tau<1\}+Q_\infty1\{\tau=1\}\right], L x ( τ ) = E [ Q ( ξ τ , i τ ) 1 { τ < 1 } + Q ∞ 1 { τ = 1 } ] ,
where ξ τ , i τ \xi_\tau,i_\tau ξ τ , i τ are the box coordinate and the initial rank (counted together with the history x x x ) of the selected atom; for A m , B m A_m,B_m A m , B m this is the expected loss in the original problem, by the conditioning in § 2 . The history is a state x x x with components in [ 0 , ∞ ] [0,\infty] [ 0 , ∞ ] : a finite state x ∈ S x \in S x ∈ S , the empty history ∞ \infty ∞ , or a state with some components equal to ∞ \infty ∞ (fewer than m m m scores observed). The value function is v ( x ) = inf τ L x ( τ ) v(x)=\inf_\tau L_x(\tau) v ( x ) = inf τ L x ( τ ) ; thus v ( ∞ ) v(\infty) v ( ∞ ) is a m a_m a m , respectively b m b_m b m in the corresponding stopping problems. For bounded Borel functions w w w on S S S define the operator
P [ w ] ( x ) : = ∫ 0 x m min { Q ( ξ , i ( x , ξ ) ) , w ( x ∪ ξ ) } d ξ . P[w](x):=\int_0^{x_m}\min\left\{Q(\xi,i(x,\xi)),w(x\cup\xi)\right\}\,\mathrm{d}\xi. P [ w ] ( x ) := ∫ 0 x m min { Q ( ξ , i ( x , ξ )) , w ( x ∪ ξ ) } d ξ .
The map ( t , x ) ↦ ( u , ξ ) = ( − log ( 1 − t ) , ( 1 − t ) x ) (t,x)\mapsto(u,\xi)=(-\log(1-t),(1-t)x) ( t , x ) ↦ ( u , ξ ) = ( − log ( 1 − t ) , ( 1 − t ) x ) preserves the Lebesgue measure, and transforms Π \Pi Π into a unit rate PPP Π ~ \widetilde{\Pi} Π on [ 0 , ∞ ) × [ 0 , ∞ ) [0,\infty)\times[0,\infty) [ 0 , ∞ ) × [ 0 , ∞ ) ; the time t = 1 t=1 t = 1 corresponds to u = ∞ u=\infty u = ∞ . In the new time variable u u u the state in box coordinates, Z u = t ˉ y t Z_u=\bar{t}\,y_t Z u = t ˉ y t , is a piecewise deterministic Markov process: between arrivals it drifts from some state Z u Z_u Z u along the ray Z u ′ = e − ( u ′ − u ) Z u Z_{u'}=e^{-(u'-u)}Z_u Z u ′ = e − ( u ′ − u ) Z u toward the origin. Arrivals with box coordinates ξ < Z u , m \xi<Z_{u,m} ξ < Z u , m that change the state to Z ∪ ξ Z\cup\xi Z ∪ ξ occur at rate Z u , m Z_{u,m} Z u , m with ξ \xi ξ uniform on [ 0 , Z u , m ] [0,Z_{u,m}] [ 0 , Z u , m ] . (The map is the self-similarity of Lemma 2.2 written for all times at once.) The loss Q ( ξ , i ) Q(\xi,i) Q ( ξ , i ) depends on an atom only through ξ \xi ξ and the initial rank, and the stopping problem in these coordinates does not involve time.
A constant threshold b b b for the box coordinate is the hyperbola x = b / t ˉ x=b/\bar{t} x = b / t ˉ in the original coordinates. For m = 1 m=1 m = 1 the state is the box coordinate of the running minimum, which makes the stopping problem one-dimensional and implies that in the original coordinates the optimal threshold for record scores is a hyperbola (§ 3 ).
Remark 2.3. Hyperbolas appear also for the simple strategies of § 7 , which do not use the history. For m ≥ 2 m\ge2 m ≥ 2 the threshold depends on the history through the state t ˉ y \bar{t}y t ˉ y , which shrinks between arrivals while the past scores stay fixed, so the threshold is not a hyperbola (§ 4 ). The same scaling gives a hyperbola for the problem of minimising the expected score (Moser’s problem in the PPP [16 ] , where the optimal threshold is 2 / t ˉ 2/\bar{t} 2/ t ˉ . In discrete time there is no self-similarity, and hyperbolic thresholds appear only asymptotically [10 , 12 , 13 ] .
Call an atom ( t , x ) (t,x) ( t , x ) low if its initial rank is at most m m m , that is, if x < y m x<y_m x < y m for the history y = y t − y=y_{t-} y = y t − just before t t t , or equivalently if its box coordinate ξ = t ˉ x \xi=\bar{t}x ξ = t ˉ x is below the m m m -th component of the state Z = t ˉ y Z=\bar{t}y Z = t ˉ y just before t t t . A low atom changes the state by a jump when it arrives, and it may be accepted or declined. An atom which is not low does not change the state and is declined.
Consider the problem which starts at time 0 with the history x ∈ S x\in S x ∈ S ; at time 0 the original and the box coordinates coincide. The history y t y_t y t in the original coordinates can only decrease, so y m ≤ x m y_m \leq x_m y m ≤ x m at all times. Hence every low atom has score below x m x_m x m , and the number N N N of low atoms is stochastically dominated by the Poisson variable with mean x m x_m x m ,
P [ N > k ] ≤ P [ Poisson ( x m ) > k ] → 0 ( k → ∞ ) , (10) \mathbb{P}[N > k] \leq\mathbb{P}[\operatorname{Poisson}(x_m) > k] \to0 \quad(k \to\infty), \tag*{(10)} P [ N > k ] ≤ P [ Poisson ( x m ) > k ] → 0 ( k → ∞ ) , (10)
uniformly for x m ≤ a x_m \leq a x m ≤ a .
The selection problem is thus an optimal stopping problem for a Markov chain with an a.s. finite number of steps: the chain is the sequence of states ( i , Z ) (i,Z) ( i , Z ) right after the successive low atoms, with loss Q ( ξ , i ) Q(\xi,i) Q ( ξ , i ) being a function of the state, where ξ = Z i \xi= Z_i ξ = Z i . This makes applicable the standard discrete-time Markovian stopping theory (see [5 ] , Section 5.1).
By the first-arrival decomposition to follow, the first low atom after the time 0, in the problem with the state x x x , arrives at the time r r r in the variable r = e − u ∈ ( 0 , 1 ) r=e^{-u}\in(0,1) r = e − u ∈ ( 0 , 1 ) with the density x m e − x m ( 1 − r ) d r x_m e^{-x_m(1-r)}\,dr x m e − x m ( 1 − r ) d r , its box coordinate is uniform on [ 0 , r x m ] [0,rx_m] [ 0 , r x m ] and independent of r r r , and the state after the atom is r x ∪ ξ rx\cup\xi r x ∪ ξ ; with probability e − x m e^{-x_m} e − x m there is no low atom at all. For a Borel set A ⊂ { ( x , ξ ) : ξ < x m } A\subset\{(x,\xi):\xi<x_m\} A ⊂ {( x , ξ ) : ξ < x m } (referred to as acceptance set for the arriving score) and a bounded Borel w w w define
( T A w ) ( x ) = e − x m ( Q ∞ + ∫ 0 1 e x m r P A [ w ] ( r x ) r d r ) , (11) (T_Aw)(x)=e^{-x_m}\left(Q_\infty+\int_0^1 e^{x_m r}\frac{P_A[w](rx)}{r}\,dr\right), \tag*{(11)} ( T A w ) ( x ) = e − x m ( Q ∞ + ∫ 0 1 e x m r r P A [ w ] ( r x ) d r ) , (11)
P A [ w ] ( x ) = ∫ 0 x m ( 1 A Q + 1 A c w ( x ∪ ξ ) ) d ξ , Q = Q ( ξ , i ( x , ξ ) ) , P_A[w](x)=\int_0^{x_m}\left(\mathbf{1}_A Q+\mathbf{1}_{A^c}w(x\cup\xi)\right)\,d\xi,\qquad Q=Q(\xi,i(x,\xi)), P A [ w ] ( x ) = ∫ 0 x m ( 1 A Q + 1 A c w ( x ∪ ξ ) ) d ξ , Q = Q ( ξ , i ( x , ξ )) ,
and T = T A w T=T_{A_w} T = T A w for A w = { ( x , ξ ) : Q ( ξ , i ( x , ξ ) ) ≤ w ( x ∪ ξ ) } A_w=\{(x,\xi):Q(\xi,i(x,\xi))\leq w(x\cup\xi)\} A w = {( x , ξ ) : Q ( ξ , i ( x , ξ )) ≤ w ( x ∪ ξ )} , so that P A w [ w ] = P [ w ] P_{A_w}[w]=P[w] P A w [ w ] = P [ w ] and
( T w ) ( x ) = e − x m ( Q ∞ + ∫ 0 1 e x m r P [ w ] ( r x ) r d r ) . (12) (Tw)(x)=e^{-x_m}\left(Q_\infty+\int_0^1 e^{x_m r}\frac{P[w](rx)}{r}\,dr\right). \tag*{(12)} ( T w ) ( x ) = e − x m ( Q ∞ + ∫ 0 1 e x m r r P [ w ] ( r x ) d r ) . (12)
If 0 ≤ w ≤ Q ∞ 0\leq w\leq Q_\infty 0 ≤ w ≤ Q ∞ and Q ≤ Q ∞ Q\leq Q_\infty Q ≤ Q ∞ on A A A (in particular for A = A w A=A_w A = A w ), then 0 ≤ P A [ w ] ( r x ) ≤ r x m Q ∞ 0\leq P_A[w](rx)\leq rx_mQ_\infty 0 ≤ P A [ w ] ( r x ) ≤ r x m Q ∞ , so the integral converges and e − x m Q ∞ ≤ T A w ≤ Q ∞ e^{-x_m}Q_\infty\leq T_Aw\leq Q_\infty e − x m Q ∞ ≤ T A w ≤ Q ∞ .
The next result makes the dynamic programming equation of this chain explicit, and adds the uniqueness of its solution, the optimal strategy, and the case of the empty history.
Theorem 2.4. (i) The value function v v v is continuous on S S S with 0 ≤ v ≤ Q ∞ 0\leq v\leq Q_\infty 0 ≤ v ≤ Q ∞ and v ( 0 ) = Q ∞ v(0)=Q_\infty v ( 0 ) = Q ∞ , and along every ray the function s ↦ v ( s x ) s\mapsto v(sx) s ↦ v ( s x ) is continuously differentiable on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) , with
∑ i = 1 m x i ∂ v ( x ) ∂ x i + x m v ( x ) = P [ v ] ( x ) , (13) \sum_{i=1}^{m}x_i\frac{\partial v(x)}{\partial x_i}+x_m v(x)=P[v](x), \tag*{(13)} i = 1 ∑ m x i ∂ x i ∂ v ( x ) + x m v ( x ) = P [ v ] ( x ) , (13) where ∑ i x i ∂ i v ( x ) \sum_i x_i\partial_i v(x) ∑ i x i ∂ i v ( x ) is the derivative of s ↦ v ( s x ) s\mapsto v(sx) s ↦ v ( s x ) at s = 1 s=1 s = 1 . Equivalently, v = T v v=Tv v = T v .
(ii) The solution is unique: every bounded solution of w = T w w=Tw w = T w is equal to v v v . In particular, a function w w w which is bounded, continuous and continuously differentiable along the rays, satisfies (13) and w ( s x ) → Q ∞ w(sx)\to Q_\infty w ( s x ) → Q ∞ as s → 0 s\to0 s → 0 , is the value function.
(iii) The strategy τ ∗ \tau^* τ ∗ which, in the problem with the initial state x ∈ S x\in S x ∈ S , selects the first low atom with the box coordinate ξ \xi ξ satisfying
Q ( ξ , i ( Z , ξ ) ) ≤ v ( Z ∪ ξ ) , (14) Q(\xi,i(Z,\xi))\leq v(Z\cup\xi), \tag*{(14)} Q ( ξ , i ( Z , ξ )) ≤ v ( Z ∪ ξ ) , (14) where Z Z Z is the state immediately before the arrival of the atom, is optimal: L x ( τ ∗ ) = v ( x ) L_x(\tau^*)=v(x) L x ( τ ∗ ) = v ( x ) .
(iv) The value for the empty history is v ( ∞ ) = lim c → ∞ v ( c , … , c ) = inf x v ( x ) v(\infty)=\lim_{c\to\infty}v(c,\ldots,c)=\inf_xv(x) v ( ∞ ) = lim c → ∞ v ( c , … , c ) = inf x v ( x ) . The strategy τ ∗ \tau^* τ ∗ , defined by (14) with Z Z Z the current history (the missing components being ∞ \infty ∞ ), is optimal for the empty history whenever the stopping time is not degenerate at 0, that is, P [ τ ∗ > 0 ] = 1 \mathbb{P}[\tau^*>0]=1 P [ τ ∗ > 0 ] = 1 ; this holds under (9) .
Proof. Step 1 (the contraction estimate). Let w , w ′ w,w' w , w ′ be bounded Borel functions and
δ ( q ) = sup { ∣ w ( y ) − w ′ ( y ) ∣ : y m ≤ q } . (15) \delta(q)=\sup\{|w(y)-w'(y)|:y_m\leq q\}. \tag*{(15)} δ ( q ) = sup { ∣ w ( y ) − w ′ ( y ) ∣ : y m ≤ q } . (15)
For every acceptance set A A A , ∣ P A [ w ] − P A [ w ′ ] ∣ ( r x ) ≤ r x m δ ( r x m ) |P_A[w]-P_A[w']|(rx) \le rx_m\,\delta(rx_m) ∣ P A [ w ] − P A [ w ′ ] ∣ ( r x ) ≤ r x m δ ( r x m ) , and the same holds for P P P since ∣ min { Q , w } − min { Q , w ′ } ∣ ≤ ∣ w − w ′ ∣ |\min\{Q,w\}-\min\{Q,w'\}| \le|w-w'| ∣ min { Q , w } − min { Q , w ′ } ∣ ≤ ∣ w − w ′ ∣ . Hence, by (12) and e − x m ( 1 − r ) ≤ 1 e^{-x_m(1-r)} \le1 e − x m ( 1 − r ) ≤ 1 ,
∣ T A w ( x ) − T A w ′ ( x ) ∣ ∨ ∣ T w ( x ) − T w ′ ( x ) ∣ ≤ ∫ 0 1 x m δ ( r x m ) d r = ∫ 0 x m δ ( q ) d q . (16) |T_Aw(x)-T_Aw'(x)| \vee|Tw(x)-Tw'(x)| \le\int_0^1 x_m\,\delta(rx_m)\,\mathrm{d}r = \int_0^{x_m}\delta(q)\,\mathrm{d}q. \tag*{(16)} ∣ T A w ( x ) − T A w ′ ( x ) ∣ ∨ ∣ T w ( x ) − T w ′ ( x ) ∣ ≤ ∫ 0 1 x m δ ( r x m ) d r = ∫ 0 x m δ ( q ) d q . (16)
If w = T A w w=T_Aw w = T A w and w ′ = T A w ′ w'=T_Aw' w ′ = T A w ′ (or w = T w w=Tw w = T w , w ′ = T w ′ w'=Tw' w ′ = T w ′ ), then δ ( a ) ≤ ∫ 0 a δ ( q ) d q \delta(a) \le\int_0^a\delta(q)\,\mathrm{d}q δ ( a ) ≤ ∫ 0 a δ ( q ) d q for all a a a , with δ \delta δ bounded and nondecreasing, so by iteration δ ( a ) ≤ sup δ ⋅ a n / n ! → 0 \delta(a) \le\sup\delta\cdot a^n/n! \to0 δ ( a ) ≤ sup δ ⋅ a n / n ! → 0 and w = w ′ w=w' w = w ′ . This is the uniqueness of the bounded Borel fixed point of T A T_A T A and of T T T .
Step 2 (iteration). Let w 0 ≡ Q ∞ w_0 \equiv Q_\infty w 0 ≡ Q ∞ , w k + 1 = T w k w_{k+1}=Tw_k w k + 1 = T w k . The operator T T T is monotone, and w 1 ≤ w 0 w_1 \le w_0 w 1 ≤ w 0 , hence w k + 1 ≤ w k w_{k+1} \le w_k w k + 1 ≤ w k , and w k ↓ v ^ w_k \downarrow\hat v w k ↓ v ^ with e − x m Q ∞ ≤ v ^ ≤ Q ∞ e^{-x_m}Q_\infty\le\hat v \le Q_\infty e − x m Q ∞ ≤ v ^ ≤ Q ∞ . Each w k w_k w k is continuous: for bounded continuous w w w the map x ↦ P [ w ] ( x ) x \mapsto P[w](x) x ↦ P [ w ] ( x ) is continuous, because for every ξ ∉ { x 1 , … , x m } \xi\notin\{x_1,\ldots,x_m\} ξ ∈ / { x 1 , … , x m } the integrand and the upper limit of integration depend continuously on x x x , and the integrand is bounded by Q ∞ Q_\infty Q ∞ (by dominated convergence); then T w Tw T w is also continuous by the same token. With δ k ( a ) = sup x m ≤ a ∣ w k + 1 − w k ∣ \delta_k(a)=\sup_{x_m\le a}|w_{k+1}-w_k| δ k ( a ) = sup x m ≤ a ∣ w k + 1 − w k ∣ , (16) gives δ k + 1 ( a ) ≤ ∫ 0 a δ k ( x ) d x \delta_{k+1}(a)\le\int_0^a\delta_k(x)\,\mathrm{d}x δ k + 1 ( a ) ≤ ∫ 0 a δ k ( x ) d x , hence δ k ( a ) ≤ Q ∞ a k / k ! \delta_k(a)\le Q_\infty a^k/k! δ k ( a ) ≤ Q ∞ a k / k ! , so w k → v ^ w_k\to\hat v w k → v ^ uniformly on { x m ≤ a } \{x_m\le a\} { x m ≤ a } for every a a a , v ^ \hat v v ^ is continuous, satisfies v ^ = T v ^ \hat v=T\hat v v ^ = T v ^ by monotone convergence, and v ^ ( 0 ) = Q ∞ \hat v(0)=Q_\infty v ^ ( 0 ) = Q ∞ .
Step 3 (the value of the problem with k k k decision epochs). The decision epochs are the arrivals of low atoms; and the sequence of renewed histories is a Markov chain terminating after finitely many steps (no further low atoms), with the terminal loss Q ∞ Q_\infty Q ∞ . Let R k \mathcal R_k R k be the class of admissible strategies which may select only from the first k k k low atoms. Optimisation over R k \mathcal R_k R k is a finite-horizon problem, solved by backward induction [5 ] : conditionally on the first low atom, by Lemma 2.2 and the Poisson property the future is the problem started at the new state r x ∪ ξ rx\cup\xi r x ∪ ξ , so the value of the k k k -epoch problem is w k = T w k − 1 w_k=Tw_{k-1} w k = T w k − 1 , w 0 = Q ∞ w_0=Q_\infty w 0 = Q ∞ , which are the functions of Step 2. Now let τ \tau τ be an arbitrary strategy and let τ ( k ) ∈ R k \tau^{(k)}\in\mathcal R_k τ ( k ) ∈ R k make the same selection if it is a low atom among the first k k k , and no selection otherwise. Selecting an atom of initial rank above m m m costs at least Q ∞ Q_\infty Q ∞ , so the loss changes only on the event that τ \tau τ selects a later atom, and L x ( τ ( k ) ) ≤ L x ( τ ) + Q ∞ P [ N > k ] L_x(\tau^{(k)})\le L_x(\tau)+Q_\infty\mathbb P[N>k] L x ( τ ( k ) ) ≤ L x ( τ ) + Q ∞ P [ N > k ] . By (10) and w k ≥ v ^ w_k\ge\hat v w k ≥ v ^ ,
L x ( τ ) ≥ w k ( x ) − Q ∞ P [ N > k ] ≥ v ^ ( x ) − Q ∞ P [ N > k ] → v ^ ( x ) , L_x(\tau)\ge w_k(x)-Q_\infty\mathbb P[N>k]\ge\hat v(x)-Q_\infty\mathbb P[N>k]\to\hat v(x), L x ( τ ) ≥ w k ( x ) − Q ∞ P [ N > k ] ≥ v ^ ( x ) − Q ∞ P [ N > k ] → v ^ ( x ) ,
whence v ≥ v ^ v\ge\hat v v ≥ v ^ .
Step 4 (the strategy τ ∗ \tau^* τ ∗ ). Let A ∗ = A v ^ A^*=A_{\hat v} A ∗ = A v ^ be the acceptance set of (14) with v ^ \hat v v ^ in place of v v v , and W ( x ) = L x ( τ ∗ ) ∈ [ 0 , Q ∞ ] W(x)=L_x(\tau^*)\in[0,Q_\infty] W ( x ) = L x ( τ ∗ ) ∈ [ 0 , Q ∞ ] (a selected atom has Q ≤ v ^ ≤ Q ∞ Q\le\hat v\le Q_\infty Q ≤ v ^ ≤ Q ∞ ). The first-arrival decomposition gives W = T A ∗ W W=T_{A^*}W W = T A ∗ W , and v ^ = T v ^ = T A ∗ v ^ \hat v=T\hat v=T_{A^*}\hat v v ^ = T v ^ = T A ∗ v ^ , since the minimum is attained by Q Q Q on A ∗ A^* A ∗ . By the uniqueness in Step 1, W = v ^ W=\hat v W = v ^ . With Step 3, v ^ = W ≥ v ≥ v ^ \hat v=W\ge v\ge\hat v v ^ = W ≥ v ≥ v ^ . Hence v = v ^ v=\hat v v = v ^ , and τ ∗ \tau^* τ ∗ is optimal. This proves (iii), the uniqueness in (ii) for T T T , and v = T v v=Tv v = T v in (i).
Step 5 (the differential form). By Step 2 and v = v ^ v=\hat v v = v ^ , for fixed x x x the function f ( s ) = v ( s x ) f(s)=v(sx) f ( s ) = v ( s x ) satisfies
f ( s ) = e − s x m ( Q ∞ + ∫ 0 s e x m ρ P [ v ] ( ρ x ) ρ − 1 d ρ ) f(s)=e^{-sx_m}\left(Q_\infty+\int_0^s e^{x_m\rho}P[v](\rho x)\rho^{-1}\,\mathrm{d}\rho\right) f ( s ) = e − s x m ( Q ∞ + ∫ 0 s e x m ρ P [ v ] ( ρ x ) ρ − 1 d ρ )
with a continuous integrand bounded by x m Q ∞ e x m ρ x_mQ_\infty e^{x_m\rho} x m Q ∞ e x m ρ , so f ∈ C 1 ( 0 , ∞ ) f\in C^1(0,\infty) f ∈ C 1 ( 0 , ∞ ) and s f ′ ( s ) + s x m f ( s ) = P [ v ] ( s x ) sf'(s)+sx_mf(s)=P[v](sx) s f ′ ( s ) + s x m f ( s ) = P [ v ] ( s x ) , which is (13) at s x sx s x . Conversely, let w w w be as in the second statement of (ii). Then ( e s x m w ( s x ) ) ′ = e s x m P [ w ] ( s x ) / s (e^{sx_m}w(sx))'=e^{sx_m}P[w](sx)/s ( e s x m w ( s x ) ) ′ = e s x m P [ w ] ( s x ) / s , and integrating over [ ε , 1 ] [\varepsilon,1] [ ε , 1 ] and letting ε → 0 \varepsilon\to0 ε → 0 , with w ( ε x ) → Q ∞ w(\varepsilon x)\to Q_\infty w ( ε x ) → Q ∞ , gives w = T w w=Tw w = T w , so w = v w=v w = v by Step 1. The same computation shows that, for a bounded w w w which is continuously differentiable along the rays, w = T w w=Tw w = T w is equivalent to (13) together with w ( s x ) → Q ∞ w(sx)\to Q_\infty w ( s x ) → Q ∞ as s → 0 s\to0 s → 0 .
Step 6 (the empty history). Let t > 0 t>0 t > 0 and let Z t : = t y t Z_t:=t y_t Z t := t y t be the state at time t t t (indexed in this step by the original time) in the problem with the empty initial history; Z t Z_t Z t is a.s. finite and tends to ∞ \infty ∞ as t ↓ 0 t\downarrow0 t ↓ 0 . Conditionally on the information at time t t t the stopping problem is the one with the initial history Z t Z_t Z t (Lemma 2.2 ). By Lemma 2.6 (i), which is proved by coupling and does not depend on the theorem, E v ( Z t ) ↓ v ∞ : = lim c v ( c , … , c ) = inf v \mathbb E v(Z_t)\downarrow v_\infty:=\lim_{c}v(c,\ldots,c)=\inf v E v ( Z t ) ↓ v ∞ := lim c v ( c , … , c ) = inf v as $t\downarrow0. To argue v ( ∞ ) = v ∞ v(\infty)=v_\infty v ( ∞ ) = v ∞ we note first that the strategy which does nothing before t t t and then follows τ ∗ \tau^* τ ∗ has the loss E v ( Z t ) \mathbb{E}v(Z_t) E v ( Z t ) by (iii), so v ( ∞ ) ≤ v ∞ v(\infty)\le v_\infty v ( ∞ ) ≤ v ∞ . Conversely, for every strategy τ \tau τ , conditioning on the information at the time t t t ,
L ∞ ( τ ) ≥ E [ v ( Z t ) 1 { τ > t } ] ≥ E v ( Z t ) − Q ∞ P [ τ ≤ t ] ≥ v ∞ − Q ∞ P [ τ ≤ t ] , L_\infty(\tau)\ge\mathbb{E}\left[v(Z_t)1\{\tau>t\}\right]\ge\mathbb{E}v(Z_t)-Q_\infty\mathbb{P}[\tau\le t]\ge v_\infty-Q_\infty\mathbb{P}[\tau\le t], L ∞ ( τ ) ≥ E [ v ( Z t ) 1 { τ > t } ] ≥ E v ( Z t ) − Q ∞ P [ τ ≤ t ] ≥ v ∞ − Q ∞ P [ τ ≤ t ] ,
and P [ τ ≤ t ] → 0 \mathbb{P}[\tau\le t]\to0 P [ τ ≤ t ] → 0 as t → 0 t\to0 t → 0 , because τ > 0 \tau>0 τ > 0 a.s. So L ∞ ( τ ) ≥ v ∞ L_\infty(\tau)\ge v_\infty L ∞ ( τ ) ≥ v ∞ . This does not use (9) .
Next, we show attainment of the optimum. The strategy τ ∗ \tau^* τ ∗ for the empty history is the first atom satisfying (14) , where the components of the state not yet filled are ∞ \infty ∞ ; after any time t > 0 t>0 t > 0 there are only finitely many low atoms, so acceptable atoms can accumulate only at the time 0. Suppose P [ τ ∗ > 0 ] = 1 \mathbb{P}[\tau^*>0]=1 P [ τ ∗ > 0 ] = 1 , that is, τ ∗ \tau^* τ ∗ is not degenerate at 0. Then τ ∗ \tau^* τ ∗ is a well defined stopping time, and by (iii) applied at the time t t t ,
L ∞ ( τ ∗ ) = E [ Q 1 { τ ∗ ≤ t } ] + E [ v ( Z t ) 1 { τ ∗ > t } ] . L_\infty(\tau^*)=\mathbb{E}\left[Q1\{\tau^*\le t\}\right]+\mathbb{E}\left[v(Z_t)1\{\tau^*>t\}\right]. L ∞ ( τ ∗ ) = E [ Q 1 { τ ∗ ≤ t } ] + E [ v ( Z t ) 1 { τ ∗ > t } ] .
Since P [ τ ∗ ≤ t ] → 0 \mathbb{P}[\tau^*\le t]\to0 P [ τ ∗ ≤ t ] → 0 the dominated convergence gives L ∞ ( τ ∗ ) = v ∞ = v ( ∞ ) L_\infty(\tau^*)=v_\infty=v(\infty) L ∞ ( τ ∗ ) = v ∞ = v ( ∞ ) .
It remains to see that (9) implies P [ τ ∗ > 0 ] = 1 \mathbb{P}[\tau^*>0]=1 P [ τ ∗ > 0 ] = 1 . First, v ( ∞ ) < Q ∞ v(\infty)<Q_\infty v ( ∞ ) < Q ∞ : the strategy which stops at the first atom with score below b b b stops with probability 1 − e − b 1-e^{-b} 1 − e − b at an atom of initial rank 1 with ξ ≤ b \xi\le b ξ ≤ b , so its loss is at most Q ∞ − ( 1 − e − b ) ( Q ∞ − Q ( b , 1 ) ) < Q ∞ Q_\infty-(1-e^{-b})(Q_\infty-Q(b,1))<Q_\infty Q ∞ − ( 1 − e − b ) ( Q ∞ − Q ( b , 1 )) < Q ∞ for small b b b , because Q ( 0 + , 1 ) < Q ∞ Q(0+,1)<Q_\infty Q ( 0 + , 1 ) < Q ∞ . By (9) and v ( c , … , c ) → v ( ∞ ) < Q ∞ v(c,\ldots,c)\to v(\infty)<Q_\infty v ( c , … , c ) → v ( ∞ ) < Q ∞ there is c 0 c_0 c 0 with Q ( ξ , 1 ) > v ( ξ , … , ξ ) Q(\xi,1)>v(\xi,\ldots,\xi) Q ( ξ , 1 ) > v ( ξ , … , ξ ) for all ξ ≥ c 0 \xi\ge c_0 ξ ≥ c 0 . Let s 0 ∈ ( 0 , 1 2 ) s_0\in(0,\frac12) s 0 ∈ ( 0 , 2 1 ) and let E E E be the event that there is no atom with score below 2 c 0 2c_0 2 c 0 before s 0 s_0 s 0 ; P [ E c ] ≤ 2 c 0 s 0 \mathbb{P}[E^c]\le2c_0s_0 P [ E c ] ≤ 2 c 0 s 0 . On E E E every atom before s 0 s_0 s 0 has box coordinate at least c 0 c_0 c 0 , and the state after its arrival is at least ( c 0 , … , c 0 ) (c_0,\ldots,c_0) ( c 0 , … , c 0 ) componentwise, so by Lemma 2.6 (i) v ( state ) ≤ v ( c 0 , … , c 0 ) < Q ( c 0 , 1 ) ≤ Q ( ξ , i ) v(\text{state})\le v(c_0,\ldots,c_0)<Q(c_0,1)\le Q(\xi,i) v ( state ) ≤ v ( c 0 , … , c 0 ) < Q ( c 0 , 1 ) ≤ Q ( ξ , i ) : no atom before s 0 s_0 s 0 is acceptable. Hence P [ τ ∗ ≤ s 0 ] ≤ 2 c 0 s 0 → 0 \mathbb{P}[\tau^*\le s_0]\le2c_0s_0\to0 P [ τ ∗ ≤ s 0 ] ≤ 2 c 0 s 0 → 0 .
Remark 2.5. The boundary condition is essential: the left side of (13) vanishes at 0 regardless of the value there, and the form v = T v v=Tv v = T v has the boundary condition built in, as the term Q ∞ e − x m Q_\infty e^{-x_m} Q ∞ e − x m of no low atom. No smoothness in x x x is needed, only along the rays; in fact v v v is C 1 C^1 C 1 in the interior for m = 2 m=2 m = 2 (Proposition 4.6 ). The strategy τ ∗ \tau^* τ ∗ may terminate without selection. Condition (9) is needed only for the attainment of the value v ( ∞ ) v(\infty) v ( ∞ ) for the empty history, to exclude acceptance of the rank-1 atoms with huge scores, which accumulate at t = 0 t=0 t = 0 ; the value itself is lim c v ( c , … , c ) \lim_{c}v(c,\ldots,c) lim c v ( c , … , c ) without it. Without (9) the value need not be attained: for m = 1 m=1 m = 1 , Q ( ξ , i ) = 1 { i ≥ 2 } Q(\xi,i)=1\{i\ge2\} Q ( ξ , i ) = 1 { i ≥ 2 } and Q ∞ = 1 Q_\infty=1 Q ∞ = 1 we have v ( ∞ ) = 0 v(\infty)=0 v ( ∞ ) = 0 (wait until time s 0 s_0 s 0 and accept the next record, which is missed with probability s 0 s_0 s 0 ) but no strategy achieves this; here every record is acceptable and τ ∗ \tau^* τ ∗ is degenerate at 0.
Monotonicity of the value function is shown next.
Lemma 2.6. (i) For every adapted loss structure Q Q Q as above, v v v is nonincreasing in every component: if x ′ ≤ x x'\le x x ′ ≤ x componentwise, then v ( x ) ≤ v ( x ′ ) v(x)\le v(x') v ( x ) ≤ v ( x ′ ) , where some of the components of x x x may be ∞ \infty ∞ .
(ii) For the losses (6) , (7) , v v v is strictly decreasing in every component x 1 , … , x m x_1,\ldots,x_m x 1 , … , x m , and
v ( ∞ ) < v ( x ) < v ( 0 ) = Q ∞ ( x ∈ S , x ≠ 0 ) . v(\infty)<v(x)<v(0)=Q_\infty\qquad(x\in S,\ x\ne0). v ( ∞ ) < v ( x ) < v ( 0 ) = Q ∞ ( x ∈ S , x = 0 ) . (iii) v ( x ) → v ( ∞ ) v(x)\to v(\infty) v ( x ) → v ( ∞ ) as x 1 → ∞ x_1\to\infty x 1 → ∞ .
Proof. (i) Let τ ′ \tau' τ ′ be a strategy in the problem with the history x ′ x' x ′ . It is a function of the future atoms and of x ′ x' x ′ , so it can be applied with the history x x x . For every realisation the initial rank of the selected atom is not larger under x x x than under x ′ x' x ′ , and Q Q Q is nondecreasing in the rank, so L x ( τ ′ ) ≤ L x ′ ( τ ′ ) L_x(\tau')\le L_{x'}(\tau') L x ( τ ′ ) ≤ L x ′ ( τ ′ ) ; taking the infimum over τ ′ \tau' τ ′ gives v ( x ) ≤ v ( x ′ ) v(x)\le v(x') v ( x ) ≤ v ( x ′ ) . This proof does not use Theorem 2.4 , which uses (i) in Step 6. (ii) For x ≠ 0 x \ne0 x = 0 we have x m > 0 x_m > 0 x m > 0 and v ( x ) < Q ∞ v(x) < Q_\infty v ( x ) < Q ∞ : the strategy which accepts the first low atom with box coordinate below ε \varepsilon ε stops with positive probability, at an atom of initial rank at most m m m , and its loss is then at most Q ( ε , m ) < Q ∞ Q(\varepsilon,m) < Q_\infty Q ( ε , m ) < Q ∞ for small ε \varepsilon ε .
For the strict inequalities let x ′ ≤ x x' \le x x ′ ≤ x componentwise and x ′ ≠ x x' \ne x x ′ = x , where x ′ ∈ S x' \in S x ′ ∈ S and either x ∈ S x \in S x ∈ S or x = ∞ x = \infty x = ∞ ; we show that v ( x ) < v ( x ′ ) v(x) < v(x') v ( x ) < v ( x ′ ) . Let τ ′ \tau' τ ′ be the strategy τ ∗ \tau^* τ ∗ of Theorem 2.4 (iii) for the history x ′ x' x ′ ; it selects only low atoms, that is, atoms of initial rank at most m m m under x ′ x' x ′ . Since τ ′ \tau' τ ′ is a function of the future atoms and of x ′ x' x ′ , it can be applied with the history x x x , and by the coupling of (i), L x ( τ ′ ) ≤ L x ′ ( τ ′ ) L_x(\tau') \le L_{x'}(\tau') L x ( τ ′ ) ≤ L x ′ ( τ ′ ) . Suppose that v ( x ) = v ( x ′ ) v(x) = v(x') v ( x ) = v ( x ′ ) . Then
L x ( τ ′ ) ≥ v ( x ) = v ( x ′ ) = L x ′ ( τ ′ ) ≥ L x ( τ ′ ) , L_x(\tau') \ge v(x) = v(x') = L_{x'}(\tau') \ge L_x(\tau'), L x ( τ ′ ) ≥ v ( x ) = v ( x ′ ) = L x ′ ( τ ′ ) ≥ L x ( τ ′ ) ,
so τ ′ \tau' τ ′ is optimal for x x x as well, and the two losses coincide. (In general, it is not true that a strategy loses strictly when a component is lowered: a strategy which stops at the first atom with score below ε < x 1 ′ \varepsilon< x'_1 ε < x 1 ′ has the same loss under both histories. So the optimality of τ ′ \tau' τ ′ has to be used.)
Let j j j be an index with x j ′ < x j x'_j < x_j x j ′ < x j (j = 1 j = 1 j = 1 if x = ∞ x = \infty x = ∞ ), let c : = x m c := x_m c := x m if x ∈ S x \in S x ∈ S and let c > x m ′ c > x'_m c > x m ′ be a finite level if x = ∞ x = \infty x = ∞ , and a : = min ( x j , c ) > x j ′ a := \min(x_j,c) > x'_j a := min ( x j , c ) > x j ′ . Fix δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , to be chosen below, and let F F F be the event that Π \Pi Π has no atom with score below c c c in [ 0 , 1 − δ ] [0,1-\delta] [ 0 , 1 − δ ] , and that the first atom with score below c c c in ( 1 − δ , 1 ] (1-\delta,1] ( 1 − δ , 1 ] has a score z ∈ ( x j ′ , a ) z \in(x'_j,a) z ∈ ( x j ′ , a ) . Then P [ F ] > 0 \mathbb{P}[F] > 0 P [ F ] > 0 , and on F F F the strategy τ ′ \tau' τ ′ has not stopped before this atom, since an atom selected by τ ′ \tau' τ ′ has score below x m ′ ≤ c x'_m \le c x m ′ ≤ c . Let i < i ′ i < i' i < i ′ be the initial ranks of the atom under x x x and under x ′ x' x ′ (the rank is larger under x ′ x' x ′ because x j ′ < z < x j x'_j < z < x_j x j ′ < z < x j ), so that i ′ ≤ m i' \le m i ′ ≤ m if τ ′ \tau' τ ′ selects the atom, and i ≤ j ≤ m i \le j \le m i ≤ j ≤ m ; let ξ ≤ δ c \xi\le\delta c ξ ≤ δ c be the box coordinate of the atom. We have the following dichotomy.
(a) If τ ′ \tau' τ ′ selects the atom with positive probability on F F F , then Q ( ξ , i ) < Q ( ξ , i ′ ) Q(\xi,i) < Q(\xi,i') Q ( ξ , i ) < Q ( ξ , i ′ ) since Q Q Q is strictly increasing in the rank for ranks up to m m m . The loss under x x x is then smaller on a set of positive probability and not larger elsewhere, so L x ( τ ′ ) < L x ′ ( τ ′ ) L_x(\tau') < L_{x'}(\tau') L x ( τ ′ ) < L x ′ ( τ ′ ) , which is a contradiction.
(b) Otherwise τ ′ \tau' τ ′ rejects the atom a.s. on F F F . We show that selecting the atom is strictly better under x x x than continuing optimally, for small δ \delta δ . If x ∈ S x \in S x ∈ S , the loss of selection is at most Q ( δ c , m ) → Q ( 0 , m ) < Q ∞ Q(\delta c,m) \to Q(0,m) < Q_\infty Q ( δ c , m ) → Q ( 0 , m ) < Q ∞ as δ → 0 \delta\to0 δ → 0 (Q ( 0 , m ) Q(0,m) Q ( 0 , m ) is m m m in A m A_m A m and 0 0 0 in B m B_m B m ). After the arrival all components of the state in box coordinates are at most δ c \delta c δ c , so by (i) and continuity of v v v at 0 0 0 the continuation value is at least v ( δ c , … , δ c ) → Q ∞ v(\delta c,\ldots,\delta c) \to Q_\infty v ( δ c , … , δ c ) → Q ∞ . If x = ∞ x = \infty x = ∞ , then i = 1 i = 1 i = 1 , the loss of selection is at most Q ( δ c , 1 ) → Q ( 0 , 1 ) Q(\delta c,1) \to Q(0,1) Q ( δ c , 1 ) → Q ( 0 , 1 ) , and the continuation value is at least v ( ∞ ) v(\infty) v ( ∞ ) by (i). Here v ( ∞ ) > Q ( 0 , 1 ) v(\infty) > Q(0,1) v ( ∞ ) > Q ( 0 , 1 ) : by Theorem 2.4 (iv) the value is attained by an optimal strategy, which loses at least Q ( ξ , 1 ) > Q ( 0 , 1 ) Q(\xi,1) > Q(0,1) Q ( ξ , 1 ) > Q ( 0 , 1 ) when it selects an atom of level ξ > 0 \xi> 0 ξ > 0 , and Q ∞ > Q ( 0 , 1 ) Q_\infty> Q(0,1) Q ∞ > Q ( 0 , 1 ) when it selects nothing. Modifying τ ′ \tau' τ ′ to select the atom on F F F (an event determined at the arrival of the atom) lowers the expected loss under x x x , so τ ′ \tau' τ ′ is not optimal for x x x , again a contradiction.
Hence v ( x ) < v ( x ′ ) v(x) < v(x') v ( x ) < v ( x ′ ) .
(iii) Since x ≥ ( x 1 , … , x 1 ) x \ge(x_1,\ldots,x_1) x ≥ ( x 1 , … , x 1 ) , part (i) and Theorem 2.4 (iv) give v ( ∞ ) ≤ v ( x ) ≤ v ( x 1 , … , x 1 ) → v ( ∞ ) v(\infty) \le v(x) \le v(x_1,\ldots,x_1) \to v(\infty) v ( ∞ ) ≤ v ( x ) ≤ v ( x 1 , … , x 1 ) → v ( ∞ ) as x 1 → ∞ x_1 \to\infty x 1 → ∞ . □ \square □
The adaptive threshold
Suppose that at time t t t the history in the original coordinates is y y y . By Lemma 2.2 and Theorem 2.4 , an atom ( t , x ) (t,x) ( t , x ) with initial rank i = i ( y , x ) i=i(y,x) i = i ( y , x ) is acceptable for the optimal strategy if and only if
Q ( x ˉ , i ) ≤ v ( t ˉ ( y ∪ x ) ) . (17) Q(\bar{x},i) \le v(\bar{t}(y \cup x)). \tag*{(17)} Q ( x ˉ , i ) ≤ v ( t ˉ ( y ∪ x )) . (17)
Let H ( t , y ) H(t,y) H ( t , y ) be the supremum of the scores x x x satisfying (17) ; this is a deterministic function of t t t and y y y .
We now define the random adaptive threshold process ( H t , t ∈ [ 0 , 1 ) ) (H_t,\ t \in[0,1)) ( H t , t ∈ [ 0 , 1 )) on the whole unit interval. Starting from the initial history y 0 \mathbf{y}_0 y 0 (which may be empty), consider the reduced history updated only by the atoms arriving after time 0 0 0 above the threshold: the arrivals below the threshold are acceptable, but they are ignored in the definition. Denoting y t ∘ \mathbf{y}^{\circ}_t y t ∘ the history so obtained, we define
H t : = H ( t , y t ∘ ) , C t : = v ( t ˉ y t ∘ ) . H_t := H(t,\mathbf{y}^{\circ}_t),\qquad C_t := v(\bar{t}\mathbf{y}^{\circ}_t). H t := H ( t , y t ∘ ) , C t := v ( t ˉ y t ∘ ) .
Thus C t C_t C t is the minimal expected loss to go from time t t t for the history y t ∘ \mathbf{y}^{\circ}_t y t ∘ , whose entries are scores of the initial history or of atoms which were unacceptable at arrival, i.e. the continuation value given that no acceptable atom has arrived; up to time τ \tau τ this is the actual continuation value. The process ( H t ) (H_t) ( H t ) is adapted to the arrivals of the PPP above the threshold itself, and the optimal strategy stops at the first atom below the threshold,
τ = inf { t > 0 : Π ∩ { ( t , x ) : x < H t } ≠ ∅ } \tau= \inf\{t>0:\Pi\cap\{(t,x):x<H_t\}\ne\varnothing\} τ = inf { t > 0 : Π ∩ {( t , x ) : x < H t } = ∅ }
(τ = 1 \tau=1 τ = 1 if no such t t t ). Up to time τ \tau τ the history y t ∘ \mathbf{y}^{\circ}_t y t ∘ is the actual history. After τ \tau τ the process ( H t ) (H_t) ( H t ) is a formal continuation, which is convenient since it lives on the whole interval, and is the analogue of the memoryless rules, which stop at the first atom below a nonrandom precommitted threshold.
Proposition 2.7. (i) The set of scores x x x satisfying (17) is an interval [ 0 , H t ) [0,H_t) [ 0 , H t ) (possibly with the right endpoint).
(ii) Along every path of the PPP the continuation value C t C_t C t is nondecreasing in t t t ; in particular C t ≥ C 0 = v ( y 0 ) C_t\ge C_0=v(\mathbf{y}_0) C t ≥ C 0 = v ( y 0 ) , which is v ( ∞ ) v(\infty) v ( ∞ ) for the empty initial history.
(iii) The threshold H t H_t H t is nondecreasing in t t t : between arrivals it is continuous and either increases or is flat, and at an arrival of an atom above the threshold it either does not change or jumps up.
(iv) If H t H_t H t reaches a past score y i ∘ y_i^\circ y i ∘ , either continuously or by a jump at an arrival (then y i ∘ y_i^\circ y i ∘ may be the score of the arriving atom), it stays flat at y i ∘ y_i^\circ y i ∘ for a positive time, almost surely.
Proof. Write Φ t ( x ) : = Q ( t ˉ x , i ) − v ( t ˉ ( y t ∘ ∪ x ) ) \Phi_t(x):=Q(\bar{t}x,i)-v(\bar{t}(\mathbf{y}^{\circ}_t\cup x)) Φ t ( x ) := Q ( t ˉ x , i ) − v ( t ˉ ( y t ∘ ∪ x )) with i = i ( y t ∘ , x ) i=i(\mathbf{y}^{\circ}_t,x) i = i ( y t ∘ , x ) , so that x x x is acceptable if and only if Φ t ( x ) ≤ 0 \Phi_t(x)\le0 Φ t ( x ) ≤ 0 .
(i) Let z < x z<x z < x and suppose that x x x satisfies (17) . Then i ( y t ∘ , z ) ≤ i ( y t ∘ , x ) i(\mathbf{y}^{\circ}_t,z)\le i(\mathbf{y}^{\circ}_t,x) i ( y t ∘ , z ) ≤ i ( y t ∘ , x ) , t ˉ z < t ˉ x \bar{t}z<\bar{t}x t ˉ z < t ˉ x , and Q Q Q is nondecreasing in i i i and in the level; also y t ∘ ∪ z ≤ y t ∘ ∪ x \mathbf{y}^{\circ}_t\cup z\le\mathbf{y}^{\circ}_t\cup x y t ∘ ∪ z ≤ y t ∘ ∪ x componentwise, so by Lemma 2.6 v ( t ˉ ( y t ∘ ∪ z ) ) ≥ v ( t ˉ ( y t ∘ ∪ x ) ) v(\bar{t}(\mathbf{y}^{\circ}_t\cup z))\ge v(\bar{t}(\mathbf{y}^{\circ}_t\cup x)) v ( t ˉ ( y t ∘ ∪ z )) ≥ v ( t ˉ ( y t ∘ ∪ x )) , thus z z z satisfies (17) too.
(ii) Between arrivals above the threshold the reduced history y t ∘ \mathbf{y}^{\circ}_t y t ∘ is fixed and t ˉ \bar{t} t ˉ decreases, so t ˉ y t ∘ \bar{t}\mathbf{y}^{\circ}_t t ˉ y t ∘ decreases componentwise and C t = v ( t ˉ y t ∘ ) C_t=v(\bar{t}\mathbf{y}^{\circ}_t) C t = v ( t ˉ y t ∘ ) does not decrease by Lemma 2.6 . When an atom above the threshold arrives at time t t t , the new history y t ∘ \mathbf{y}^{\circ}_t y t ∘ consists of the m m m lowest scores among y t − ∘ \mathbf{y}^{\circ}_{t-} y t − ∘ and the new score, so y t ∘ ≤ y t − ∘ \mathbf{y}^{\circ}_t\le\mathbf{y}^{\circ}_{t-} y t ∘ ≤ y t − ∘ and C t C_t C t jumps up (or does not change, if the new score is above the m m m -th lowest score of y t − ∘ \mathbf{y}^{\circ}_{t-} y t − ∘ ).
(iii) Between arrivals the history y t ∘ \mathbf{y}^{\circ}_t y t ∘ and the ranks i ( y t ∘ , x ) i(\mathbf{y}^{\circ}_t,x) i ( y t ∘ , x ) are fixed, and Φ t ( x ) \Phi_t(x) Φ t ( x ) is continuous and strictly decreasing in t t t , since Q Q Q is increasing in the level t ˉ x \bar{t}x t ˉ x , which decreases, and v v v increases when the arguments decrease. Hence the set of acceptable scores grows with t t t , which means that H t H_t H t is nondecreasing; it moves continuously, since for the conditions (6) , (7) the function Φ t ( x ) \Phi_t(x) Φ t ( x ) is jointly continuous in ( t , x ) (t,x) ( t , x ) and strictly increasing in x x x between consecutive past scores, and jumps up at the past scores.
At an arrival of an atom at time t t t with the score x 0 ≥ H t − x_0\ge H_{t-} x 0 ≥ H t − (the arrivals below the threshold are ignored) the reduced history changes from y t − ∘ \mathbf{y}^{\circ}_{t-} y t − ∘ to y t ∘ \mathbf{y}^{\circ}_t y t ∘ , the m m m lowest among y t − ∘ \mathbf{y}^{\circ}_{t-} y t − ∘ and x 0 x_0 x 0 ; this is no change if x 0 x_0 x 0 is above the m m m -th lowest score of y t − ∘ \mathbf{y}^{\circ}_{t-} y t − ∘ . Let z < H t − z<H_{t-} z < H t − . Since x 0 > z x_0>z x 0 > z , the initial rank of z z z is the same under y t − ∘ \mathbf{y}^{\circ}_{t-} y t − ∘ and y t ∘ \mathbf{y}^{\circ}_t y t ∘ , while y t ∘ ∪ z ≤ y t − ∘ ∪ z \mathbf{y}^{\circ}_t\cup z\le\mathbf{y}^{\circ}_{t-}\cup z y t ∘ ∪ z ≤ y t − ∘ ∪ z , so v ( t ˉ ( y t ∘ ∪ z ) ) ≥ v ( t ˉ ( y t − ∘ ∪ z ) ) v(\bar{t}(\mathbf{y}^{\circ}_t\cup z))\ge v(\bar{t}(\mathbf{y}^{\circ}_{t-}\cup z)) v ( t ˉ ( y t ∘ ∪ z )) ≥ v ( t ˉ ( y t − ∘ ∪ z )) and Φ ( z ) \Phi(z) Φ ( z ) does not increase. Thus every z < H t − z<H_{t-} z < H t − remains acceptable, so H H H does not decrease. Here it is essential that the arrivals below the threshold are ignored, since such an arrival would raise the rank of the higher scores and lower H t H_t H t .
(iv) Suppose that H t = y i ∘ H_t=y_i^\circ H t = y i ∘ at some time t t t , where the scores below y i ∘ y_i^\circ y i ∘ are acceptable and those above are not. Compare the adapted loss at the levels y i ∘ − y_i^\circ- y i ∘ − and y i ∘ + y_i^\circ+ y i ∘ + : the initial rank is i i i below and i + 1 i+1 i + 1 above, so the loss jumps up by Δ i ( ξ ) > 0 \Delta_i(\xi)>0 Δ i ( ξ ) > 0 , which is 1 1 1 in A m A_m A m and e − ξ ξ m − i / ( m − i ) ! e^{-\xi}\xi^{m-i}/(m-i)! e − ξ ξ m − i / ( m − i )! in B m B_m B m for i ≤ m i\le m i ≤ m , whereas the continuation value is continuous in x x x . Thus the acceptable set ends at y i ∘ y_i^\circ y i ∘ whenever Q ( t ˉ y i ∘ , i ) ≤ v < Q ( t ˉ y i ∘ , i + 1 ) Q(\bar{t}y_i^\circ,i)\le v<Q(\bar{t}y_i^\circ,i+1) Q ( t ˉ y i ∘ , i ) ≤ v < Q ( t ˉ y i ∘ , i + 1 ) , with v v v the continuation value at x = y i ∘ x=y_i^\circ x = y i ∘ . If H H H reaches y i ∘ y_i^\circ y i ∘ continuously, then Q ( t ˉ y i ∘ , i ) = v Q(\bar{t}y_i^\circ,i)=v Q ( t ˉ y i ∘ , i ) = v at the time of arrival, so the second inequality holds with the margin Δ i \Delta_i Δ i . If H H H lands on y i ∘ y_i^\circ y i ∘ by a jump, at the arrival of an atom ( t , x 0 ) (t,x_0) ( t , x 0 ) , the second inequality holds strictly, except in the borderline case Q ( t ˉ y i ∘ , i + 1 ) = v Q(\bar{t}y_i^\circ,i+1)=v Q ( t ˉ y i ∘ , i + 1 ) = v , in which H H H would leave y i ∘ y_i^\circ y i ∘ at once. The borderline case has probability zero: between consecutive arrivals, for a fixed score x 0 x_0 x 0 the difference Q ( t ˉ y i ∘ , i + 1 ) − v Q(\bar{t}y_i^\circ,i+1)-v Q ( t ˉ y i ∘ , i + 1 ) − v is strictly decreasing in t t t , because Q ( ⋅ , i + 1 ) Q(\mathord{\cdot},i+1) Q ( ⋅ , i + 1 ) is strictly increasing in the level for i + 1 ≤ m i+1\le m i + 1 ≤ m and v v v does not decrease in t t t by Lemma 2.6 (i) (for i = m i=m i = m there is no borderline case, since Q ( ⋅ , m + 1 ) ≥ Q ∞ > v Q(\mathord{\cdot},m+1)\ge Q_\infty>v Q ( ⋅ , m + 1 ) ≥ Q ∞ > v ), so it vanishes at most once; the pairs ( t , x 0 ) (t,x_0) ( t , x 0 ) of this kind form a Lebesgue null set, and by the compensator formula the expected number of atoms of Π \Pi Π in it is zero. Between arrivals Q ( t ˉ y i ∘ , i + 1 ) − v Q(\bar{t}y_i^\circ,i+1)-v Q ( t ˉ y i ∘ , i + 1 ) − v decreases continuously in t t t , hence the inequality persists, and H H H stays flat at y i ∘ y_i^\circ y i ∘ , during a positive time interval.
Thus if the threshold is not in a flat stretch, it drifts smoothly between arrivals in a manner determined by the frozen history, and jumps up when an atom arrives above it and lowers the history. A jump takes the threshold up to a level where the loss of acceptance and the continuation value balance, or to a past score, and in the latter case the threshold stays there by (iv). Since the loss above a past score is higher by a jump, we do not expect the threshold to be carried across the score of the arriving atom; for A m A_m A m this is Lemma 2.8 below, which rests on the linearity of the loss, below truncation, in the rank; for B 2 B_2 B 2 this is verified in § 4 . For m = 1 m=1 m = 1 the drift follows a hyperbola up to the lowest score and is frozen afterwards, but for m ≥ 2 m\ge2 m ≥ 2 the stopping boundary in box coordinates depends on the state, which itself shrinks in time between history updates. Every time the threshold reaches a past score (either by drift or a jump) it stays flat there, as the loss jumps above the atom. In words, (ii) says that if no atom has been accepted up to time t t t , then the prospects of the observer can only have worsened.
Lemma 2.8. In A m A_m A m , for every state x ∈ S x\in S x ∈ S and every ξ < x m \xi<x_m ξ < x m ,
v ( x ∪ ξ ) ≤ v ( x ) + 1. v(x\cup\xi)\le v(x)+1. v ( x ∪ ξ ) ≤ v ( x ) + 1.
Consequently, when a low atom ( t , x 0 ) (t,x_0) ( t , x 0 ) which is not acceptable arrives, no score above x 0 x_0 x 0 is acceptable after the arrival: the threshold is not carried across x 0 x_0 x 0 .
Proof. Let τ \tau τ be a strategy in the problem with the history x x x , and apply it with the history x ∪ ξ x\cup\xi x ∪ ξ , as in the proof of Lemma 2.6 (i). Compared with the levels x 1 , … , x m x_1,\ldots,x_m x 1 , … , x m , the m + 1 m+1 m + 1 levels x 1 , … , x m , ξ x_1,\ldots,x_m,\xi x 1 , … , x m , ξ raise the initial rank i i i of every atom by at most one; removing the largest of them, x m x_m x m , changes only the ranks which exceed m m m , so it does not change min ( i , m + 1 ) \min(i,m+1) min ( i , m + 1 ) . Hence the loss (6) of the selected atom is larger by at most 1 under x ∪ ξ x\cup\xi x ∪ ξ , the loss with no selection is the same, and L x ∪ ξ ( τ ) ≤ L x ( τ ) + 1 L_{x\cup\xi}(\tau)\le L_x(\tau)+1 L x ∪ ξ ( τ ) ≤ L x ( τ ) + 1 . Taking the infimum over τ \tau τ gives the inequality.
Let y y y be the history just before the arrival of ( t , x 0 ) (t,x_0) ( t , x 0 ) , let i 0 = i ( y , x 0 ) i_0=i(y,x_0) i 0 = i ( y , x 0 ) be the initial rank of the atom and y ′ = y ∪ x 0 y'=y\cup x_0 y ′ = y ∪ x 0 the history after the arrival. The atom is not acceptable, that is, Q ( t ˉ x 0 , i 0 ) > v ( t ˉ y ′ ) Q(\bar{t}x_0,i_0)>v(\bar{t}y') Q ( t ˉ x 0 , i 0 ) > v ( t ˉ y ′ ) . A score z ≥ y m ′ z\ge y'_m z ≥ y m ′ is not low, hence not acceptable. For x 0 < z < y m ′ x_0<z<y'_m x 0 < z < y m ′ the initial rank of z z z under y ′ y' y ′ is at least i 0 + 1 ≤ m i_0+1\le m i 0 + 1 ≤ m , so by the monotonicity of Q Q Q and the first part of the proof
Q ( t ˉ z , i ( y ′ , z ) ) ≥ Q ( t ˉ x 0 , i 0 ) + 1 > v ( t ˉ y ′ ) + 1 ≥ v ( t ˉ ( y ′ ∪ z ) ) , Q(\bar{t}z,i(y',z))\ge Q(\bar{t}x_0,i_0)+1>v(\bar{t}y')+1\ge v(\bar{t}(y'\cup z)), Q ( t ˉ z , i ( y ′ , z )) ≥ Q ( t ˉ x 0 , i 0 ) + 1 > v ( t ˉ y ′ ) + 1 ≥ v ( t ˉ ( y ′ ∪ z )) ,
and z z z does not satisfy (17) .
One tracked score: m = 1 m=1 m = 1
For m = 1 m=1 m = 1 only records can be accepted, and the state is a single number: the box coordinate ξ \xi ξ of the lowest score Y Y Y observed so far. In the original coordinates we call ( t , 1 ] × ( 0 , Y ) (t,1] \times(0,Y) ( t , 1 ] × ( 0 , Y ) the south-east window of the current record. The area is ξ = t Y ˉ \xi=t\bar{Y} ξ = t Y ˉ ; the new records can only arrive into this window, other arrivals being of no interest. The area decreases with time, and by the first arrival into the window it is replaced by the smaller window below the record.
A hyperbolic threshold
Suppose a record arrives with box coordinate ξ \xi ξ . If it is accepted, the loss is Q ( ξ , 1 ) Q(\xi,1) Q ( ξ , 1 ) , which is increasing in ξ \xi ξ . If it is continued, the state becomes ξ \xi ξ , and the future loss is the continuation value v ( ξ ) v(\xi) v ( ξ ) , which is decreasing in ξ \xi ξ by Lemma 2.6 . Therefore
{ ξ : Q ( ξ , 1 ) ≤ v ( ξ ) } = ( 0 , b ] \{\xi: Q(\xi,1) \le v(\xi)\}=(0,b] { ξ : Q ( ξ , 1 ) ≤ v ( ξ )} = ( 0 , b ]
for some b > 0 b>0 b > 0 : the optimal strategy stops at the first record ( t , x ) (t,x) ( t , x ) with t x ˉ ≤ b t\bar{x}\le b t x ˉ ≤ b , that is, at the first record below the hyperbola h ( t ) = b / t ˉ h(t)=b/\bar{t} h ( t ) = b / t ˉ . We call this strategy R b \mathrm{R}_b R b , and the problem is reduced to optimisation over b b b . In the original PPP coordinates the adaptive threshold is H t = min ( Y , b / t ˉ ) H_t=\min(Y,b/\bar{t}) H t = min ( Y , b / t ˉ ) , where Y Y Y is the lowest score of the reduced history (up to the time τ \tau τ , the lowest score observed); it drifts along the hyperbola until it meets Y Y Y , where it stays frozen.
The south-west window and the loss of R b \mathrm{R}_b R b
Let h ( t ) = b / t ˉ h(t)=b/\bar{t} h ( t ) = b / t ˉ . Consider the south-west window
W t = ( 0 , t ) × ( 0 , h ( t ) ) , W_t=(0,t)\times(0,h(t)), W t = ( 0 , t ) × ( 0 , h ( t )) ,
Figure 1. A realisation of Π \Pi Π with the hyperbola x = b / t ˉ x=b/\bar{t} x = b / t ˉ , b = 0.6176 b=0.6176 b = 0.6176 , the optimal threshold in problem A1. The atom at ( 0.42 , 1.22 ) (0.42,1.22) ( 0.42 , 1.22 ) arrives above the curve; the curve passes its level at t = 0.49 t=0.49 t = 0.49 , so the window meets this atom through its upper side. The first record below the curve afterwards (circled, t = 0.557 t=0.557 t = 0.557 ) is selected. Shaded: the south-west window with the apex on the hyperbola at the time of selection; the selected atom is on its right side.
with the apex ( t , h ( t ) ) (t,h(t)) ( t , h ( t )) on the hyperbola, and let the apex slide along the hyperbola, so that its time coordinate moves at unit speed. The window grows, its area is ∣ W t ∣ = t h ( t ) = b t / t ˉ |W_t|=t h(t)=bt/\bar{t} ∣ W t ∣ = t h ( t ) = b t / t ˉ , and the new area is swept by two sides: the right side, of length h ( t ) h(t) h ( t ) , and the upper side, of length t t t , rising at the speed h ′ ( t ) h'(t) h ′ ( t ) . The atoms of Π \Pi Π are met by the window according to a Poisson process in t t t , with the intensity h ( t ) + t h ′ ( t ) = d ∣ W t ∣ / d t h(t)+th'(t)=\mathrm{d}|W_t|/\mathrm{d}t h ( t ) + t h ′ ( t ) = d ∣ W t ∣/ d t , which splits in the rates h ( t ) h(t) h ( t ) for the right side and t h ′ ( t ) th'(t) t h ′ ( t ) for the upper side. The probability that no atom is met before time t t t is e − b t / t ˉ e^{-bt/\bar{t}} e − b t / t ˉ . To assess the rule we need to consider two cases.
(right) The first atom is met by the right side at time t t t : this is an atom ( t , x ) (t,x) ( t , x ) with x x x uniform on ( 0 , h ( t ) ) (0,h(t)) ( 0 , h ( t )) . Since the window was empty at time 0, this is a record below the hyperbola, so the strategy R b R_b R b stops with the box coordinate t ˉ x \bar{t}x t ˉ x uniform on ( 0 , b ) (0,b) ( 0 , b ) , and the expected loss is
g ˉ ( b ) : = 1 b ∫ 0 b Q ( u , 1 ) d u . \bar{g}(b):=\frac{1}{b}\int_0^b Q(u,1)\,\mathrm{d}u. g ˉ ( b ) := b 1 ∫ 0 b Q ( u , 1 ) d u .
(upper) The first atom is met by the upper side at time t t t : this is an earlier atom ( s , h ( t ) ) (s,h(t)) ( s , h ( t )) , s < t s<t s < t , located above the hyperbola at the time s s s of its arrival and was not accepted. The scores observed before t t t are all above h ( t ) h(t) h ( t ) , so it is the lowest so far, and its south-east window has the area t h ˉ ( t ) = b t\bar{h}(t)=b t h ˉ ( t ) = b . From time t t t the strategy selects greedily the next record (if any), as records fall into the window below the hyperbola. The expected loss of this future action is G ( b ) G(b) G ( b ) computed below.
The probabilities of the two cases are
P [ r i g h t ] = ∫ 0 1 e − b t / t ˉ b t ˉ d t = b e b J 1 ( b ) , P [ u p p e r ] = ∫ 0 1 e − b t / t ˉ b t t ˉ 2 d t = 1 − b e b J 1 ( b ) , \mathbb{P}[\mathrm{right}]=\int_0^1 e^{-bt/\bar{t}}\frac{b}{\bar{t}}\,\mathrm{d}t=be^bJ_1(b),\qquad\mathbb{P}[\mathrm{upper}]=\int_0^1 e^{-bt/\bar{t}}\frac{bt}{\bar{t}^2}\,\mathrm{d}t=1-be^bJ_1(b), P [ right ] = ∫ 0 1 e − b t / t ˉ t ˉ b d t = b e b J 1 ( b ) , P [ upper ] = ∫ 0 1 e − b t / t ˉ t ˉ 2 b t d t = 1 − b e b J 1 ( b ) ,
where J 1 ( b ) : = ∫ b ∞ e − s s − 1 d s J_1(b):=\int_b^\infty e^{-s}s^{-1}\,\mathrm{d}s J 1 ( b ) := ∫ b ∞ e − s s − 1 d s is the exponential integral function.
The greedy phase. Suppose the state is ξ \xi ξ , that is, at time 0 the lowest score is ξ \xi ξ and the south-east window ( 0 , 1 ] × ( 0 , ξ ) (0,1]\times(0,\xi) ( 0 , 1 ] × ( 0 , ξ ) has the area ξ \xi ξ . With probability e − ξ e^{-\xi} e − ξ the window contains no atoms. Otherwise the first atom arrives at time s ∈ ( 0 , 1 ) s \in(0,1) s ∈ ( 0 , 1 ) with exponential density ξ e − ξ s \xi e^{-\xi s} ξ e − ξ s , it is then a record with the score ξ u \xi u ξ u , where u u u is sampled independently from U [ 0 , 1 ] U[0,1] U [ 0 , 1 ] , and the new state becomes ξ ( 1 − s ) u \xi(1-s)u ξ ( 1 − s ) u . It follows that
G ( ξ ) = Q ∞ e − ξ + ∫ 0 ξ e y − ξ g ˉ ( y ) d y , equivalently G ′ + G = g ˉ , G ( 0 ) = Q ∞ . (18) G(\xi)=Q_{\infty}e^{-\xi}+\int_{0}^{\xi}e^{y-\xi}\bar{g}(y)\,dy,\qquad\text{equivalently}\qquad G'+G=\bar{g},\quad G(0)=Q_{\infty}. \tag*{(18)} G ( ξ ) = Q ∞ e − ξ + ∫ 0 ξ e y − ξ g ˉ ( y ) d y , equivalently G ′ + G = g ˉ , G ( 0 ) = Q ∞ . (18)
For A 1 A_1 A 1 and B 1 B_1 B 1 , with J 2 ( ξ ) : = ∫ 0 ξ ( e s − 1 ) s − 1 d s J_2(\xi):=\int_{0}^{\xi}(e^s-1)s^{-1}\,ds J 2 ( ξ ) := ∫ 0 ξ ( e s − 1 ) s − 1 d s ,
A 1 : g ( ξ ) = 1 + ξ , Q ∞ = 2 : G ( ξ ) = 1 + ξ 2 + 3 2 e − ξ , (19) A_1:\qquad g(\xi)=1+\xi,\ Q_{\infty}=2:\qquad G(\xi)=\frac{1+\xi}{2}+\frac{3}{2}e^{-\xi}, \tag*{(19)} A 1 : g ( ξ ) = 1 + ξ , Q ∞ = 2 : G ( ξ ) = 2 1 + ξ + 2 3 e − ξ , (19)
B 1 : g ( ξ ) = 1 − e − ξ , Q ∞ = 1 : G ( ξ ) = 1 − e − ξ J 2 ( ξ ) . (20) B_1:\qquad g(\xi)=1-e^{-\xi},\ Q_{\infty}=1:\qquad G(\xi)=1-e^{-\xi}J_2(\xi). \tag*{(20)} B 1 : g ( ξ ) = 1 − e − ξ , Q ∞ = 1 : G ( ξ ) = 1 − e − ξ J 2 ( ξ ) . (20)
In detail, for A 1 A_1 A 1 , g ˉ ( y ) = 1 + y / 2 \bar{g}(y)=1+y/2 g ˉ ( y ) = 1 + y /2 and ∫ 0 ξ e y ( 1 + y / 2 ) d y = e ξ − 1 + 1 2 ( ( ξ − 1 ) e ξ + 1 ) \int_{0}^{\xi}e^y(1+y/2)\,dy=e^\xi-1+\frac{1}{2}((\xi-1)e^\xi+1) ∫ 0 ξ e y ( 1 + y /2 ) d y = e ξ − 1 + 2 1 (( ξ − 1 ) e ξ + 1 ) ; and for B 1 B_1 B 1 , g ˉ ( y ) = 1 − ( 1 − e − y ) y − 1 \bar{g}(y)=1-(1-e^{-y})y^{-1} g ˉ ( y ) = 1 − ( 1 − e − y ) y − 1 and ∫ 0 ξ e y ( 1 − e − y ) y − 1 d y = J 2 ( ξ ) \int_{0}^{\xi}e^y(1-e^{-y})y^{-1}\,dy=J_2(\xi) ∫ 0 ξ e y ( 1 − e − y ) y − 1 d y = J 2 ( ξ ) .
Proposition 3.1. The expected loss of the rule R b R_b R b started from ∞ \infty ∞ is
R ( b ) = b e b J 1 ( b ) g ˉ ( b ) + ( 1 − b e b J 1 ( b ) ) G ( b ) = G ( b ) + b e b J 1 ( b ) G ′ ( b ) . R(b)=be^bJ_1(b)\bar{g}(b)+(1-be^bJ_1(b))G(b)=G(b)+be^bJ_1(b)G'(b). R ( b ) = b e b J 1 ( b ) g ˉ ( b ) + ( 1 − b e b J 1 ( b )) G ( b ) = G ( b ) + b e b J 1 ( b ) G ′ ( b ) . Proof. The first expression is the decomposition into the cases of the right and the upper side. The second follows from g ˉ = G + G ′ \bar{g}=G+G' g ˉ = G + G ′ .
For B 1 B_1 B 1 the two terms are the contributions of the upper and the right crossing of the window to the success probability, which is the splitting used for the best-choice problem in [17 , 18 ] ; Proposition 3.1 extends it to an arbitrary loss Q ( ξ , 1 ) Q(\xi,1) Q ( ξ , 1 ) .
Optimising b b b
By (18) , ξ ( G ′ + G ) = ∫ 0 ξ g ( z ) d z \xi(G'+G)=\int_{0}^{\xi}g(z)\,dz ξ ( G ′ + G ) = ∫ 0 ξ g ( z ) d z , and differentiating, ξ G ′ ′ + ( 1 + ξ ) G ′ = g − G \xi G''+(1+\xi)G'=g-G ξ G ′′ + ( 1 + ξ ) G ′ = g − G . With ρ ( b ) = b e b J 1 ( b ) \rho(b)=be^bJ_1(b) ρ ( b ) = b e b J 1 ( b ) we have ρ ′ ( b ) = ( 1 + b ) e b J 1 ( b ) − 1 \rho'(b)=(1+b)e^bJ_1(b)-1 ρ ′ ( b ) = ( 1 + b ) e b J 1 ( b ) − 1 , so
R ′ ( b ) = G ′ ( 1 + ρ ′ ) + ρ G ′ ′ = e b J 1 ( b ) [ ( 1 + b ) G ′ ( b ) + b G ′ ′ ( b ) ] = e b J 1 ( b ) ( Q ( b , 1 ) − G ( b ) ) . (21) R'(b)=G'(1+\rho')+\rho G''=e^bJ_1(b)[(1+b)G'(b)+bG''(b)]=e^bJ_1(b)(Q(b,1)-G(b)). \tag*{(21)} R ′ ( b ) = G ′ ( 1 + ρ ′ ) + ρ G ′′ = e b J 1 ( b ) [( 1 + b ) G ′ ( b ) + b G ′′ ( b )] = e b J 1 ( b ) ( Q ( b , 1 ) − G ( b )) . (21)
The right side vanishes at the balance point : accepting a record of level b b b and waiting for the next record are equally good. For A 1 A_1 A 1 , Q ( b , 1 ) − G ( b ) = 1 + b 2 − 3 2 e − b Q(b,1)-G(b)=\frac{1+b}{2}-\frac{3}{2}e^{-b} Q ( b , 1 ) − G ( b ) = 2 1 + b − 2 3 e − b is increasing; for B 1 B_1 B 1 , Q ( b , 1 ) − G ( b ) = e − b ( J 2 ( b ) − 1 ) Q(b,1)-G(b)=e^{-b}(J_2(b)-1) Q ( b , 1 ) − G ( b ) = e − b ( J 2 ( b ) − 1 ) has the sign of J 2 ( b ) − 1 J_2(b)-1 J 2 ( b ) − 1 , and J 2 J_2 J 2 is increasing. In both cases the difference is negative at b = 0 b=0 b = 0 and has a single zero, so R R R decreases up to this root and increases afterwards.
Theorem 3.2. (i) In A 1 A_1 A 1 the optimal strategy stops at the first record below the hyperbola x = b A / t ˉ x=b_A/\bar{t} x = b A / t ˉ , where b A = 0.617642 … b_A=0.617642\ldots b A = 0.617642 … is the root of ( 1 + b ) e b = 3 (1+b)e^b=3 ( 1 + b ) e b = 3 . The value is
a 1 = 1 + b A − K A J 1 ( b A ) = 1.462488 … , K A = 1 2 b A 2 e b A = 0.353739 … . a_1=1+b_A-K_AJ_1(b_A)=1.462488\ldots,\qquad K_A=\frac{1}{2}b_A^2e^{b_A}=0.353739\ldots. a 1 = 1 + b A − K A J 1 ( b A ) = 1.462488 … , K A = 2 1 b A 2 e b A = 0.353739 … . (ii) In B 1 B_1 B 1 the optimal strategy stops at the first record below the hyperbola x = b B / t ˉ x=b_B/\bar{t} x = b B / t ˉ , where b B = 0.804352 … b_B=0.804352\ldots b B = 0.804352 … is the root of J 2 ( b ) = 1 J_2(b)=1 J 2 ( b ) = 1 . The value is
b 1 = 1 − e − b B − K B J 1 ( b B ) = 0.419836 … , K B = e b B − 1 − b B = 0.430896 … , b_1=1-e^{-b_B}-K_BJ_1(b_B)=0.419836\ldots,\qquad K_B=e^{b_B}-1-b_B=0.430896\ldots, b 1 = 1 − e − b B − K B J 1 ( b B ) = 0.419836 … , K B = e b B − 1 − b B = 0.430896 … , so the maximal probability of success is 1 − b 1 = 0.580164 … 1-b_1=0.580164\ldots 1 − b 1 = 0.580164 … .
Proof. The optimal strategy is R b R_b R b for some b b b , and by (21) the best b b b is the root of the balance equation Q ( b , 1 ) = G ( b ) Q(b,1)=G(b) Q ( b , 1 ) = G ( b ) . For A 1 A_1 A 1 this is 1 + b 2 = 3 2 e − b \frac{1+b}{2}=\frac{3}{2}e^{-b} 2 1 + b = 2 3 e − b , that is ( 1 + b ) e b = 3 (1+b)e^b=3 ( 1 + b ) e b = 3 ; for B 1 B_1 B 1 it is J 2 ( b ) = 1 J_2(b)=1 J 2 ( b ) = 1 . At the root G ( b ) = Q ( b , 1 ) G(b)=Q(b,1) G ( b ) = Q ( b , 1 ) equals 1 + b 1+b 1 + b , respectively 1 − e − b 1-e^{-b} 1 − e − b , and − b e b G ′ ( b ) -be^bG'(b) − b e b G ′ ( b ) equals 1 2 b 2 e b \frac{1}{2}b^2e^b 2 1 b 2 e b (using e b = 3 / ( 1 + b ) e^b=3/(1+b) e b = 3/ ( 1 + b ) ), respectively e b − 1 − b e^b-1-b e b − 1 − b , since G ′ = e − b ( 1 − e b / b ) G'=e^{-b}(1-e^b/b) G ′ = e − b ( 1 − e b / b ) when J 2 ( b ) = 1 J_2(b)=1 J 2 ( b ) = 1 .
The second case is the known solution of the best-choice problem [10 , 13 , 18 ] . We have used the optimality equation only through the interval structure of the optimal strategy.
Remark 3.3 (The value function). For m = 1 m=1 m = 1 equation (13) has the form
ξ v ′ ( ξ ) + ξ v ( ξ ) = ∫ 0 ξ min { Q ( w , 1 ) , v ( w ) } d w . \xi v'(\xi)+\xi v(\xi)=\int_0^\xi\min\{Q(w,1),v(w)\}\,\mathrm{d}w. ξ v ′ ( ξ ) + ξ v ( ξ ) = ∫ 0 ξ min { Q ( w , 1 ) , v ( w )} d w .
For ξ ≤ b \xi\le b ξ ≤ b it gives v = G v=G v = G , and for ξ > b \xi>b ξ > b the integrand is v v v , so ξ v ′ ′ + ( 1 + ξ ) v ′ = 0 \xi v''+(1+\xi)v'=0 ξ v ′′ + ( 1 + ξ ) v ′ = 0 , that is ( ξ e ξ v ′ ) ′ = 0 (\xi e^\xi v')'=0 ( ξ e ξ v ′ ) ′ = 0 , and v ′ v' v ′ is continuous at b b b . Hence
v ( ξ ) = G ( ξ ) , ξ ≤ b ; v ( ξ ) = v ( ∞ ) + K ∗ J 1 ( ξ ) , ξ ≥ b , v(\xi)=G(\xi),\quad\xi\le b;\qquad v(\xi)=v(\infty)+K_*J_1(\xi),\quad\xi\ge b, v ( ξ ) = G ( ξ ) , ξ ≤ b ; v ( ξ ) = v ( ∞ ) + K ∗ J 1 ( ξ ) , ξ ≥ b ,
with K ∗ = K A K_*=K_A K ∗ = K A for A 1 A_1 A 1 and K ∗ = K B K_*=K_B K ∗ = K B for B 1 B_1 B 1 . Here v ( ∞ ) = a 1 v(\infty)=a_1 v ( ∞ ) = a 1 , respectively b 1 b_1 b 1 . This function is the edge function of the two-dimensional problems below.
Two tracked scores: m = 2 m=2 m = 2
For m = 2 m=2 m = 2 the state x = ( x 1 , x 2 ) \mathbf{x}=(x_1,x_2) x = ( x 1 , x 2 ) is the lowest and the second lowest scores in box coordinates. An arriving atom at level ξ \xi ξ is a record if ξ < x 1 \xi<x_1 ξ < x 1 (the new state is ( ξ , x 1 ) (\xi,x_1) ( ξ , x 1 ) ) and a 2-record if x 1 < ξ < x 2 x_1<\xi<x_2 x 1 < ξ < x 2 (the new state is ( x 1 , ξ ) (x_1,\xi) ( x 1 , ξ ) ); atoms with ξ > x 2 \xi>x_2 ξ > x 2 are ignored. Equation (13) takes the form
x 1 ∂ v ∂ x 1 + x 2 ∂ v ∂ x 2 + x 2 v = ∫ 0 x 1 min { Q ( ξ , 1 ) , v ( ξ , x 1 ) } d ξ + ∫ x 1 x 2 min { Q ( ξ , 2 ) , v ( x 1 , ξ ) } d ξ . (22) x_1\frac{\partial v}{\partial x_1}+x_2\frac{\partial v}{\partial x_2}+x_2v
=\int_0^{x_1}\min\{Q(\xi,1),v(\xi,x_1)\}\,\mathrm{d}\xi
+\int_{x_1}^{x_2}\min\{Q(\xi,2),v(x_1,\xi)\}\,\mathrm{d}\xi. \tag*{(22)} x 1 ∂ x 1 ∂ v + x 2 ∂ x 2 ∂ v + x 2 v = ∫ 0 x 1 min { Q ( ξ , 1 ) , v ( ξ , x 1 )} d ξ + ∫ x 1 x 2 min { Q ( ξ , 2 ) , v ( x 1 , ξ )} d ξ . (22)
Two boundaries
In the state ( x 1 , x 2 ) (x_1,x_2) ( x 1 , x 2 ) a record of level ξ \xi ξ is acceptable by the optimal strategy if and only if Q ( ξ , 1 ) ≤ v ( ξ , x 1 ) Q(\xi,1)\le v(\xi,x_1) Q ( ξ , 1 ) ≤ v ( ξ , x 1 ) , and a 2-record of level ξ \xi ξ is acceptable if and only if Q ( ξ , 2 ) ≤ v ( x 1 , ξ ) Q(\xi,2)\le v(x_1,\xi) Q ( ξ , 2 ) ≤ v ( x 1 , ξ ) . By Proposition 2.7(i) the acceptable levels form an interval, and both boundaries of the stopping sets are determined by balancing the loss of acceptance against the continuation value. Therefore, for a given x 1 x_1 x 1 there are two cases.
2-records are acceptable. Then also records are acceptable, and the 2-records are acceptable up to the level β 2 ( x 1 ) > x 1 \beta_2(x_1)>x_1 β 2 ( x 1 ) > x 1 , the rank-2 boundary , which is the root of
Q ( β 2 , 2 ) = v ( x 1 , β 2 ) . (23) Q(\beta_2,2)=v(x_1,\beta_2). \tag*{(23)} Q ( β 2 , 2 ) = v ( x 1 , β 2 ) . (23)
2-records are not acceptable. Then the records are acceptable up to the level β 1 ( x 1 ) ≤ x 1 \beta_1(x_1)\le x_1 β 1 ( x 1 ) ≤ x 1 , the rank-1 boundary , which is the root of
Q ( β 1 , 1 ) = v ( β 1 , x 1 ) , (24) Q(\beta_1,1)=v(\beta_1,x_1), \tag*{(24)} Q ( β 1 , 1 ) = v ( β 1 , x 1 ) , (24)
or β 1 ( x 1 ) = x 1 \beta_1(x_1)=x_1 β 1 ( x 1 ) = x 1 if all records are acceptable.
Both equations are balance conditions (continuous fit): the left side is the loss of acceptance, the right side is the loss of continuation after the new state is formed. In the state space the sets { x 1 ≤ β 1 ( x 2 ) } \{x_1\le\beta_1(x_2)\} { x 1 ≤ β 1 ( x 2 )} and { x 2 ≤ β 2 ( x 1 ) } \{x_2\le\beta_2(x_1)\} { x 2 ≤ β 2 ( x 1 )} consist of the states which are reached by an acceptable record, respectively 2-record (Figure 2 ). In the original coordinates, with y 1 ∘ < y 2 ∘ y_1^\circ<y_2^\circ y 1 ∘ < y 2 ∘ the two lowest scores of the reduced history, the adaptive threshold is
Figure 2. Decision regions in the state plane ( x 1 , x 2 ) (x_1, x_2) ( x 1 , x 2 ) , x 1 < x 2 x_1 < x_2 x 1 < x 2 , in box coordinates, for A2 _2 2 (left) and B2 _2 2 (right). A record of level ξ \xi ξ arriving in the state ( x 1 , x 2 ) (x_1,x_2) ( x 1 , x 2 ) leads to the new state ( ξ , x 1 ) (\xi,x_1) ( ξ , x 1 ) , and a 2-record to ( x 1 , ξ ) (x_1,\xi) ( x 1 , ξ ) ; the shade of a state says what the optimal strategy does with the atom which leads to it. Dark grey, region R \mathcal{R} R : both ranks are acceptable; its upper boundary (dashed) is the curve x 2 = β 2 ( x 1 ) x_2 = \beta_2(x_1) x 2 = β 2 ( x 1 ) of balance Q ( x 2 , 2 ) = v ( x 1 , x 2 ) Q(x_2,2) = v(x_1,x_2) Q ( x 2 , 2 ) = v ( x 1 , x 2 ) , joining ( 0 , β 2 ( 0 ) ) (0,\beta_2(0)) ( 0 , β 2 ( 0 )) to ( γ , γ ) (\gamma,\gamma) ( γ , γ ) . Light grey: only records are acceptable, up to the curve x 1 = β 1 ( x 2 ) x_1 = \beta_1(x_2) x 1 = β 1 ( x 2 ) (solid) of balance Q ( x 1 , 1 ) = v ( x 1 , x 2 ) Q(x_1,1) = v(x_1,x_2) Q ( x 1 , 1 ) = v ( x 1 , x 2 ) , which coincides with the diagonal up to ( x ∗ , x ∗ ) (x^*,x^*) ( x ∗ , x ∗ ) and then continues as a strip narrowing to β 1 ( ∞ ) = H 0 \beta_1(\infty) = H_0 β 1 ( ∞ ) = H 0 (dotted). White: continuation. The curve β 2 \beta_2 β 2 is the explicit curve (35) in A2 _2 2 and the solution set of (37) in B2 _2 2 ; β 1 \beta_1 β 1 is computed by quadrature.
H t = min ( y 2 ∘ , β 2 ( t y ˉ 1 ∘ ) t ˉ ) in the case (i) , H t = β 1 ( t y ˉ 1 ∘ ) t ˉ in the case (ii) . H_t=\min\left(y_2^\circ,\frac{\beta_2(t\bar y_1^\circ)}{\bar t}\right)\text{ in the case (i)},\qquad
H_t=\frac{\beta_1(t\bar y_1^\circ)}{\bar t}\text{ in the case (ii)}. H t = min ( y 2 ∘ , t ˉ β 2 ( t y ˉ 1 ∘ ) ) in the case (i) , H t = t ˉ β 1 ( t y ˉ 1 ∘ ) in the case (ii) .
Between arrivals H t H_t H t is nondecreasing by Proposition 2.7, but it is not a hyperbola, because β 1 , β 2 \beta_1,\beta_2 β 1 , β 2 are evaluated at the shrinking state t y ˉ 1 ∘ t\bar y_1^\circ t y ˉ 1 ∘ , while the past scores are frozen. The threshold stays flat at y 2 ∘ y_2^\circ y 2 ∘ , respectively y 1 ∘ y_1^\circ y 1 ∘ , when it reaches the past score.
Remark 4.1 (Jumps for m = 2 m=2 m = 2 ). In the case (i) every record is below y 1 0 ≤ H t y_1^0 \le H_t y 1 0 ≤ H t and is accepted, while a 2-record above H t H_t H t can only lower y 2 0 y_2^0 y 2 0 to its score x 0 ≥ H t x_0 \ge H_t x 0 ≥ H t , which leaves H t = min ( y 2 0 , β 2 ( t y ˉ 1 0 ) / t ) H_t=\min(y_2^0,\beta_2(t\bar{y}_1^0)/t) H t = min ( y 2 0 , β 2 ( t y ˉ 1 0 ) / t ) unchanged. In the case (ii) an atom above y 1 0 y_1^0 y 1 0 does not change H t H_t H t , and a rejected record x 0 ∈ [ H t , y 1 0 ) x_0 \in[H_t,y_1^0) x 0 ∈ [ H t , y 1 0 ) becomes the new lowest score (this requires t y ˉ 1 0 > x ∗ t\bar{y}_1^0>x^* t y ˉ 1 0 > x ∗ , since otherwise H t = y 1 0 H_t=y_1^0 H t = y 1 0 ). Then t x ˉ 0 ≥ β 1 ( t y ˉ 1 0 ) ≥ H 0 > γ t\bar{x}_0 \ge\beta_1(t\bar{y}_1^0) \ge H_0>\gamma t x ˉ 0 ≥ β 1 ( t y ˉ 1 0 ) ≥ H 0 > γ . The first inequality holds because x 0 ≥ H t x_0 \ge H_t x 0 ≥ H t . The second holds because β 1 \beta_1 β 1 is nonincreasing on [ x ∗ , ∞ ) [x^*,\infty) [ x ∗ , ∞ ) with β 1 ( ∞ ) = H 0 \beta_1(\infty)=H_0 β 1 ( ∞ ) = H 0 : the root of Q ( ξ , 1 ) = v ( ξ , u ) Q(\xi,1)=v(\xi,u) Q ( ξ , 1 ) = v ( ξ , u ) moves to the left as u u u grows, since v v v decreases in its second argument (Lemma 2.6 ). The third is Lemma 4.5 (numerically H 0 = 0.902 H_0=0.902 H 0 = 0.902 and γ = 0.389 \gamma=0.389 γ = 0.389 in A2 _2 2 , H 0 = 1.088 H_0=1.088 H 0 = 1.088 and γ = 0.706 \gamma=0.706 γ = 0.706 in B2 _2 2 ). So we stay in the case (ii), and the new threshold is β 1 ( t x ˉ 0 ) / t ˉ \beta_1(t\bar{x}_0)/\bar{t} β 1 ( t x ˉ 0 ) / t ˉ . It is at least H t H_t H t , because t x ˉ 0 ≥ β 1 ( t y ˉ 1 0 ) t\bar{x}_0 \ge\beta_1(t\bar{y}_1^0) t x ˉ 0 ≥ β 1 ( t y ˉ 1 0 ) while β 1 ( u ) = u \beta_1(u)=u β 1 ( u ) = u for u ≤ x ∗ u \le x^* u ≤ x ∗ and β 1 \beta_1 β 1 is nonincreasing on [ x ∗ , ∞ ) [x^*,\infty) [ x ∗ , ∞ ) , and it is at most x 0 x_0 x 0 , because β 1 ( u ) ≤ u \beta_1(u)\le u β 1 ( u ) ≤ u . Thus a jump takes H t H_t H t at most to the score of the arriving atom, and exactly there if t x 0 ≤ x ∗ t x_0 \le x^* t x 0 ≤ x ∗ (all records are acceptable); then H t H_t H t stays flat at x 0 x_0 x 0 by Proposition 2.7(iv).
Lemma 4.2. In both problems A2 _2 2 and B2 _2 2 the function x ↦ Q ( x , 2 ) − v ( x , x ) x\mapsto Q(x,2)-v(x,x) x ↦ Q ( x , 2 ) − v ( x , x ) is continuous and strictly increasing, with a unique zero γ \gamma γ . For x 1 < γ x_1<\gamma x 1 < γ equation (23) has a unique root β 2 ( x 1 ) > x 1 \beta_2(x_1)>x_1 β 2 ( x 1 ) > x 1 , which is a strictly decreasing function of x 1 x_1 x 1 with β 2 ( x 1 ) → γ \beta_2(x_1)\to\gamma β 2 ( x 1 ) → γ as x 1 ↑ γ x_1\uparrow\gamma x 1 ↑ γ ; a 2-record is acceptable if and only if its level is below β 2 ( x 1 ) \beta_2(x_1) β 2 ( x 1 ) . For x 1 ≥ γ x_1\ge\gamma x 1 ≥ γ no 2-record is acceptable.
Proof. Q ( x , 2 ) Q(x,2) Q ( x , 2 ) is strictly increasing and v ( x , x ) v(x,x) v ( x , x ) is strictly decreasing by Lemma 2.6 , and v v v is continuous. As x → 0 x\to0 x → 0 the difference tends to Q ( 0 , 2 ) − Q ∞ < 0 Q(0,2)-Q_\infty<0 Q ( 0 , 2 ) − Q ∞ < 0 (it equals 2 − 3 = − 1 2-3=-1 2 − 3 = − 1 in A2 _2 2 and 0 − 1 = − 1 0-1=-1 0 − 1 = − 1 in B2 _2 2 ), and for large x x x it is positive: Q ( x , 2 ) = 2 + x → ∞ Q(x,2)=2+x\to\infty Q ( x , 2 ) = 2 + x → ∞ in A2 _2 2 , and Q ( x , 2 ) = 1 − e − x → 1 > b 2 Q(x,2)=1-e^{-x}\to1>b_2 Q ( x , 2 ) = 1 − e − x → 1 > b 2 in B2 _2 2 . For fixed x 1 x_1 x 1 the function ξ ↦ Q ( ξ , 2 ) − v ( x 1 , ξ ) \xi\mapsto Q(\xi,2)-v(x_1,\xi) ξ ↦ Q ( ξ , 2 ) − v ( x 1 , ξ ) is strictly increasing on ( x 1 , ∞ ) (x_1,\infty) ( x 1 , ∞ ) and positive for large ξ \xi ξ ; it is negative at ξ = x 1 \xi=x_1 ξ = x 1 if and only if x 1 < γ x_1<\gamma x 1 < γ . This gives the root and the threshold form. Raising x 1 x_1 x 1 lowers v ( x 1 , ξ ) v(x_1,\xi) v ( x 1 , ξ ) for every ξ \xi ξ , so the root moves to the left.
Thus the rank-2 boundary is a decreasing curve x 2 = β 2 ( x 1 ) x_2=\beta_2(x_1) x 2 = β 2 ( x 1 ) in the plane, which runs from a point ( 0 , β 2 ( 0 ) ) (0,\beta_2(0)) ( 0 , β 2 ( 0 )) on the axis to the point ( γ , γ ) (\gamma,\gamma) ( γ , γ ) on the diagonal.
The edge
The score x 1 → 0 x_1\to0 x 1 → 0 approaches the lowest possible, which contributes 1 to every other initial rank. The loss in A2 _2 2 is min ( i , 3 ) + ξ = 1 + min ( i − 1 , 2 ) + ξ \min(i,3)+\xi=1+\min(i-1,2)+\xi min ( i , 3 ) + ξ = 1 + min ( i − 1 , 2 ) + ξ , thus the problem with the state ( 0 , x ) (0,x) ( 0 , x ) amounts to problem A1 _1 1 with the state x x x , and the loss increased by 1. In B2 _2 2 the loss 1 ( r > 2 ) \mathbf{1}(r>2) 1 ( r > 2 ) becomes 1 ( r − 1 > 1 ) \mathbf{1}(r-1>1) 1 ( r − 1 > 1 ) . Hence
v A 2 ( 0 , x ) = 1 + v A 1 ( x ) , v B 2 ( 0 , x ) = v B 1 ( x ) . v_{\mathrm{A}_2}(0,x)=1+v_{\mathrm{A}_1}(x),\qquad v_{\mathrm{B}_2}(0,x)=v_{\mathrm{B}_1}(x). v A 2 ( 0 , x ) = 1 + v A 1 ( x ) , v B 2 ( 0 , x ) = v B 1 ( x ) .
Proposition 4.3. At the edge x 1 = 0 x_1=0 x 1 = 0 the rank-2 boundary is β 2 ( 0 ) = b A = 0.617642 … \beta_2(0)=b_{\mathrm{A}}=0.617642\ldots β 2 ( 0 ) = b A = 0.617642 … in A2 _2 2 and β 2 ( 0 ) = b B = 0.804352 … \beta_2(0)=b_{\mathrm{B}}=0.804352\ldots β 2 ( 0 ) = b B = 0.804352 … in B2 _2 2 , which are the hyperbola constants of Theorem 3.2 .
Proof. For A2 _2 2 , Q ( β , 2 ) = 2 + β Q(\beta,2)=2+\beta Q ( β , 2 ) = 2 + β and v ( 0 , β ) = 1 + v A 1 ( β ) v(0,\beta)=1+v_{\mathrm{A}_1}(\beta) v ( 0 , β ) = 1 + v A 1 ( β ) , so equation (23) reads 1 + β = v A 1 ( β ) 1+\beta=v_{\mathrm{A}_1}(\beta) 1 + β = v A 1 ( β ) , which is the balance equation Q ( β , 1 ) = v A 1 ( β ) Q(\beta,1)=v_{\mathrm{A}_1}(\beta) Q ( β , 1 ) = v A 1 ( β ) defining b A b_{\mathrm{A}} b A . For B2 _2 2 , Q ( β , 2 ) = 1 − e − β Q(\beta,2)=1-e^{-\beta} Q ( β , 2 ) = 1 − e − β is the loss of a record in B1 _1 1 , and v ( 0 , β ) = v B 1 ( β ) v(0,\beta)=v_{\mathrm{B}_1}(\beta) v ( 0 , β ) = v B 1 ( β ) , which defines b B b_{\mathrm{B}} b B .
On the edge the stopping set for 2-records is the interval [ 0 , β 2 ( 0 ) ] [0,\beta_2(0)] [ 0 , β 2 ( 0 )] , and the value v ( 0 , x 2 ) v(0,x_2) v ( 0 , x 2 ) is explicit for all x 2 x_2 x 2 by Remark 3.3.
The lower bound and the region R \mathcal{R} R
Let q ( i ) : = Q ( 0 , i ) q(i):=Q(0,i) q ( i ) := Q ( 0 , i ) , which is min ( i , m + 1 ) \min(i,m+1) min ( i , m + 1 ) in Am _m m and 1 ( i > m ) 1(i>m) 1 ( i > m ) in Bm _m m ; then Q ( ξ , i ) ≥ q ( i ) Q(\xi,i)\ge q(i) Q ( ξ , i ) ≥ q ( i ) for all ξ \xi ξ and q ( i ) = Q ∞ q(i)=Q_\infty q ( i ) = Q ∞ for i > m i>m i > m . The following bound is the analogue, for the adapted losses, of the bound (14) in [14 ] for the loss depending on the final rank, and is proved in the same way.
Lemma 4.4. For every state x x x , with x 0 : = 0 x_0 := 0 x 0 := 0 ,
v ( x ) ≥ ∑ j = 1 m q ( j ) ( e − x j − 1 − e − x j ) + Q ∞ e − x m . v(\mathbf{x}) \ge\sum_{j=1}^{m}q(j)\left(e^{-x_{j-1}}-e^{-x_j}\right)+Q_\infty e^{-x_m}. v ( x ) ≥ j = 1 ∑ m q ( j ) ( e − x j − 1 − e − x j ) + Q ∞ e − x m . In particular, for m = 2 m=2 m = 2 , v ( x 1 , x 2 ) ≥ q ( 1 ) ( 1 − e − x 1 ) + q ( 2 ) ( e − x 1 − e − x 2 ) + Q ∞ e − x 2 v(x_1,x_2) \ge q(1)(1-e^{-x_1})+q(2)(e^{-x_1}-e^{-x_2})+Q_\infty e^{-x_2} v ( x 1 , x 2 ) ≥ q ( 1 ) ( 1 − e − x 1 ) + q ( 2 ) ( e − x 1 − e − x 2 ) + Q ∞ e − x 2 . Proof. In the problem with the initial history x x x , let E j E_j E j be the event that Π \Pi Π has no atom with score below x j x_j x j , so P [ E j ] = e − x j \mathbb{P}[E_j]=e^{-x_j} P [ E j ] = e − x j . On E j E_j E j every accepted atom has the initial rank at least j + 1 j+1 j + 1 . Hence the initial rank I I I of the accepted atom (with I = m + 1 I=m+1 I = m + 1 if there is none) satisfies P [ I ≥ j + 1 ] ≥ e − x j \mathbb{P}[I\ge j+1]\ge e^{-x_j} P [ I ≥ j + 1 ] ≥ e − x j for j ≤ m j\le m j ≤ m , and the loss is at least q ( I ) q(I) q ( I ) . By summation by parts,
E q ( I ) = q ( 1 ) + ∑ j ≥ 1 ( q ( j + 1 ) − q ( j ) ) P [ I ≥ j + 1 ] \mathbb{E}q(I)=q(1)+\sum_{j\ge1}(q(j+1)-q(j))\mathbb{P}[I\ge j+1] E q ( I ) = q ( 1 ) + j ≥ 1 ∑ ( q ( j + 1 ) − q ( j )) P [ I ≥ j + 1 ] is bounded below by the right side, since q q q is nondecreasing.
Lemma 4.5. In A2 _2 2 and B2 _2 2 we have Q ( γ , 1 ) < v ( γ , u ) Q(\gamma,1)<v(\gamma,u) Q ( γ , 1 ) < v ( γ , u ) for every u > γ u>\gamma u > γ , with a difference bounded away from zero. Consequently β 1 ( u ) > γ \beta_1(u)>\gamma β 1 ( u ) > γ for u > x ∗ u>x^* u > x ∗ , and H 0 > γ H_0>\gamma H 0 > γ . Proof. In A2 _2 2 Lemma 4.4 gives v ( γ , u ) ≥ 1 + e − γ + e − u > 1 + e − γ v(\gamma,u)\ge1+e^{-\gamma}+e^{-u}>1+e^{-\gamma} v ( γ , u ) ≥ 1 + e − γ + e − u > 1 + e − γ , while Q ( γ , 1 ) = 1 + γ Q(\gamma,1)=1+\gamma Q ( γ , 1 ) = 1 + γ , and e − γ = 0.678 > γ = 0.389 e^{-\gamma}=0.678>\gamma=0.389 e − γ = 0.678 > γ = 0.389 .
In B2 _2 2 consider the problem with the initial history ( γ , u ) (\gamma,u) ( γ , u ) , and let E E E be the event that Π \Pi Π has no atom with score below γ \gamma γ , so P [ E ] = e − γ \mathbb{P}[E]=e^{-\gamma} P [ E ] = e − γ . On E E E the score γ \gamma γ of the history is below every atom, hence a selected atom has final rank at most 2 only if it is the lowest atom of Π \Pi Π . The event E E E depends only on the atoms with score below γ \gamma γ , which are independent of the other atoms; so given E E E the process Π \Pi Π is a Poisson process of unit intensity on [ 0 , 1 ] × ( γ , ∞ ) [0,1]\times(\gamma,\infty) [ 0 , 1 ] × ( γ , ∞ ) , and after the shift of the scores by γ \gamma γ the task is to select the lowest atom, which is problem B1 _1 1 with empty history; every strategy fails in it with probability at least b 1 \mathbf{b}_1 b 1 . Thus v ( γ , u ) ≥ e − γ b 1 = 0.207 v(\gamma,u)\ge e^{-\gamma}\mathbf{b}_1=0.207 v ( γ , u ) ≥ e − γ b 1 = 0.207 by Theorem 3.2, while Q ( γ , 1 ) = 1 − ( 1 + γ ) e − γ = 0.158 Q(\gamma,1)=1-(1+\gamma)e^{-\gamma}=0.158 Q ( γ , 1 ) = 1 − ( 1 + γ ) e − γ = 0.158 .
Both bounds do not depend on u u u , so they hold for v ( γ , ∞ ) v(\gamma,\infty) v ( γ , ∞ ) as well. Since ξ ↦ Q ( ξ , 1 ) − v ( ξ , u ) \xi\mapsto Q(\xi,1)-v(\xi,u) ξ ↦ Q ( ξ , 1 ) − v ( ξ , u ) is increasing, its root β 1 ( u ) \beta_1(u) β 1 ( u ) is above γ \gamma γ for u > x ∗ u>x^* u > x ∗ , and so is the root H 0 H_0 H 0 of Q ( ξ , 1 ) = v ( ξ , ∞ ) Q(\xi,1)=v(\xi,\infty) Q ( ξ , 1 ) = v ( ξ , ∞ ) .
Let R \mathcal{R} R be the set of states ( x 1 , x 2 ) (x_1,x_2) ( x 1 , x 2 ) with x 1 < γ x_1<\gamma x 1 < γ and x 1 < x 2 ≤ β 2 ( x 1 ) x_1<x_2\le\beta_2(x_1) x 1 < x 2 ≤ β 2 ( x 1 ) , that is, the region between the diagonal and the rank-2 boundary. In R \mathcal{R} R every 2-record is acceptable. If also every record is acceptable, then (22) is linear:
x 1 ∂ v ∂ x 1 + x 2 ∂ v ∂ x 2 + x 2 v = ∫ 0 x 1 Q ( ξ , 1 ) d ξ + ∫ x 1 x 2 Q ( ξ , 2 ) d ξ . (25) x_1\frac{\partial v}{\partial x_1}+x_2\frac{\partial v}{\partial x_2}+x_2v=\int_0^{x_1}Q(\xi,1)\,\mathrm{d}\xi+\int_{x_1}^{x_2}Q(\xi,2)\,\mathrm{d}\xi. \tag*{(25)} x 1 ∂ x 1 ∂ v + x 2 ∂ x 2 ∂ v + x 2 v = ∫ 0 x 1 Q ( ξ , 1 ) d ξ + ∫ x 1 x 2 Q ( ξ , 2 ) d ξ . (25)
The region R \mathcal{R} R is star-shaped with respect to the origin, because β 2 \beta_2 β 2 is decreasing: if ( x 1 , x 2 ) ∈ R (x_1,x_2)\in\mathcal{R} ( x 1 , x 2 ) ∈ R and 0 < s < 1 0<s<1 0 < s < 1 , then s x 2 < x 2 ≤ β 2 ( x 1 ) < β 2 ( s x 1 ) sx_2<x_2\le\beta_2(x_1)<\beta_2(sx_1) s x 2 < x 2 ≤ β 2 ( x 1 ) < β 2 ( s x 1 ) . Along a ray x 2 = κ x 1 x_2=\kappa x_1 x 2 = κ x 1 the left side of (25) is an ordinary differential operator for f ( s ) = v ( s , κ s ) f(s)=v(s,\kappa s) f ( s ) = v ( s , κ s ) , namely s f ′ + κ s f sf'+\kappa sf s f ′ + κ s f , with the initial value f ( 0 ) = Q ∞ f(0)=Q_\infty f ( 0 ) = Q ∞ . This determines v v v on R \mathcal{R} R . All records are acceptable in the state ( x 1 , x 2 ) (x_1,x_2) ( x 1 , x 2 ) if Q ( ξ , 1 ) ≤ v ( ξ , x 1 ) Q(\xi,1)\le v(\xi,x_1) Q ( ξ , 1 ) ≤ v ( ξ , x 1 ) for all ξ < x 1 \xi<x_1 ξ < x 1 , which holds for x 1 ≤ x ∗ x_1\le x^* x 1 ≤ x ∗ , the root of (31) below, since then v ( ξ , x 1 ) ≥ v d ( x 1 ) ≥ Q ( x 1 , 1 ) ≥ Q ( ξ , 1 ) v(\xi,x_1)\ge v_d(x_1)\ge Q(x_1,1)\ge Q(\xi,1) v ( ξ , x 1 ) ≥ v d ( x 1 ) ≥ Q ( x 1 , 1 ) ≥ Q ( ξ , 1 ) by Lemma 2.6 (i).
Beyond the rank-2 boundary
For m = 2 m=2 m = 2 the value function is continuously differentiable in the open cone Ω = { 0 < x 1 < x 2 } \Omega=\{0<x_1<x_2\} Ω = { 0 < x 1 < x 2 } , across the boundaries β 1 , β 2 \beta_1,\beta_2 β 1 , β 2 included. The proof does not use smooth fit; it uses the ray representation (12) and the fact that x 2 x_2 x 2 enters the right side of (22) only as the upper limit of integration.
Proposition 4.6 (Regularity). In A2 _2 2 and B2 _2 2 the value function v v v is continuously differentiable in Ω \Omega Ω , and g = ∂ 2 v g=\partial_2v g = ∂ 2 v is differentiable along the rays and satisfies
( x 1 ∂ 1 + x 2 ∂ 2 ) g + ( 1 + x 2 ) g = min { Q ( x 2 , 2 ) − v , 0 } in Ω . (26) (x_1\partial_1+x_2\partial_2)g+(1+x_2)g=\min\{Q(x_2,2)-v,0\}\qquad\text{in }\Omega. \tag*{(26)} ( x 1 ∂ 1 + x 2 ∂ 2 ) g + ( 1 + x 2 ) g = min { Q ( x 2 , 2 ) − v , 0 } in Ω. (26) :::`
Proof. Let P P P be the right side of (22) . The integrands are bounded and continuous in ( ξ , x ) (\xi,x) ( ξ , x ) except at ξ = x 1 \xi=x_1 ξ = x 1 , a null set, so P P P is continuous.
Step 1. For ξ < x 2 \xi<x_2 ξ < x 2 the state x ∪ ξ x\cup\xi x ∪ ξ does not contain x 2 x_2 x 2 , and the rank of ξ \xi ξ does not depend on x 2 x_2 x 2 ; thus x 2 x_2 x 2 enters P P P only as the upper limit. In Ω \Omega Ω the integrand near ξ = x 2 \xi=x_2 ξ = x 2 is min { Q ( ξ , 2 ) , v ( x 1 , ξ ) } \min\{Q(\xi,2),v(x_1,\xi)\} min { Q ( ξ , 2 ) , v ( x 1 , ξ )} , which is continuous in ξ \xi ξ , hence
∂ 2 P ( x ) = min { Q ( x 2 , 2 ) , v ( x ) } , \partial_2P(x)=\min\{Q(x_2,2),v(x)\}, ∂ 2 P ( x ) = min { Q ( x 2 , 2 ) , v ( x )} ,
a continuous function in Ω \Omega Ω .
Step 2. Differentiate (12) in x 2 x_2 x 2 at fixed x 1 x_1 x 1 . Since ∂ x 2 [ P ( r x ) ] = r ∂ 2 P ( r x ) \partial_{x_2}[P(rx)]=r\partial_2P(rx) ∂ x 2 [ P ( r x )] = r ∂ 2 P ( r x ) , and the x 2 x_2 x 2 -derivative of the integrand is bounded and continuous in r ∈ ( 0 , 1 ] r\in(0,1] r ∈ ( 0 , 1 ] ,
∂ 2 v ( x ) = − v ( x ) + e − x 2 ∫ 0 1 e x 2 r [ P ( r x ) + ∂ 2 P ( r x ) ] d r (27) \partial_2v(x)=-v(x)+e^{-x_2}\int_0^1e^{x_2r}[P(rx)+\partial_2P(rx)]\,dr \tag*{(27)} ∂ 2 v ( x ) = − v ( x ) + e − x 2 ∫ 0 1 e x 2 r [ P ( r x ) + ∂ 2 P ( r x )] d r (27)
so ∂ 2 v \partial_2v ∂ 2 v exists and is continuous in Ω \Omega Ω .
Step 3. By (12) the function f ( s ) = v ( s x ) f(s)=v(sx) f ( s ) = v ( s x ) satisfies ( e s x 2 f ) ′ = e s x 2 P ( s x ) / s (e^{sx_2}f)'=e^{sx_2}P(sx)/s ( e s x 2 f ) ′ = e s x 2 P ( s x ) / s , whose right side is continuous for s > 0 s>0 s > 0 . Hence f f f is continuously differentiable, and
D v : = ( x 1 ∂ 1 + x 2 ∂ 2 ) v = P − x 2 v Dv:=(x_1\partial_1+x_2\partial_2)v=P-x_2v D v := ( x 1 ∂ 1 + x 2 ∂ 2 ) v = P − x 2 v
is continuous. In the coordinates x 1 = s x_1=s x 1 = s , x 2 = κ s x_2=\kappa s x 2 = κ s the function F ( s , κ ) = v ( s , κ s ) F(s,\kappa)=v(s,\kappa s) F ( s , κ ) = v ( s , κ s ) has the continuous partial derivatives ∂ s F = ( D v ) / s \partial_sF=(Dv)/s ∂ s F = ( D v ) / s and ∂ κ F = s ∂ 2 v \partial_\kappa F=s\partial_2v ∂ κ F = s ∂ 2 v . So F F F is continuously differentiable, and so is v v v , because ( x 1 , x 2 ) ↦ ( s , κ ) (x_1,x_2)\mapsto(s,\kappa) ( x 1 , x 2 ) ↦ ( s , κ ) is a diffeomorphism on Ω \Omega Ω .
Step 4. Put g = ∂ 2 v g=\partial_2v g = ∂ 2 v and substitute r = u / s r=u/s r = u / s in (27) at the point s x sx s x :
s e s x 2 ( g + v ) ( s x ) = ∫ 0 s e x 2 u [ P ( u x ) + ∂ 2 P ( u x ) ] d u . s e^{sx_2}(g+v)(sx)=\int_0^s e^{x_2u}[P(ux)+\partial_2P(ux)]\,du. s e s x 2 ( g + v ) ( s x ) = ∫ 0 s e x 2 u [ P ( ux ) + ∂ 2 P ( ux )] d u .
The right side is continuously differentiable in s s s . Differentiating, and using d d s v ( s x ) = ( P − s x 2 v ) ( s x ) / s \frac{d}{ds}v(sx)=(P-sx_2v)(sx)/s d s d v ( s x ) = ( P − s x 2 v ) ( s x ) / s from Step 3, we obtain s d d s g ( s x ) + ( 1 + s x 2 ) g ( s x ) + v ( s x ) = ∂ 2 P ( s x ) s\frac{d}{ds}g(sx)+(1+sx_2)g(sx)+v(sx)=\partial_2P(sx) s d s d g ( s x ) + ( 1 + s x 2 ) g ( s x ) + v ( s x ) = ∂ 2 P ( s x ) . With Step 1 this is (26) at the point s x . □ sx. \square s x . □
In the region x 2 > β 2 ( x 1 ) x_2>\beta_2(x_1) x 2 > β 2 ( x 1 ) the 2-records are not acceptable, so Q ( x 2 , 2 ) > v Q(x_2,2)>v Q ( x 2 , 2 ) > v and the right side of (26) vanishes: ( x 1 ∂ 1 + x 2 ∂ 2 ) g + ( 1 + x 2 ) g = 0 (x_1\partial_1+x_2\partial_2)g+(1+x_2)g=0 ( x 1 ∂ 1 + x 2 ∂ 2 ) g + ( 1 + x 2 ) g = 0 . Along a ray x 2 = κ x 1 x_2=\kappa x_1 x 2 = κ x 1 this is ( x 2 e x 2 g ) ′ = 0 (x_2e^{x_2}g)'=0 ( x 2 e x 2 g ) ′ = 0 , hence
∂ v ∂ x 2 ( x 1 , x 2 ) = C ( κ ) e − x 2 x 2 , κ = x 2 x 1 (28) \frac{\partial v}{\partial x_2}(x_1,x_2)=C(\kappa)\frac{e^{-x_2}}{x_2},\qquad\kappa=\frac{x_2}{x_1} \tag*{(28)} ∂ x 2 ∂ v ( x 1 , x 2 ) = C ( κ ) x 2 e − x 2 , κ = x 1 x 2 (28)
for a function C C C of one variable. Since ∂ 2 v \partial_2v ∂ 2 v is continuous (Proposition 4.6 ), C ( κ ) C(\kappa) C ( κ ) is the value of x 2 e x 2 ∂ 2 v x_2e^{x_2}\partial_2v x 2 e x 2 ∂ 2 v computed from the closed form on R \mathcal{R} R at the point where the ray meets the boundary. As κ → ∞ \kappa\to\infty κ → ∞ this point tends to ( 0 , β 2 ( 0 ) ) (0,\beta_2(0)) ( 0 , β 2 ( 0 )) and C ( ∞ ) = − K A C(\infty)=-K_A C ( ∞ ) = − K A in A 2 A_2 A 2 , − K B -K_B − K B in B 2 B_2 B 2 , by Remark 3.3. Integrating (28) from the boundary, we obtain
v ( x 1 , x 2 ) = Q ( β 2 ( x 1 ) , 2 ) + ∫ β 2 ( x 1 ) x 2 C ( ξ x 1 ) e − ξ ξ d ξ , x 1 < γ , x 2 > β 2 ( x 1 ) . (29) v(x_1,x_2)=Q(\beta_2(x_1),2)+\int_{\beta_2(x_1)}^{x_2}C\left(\frac{\xi}{x_1}\right)\frac{e^{-\xi}}{\xi}\,d\xi,\qquad x_1<\gamma,\ x_2>\beta_2(x_1). \tag*{(29)} v ( x 1 , x 2 ) = Q ( β 2 ( x 1 ) , 2 ) + ∫ β 2 ( x 1 ) x 2 C ( x 1 ξ ) ξ e − ξ d ξ , x 1 < γ , x 2 > β 2 ( x 1 ) . (29)
For x 1 ≥ γ x_1\ge\gamma x 1 ≥ γ no 2-record is acceptable and the whole region x 2 > x 1 x_2>x_1 x 2 > x 1 is of this kind: v ( x 1 , x 2 ) = v d ( x 1 ) + ∫ x 1 x 2 C ( ξ / x 1 ) e − ξ ξ − 1 d ξ v(x_1,x_2)=v_d(x_1)+\int_{x_1}^{x_2}C(\xi/x_1)e^{-\xi}\xi^{-1}\,d\xi v ( x 1 , x 2 ) = v d ( x 1 ) + ∫ x 1 x 2 C ( ξ / x 1 ) e − ξ ξ − 1 d ξ , where v d ( x ) = v ( x , x ) v_d(x)=v(x,x) v d ( x ) = v ( x , x ) is the value on the diagonal. On the diagonal the second integral in (22) vanishes, and
v d ′ ( x ) + v d ( x ) = 1 x ∫ 0 x min { Q ( ξ , 1 ) , v ( ξ , x ) } d ξ , v d ( γ ) = Q ( γ , 2 ) , (30) v_d'(x)+v_d(x)=\frac{1}{x}\int_0^x\min\{Q(\xi,1),v(\xi,x)\}\,d\xi,\qquad v_d(\gamma)=Q(\gamma,2), \tag*{(30)} v d ′ ( x ) + v d ( x ) = x 1 ∫ 0 x min { Q ( ξ , 1 ) , v ( ξ , x )} d ξ , v d ( γ ) = Q ( γ , 2 ) , (30)
and v ( ∞ ) = lim x → ∞ v d ( x ) v(\infty)=\lim_{x\to\infty}v_d(x) v ( ∞ ) = lim x → ∞ v d ( x ) .
The diagonal critical score. As long as all records are acceptable the right side of (30) is 1 x ∫ 0 x Q ( ξ , 1 ) d ξ \frac{1}{x}\int_0^x Q(\xi,1)\,\mathrm{d}\xi x 1 ∫ 0 x Q ( ξ , 1 ) d ξ , and the equation is linear, with the same solution as on R \mathcal{R} R . Since Q ( ξ , 1 ) − v ( ξ , x ) Q(\xi,1)-v(\xi,x) Q ( ξ , 1 ) − v ( ξ , x ) is increasing in ξ \xi ξ , the worst record has ξ = x \xi=x ξ = x , and all records are acceptable up to the root x ∗ x^* x ∗ of the balance equation
Q ( x , 1 ) = v d ( x ) . (31) Q(x,1)=v_{\mathrm{d}}(x). \tag*{(31)} Q ( x , 1 ) = v d ( x ) . (31)
For x 1 > x ∗ x_1>x^* x 1 > x ∗ the boundary β 1 \beta_1 β 1 bends away from the diagonal. Since β 1 ( x 1 ) ≤ x ∗ \beta_1(x_1)\leq x^* β 1 ( x 1 ) ≤ x ∗ for every x 1 x_1 x 1 , the root of (24) needs the value v ( β 1 , x 1 ) = v d ( β 1 ) + ∫ β 1 x 1 C ( ξ / β 1 ) e − ξ d ξ v(\beta_1,x_1)=v_{\mathrm{d}}(\beta_1)+\int_{\beta_1}^{x_1}C(\xi/\beta_1)e^{-\xi}\,\mathrm{d}\xi v ( β 1 , x 1 ) = v d ( β 1 ) + ∫ β 1 x 1 C ( ξ / β 1 ) e − ξ d ξ with β 1 < x ∗ \beta_1<x^* β 1 < x ∗ only. Here (28) applies on the whole segment from ( β 1 , β 1 ) (\beta_1,\beta_1) ( β 1 , β 1 ) to ( β 1 , x 1 ) (\beta_1,x_1) ( β 1 , x 1 ) , because β 1 > γ \beta_1>\gamma β 1 > γ by Lemma 4.5 . Therefore the critical scores β 2 \beta_2 β 2 , β 1 \beta_1 β 1 and the initial threshold H 0 = β 1 ( ∞ ) H_0=\beta_1(\infty) H 0 = β 1 ( ∞ ) are all given by explicit equations. The initial threshold is itself a balance point: a record of level H 0 H_0 H 0 arriving at time 0 into the empty history leads to the state ( H 0 , ∞ ) (H_0,\infty) ( H 0 , ∞ ) , and H 0 H_0 H 0 is the root of Q ( H 0 , 1 ) = v ( H 0 , ∞ ) Q(H_0,1)=v(H_0,\infty) Q ( H 0 , 1 ) = v ( H 0 , ∞ ) , where v ( x , ∞ ) : = lim x 2 → ∞ v ( x , x 2 ) v(x,\infty):=\lim_{x_2\to\infty}v(x,x_2) v ( x , ∞ ) := lim x 2 → ∞ v ( x , x 2 ) ; this is (24) with x 1 = ∞ x_1=\infty x 1 = ∞ .
Beyond x ∗ x^* x ∗ the function v d v_{\mathrm{d}} v d is not elementary, since (30) is an integro-differential equation of Volterra type. One differentiation, however, removes the integral and leaves two quadratures of functions that are already known.
Proposition 4.7 (Quadratures for a 2 \mathbf{a}_2 a 2 and b 2 \mathbf{b}_2 b 2 ). In A 2 A_2 A 2 and in B 2 B_2 B 2 put Θ ( y ) : = ∫ y 1 C ( 1 / s ) d s \Theta(y):=\int_y^1 C(1/s)\,\mathrm{d}s Θ ( y ) := ∫ y 1 C ( 1/ s ) d s for 0 < y ≤ 1 0<y\leq1 0 < y ≤ 1 , and K : = − x ∗ e x ∗ v d ′ ( x ∗ ) K:=-x^*e^{x^*}v_{\mathrm{d}}'(x^*) K := − x ∗ e x ∗ v d ′ ( x ∗ ) . For x > x ∗ x>x^* x > x ∗
( x e x v d ′ ( x ) ) ′ = Θ ( β 1 ( x ) x ) , (32) \left(xe^xv_{\mathrm{d}}'(x)\right)'=\Theta\left(\frac{\beta_1(x)}{x}\right), \tag*{(32)} ( x e x v d ′ ( x ) ) ′ = Θ ( x β 1 ( x ) ) , (32) and
v ( ∞ ) = R ( x ∗ ) + ∫ x ∗ ∞ Θ ( β 1 ( s ) s ) J 1 ( s ) d s , R ( x ∗ ) = Q ( x ∗ , 1 ) − K J 1 ( x ∗ ) , (33) v(\infty)=R(x^*)+\int_{x^*}^{\infty}\Theta\left(\frac{\beta_1(s)}{s}\right)J_1(s)\,\mathrm{d}s,\qquad R(x^*)=Q(x^*,1)-KJ_1(x^*), \tag*{(33)} v ( ∞ ) = R ( x ∗ ) + ∫ x ∗ ∞ Θ ( s β 1 ( s ) ) J 1 ( s ) d s , R ( x ∗ ) = Q ( x ∗ , 1 ) − K J 1 ( x ∗ ) , (33) where R ( x ∗ ) R(x^*) R ( x ∗ ) is the loss of the record rule R b R_{\mathrm{b}} R b with b = x ∗ b=x^* b = x ∗ , and K = 1 2 x ∗ 2 e x ∗ K=\frac{1}{2}x^{*2}e^{x^*} K = 2 1 x ∗ 2 e x ∗ in A 2 A_2 A 2 , K = 2 e x ∗ − x ∗ 2 − 2 x ∗ − 2 K=2e^{x^*}-x^{*2}-2x^*-2 K = 2 e x ∗ − x ∗ 2 − 2 x ∗ − 2 in B 2 B_2 B 2 .
Proof. Multiply (30) by x x x and differentiate, which is allowed by Proposition 4.6 . For x > x ∗ x>x^* x > x ∗ the integrand min { Q ( ξ , 1 ) , v ( ξ , x ) } \min\{Q(\xi,1),v(\xi,x)\} min { Q ( ξ , 1 ) , v ( ξ , x )} equals Q ( ξ , 1 ) Q(\xi,1) Q ( ξ , 1 ) for ξ ≤ β 1 ( x ) \xi\leq\beta_1(x) ξ ≤ β 1 ( x ) and v ( ξ , x ) v(\xi,x) v ( ξ , x ) above; it is continuous at ξ = β 1 ( x ) \xi=\beta_1(x) ξ = β 1 ( x ) and equals v d ( x ) v_{\mathrm{d}}(x) v d ( x ) at ξ = x \xi=x ξ = x . Hence
( x v d ′ ) ′ + ( x v d ′ ) ′ = v d ( x ) + ∫ β 1 ( x ) x ∂ 2 v ( ξ , x ) d ξ . (xv_{\mathrm{d}}')'+(xv_{\mathrm{d}}')'=v_{\mathrm{d}}(x)+\int_{\beta_1(x)}^x\partial_2v(\xi,x)\,\mathrm{d}\xi. ( x v d ′ ) ′ + ( x v d ′ ) ′ = v d ( x ) + ∫ β 1 ( x ) x ∂ 2 v ( ξ , x ) d ξ .
For x ≥ x ∗ x\geq x^* x ≥ x ∗ every state ( ξ , x ) (\xi,x) ( ξ , x ) with ξ < x \xi<x ξ < x lies above the rank-2 boundary. Indeed, by Lemma 4.2 and Proposition 4.3 we have β 2 ( ξ ) ≤ β 2 ( 0 ) \beta_2(\xi)\leq\beta_2(0) β 2 ( ξ ) ≤ β 2 ( 0 ) for ξ < γ \xi<\gamma ξ < γ , and there is no boundary for ξ ≥ γ \xi\geq\gamma ξ ≥ γ ; and β 2 ( 0 ) < x ∗ \beta_2(0)<x^* β 2 ( 0 ) < x ∗ : in A 2 A_2 A 2 the increasing function ( 1 + b ) e b (1+b)e^b ( 1 + b ) e b equals 3 at b A b_A b A and 5 at x ∗ x^* x ∗ , and in B 2 B_2 B 2 the increasing function J 2 J_2 J 2 equals 1 at b B b_B b B and x ∗ + 1 2 > 1 x^*+\frac{1}{2}>1 x ∗ + 2 1 > 1 at x ∗ x^* x ∗ (here x ∗ > 1 2 x^*>\frac{1}{2} x ∗ > 2 1 , because J 2 ( x ) − x − 1 2 J_2(x)-x-\frac{1}{2} J 2 ( x ) − x − 2 1 is increasing and negative at x = 1 2 x=\frac{1}{2} x = 2 1 , where J 2 ( 1 2 ) = 0.5702 J_2(\frac{1}{2})=0.5702 J 2 ( 2 1 ) = 0.5702 ). So no 2-record is acceptable in these states, and (28) gives ∂ 2 v ( ξ , x ) = C ( x / ξ ) e − x / x \partial_2v(\xi,x)=C(x/\xi)e^{-x/x} ∂ 2 v ( ξ , x ) = C ( x / ξ ) e − x / x for all ξ < x \xi<x ξ < x . With ξ = s x \xi=sx ξ = s x the integral equals e − x Θ ( β 1 ( x ) / x ) e^{-x}\Theta(\beta_1(x)/x) e − x Θ ( β 1 ( x ) / x ) . This is ( x v d ′ ) ′ + x v d ′ = e − x Θ (xv_{\mathrm{d}}')'+xv_{\mathrm{d}}'=e^{-x}\Theta ( x v d ′ ) ′ + x v d ′ = e − x Θ , that is (32) . Integrating from x ∗ x^* x ∗ gives
x e x v d ′ ( x ) = − K + ∫ x ∗ x Θ ( β 1 ( s ) s ) d s . xe^xv_{\mathrm{d}}'(x)=-K+\int_{x^*}^x\Theta\left(\frac{\beta_1(s)}{s}\right)\,\mathrm{d}s. x e x v d ′ ( x ) = − K + ∫ x ∗ x Θ ( s β 1 ( s ) ) d s .
On [ 0 , x ∗ ] [0,x^*] [ 0 , x ∗ ] the function v d v_{\mathrm{d}} v d is the function G G G of the record rule, so v d ( x ∗ ) = Q ( x ∗ , 1 ) v_{\mathrm{d}}(x^*)=Q(x^*,1) v d ( x ∗ ) = Q ( x ∗ , 1 ) and, by Proposition 3.1, R ( x ∗ ) = G ( x ∗ ) + x ∗ e x ∗ J 1 ( x ∗ ) G ′ ( x ∗ ) = Q ( x ∗ , 1 ) − K J 1 ( x ∗ ) R(x^*)=G(x^*)+x^*e^{x^*}J_1(x^*)G'(x^*)=Q(x^*,1)-KJ_1(x^*) R ( x ∗ ) = G ( x ∗ ) + x ∗ e x ∗ J 1 ( x ∗ ) G ′ ( x ∗ ) = Q ( x ∗ , 1 ) − K J 1 ( x ∗ ) . Finally v ( ∞ ) = v d ( x ∗ ) + ∫ x ∗ ∞ v d ′ ( x ) d x v(\infty)=v_{\mathrm{d}}(x^*)+\int_{x^*}^{\infty}v_{\mathrm{d}}'(x)\,\mathrm{d}x v ( ∞ ) = v d ( x ∗ ) + ∫ x ∗ ∞ v d ′ ( x ) d x ; inserting v d ′ v_{\mathrm{d}}' v d ′ , dividing by x e x xe^x x e x and exchanging the order of integration in the double integral (the function Θ \Theta Θ is bounded) gives (33) . The values of K K K follow from v d ( x ) = 1 2 + x 2 + 5 2 e − x v_{\mathrm{d}}(x)=\frac{1}{2}+\frac{x}{2}+\frac{5}{2}e^{-x} v d ( x ) = 2 1 + 2 x + 2 5 e − x in A 2 A_2 A 2 with ( 1 + x ∗ ) e x ∗ = 5 (1+x^*)e^{x^*}=5 ( 1 + x ∗ ) e x ∗ = 5 , and from v d ( x ) = 1 − e − x ( 2 J 2 ( x ) − x ) v_{\mathrm{d}}(x)=1-e^{-x}(2J_2(x)-x) v d ( x ) = 1 − e − x ( 2 J 2 ( x ) − x ) in B 2 B_2 B 2 with J 2 ( x ∗ ) = x ∗ + 1 2 J_2(x^*)=x^*+\frac{1}{2} J 2 ( x ∗ ) = x ∗ + 2 1 . ▫
Since C < 0 C<0 C < 0 , the optimal value is the loss of the record rule with b = x ∗ b=x^* b = x ∗ plus a negative integral. The numbers are
with K = 1.146846 K=1.146846 K = 1.146846 in A2 _2 2 and K = 0.842425 K=0.842425 K = 0.842425 in B2 _2 2 . In A2 _2 2 the function C C C is used in its parametric form (§ 5 ); in B2 _2 2 it is tabulated, and Θ \Theta Θ is computed from the table, so b 2 b_2 b 2 is obtained to six digits. The weight β 1 ( s ) \beta_1(s) β 1 ( s ) is itself a root of the balance equation with v d v_d v d and C C C on [ 0 , x ∗ ] [0,x^*] [ 0 , x ∗ ] only. The values for x 1 > x ∗ x_1>x^* x 1 > x ∗ are not the analytic continuation of the formula valid for x 1 < x ∗ x_1<x^* x 1 < x ∗ : in the ray representation (12) the bend of β 1 \beta_1 β 1 at x ∗ x^* x ∗ enters through the ray point r = x ∗ / x 1 r=x^*/x_1 r = x ∗ / x 1 .
Problem A2
Here Q ( ξ , 1 ) = 1 + ξ Q(\xi,1)=1+\xi Q ( ξ , 1 ) = 1 + ξ , Q ( ξ , 2 ) = 2 + ξ Q(\xi,2)=2+\xi Q ( ξ , 2 ) = 2 + ξ , Q ∞ = 3 Q_\infty=3 Q ∞ = 3 , and q ( i ) = min ( i , 3 ) q(i)=\min(i,3) q ( i ) = min ( i , 3 ) . Lemma 4.4 gives v ( x 1 , x 2 ) ≥ 1 + e − x 1 + e − x 2 v(x_1,x_2)\ge1+e^{-x_1}+e^{-x_2} v ( x 1 , x 2 ) ≥ 1 + e − x 1 + e − x 2 . A record of level ξ < x 1 \xi<x_1 ξ < x 1 is acceptable provided 1 + ξ ≤ v ( ξ , x 1 ) 1+\xi\le v(\xi,x_1) 1 + ξ ≤ v ( ξ , x 1 ) , which is guaranteed if 1 + ξ ≤ 1 + e − ξ + e − x 1 1+\xi\le1+e^{-\xi}+e^{-x_1} 1 + ξ ≤ 1 + e − ξ + e − x 1 ; this holds for all ξ < x 1 ≤ L A \xi<x_1\le L_A ξ < x 1 ≤ L A , where L A = 0.8526 … L_A=0.8526\ldots L A = 0.8526 … is the root of x e x = 2 xe^x=2 x e x = 2 (the worst case being ξ = x 1 \xi=x_1 ξ = x 1 ).
Theorem 5.1. On R ∩ { x 1 ≤ L A } \mathcal{R}\cap\{x_1\le L_A\} R ∩ { x 1 ≤ L A }
v ( x 1 , x 2 ) = 3 2 + x 2 2 − x 1 x 2 + ( 3 2 + x 1 x 2 ) e − x 2 . (34) v(x_1,x_2)=\frac{3}{2}+\frac{x_2}{2}-\frac{x_1}{x_2}+\left(\frac{3}{2}+\frac{x_1}{x_2}\right)e^{-x_2}. \tag*{(34)} v ( x 1 , x 2 ) = 2 3 + 2 x 2 − x 2 x 1 + ( 2 3 + x 2 x 1 ) e − x 2 . (34)
The diagonal point is γ = 0.388925 … \gamma=0.388925\ldots γ = 0.388925 … , which is the root of ( 3 + γ ) e γ = 5 (3+\gamma)e^\gamma=5 ( 3 + γ ) e γ = 5 , so R ⊂ { x 1 ≤ L A } \mathcal{R}\subset\{x_1\le L_A\} R ⊂ { x 1 ≤ L A } . The rank-2 boundary is the curve x 1 = φ ( x 2 ) x_1=\varphi(x_2) x 1 = φ ( x 2 ) for
φ ( x 2 ) = x 2 ( 3 − ( 1 + x 2 ) e x 2 ) 2 ( e x 2 − 1 ) , γ ≤ x 2 ≤ b A , (35) \varphi(x_2)=\frac{x_2\left(3-(1+x_2)e^{x_2}\right)}{2(e^{x_2}-1)},\qquad\gamma\le x_2\le b_A, \tag*{(35)} φ ( x 2 ) = 2 ( e x 2 − 1 ) x 2 ( 3 − ( 1 + x 2 ) e x 2 ) , γ ≤ x 2 ≤ b A , (35)
which starts at the point ( 0 , b A ) (0,b_A) ( 0 , b A ) of the edge x 1 = 0 x_1=0 x 1 = 0 , b A = 0.617642 … b_A=0.617642\ldots b A = 0.617642 … , and ends at the diagonal point ( γ , γ ) (\gamma,\gamma) ( γ , γ ) ; as x 2 x_2 x 2 decreases from b A b_A b A to γ \gamma γ , φ ( x 2 ) \varphi(x_2) φ ( x 2 ) increases from 0 0 0 to γ \gamma γ . Equivalently, the boundary point on the ray x 2 = κ x 1 x_2=\kappa x_1 x 2 = κ x 1 is the root x 2 x_2 x 2 of κ = 2 ( e x 2 − 1 ) / ( 3 − ( 1 + x 2 ) e x 2 ) \kappa=2(e^{x_2}-1)/(3-(1+x_2)e^{x_2}) κ = 2 ( e x 2 − 1 ) / ( 3 − ( 1 + x 2 ) e x 2 ) , which is a strictly increasing function of x 2 x_2 x 2 from κ = 1 \kappa=1 κ = 1 at x 2 = γ x_2=\gamma x 2 = γ to κ = ∞ \kappa=\infty κ = ∞ at x 2 = b A x_2=b_A x 2 = b A .
Proof. On this set (25) holds with the right-hand side
∫ 0 x 1 ( 1 + ξ ) d ξ + ∫ x 1 x 2 ( 2 + ξ ) d ξ = 2 x 2 − x 1 + 1 2 x 2 2 . \int_0^{x_1}(1+\xi)\,\mathrm{d}\xi+\int_{x_1}^{x_2}(2+\xi)\,\mathrm{d}\xi=2x_2-x_1+\frac{1}{2}x_2^2. ∫ 0 x 1 ( 1 + ξ ) d ξ + ∫ x 1 x 2 ( 2 + ξ ) d ξ = 2 x 2 − x 1 + 2 1 x 2 2 .
For f ( s ) = v ( s , κ s ) f(s)=v(s,\kappa s) f ( s ) = v ( s , κ s ) this is f ′ + κ f = 2 κ − 1 + 1 2 κ 2 s f'+\kappa f=2\kappa-1+\frac{1}{2}\kappa^2s f ′ + κ f = 2 κ − 1 + 2 1 κ 2 s , f ( 0 ) = 3 f(0)=3 f ( 0 ) = 3 , whence
f ( s ) = 3 2 − 1 κ + κ s 2 + ( 3 2 + 1 κ ) e − κ s , f(s)=\frac{3}{2}-\frac{1}{\kappa}+\frac{\kappa s}{2}+\left(\frac{3}{2}+\frac{1}{\kappa}\right)e^{-\kappa s}, f ( s ) = 2 3 − κ 1 + 2 κ s + ( 2 3 + κ 1 ) e − κ s ,
which is (34) with x 2 = κ s x_2=\kappa s x 2 = κ s , x 1 / x 2 = 1 / κ x_1/x_2=1/\kappa x 1 / x 2 = 1/ κ . The balance equation (23) , 2 + x 2 = v ( x 1 , x 2 ) 2+x_2=v(x_1,x_2) 2 + x 2 = v ( x 1 , x 2 ) , becomes
1 + x 2 2 + x 1 x 2 = ( 3 2 + x 1 x 2 ) e − x 2 , \frac{1+x_2}{2}+\frac{x_1}{x_2}=\left(\frac{3}{2}+\frac{x_1}{x_2}\right)e^{-x_2}, 2 1 + x 2 + x 2 x 1 = ( 2 3 + x 2 x 1 ) e − x 2 ,
which is solved for x 1 x_1 x 1 by (35) . At x 2 = b A x_2=b_A x 2 = b A we have ( 1 + x 2 ) e x 2 = 3 (1+x_2)e^{x_2}=3 ( 1 + x 2 ) e x 2 = 3 and φ = 0 \varphi=0 φ = 0 . On the diagonal v ( x , x ) = 1 2 + x 2 + 5 2 e − x v(x,x)=\frac{1}{2}+\frac{x}{2}+\frac{5}{2}e^{-x} v ( x , x ) = 2 1 + 2 x + 2 5 e − x , and the difference Q ( x , 2 ) − v ( x , x ) = 3 2 + x 2 − 5 2 e − x Q(x,2)-v(x,x)=\frac{3}{2}+\frac{x}{2}-\frac{5}{2}e^{-x} Q ( x , 2 ) − v ( x , x ) = 2 3 + 2 x − 2 5 e − x vanishes exactly when ( 3 + x ) e x = 5 (3+x)e^x=5 ( 3 + x ) e x = 5 , at γ ∗ = 0.388925 … < L A \gamma_* =0.388925\ldots<L_A γ ∗ = 0.388925 … < L A . At x = L A x=L_A x = L A the difference equals 0.86 0.86 0.86 . Let γ \gamma γ be as in Lemma 4.2 . If γ > L A \gamma>L_A γ > L A , then the diagonal states with x ≤ L A x\le L_A x ≤ L A lie in R \mathcal{R} R , where (34) holds, and the difference would be positive at L A L_A L A and hence have its zero below L A L_A L A , a contradiction. So γ ≤ L A \gamma\le L_A γ ≤ L A , (34) holds up to the diagonal point, and γ = γ ∗ \gamma=\gamma_* γ = γ ∗ by uniqueness of the zero. □ \square □
The closed form agrees on the edge with v ( 0 , x ) = 1 + G ( x ) v(0,x)=1+G(x) v ( 0 , x ) = 1 + G ( x ) , as it should by Proposition 4.3. For the continuation region (34) gives the function C C C in a parametric form: at the boundary point ( x 1 , x 2 ) = ( φ ( x 2 ) , x 2 ) (x_1,x_2)=(\varphi(x_2),x_2) ( x 1 , x 2 ) = ( φ ( x 2 ) , x 2 ) we have κ = x 2 / φ \kappa=x_2/\varphi κ = x 2 / φ and
C ( κ ) = x 2 e x 2 ( 1 2 + φ x 2 2 ) − x 2 ( 3 2 + φ x 2 + φ x 2 2 ) . C(\kappa)=x_2e^{x_2}\left(\frac{1}{2}+\frac{\varphi}{x_2^2}\right)-x_2\left(\frac{3}{2}+\frac{\varphi}{x_2}+\frac{\varphi}{x_2^2}\right). C ( κ ) = x 2 e x 2 ( 2 1 + x 2 2 φ ) − x 2 ( 2 3 + x 2 φ + x 2 2 φ ) .
which tends to − K A -K_A − K A as x 2 → b A x_2\to b_A x 2 → b A .
The diagonal and the rank-1 boundary. As long as all records are acceptable, (30) is linear and its solution is the same as on R \mathcal{R} R , which is v d ( x ) = 1 2 + x 2 + 5 2 e − x v_d(x)=\frac{1}{2}+\frac{x}{2}+\frac{5}{2}e^{-x} v d ( x ) = 2 1 + 2 x + 2 5 e − x . The balance equation (31) , 1 + x = v d ( x ) 1+x=v_d(x) 1 + x = v d ( x ) , is ( 1 + x ) e x = 5 (1+x)e^x=5 ( 1 + x ) e x = 5 , with the root x ∗ = 0.944456 … x^*=0.944456\ldots x ∗ = 0.944456 … (this is also the hyperbola constant of the record rule with Q ∞ = 3 Q_\infty=3 Q ∞ = 3 ). The rank-1 boundary is the root of 1 + β 1 = v d ( β 1 ) + ∫ 0 x 2 C ( ξ / β 1 ) e − ξ ξ − 1 d ξ 1+\beta_1=v_d(\beta_1)+\int_0^{x_2}C(\xi/\beta_1)e^{-\xi}\xi^{-1}\,d\xi 1 + β 1 = v d ( β 1 ) + ∫ 0 x 2 C ( ξ / β 1 ) e − ξ ξ − 1 d ξ with x 2 x_2 x 2 in place of x 1 x_1 x 1 ; for x 2 → ∞ x_2\to\infty x 2 → ∞ it gives the initial threshold H 0 = β 1 ( ∞ ) = 0.90169 H_0=\beta_1(\infty)=0.90169 H 0 = β 1 ( ∞ ) = 0.90169 , the root of the balance equation 1 + H 0 = v ( H 0 , ∞ ) 1+H_0=v(H_0,\infty) 1 + H 0 = v ( H 0 , ∞ ) of the arrival at time 0.
By Proposition 4.7 the value is a 2 = 1.654341 … a_2=1.654341\ldots a 2 = 1.654341 … ; § 8 gives independent checks. For comparison, consider the record rule R b R_b R b of § 3 , which stops at the first record below the hyperbola x = b / t ˉ x=b/\bar{t} x = b / t ˉ and never accepts a 2-record. With Q ( ξ , 1 ) = 1 + ξ Q(\xi,1)=1+\xi Q ( ξ , 1 ) = 1 + ξ and Q ∞ = 3 Q_\infty=3 Q ∞ = 3 , its best constant b b b is the root of the balance equation Q ( b , 1 ) = G ( b ) Q(b,1)=G(b) Q ( b , 1 ) = G ( b ) , which is ( 1 + b ) e b = 5 (1+b)e^b=5 ( 1 + b ) e b = 5 , that is b = 0.944456 … ( = x ∗ ) b=0.944456\ldots(=x^*) b = 0.944456 … ( = x ∗ ) , and the expected loss is 1.668057 by Proposition 3.1. The optimal rule in A 2 A_2 A 2 improves on this only by 0.8%, which is the integral in (33) divided by a 2 a_2 a 2 .
Remark 5.2 (A m A_m A m where every rank is kept). Let the state be x 1 < ⋯ < x m x_1<\cdots<x_m x 1 < ⋯ < x m in A m A_m A m and put S = x 1 + ⋯ + x m − 1 S=x_1+\cdots+x_{m-1} S = x 1 + ⋯ + x m − 1 . On the set of states where an arrival of every initial rank i ≤ m i\le m i ≤ m is acceptable, equation (13) is linear,
∑ i = 1 m x i ∂ i v + x m v = ∑ j = 1 m ∫ x j − 1 x j ( j + ξ ) d ξ = 1 2 x m 2 + m x m − S , x 0 : = 0. \sum_{i=1}^{m}x_i\partial_i v+x_m v=\sum_{j=1}^{m}\int_{x_{j-1}}^{x_j}(j+\xi)\,d\xi=\frac{1}{2}x_m^2+mx_m-S,\qquad x_0:=0. i = 1 ∑ m x i ∂ i v + x m v = j = 1 ∑ m ∫ x j − 1 x j ( j + ξ ) d ξ = 2 1 x m 2 + m x m − S , x 0 := 0.
and its solution with v ( 0 ) = m + 1 v(0)=m+1 v ( 0 ) = m + 1 is
v ( x ) = x m + 2 m − 1 2 − S x m + e − x m ( 3 2 + S x m ) . v(x)=\frac{x_m+2m-1}{2}-\frac{S}{x_m}+e^{-x_m}\left(\frac{3}{2}+\frac{S}{x_m}\right). v ( x ) = 2 x m + 2 m − 1 − x m S + e − x m ( 2 3 + x m S ) .
For m = 2 m=2 m = 2 this is (34) . The lower levels enter through their sum only. The balance for the rank m m m , Q ( x m , m ) = v ( x ) Q(x_m,m)=v(x) Q ( x m , m ) = v ( x ) , becomes S = φ ( x m ) S=\varphi(x_m) S = φ ( x m ) with the function φ \varphi φ of (35) , the same for every m m m . This surface reaches the corner x 1 = ⋯ = x m x_1=\cdots=x_m x 1 = ⋯ = x m of the state space at the root of ( x + 2 m − 1 ) e x = 2 m + 1 (x+2m-1)e^x=2m+1 ( x + 2 m − 1 ) e x = 2 m + 1 , which is γ \gamma γ for m = 2 m=2 m = 2 , and 0.2817, 0.2203 for m = 3 , 4 m=3,4 m = 3 , 4 , respectively. With all levels equal to x x x the formula is the function G ( x ) = x + 1 2 + 2 m + 1 2 e − x G(x)=\frac{x+1}{2}+\frac{2m+1}{2}e^{-x} G ( x ) = 2 x + 1 + 2 2 m + 1 e − x of the record rule. The set where every rank is acceptable contains a neighbourhood of the origin, where v v v is close to m + 1 m+1 m + 1 and the loss of stopping is at most m + ξ m+\xi m + ξ ; for m ≥ 3 m\ge3 m ≥ 3 we have not determined how far it extends, and the formula is claimed only there. For m = 3 m=3 m = 3 the method of Proposition 4.7 does not give a 3 a_3 a 3 by quadratures, because the unknown is a function of two variables (the value on the states with x 2 = x 3 x_2=x_3 x 2 = x 3 ); numerically a 3 = 1.7677 a_3=1.7677 a 3 = 1.7677 , against 1.80407 for the record rule R b R_b R b , b = 1.1708 b=1.1708 b = 1.1708 the root of ( 1 + b ) e b = 7 (1+b)e^b=7 ( 1 + b ) e b = 7 .
Problem B2
The problem B2 _2 2 has a very similar structure. Here Q ( ξ , 1 ) = 1 − e − ξ ( 1 + ξ ) Q(\xi,1)=1-e^{-\xi}(1+\xi) Q ( ξ , 1 ) = 1 − e − ξ ( 1 + ξ ) , Q ( ξ , 2 ) = 1 − e − ξ Q(\xi,2)=1-e^{-\xi} Q ( ξ , 2 ) = 1 − e − ξ , Q ∞ = 1 Q_\infty=1 Q ∞ = 1 , and q ( i ) = 1 ( i > 2 ) q(i)=1(i>2) q ( i ) = 1 ( i > 2 ) . Lemma 4.4 gives v ( x 1 , x 2 ) ≥ e − x 2 v(x_1,x_2)\ge e^{-x_2} v ( x 1 , x 2 ) ≥ e − x 2 . A record of level ξ < x 1 \xi<x_1 ξ < x 1 is acceptable as soon as Q ( ξ , 1 ) ≤ e − x 1 Q(\xi,1)\le e^{-x_1} Q ( ξ , 1 ) ≤ e − x 1 , which holds for all ξ < x 1 ≤ L B \xi<x_1\le L_B ξ < x 1 ≤ L B , where L B = 1.1462 … L_B=1.1462\ldots L B = 1.1462 … is the root of ( 2 + L ) e − L = 1 (2+L)e^{-L}=1 ( 2 + L ) e − L = 1 .
Theorem 6.1. On R ∩ { x 1 ≤ L B } \mathcal{R} \cap\{x_1 \le L_{\mathrm{B}}\} R ∩ { x 1 ≤ L B } the value is v = 1 − Ψ v = 1 - \Psi v = 1 − Ψ , where
Ψ ( x 1 , x 2 ) = e − x 2 [ 2 J 2 ( x 2 ) − J 2 ( x 2 − x 1 ) − x 1 x 2 − x 1 ( e x 2 − x 1 − 1 ) ] . (36) \Psi(x_1,x_2)=e^{-x_2}\left[2J_2(x_2)-J_2(x_2-x_1)-\frac{x_1}{x_2-x_1}\left(e^{x_2-x_1}-1\right)\right]. \tag*{(36)} Ψ ( x 1 , x 2 ) = e − x 2 [ 2 J 2 ( x 2 ) − J 2 ( x 2 − x 1 ) − x 2 − x 1 x 1 ( e x 2 − x 1 − 1 ) ] . (36) The diagonal point is γ = 0.705926 … \gamma=0.705926\ldots γ = 0.705926 … , the root of 2 J 2 ( γ ) − γ = 1 2J_2(\gamma)-\gamma=1 2 J 2 ( γ ) − γ = 1 , and R ⊂ { x 1 ≤ L B } \mathcal{R}\subset\{x_1\le L_{\mathrm{B}}\} R ⊂ { x 1 ≤ L B } . The rank-2 boundary x 2 = β 2 ( x 1 ) x_2=\beta_2(x_1) x 2 = β 2 ( x 1 ) is given by the balance equation Ψ ( x 1 , x 2 ) = e − x 2 \Psi(x_1,x_2)=e^{-x_2} Ψ ( x 1 , x 2 ) = e − x 2 , that is, with w = x 2 − x 1 w=x_2-x_1 w = x 2 − x 1 ,
2 J 2 ( x 2 ) − J 2 ( w ) − x 2 − w w ( e w − 1 ) = 1 , (37) 2J_2(x_2)-J_2(w)-\frac{x_2-w}{w}\left(e^w-1\right)=1, \tag*{(37)} 2 J 2 ( x 2 ) − J 2 ( w ) − w x 2 − w ( e w − 1 ) = 1 , (37) which gives β 2 ( 0 ) = b B = 0.804352 … \beta_2(0)=b_{\mathrm{B}}=0.804352\ldots β 2 ( 0 ) = b B = 0.804352 … (at w = x 2 w=x_2 w = x 2 , where it reduces to J 2 ( x 2 ) = 1 J_2(x_2)=1 J 2 ( x 2 ) = 1 ) and the diagonal point x 2 = γ x_2=\gamma x 2 = γ at w → 0 w\to0 w → 0 . On the ray x 2 = κ x 1 x_2=\kappa x_1 x 2 = κ x 1 the boundary point is the root x 2 x_2 x 2 of
2 J 2 ( x 2 ) − J 2 ( x 2 κ − 1 κ ) − 1 κ − 1 ( e x 2 ( κ − 1 ) / κ − 1 ) = 1. 2J_2(x_2)-J_2\left(x_2\frac{\kappa-1}{\kappa}\right)-\frac{1}{\kappa-1}\left(e^{x_2(\kappa-1)/\kappa}-1\right)=1. 2 J 2 ( x 2 ) − J 2 ( x 2 κ κ − 1 ) − κ − 1 1 ( e x 2 ( κ − 1 ) / κ − 1 ) = 1.
Proof. On this set the right-hand side of (25) is
∫ 0 x 1 ( 1 − e − ξ ( 1 + ξ ) ) d ξ + ∫ x 1 x 2 ( 1 − e − ξ ) d ξ = x 2 − 2 + ( 1 + x 1 ) e − x 1 + e − x 2 . \int_0^{x_1}\left(1-e^{-\xi}(1+\xi)\right)\,d\xi+\int_{x_1}^{x_2}\left(1-e^{-\xi}\right)\,d\xi=x_2-2+(1+x_1)e^{-x_1}+e^{-x_2}. ∫ 0 x 1 ( 1 − e − ξ ( 1 + ξ ) ) d ξ + ∫ x 1 x 2 ( 1 − e − ξ ) d ξ = x 2 − 2 + ( 1 + x 1 ) e − x 1 + e − x 2 .
For f ( s ) = v ( s , κ s ) f(s)=v(s,\kappa s) f ( s ) = v ( s , κ s ) , equation (25) after multiplication by e κ s / s e^{\kappa s}/s e κ s / s is
( e κ s f ) ′ = e κ s ( κ + − 2 + ( 1 + s ) e − s + e − κ s s ) , e κ s f → 1 ( s → 0 ) . \left(e^{\kappa s}f\right)'=e^{\kappa s}\left(\kappa+\frac{-2+(1+s)e^{-s}+e^{-\kappa s}}{s}\right),\qquad e^{\kappa s}f\to1\quad(s\to0). ( e κ s f ) ′ = e κ s ( κ + s − 2 + ( 1 + s ) e − s + e − κ s ) , e κ s f → 1 ( s → 0 ) .
The right-hand side is integrable at 0; integrating and expressing the result through J 2 J_2 J 2 gives (36) with x 2 = κ s x_2=\kappa s x 2 = κ s , x_1/x_2=1/\kappa. (The substitution of (36) into (25) was also checked numerically, the residual being $10^{-11}, and at x 1 = 0 x_1=0 x 1 = 0 it reduces to 1 − e − x 2 J 2 ( x 2 ) 1-e^{-x_2}J_2(x_2) 1 − e − x 2 J 2 ( x 2 ) of (19).) Letting $x_2\downarrow x_1=x$ gives $v(x,x)=1-e^{-x}(2J_2(x)-x)$, so $Q(x,2)-v(x,x)=e^{-x}(2J_2(x)-x-1)$, whose zero is $\gamma^*=0.7059\ldots<L_{\mathrm{B}}$, and which is positive at $L_{\mathrm{B}}$. As in the proof of Theorem 5.1, {citet}Lemma 4.2` gives γ = γ ∗ \gamma=\gamma^* γ = γ ∗ .
The value is b 2 = 0.19946 … b_2=0.19946\ldots b 2 = 0.19946 … (Proposition 4.7), thus the maximal probability of choosing one of the two best is about 1 − b 2 = 0.80054 1-b_2=0.80054 1 − b 2 = 0.80054 . The function C C C is obtained from (36) as for A 2 A_2 A 2 , with C ( ∞ ) = − K B C(\infty)=-K_{\mathrm{B}} C ( ∞ ) = − K B .
Remark 6.2 (The shape of β 2 \beta_2 β 2 in B 2 \mathrm{B}_2 B 2 ). Put g ( w ) = ( e w − 1 ) / w g(w)=(e^w-1)/w g ( w ) = ( e w − 1 ) / w , so that J 2 ′ = g J'_2=g J 2 ′ = g . Expanding (37) in x 1 x_1 x 1 at fixed x 2 x_2 x 2 , the terms of first order cancel and the equation becomes J 2 ( x 2 ) = 1 − 1 2 x 2 2 g ′ ( x 2 ) + O ( x 1 3 ) J_2(x_2)=1-\frac{1}{2}x_2^2g'(x_2)+O(x_1^3) J 2 ( x 2 ) = 1 − 2 1 x 2 2 g ′ ( x 2 ) + O ( x 1 3 ) . Hence β 2 ( x 1 ) = b B − κ x 1 2 + O ( x 1 3 ) \beta_2(x_1)=b_{\mathrm{B}}-\kappa x_1^2+O(x_1^3) β 2 ( x 1 ) = b B − κ x 1 2 + O ( x 1 3 ) with κ = g ′ ( b B ) / ( 2 g ( b B ) ) = 0.2832 \kappa=g'(b_{\mathrm{B}})/(2g(b_{\mathrm{B}}))=0.2832 κ = g ′ ( b B ) / ( 2 g ( b B )) = 0.2832 : the boundary leaves the edge with zero slope. At the diagonal point the slope is d x 2 / d x 1 = − 0.2273 dx_2/dx_1=-0.2273 d x 2 / d x 1 = − 0.2273 . In A 2 \mathrm{A}_2 A 2 the curve (35) leaves the edge with the slope − 0.5700 -0.5700 − 0.5700 and meets the diagonal with the slope − 0.6065 -0.6065 − 0.6065 .
The diagonal and the rank-1 boundary. As long as all records are acceptable, v d ( x ) = 1 − e − x ( 2 J 2 ( x ) − x ) v_d(x)=1-e^{-x}(2J_2(x)-x) v d ( x ) = 1 − e − x ( 2 J 2 ( x ) − x ) , and the balance equation (31) becomes J 2 ( x ) = x + 1 2 J_2(x)=x+\frac{1}{2} J 2 ( x ) = x + 2 1 , with the root x ∗ = 1.218477 … x^*=1.218477\ldots x ∗ = 1.218477 … . The quadrature for the rank-1 boundary gives the initial threshold H 0 = β 1 ( ∞ ) = 1.0883 … H_0=\beta_1(\infty)=1.0883\ldots H 0 = β 1 ( ∞ ) = 1.0883 … , the root of the balance equation Q ( H 0 , 1 ) = v ( H 0 , ∞ ) Q(H_0,1)=v(H_0,\infty) Q ( H 0 , 1 ) = v ( H 0 , ∞ ) of the arrival at time 0.
Stopping probabilities
Let p i ( x ) p_i(x) p i ( x ) be the probability that the optimal rule started in x x x stops at a i i i -record. It solves the linear version of (22) for the optimal policy of Figure 2 : at an arrival the minimum is replaced by 1 { i = rank } \mathbf{1}\{i=\operatorname{rank}\} 1 { i = rank } if the arrival is acceptable, and by p i p_i p i at the new state otherwise, with the edge conditions p 1 ( 0 , x ) = 0 p_1(0,x)=0 p 1 ( 0 , x ) = 0 and p 2 ( 0 , x ) = 1 − e − x p_2(0,x)=1-e^{-x} p 2 ( 0 , x ) = 1 − e − x for x ≤ b B x\le b_{\mathrm{B}} x ≤ b B , p 2 ( 0 , x ) = 1 − e − b B + b B J 1 ( b B ) − b B J 1 ( x ) p_2(0,x)=1-e^{-b_{\mathrm{B}}}+b_{\mathrm{B}}J_1(b_{\mathrm{B}})-b_{\mathrm{B}}J_1(x) p 2 ( 0 , x ) = 1 − e − b B + b B J 1 ( b B ) − b B J 1 ( x ) for x ≥ b B x\ge b_{\mathrm{B}} x ≥ b B .
Table 2.
The probability of success is 1 − b 2 = 0.8005 1-b_2 = 0.8005 1 − b 2 = 0.8005 , of which 0.7729 comes from records and 0.0276 ± 0.0001 0.0276 \pm0.0001 0.0276 ± 0.0001 from 2-records (simulation). All numbers in this subsection are numerical; the grid solution of the linear equation converges at first order only, because the boundary is located to within one grid step, so its entries are accurate to about 10 − 3 10^{-3} 1 0 − 3 . Thus 2-records account for only 4.6% of the stops. The probability 0.094 is that of τ = 1 \tau= 1 τ = 1 : no suitable arrival occurred.
A sample path of the threshold
Figure 3 shows two realisations of Π \Pi Π with the adaptive threshold ( H t ) (H_t) ( H t ) of the optimal rule, defined as in § 2.4 on the whole interval, with the initial value H 0 = 1.09 H_0 = 1.09 H 0 = 1.09 . It drifts up; when a record arrives above the curve, it jumps up; after a further drift it reaches the lowest score y 1 o y_1^o y 1 o and stays flat there (Proposition 2.7). The rule stops at the first atom below the curve. The 2-record boundary matters only if τ y 1 o < γ = 0.706 \tau y_1^o < \gamma= 0.706 τ y 1 o < γ = 0.706 .
Figure 3. Two realisations of Π \Pi Π (unit intensity; only the atoms with x ≤ 3.5 x \le3.5 x ≤ 3.5 are shown) with the adaptive threshold H t H_t H t (solid) of the optimal rule in B 2 \mathrm{B}_2 B 2 . The first atom below the curve is selected (circled). Between arrivals the threshold drifts up. When a record arrives above the curve (dashed circle), the threshold jumps up (heavy segment) and then rises to the score of this record, where it stays flat. The realisations were chosen to show a jump; the median stopping time among the realisations with a stop is 0.42.
Simple strategies
The optimal rules need tracking the m m m lowest scores to compute an adapted threshold. We compare them with much simpler rules. A strategy which stops at the first atom below a nonrandom curve x = h ( t ) x = h(t) x = h ( t ) is called a memoryless rule [2 , 17 ] . In this section we derive the formulas; the numerical values are collected in § 8 . For Bm _m m we evaluate the *failure probability, the quantity which is minimised; π m ( z ) = P [ Poisson ( z ) ≤ m − 1 ] \pi_m(z) = \mathbb{P}[\operatorname{Poisson}(z) \le m - 1] π m ( z ) = P [ Poisson ( z ) ≤ m − 1 ] denotes the probability of at most m − 1 m - 1 m − 1 atoms in a region of area z z z .
In the rank-information version of choosing one of the m m m best [8 , 10 , 20 ] the failure probability of the optimal rule decays exponentially fast in m m m (see Section 4.1 of [24 ] ), while a rule with a single cutoff, accepting the first atom with initial rank at most m m m arriving after time c = m − 1 / ( m − 1 ) c = m^{-1/(m-1)} c = m − 1/ ( m − 1 ) , has the success probability c c c for m ≥ 2 m \ge2 m ≥ 2 [11 ] (eq. (16), p. 162). For the full-information problem the simple rules below make the failure probability much smaller: e.g. for m = 2 m = 2 m = 2 it is between 0.20 and 0.27, against 0.4264 for the optimal rule with rank information [8 ] and 1 − c = 0.5 1 - c = 0.5 1 − c = 0.5 for the single cutoff; the comparison for m ≤ 5 m \le5 m ≤ 5 is in § 8 . The success probability c c c of the single cutoff is the maximum over the cutoff t t t of the limiting success r ( t − t r ) / ( r − 1 ) r(t - t^r)/(r - 1) r ( t − t r ) / ( r − 1 ) given in (3.2) of [8 ] , with r = m r = m r = m .
The record rule
The record rule R b \mathrm{R}_b R b of § 3 stops at the first record below the hyperbola x = b / t ˉ x = b/\bar{t} x = b / t ˉ ; the atoms of the initial rank above 1 are never accepted, whether or not they are below the hyperbola. For R b \mathrm{R}_b R b with the loss B m B_m B m the computation of § 3 applies verbatim, with g ( ξ ) = Q ( ξ , 1 ) = 1 − π m ( ξ ) g(\xi) = Q(\xi, 1) = 1 - \pi_m(\xi) g ( ξ ) = Q ( ξ , 1 ) = 1 − π m ( ξ ) and Q ∞ = 1 Q_\infty= 1 Q ∞ = 1 : the loss of a record depends on its level only. By Proposition 3.1 the failure probability is G ( b ) + b e b J 1 ( b ) G ′ ( b ) G(b) + be^bJ_1(b)G'(b) G ( b ) + b e b J 1 ( b ) G ′ ( b ) , with G G G defined by (18) . The same applies to A m A_m A m , with g ( ξ ) = 1 + ξ g(\xi) = 1 + \xi g ( ξ ) = 1 + ξ and Q ∞ = m + 1 Q_\infty= m + 1 Q ∞ = m + 1 ; the optimal constant b b b solves the balance equation Q ( b , 1 ) = G ( b ) Q(b, 1) = G(b) Q ( b , 1 ) = G ( b ) , which for A 2 A_2 A 2 is ( 1 + b ) e b = 5 (1 + b)e^b = 5 ( 1 + b ) e b = 5 .
Memoryless rules: a shifted hyperbola
Let h ( t ) = c + b / t ˉ h(t) = c + b/\bar{t} h ( t ) = c + b / t ˉ with b > 0 b > 0 b > 0 , c + b > 0 c + b > 0 c + b > 0 , and let τ \tau τ be the first atom below the curve x = h ( t ) x = h(t) x = h ( t ) , whatever its rank. This is a memoryless rule. The success probability in B m B_m B m is
W m ( c , b ) = ∫ 0 ∞ d x ∫ t x 1 e − c t t b π m ( Λ ( x ) + x t ) d t , W_m(c,b) = \int_0^\infty\mathrm{d}x \int_{t_x}^1 e^{-ct}t^b \pi_m\bigl(\Lambda(x) + xt\bigr)\,\mathrm{d}t, W m ( c , b ) = ∫ 0 ∞ d x ∫ t x 1 e − c t t b π m ( Λ ( x ) + x t ) d t ,
where t x = 0 t_x = 0 t x = 0 , Λ ( x ) = 0 \Lambda(x) = 0 Λ ( x ) = 0 for x ≤ c + b x \le c + b x ≤ c + b , and for x > c + b x > c + b x > c + b
t x = 1 − b x − c , Λ ( x ) = x − c − b − b log x − c b . t_x = 1 - \frac{b}{x-c}, \qquad\Lambda(x) = x - c - b - b\log\frac{x-c}{b}. t x = 1 − x − c b , Λ ( x ) = x − c − b − b log b x − c .
The failure probability is 1 − W m ( c , b ) 1-W_m(c,b) 1 − W m ( c , b ) . Indeed, the first atom below the curve has the density e − c t t ˉ b e^{-ct\bar{t}^{b}} e − c t t ˉ b in d x d t dx\,dt d x d t for x < h ( t ) x<h(t) x < h ( t ) , that is for t > t x t>t_x t > t x , since ∫ 0 t h ( s ) d s = c t − b log t ˉ \int_0^t h(s)\,ds=ct^{-b}\log\bar{t} ∫ 0 t h ( s ) d s = c t − b log t ˉ . The atoms with score below x x x which arrived before t t t are above the curve, in the lens { ( s , y ) : s < t , h ( s ) ≤ y < x } \{(s,y):s<t,\ h(s)\le y<x\} {( s , y ) : s < t , h ( s ) ≤ y < x } of area Λ ( x ) \Lambda(x) Λ ( x ) , and the atoms after t t t below x x x number Poisson( x t ˉ ) (x\bar{t}) ( x t ˉ ) , all independent. The final rank is at most m m m if and only if the total number is at most m − 1 m-1 m − 1 . The case c = 0 c=0 c = 0 is the first atom below b / t ˉ b/\bar{t} b / t ˉ .
Memoryless rules: a constant threshold
For B m B_m B m consider also the constant curve h ( t ) ≡ b h(t)\equiv b h ( t ) ≡ b : the rule stops at the first atom with score below b b b . Since the strip ( 0 , t ) × ( 0 , b ) (0,t)\times(0,b) ( 0 , t ) × ( 0 , b ) is empty at the time t t t of stopping, this atom is a record, and no smaller score has arrived before it. The pair ( t , x ) (t,x) ( t , x ) has the density e − b t d t d x e^{-bt}\,dt\,dx e − b t d t d x on [ 0 , 1 ] × [ 0 , b ] [0,1]\times[0,b] [ 0 , 1 ] × [ 0 , b ] , the box coordinate is ξ = x t ˉ \xi=x\bar{t} ξ = x t ˉ , and with probability e − b e^{-b} e − b no atom arrives and the loss is Q ∞ = 1 Q_\infty=1 Q ∞ = 1 . Thus the failure probability equals G ( b ) G(b) G ( b ) of (18) with g ( ξ ) = Q ( ξ , 1 ) = 1 − π m ( ξ ) g(\xi)=Q(\xi,1)=1-\pi_m(\xi) g ( ξ ) = Q ( ξ , 1 ) = 1 − π m ( ξ ) : this is the same as starting the greedy phase from the state ξ = b \xi=b ξ = b . In closed form,
1 + e − b ( ∑ j = 1 m − 1 ( m − j ) b j j ⋅ j ! − m J 2 ( b ) ) (38) 1+e^{-b}\left(\sum_{j=1}^{m-1}\frac{(m-j)b^j}{j\cdot j!}-mJ_2(b)\right) \tag*{(38)} 1 + e − b ( j = 1 ∑ m − 1 j ⋅ j ! ( m − j ) b j − m J 2 ( b ) ) (38)
where we used the identity ∫ 0 a ( 1 − π m ( z ) ) d z = E ( N a − m ) + = a − m + e − a ∑ j < m ( m − j ) a j / j ! \int_0^a(1-\pi_m(z))\,dz=\mathbb{E}(N_a-m)_+=a-m+e^{-a}\sum_{j<m}(m-j)a^j/j! ∫ 0 a ( 1 − π m ( z )) d z = E ( N a − m ) + = a − m + e − a ∑ j < m ( m − j ) a j / j ! for N a N_a N a Poisson( a ) (a) ( a ) , and then integrated in t t t with s = t ˉ s=\bar{t} s = t ˉ . For m = 1 m=1 m = 1 the expression is 1 − e − b J 2 ( b ) 1-e^{-b}J_2(b) 1 − e − b J 2 ( b ) , which is (20) . The numerical values are in § 8 .
Rank-wise hyperbolas
For m ≥ 2 m\ge2 m ≥ 2 let the rule accept an i i i -record, i ≤ m i\le m i ≤ m , if and only if its box coordinate is below b i b_i b i , that is, below the hyperbola b i / t ˉ b_i/\bar{t} b i / t ˉ . The rule is stationary in box coordinates, and its loss is computed from (13) with the minimum replaced by the policy. For m = 2 m=2 m = 2 this is a two-dimensional problem, and for m = 3 m=3 m = 3 a three-dimensional one (§ 8 ).
Numerical results and comparison
Numerical values are rounded to the last digit shown, and simulated values are given with a standard error.
Computed from the equations. The values a 2 , b 2 a_2,b_2 a 2 , b 2 are given by the quadratures of Proposition 4.7 : a 2 = 1.654341 a_2=1.654341 a 2 = 1.654341 and b 2 = 0.199459 b_2=0.199459 b 2 = 0.199459 (the latter from the tabulated function C C C , to six digits). They were also found by marching the optimality equation (22) in the top component x 2 x_2 x 2 , on a grid x j = x min e k h x_j=x_{\min}e^{kh} x j = x m i n e k h in both coordinates, so that the shrinking x ↦ ( 1 − d t ) x x\mapsto(1-dt)x x ↦ ( 1 − d t ) x is a diagonal shift of the grid; the right side involves v v v only at states with a smaller top component, so no iteration over the free boundaries is needed. With the steps h = 0.01 , 0.005 , 0.0025 h=0.01,0.005,0.0025 h = 0.01 , 0.005 , 0.0025 the observed order is 1.98 1.98 1.98 , and the extrapolation (Aitken) gives a 2 = 1.65435 a_2=1.65435 a 2 = 1.65435 and b 2 = 0.19946 b_2=0.19946 b 2 = 0.19946 , within 2 × 10 − 5 2\times10^{-5} 2 × 1 0 − 5 of the quadratures; a march of the diagonal equation (30) alone gives 1.654341 1.654341 1.654341 for A 2 A_2 A 2 . The scheme reproduces the closed forms (34) and (36) to 8 × 10 − 5 8\times10^{-5} 8 × 1 0 − 5 and 3 × 10 − 6 3\times10^{-6} 3 × 1 0 − 6 , the rank-2 boundary (35) to 10 − 4 10^{-4} 1 0 − 4 , and the rank-1 boundary, given by the quadrature of Section 4, to 3 × 10 − 5 3\times10^{-5} 3 × 1 0 − 5 (A 2 A_2 A 2 ) and 10 − 6 10^{-6} 1 0 − 6 (B 2 B_2 B 2 ); the quadrature also gives H 0 = 0.90169 H_0=0.90169 H 0 = 0.90169 and 1.0883 1.0883 1.0883 . The losses of the rules of Section 7 are values of the integrals there, optimised over the parameters by numerical quadrature and minimisation; all the numerics were done in Python (NumPy, SciPy), and the columns b / t ˉ b/\bar{t} b / t ˉ and constant b b b were recomputed with independent code, which agrees to 10 − 6 10^{-6} 1 0 − 6 ; the formula (38) was also checked by direct numerical integration and, for m = 2 m=2 m = 2 , by simulation. For the rank-wise hyperbolas the march is applied to the policy equation; for m = 3 m=3 m = 3 it is three-dimensional, and the steps 0.04, 0.02, 0.01 with extrapolation give 0.09837 (simulation of the rule, 8 × 10 6 8 \times10^{6} 8 × 1 0 6 paths: 0.0984 ± 0.0001 0.0984 \pm0.0001 0.0984 ± 0.0001 ); this is the computed value of one rule, known to about 10 − 4 10^{-4} 1 0 − 4 , so it bounds b 3 b_3 b 3 only up to this error.
Computed by simulation. The stopping probabilities of § 6 (2.8 × 10 7 2.8 \times10^{7} 2.8 × 1 0 7 trajectories of Π \Pi Π with the optimal rule, with the boundaries β 2 \beta_2 β 2 from (37) and β 1 \beta_1 β 1 from the quadrature), and the sample paths of Figure 3 . In 7 × 10 6 7 \times10^{6} 7 × 1 0 6 simulated realisations the median stopping time of the optimal rule in B 2 B_2 B 2 among the realisations with a stop is 0.422, with the quartiles 0.209 and 0.655; if no stop is counted as τ = 1 \tau=1 τ = 1 the three numbers are 0.467, 0.230 and 0.739. No atom is accepted (τ = 1 \tau=1 τ = 1 ) with the frequency 0.0939 ± 0.0001 0.0939 \pm0.0001 0.0939 ± 0.0001 , in agreement with 0.094 of the linear equation.
Simple strategies. The table gives the failure probabilities for B m B_m B m ; the last column is the optimal value b m b_m b m , which for m = 3 m=3 m = 3 is a numerical estimate, see below.
For m = 3 m=3 m = 3 the optimum of the rule c + b / t ˉ c+b/\bar{t} c + b / t ˉ over ( c , b ) (c,b) ( c , b ) is flat along a ridge. The excess of the best of the single-curve rules of the table over the optimal failure probability is 0%, 7.5% and about 20% for m = 1 , 2 , 3 m=1,2,3 m = 1 , 2 , 3 (the record rule for m = 1 , 2 m=1,2 m = 1 , 2 and the rule c + b / t ˉ c+b/\bar{t} c + b / t ˉ for m = 3 m=3 m = 3 ; the record rule for m = 1 m=1 m = 1 is optimal), and the rank-wise hyperbolas reduce the excess at m = 3 m=3 m = 3 to less than 1%. For m = 2 m=2 m = 2 the optimal rule differs from the record rule by the region of 2-records of Figure 2 and by the rank-1 boundary beyond x ∗ x^* x ∗ , which lies below the constant level x ∗ x^* x ∗ of the record rule; the effect is 0.015; two constants b 1 , b 2 b_1,b_2 b 1 , b 2 recover all of it but 2.5 × 10 − 4 2.5 \times10^{-4} 2.5 × 1 0 − 4 .
Rank information against full information. The following table gives the success probabilities for choosing one of the m m m best. The entries for rank information are limiting values: the single cutoff c = m − 1 / ( m − 1 ) c=m^{-1/(m-1)} c = m − 1/ ( m − 1 ) (the success probability is c c c , see § 7 ) and the optimal rule of [8 ] (Table 1 , success = 1 − Q m =1-Q_m = 1 − Q m ). The entries for full information are one minus the failure probabilities of the memoryless rules (constant b b b and b / t ˉ b/\bar{t} b / t ˉ of this section, with the optimal b b b in brackets), and the optimal values of [19 ] for n = 2500 n=2500 n = 2500 , which we take as the limits.
Table 1.
Table 2 (PDF p. 27).
The full-information optimal entries for m = 4 , 5 m=4,5 m = 4 , 5 are less accurate than for m ≤ 3 m \le3 m ≤ 3 : the grids in [19 ] have 56 and 32 intervals, and the column for m = 5 m=5 m = 5 is not monotone in n n n at n = 750 n=750 n = 750 , so we regard them as reliable to about 10 − 3 10^{-3} 1 0 − 3 only. A change of 10 − 3 10^{-3} 1 0 − 3 in the optimal failure probability moves the two excesses given below for m = 5 m=5 m = 5 over the ranges 149–170% and 53–66%, and those for m = 4 m=4 m = 4 over 105–114% and 43–49%.
The single level b b b is the simplest rule, it uses neither the time nor the history of the scores, and yet its success probability exceeds that of the optimal rule with rank information by 0.153, 0.127, 0.099 and 0.075 for m = 2 , … , 5 m = 2,\ldots,5 m = 2 , … , 5 (the gain shrinks since the rank-information optimum approaches 1 exponentially fast). Compared with the full-information optimum its success probability is lower by 0.074, 0.067, 0.053 and 0.040, which in the failure probability is an excess of 37%, 69%, 110% and 159%, whereas the rule b / t ˉ b/\bar{t} b / t ˉ has the excess of 20%, 32%, 46% and 60% (for m = 2 , … , 5 m = 2,\ldots,5 m = 2 , … , 5 , relative to the entries of [19 ] ; relative to b 2 b_2 b 2 and b 3 b_3 b 3 of the text the excesses for m = 2 , 3 m = 2,3 m = 2 , 3 differ in the first decimal only). For m = 1 m = 1 m = 1 the excess of the single level is 15%. Thus in the examples considered the constant level is attractive for its simplicity, but its relative excess grows with m m m . The rules which use the ranks only through a few constants capture most of the value: the record rule is within 7.5% for m = 2 m = 2 m = 2 and the rank-wise hyperbolas within 1% for m = 2 , 3 m = 2,3 m = 2 , 3 . For A 2 A_2 A 2 the record rule R b R_b R b has the loss 1.668057, against a 2 = 1.65434 a_2 = 1.65434 a 2 = 1.65434 , within 0.8%.
Comparison with the literature. The table compares our values with those of [2 ] for the truncations of Robbins’ problem (A m A_m A m ), and with those of [19 ] for choosing one of the m m m best (B m B_m B m ).
Table 3.
Goldenshluger and Malinovsky [19 ] : The optimal n n n -step success probabilities for the problem of choosing one of the m m m best, computed by the recursion of [19 ] (Table 1 there), are for m = 2 m = 2 m = 2 : 0.8044, 0.8009, 0.8007 at n = 100 , 1000 , 2500 n = 100, 1000, 2500 n = 100 , 1000 , 2500 , for m = 3 m = 3 m = 3 : 0.9026, 0.9025 at n = 1000 , 2500 n = 1000, 2500 n = 1000 , 2500 , for m = 4 m = 4 m = 4 : 0.9517, 0.9513 and for m = 5 m = 5 m = 5 : 0.9758, 0.9750 (four digits). They decrease in n n n like 1 / n 1/n 1/ n (for m = 1 m = 1 m = 1 the entries 0.5804 and 0.5803 at n = 1000 , 2500 n = 1000, 2500 n = 1000 , 2500 against the limit 0.58016). The entries we use are those at n = 2500 n = 2500 n = 2500 , which differ from the limits by O ( 1 / n ) O(1/n) O ( 1/ n ) . The extrapolation gives 0.8005 for m = 2 m = 2 m = 2 , in agreement with 1 − b 2 = 0.80054 1 - b_2 = 0.80054 1 − b 2 = 0.80054 , and 0.9024 ± 0.0002 0.9024 \pm0.0002 0.9024 ± 0.0002 for m = 3 m = 3 m = 3 , that is b 3 = 0.0976 ± 0.0002 b_3 = 0.0976 \pm0.0002 b 3 = 0.0976 ± 0.0002 (the entry 0.9025 at n = 2500 n = 2500 n = 2500 is slightly above the limit). An independent dynamic program of ours for B n , 3 B_{n,3} B n , 3 (the three lowest scores on a grid, extrapolated in the grid size; checked with three grid shapes) gives the values 0.09056, 0.09422, 0.09605 at n = 50 , 100 , 200 n = 50, 100, 200 n = 50 , 100 , 200 , whose increments halve, hence b 3 = 0.0979 ± 0.0002 b_3 = 0.0979 \pm0.0002 b 3 = 0.0979 ± 0.0002 . The two estimates differ by 3 × 10 − 4 3 \times10^{-4} 3 × 1 0 − 4 ; we state b 3 ≈ 0.098 b_3 \approx0.098 b 3 ≈ 0.098 , and the percentages for m = 3 m = 3 m = 3 above are accurate to one unit. For m = 4 , 5 m = 4,5 m = 4 , 5 the grids of [19 ] are coarse (see above), and we use the entries at n = 2500 n = 2500 n = 2500 without extrapolation.
Bruss and Ferguson [2 ] : The values W ( m ) W^{(m)} W ( m ) of [2 ] (Section 4, Table 3) are extrapolated from the optimal n n n -step values for n ≤ 17 n \le17 n ≤ 17 ; a 1 a_1 a 1 is confirmed to the three digits given. For A 2 A_2 A 2 the discrepancy is 0.0037 (0.2%). Since the finite-n n n values increase with n n n and are bounded by a 2 a_2 a 2 , a value above a 2 a_2 a 2 can only come from an overshoot of the extrapolation. To check this independently we computed the exact n n n -step dynamic program for the loss min ( i , 3 ) + ( n − k ) X k \min(i,3)+(n-k)X_k min ( i , 3 ) + ( n − k ) X k , with the state the two lowest scores, on grids of 1500 and 3000 points (the program reproduces the values V 2 = 1.25 V_2 = 1.25 V 2 = 1.25 and V 3 = 1.3915 V_3 = 1.3915 V 3 = 1.3915 of the rank loss). The values for n = 50 , 100 , 200 n = 50, 100, 200 n = 50 , 100 , 200 are 1.638947, 1.646645, 1.650495 (Richardson-extrapolated in the grid size), the differences decrease by the factor 2, and the Richardson extrapolations 2 W 2 n − W n 2W_{2n} - W_n 2 W 2 n − W n are 1.654343 and 1.654345, in agreement with a 2 = 1.65434 a_2 = 1.65434 a 2 = 1.65434 and not with 1.658. For m = 3 m = 3 m = 3 the value 1.782 of [2 ] is 0.014 above our a 3 = 1.7677 a_3 = 1.7677 a 3 = 1.7677 , which is supported by three computations of different kinds (agreeing to 10 − 6 10^{-6} 1 0 − 6 ) and by an independent finite-n n n program (1.7675 ± \pm ± 0.0005).