OPTIMAL RULES FOR THE SEQUENTIAL SELECTION

OF MONOTONE SUBSEQUENCES OF

MAXIMUM EXPECTED LENGTH.

F. THOMAS BRUSS and FREDDY DELBAEN

Université Libre de Bruxelles and Eidgenössische Technische Hochschule Zürich

Summary: This article presents new results on the problem of selecting (online) a monotone subsequence of maximum expected length from a sequence of i.i.d. random variables. We study the case where the variables are observed sequentially at the occurrence times of a Poisson process with known rate. Our approach is a detailed study of the integral equation which determines v(t), the expected number (under the optimal strategy for time horizon t) of selected points L_{t}^{t} up to time t. We first show that v(t), v′(t) and v′′(t) exist everywhere on IR^{+} . Then, in particular, we prove that v′′(t) < 0 for all t ∈ [0, ∞[, implying that v is strictly concave on IR^{+} . This settles a conjecture of Gnedin and opens the way to stronger bounds for v and its derivatives. We can show v′(t)\sqrt{2t} ∼ 1 from which we derive new and much tighter bounds for v(t), namely

\sqrt{2t} − log(1 + \sqrt{2t}) + c ≤ v(t) ≤ \sqrt{2t}.

Using a martingale approach, we can show that the variance of L_{t}^{t} satisfies

\frac{1}{3} v(t) ≤ Var(L_{t}^{t}) ≤ \frac{1}{3} v(t) + c_{1} log(t) + c_{2}.

Further we obtain several results on the process (L_{u}^{t})_{0≤u≤t}, where L_{u}^{t} denotes the number of selected points up to time u when applying the optimal rule with respect to the time horizon t. We will also show that the integral equation which yields v(t), has a unique solution. As an application, this result is used to extend a known result on the equivalence of a specific bin-packing problem with a certain subsequence problem. Our more personal interest in quick selection rules and their performance leads us also to the study of a class of convenient graph-rules. Known results on the concentration measure of record values suggest that the asymptotically best graph-rule should be the diagonal line rule, and we prove this intuition to be correct.

Keywords: Poisson process, online selection problems, baker’s problem, binpacking, patience sorting, Ulam’s problem, optimality principle, asymptotic optimality, integral equation, concavity, martingale, squared variation, predictable process, predictable compensator, graph-rule, Abelian theorem, records, concentration measure.

AMS 1991 subject classification: 60G40

1. INTRODUCTION. Let (N_{s})_{s≥0} be a Poisson process with rate 1 and with occurrence times 0 = T_{0} < T_{1} < T_{2} < ⋯ a.s.. Further let (X_{k})_{k=1,2,···} be a sequence of i.i.d. uniform random variables on [0, 1], independent of the T_{j} ’s. We suppose that the bivariate variables (T_{k}, X_{k})_{k=1,2,···} can be observed sequentially. For a given horizon t, the objective is to select online a subsequence (T_{k_{1}}, X_{k_{1}}), (T_{k_{2}}, X_{k_{2}}), ⋯ satisfying X_{k_{1}} ≤ X_{k_{2}} ≤ ⋯ for k_{1} < k_{2} < ⋯ and T_{k_{i}} ≤ t, consisting of as many elements as possible. Here online means in sequential order, without recall on preceding observations.

This problem is related to problems studied by Samuels and Steele (1981), Gnedin (1999, 2000, 2000 b), Coffman et al. (1987), and several other authors. Samuels and Steele (1981) treated the problem of selecting online a monotone subsequence of maximal expected length for a fixed number n of observations. They showed that the corresponding value v_{n} satisfies v_{n} ∼ \sqrt{2n}. They also stated that if the number of observations N is Poisson, the asymptotic solution is essentially the same with E(N) being used as a substitute for n. Gnedin (2000) provided an alternative elementary proof of this result, and Gnedin (1999) found asymptotic answers for an arbitrary number N of observations. Baryshnikov and Gnedin (2000) studied a similar multidimensional problem, both for the fixed-n case and the Poisson case, and showed the analog of the \sqrt{2n}-result. The case of N geometric is studied in more detail in Gnedin (2000).

The problem of selecting online a monotone subsequence is also related to bin-packing problems. See Coffman et al. (1987). We have a unit bin and should pack as many as possible random items into the bin using an online strategy. If the items are i.i.d. uniform on [0, 1], this problem is equivalent to the fixed n monotone subsequence problem. The baker’s problem studied by Bruss and Robertson (1991), as well as related problems studied by Rhee and Talagrand (1991) and Boshuisen and Kertz (1999) arose partially in different contexts, but some are related with the \sqrt{2n} result. In particular, as Gnedin (1999) points out, Lemma 4.1 of Bruss and Robertson (1991) yields immediately the upper bound \sqrt{2n} for the expected number of packed items, and we know that this bound is sharp.

F. THOMAS BRUSS and FREDDY DELBAEN

Dropping the online requirement leads to quite a different problem as we shall shortly outline. Conditioning on N_{t} = n, the natural question is now: What is the distribution of the length of the longest subsequence in a random permutation of n different real numbers? This question, seemingly first asked by Ulam (see Critchlow (1988) and Ulam (1972)), has attracted a great deal of scientific attention. A nice way of getting acquainted with this problem is reading the survey article by Aldous and Diaconis (1999). This paper shows the major steps provided by Hammersley (1972), Vers̀ik and Kerov (1977), Logan and Shepp (1977), the recent detailed study of Baik, Deift and Johansson (1999) and Baik and Rains(1999). It also draws attention to interesting analogies with other sorting problems.

To contrast the online problem of maximizing the expected length of the selected subsequence with the above problem we recall the “prophet” comparison of Samuels and Steele (1981): A prophet with complete foresight of the sequence achieves the maximal length, whereas a sequential decision maker without foreseeing abilities must be satisfied with what an optimal online selection strategy can achieve. Patience sorting (see e.g. Aldous and Diaconis (1999), sections 1.1 and 2.3) provides an interesting complementary comparison. This algorithm for n mixed cards, say, requires at each step a comparison of the currently held card with the top cards on the existing piles from left to right. See also Mallows (1973). Interestingly, this algorithm is online because each card need only be touched when it appears, and it produces the length of the longest subsequence which a prophet is able to achieve. However, the patience sorting algorithm does not produce a pile of cards containing this longest subsequence. It only shows its length.

In order to allow for a direct comparison between our problem and patience sorting we mention that we can see our problem as the following card game: We receive cards at the occurrence times of the Poisson process. The k th card shows here X_{k}, where the X_{1}, X_{2}, ⋯ are i.i.d. random variables which are independent of the sequence of occurrence times. The time is fixed, and the total number of cards is now random. Contrary to the patience sorting problem we must however deliver online the pile containing the increasing subsequence. Of course, as we shall exemplify later on by bin-packing problems, not every monotone subsequence problem makes sense as an interesting card game.

Let us now return to our problem. If the X_{j} ’s follow some continuous distribution function F, then the transformation (X′_{j}) := (F (X_{j})) brings us back to the uniform case. The problem of selecting online a maximum expected number of decreasing X′_{k_{j}} ’s is of course equivalent, since the variables X′_{j} and 1 − X′_{j}, j = 1, 2, ⋯ follow the same distribution.

We became interested in the problem of selecting monotone subsequences when Gnedin (private communication 1997) asked the following analytical question:

Gnedin’s problem: Let v : IR^{+} → IR^{+} be formally defined by

v(0) = 0; v′(t) = ∫_{0}^{1}[v(tx) + 1 − v(t)]^{+}dx,  (1.1)

where y^{+} = max{0, y}. Is v(t) concave on IR^{+} ?

SELECTING MONOTONE SUBSEQUENCES

We show that the answer to this question is affirmative. The question of concavity here is different from the concavity question studied by Samuels and Steele (1981) and needs a different approach. We provide a purely analytic one. Moreover, we shall study in detail, other questions concerning (1.1) and point out properties of v which seem important to us. These are, in particular, the existence and the behaviour of the derivative v′(t) and tight bounds for the solution v. Apart from mathematical curiosity, our motivation herefore is the interpretation of v in the context of the problem: The solution of equation (1.1) determines in fact the value v(t) of the problem, i.e. the maximum expected length of the selected subsequence with increasing X_{k_{j}}. Moreover, equation (1.1) can be adapted to similar problems. For example, if we replace the sequence (X_{k}) by i.i.d. random vectors Y_{k}^{t} uniform on the unit m-cube [0, 1]^{m} then the optimal selection equation for (in all coordinates) increasing subsequences Y_{k_{j}}^{t} is the same in t if integration is replaced by multiple integration. This problem was studied by Baryshnikov and Gnedin (2000). Such links with similar problems add to the motivation to get the maximum information from (1.1) itself, without having to depend on specific information from the probabilistic model.

The paper is organised as follows.

Section 2 studies the optimal value, the strategy which achieves this value and also the fluctuations of the selection process. It splits in two subsections. Section 2A is confined to the study of v(t) and the form of the optimal selection rule. Here we use elementary analytic tools as well as martingale methods. The major steps are: v is continuous and increasing (Lemma 2.2), continuously differentiable (Theorem 2.1) and, in particular, v is a strictly concave function on R^{+} (Theorem 2.2). New important bounds for v, v′ and v′′ as well as for an intrinsically connected function (called ϕ(t)) are provided in Theorems 2.3 through 2.5. Section 2B, in which we study the fluctuations of L_{t}^{t}, requires martingale methods and stopping time techniques. Theorem 2.7 and 2.8 give tight bounds for the variance of L_{t}^{t}. This subsection includes also results on convergence in probability of the selection process and a related skew bracket process (Corollary 2.3 and Lemma 2.6).

Section 3 addresses the problem of finding the asymptotically best graphical solution. Here the rule is to select any selectable observation below the graph of a chosen deterministic function f (graph–rule). Theorem 3.1 shows that the choice of f(s) = s/t is the asymptotically best graph–rule. This confirms the authors’ conjecture instigated by results of Deuschel and Zeitouni (1995) and Goldie and Resnick (1996). We also show that the asymptotic value of this rule is \sqrt{tπ/2}.

In Section 4 we extend the equivalence of monotone subsequence problems and bin-packing problems, observed by Coffman et al. (1987) for a fixed-n problem, into our Poisson model. Our main tool is Theorem 4.1, stating that the solution of (1.1) is unique.

2. THE VALUE FUNCTION AND THE OPTIMAL RULE.

2A. The Value Function and the Related Martingale.

Recall that (N_{t})_{t≥0} is a Poisson process on IR^{+} of rate 1 with occurrence times 0 = T_{0} < T_{1} < T_{2}, ⋯ a.s., and (X_{k}) a sequence of independent indentically distributed (i.i.d.) random variables, uniformly distributed on [0, 1] and independent of the T_{k} ’s. Let (Ω, F, P) be a probability space, large enough to host (T_{k})_{k=1,2,···} and (X_{k})_{k=1,2,···}, and let A_{k} = σ(T_{1}, ⋯, T_{k}, X_{1}, ⋯, X_{k}) denote the sigma-field generated by T_{1}, T_{2}, ⋯, T_{k} and X_{1}, X_{2}, ⋯, X_{k}. The history of the process at time t is denoted by F_{t}, i.e. F_{t} is the collection of sets which satisfies, for t ≥ 0, F_{t} ∩ {N_{t} = k} = A_{k} ∩ {N_{t} = k} for all k = 0, 1, · · · .

Definition 2.1 A strategy is a function ψ : IN×Ω → {0, 1} such that, for all n, ψ(n, ·) is A_{n} -measurable. We say that ψ is admissible for online decisions if n ≤ m implies that X_{n} ≤ X_{m} on the set {ω : ψ(n, ω) = 1}∩{ω : ψ(m, ω) = 1}. The set of admissible strategies will be denoted by Ψ_{a}. For ease of notation we write ψ_{n} for ψ(n, ·).

We note that the definition of an admissible strategy does not involve a time horizon. If ψ ∈ Ψ_{a}, let

Z_{t}(ψ) = ∑_{n:T_{n}≤t} ψ_{n}.

We also the define the “value” function v: IR^{+} → IR^{+} as follows:

v(t) = sup_{ψ∈Ψ_{a}} E(Z_{t}(ψ)).  (2.1)

More generally we define for 0 ≤ x ≤ 1

v(t, x) = sup_{ψ∈Ψ_{a}(x)} E(Z_{t}(ψ)),  (2.2)

where Ψ_{a}(x) denotes the class of admissible strategies confined to selections of values X_{k_{j}} ≥ x. Note that, by definition of v, v(t) = v(t, 0), and by definition of our problem, ψ_{n} = ψ_{m} = 1 implies X_{m} ≥ X_{n} for m ≥ n. It is straightforward that the value functions v(.) and v(., x) are non-decreasing and strictly positive for t > 0.

Lemma 2.1 For all t ≥ 0 and 0 ≤ x ≤ 1,

v(t, x) = v((1 − x)t).

Proof. Define X′_{n} = X_{n}1_{{X_{n}≥x}}, where 1_{E} denotes the indicator of the event E. Remove all T_{n} with X′_{n} = 0, and renumerate the remaining T_{n} ’s by T′_{1}, T′_{2}, · · ·. The T′_{n} ’s are now the occurrence times of a thinned process (N′_{t})_{t≥0} . Since the X_{n} are i.i.d. on [0, 1] and independent of the T_{n} ’s, this thinning is independent-binomial. Therefore the process (N′_{t})_{t≥0} is again a Poisson process, but now with rate 1 − x.

However, we cannot directly conclude that the value for this thinned process is v(t, x). Indeed there are two classes of strategies that play a role. The first class is the class of admissible strategies using only the history of the thinned process. The second class consists of admissible strategies that use the history of the complete process, i.e. these strategies also use the occurrence times (T_{n}) and the values (X_{n}) that cannot be selected because X_{n} ≤ x. Proposition 2.1 below shows that there is no difference when calculating the value function v.

Hence also for the thinned process, the optimal value is given by (2.2), v(t, x). To relate this to v(·), we first note that (X_{T′_{1}} − x)/(1 − x), (X_{T′_{2}} − x)/(1 − x), ⋯ are i.i.d. random variables uniformly distributed on [0, 1], and independent of the occurrence times T′_{n}, n = 1, 2, · · · . Using the time scale transformation τ(s) := s(1−x), 0 ≤ s ≤ t we can now reset the arrival rate to 1, because τ(T′_{1}), τ(T′_{2}), ⋯ follow the same distribution as T_{1}, T_{2}, · · ·. But this determines uniquely the distribution of the process (N′_{t})_{t≥0} , which is the same as the distribution of the process (N_{t(1−x)})_{t≥0} . Since elements of Ψ_{a}(x) satisfy, by definition, the admissibility property, (2.2) becomes (2.1) with t being replaced by t(1 − x). Hence v(t, x) = v(t(1 − x), 0) = v(t(1 − x)), and hence, pending the proof of the following proposition, the Lemma is proved. [ ]

Proposition 2.1 Let (T_{n}, X_{n})_{n=1,2,···} be as before and be defined on a probability space (Ω, F, P). As before, the σ -algebra σ(T_{1}, ⋯, T_{n}, X_{1}, ⋯, X_{n}) is denoted by A_{n}. Let now C ⊂ F be a σ -algebra independent of A_{∞}. Define G_{0} = C and, for n ≥ 1, G_{n} = σ(A_{n}, C). Let, as before, Ψ_{a} be the set of all A-measurable admissible strategies, whereas Ψ_{a}^{G} denotes now the set of all G−measurable admissible strategies. Then

v(t) = sup { E [ ∑_{{n:T_{n}≤t}} ψ_{n}] : (ψ_{n})_{n=1,2,....} ∈ Ψ_{a}}

= sup { E [ ∑_{{n:T_{n}≤t}} ψ_{n}] : (ψ_{n})_{n=1,2,....} ∈ Ψ_{a}^{G}} .

Proof. Since for all n, A_{n} ⊂ G_{n}, the last supremum is an upper bound for v(t). Hence it suffices to show that it is also a lower bound for v(t), that is

v(t) ≥ sup { E [ ∑_{{n:T_{n}≤t}} ψ_{n}] : (ψ_{n})_{n=1,2,....} ∈ Ψ_{a}^{G} } .

The idea in proving the latter is to decompose Ω as a product space. Let i be the mapping from Ω to Ω×Ω defined by i(ω) = (ω, ω). For each n this mapping satisfies G_{n} = i^{−1}(C ⊗ A_{n}). Also, due to independence of G and A_{∞}, the image measure of i is precisely P ⊗ P. Now let (ψ_{n})_{n≥1} ∈ Ψ_{a}^{G}. By a factorization theorem for measurable functions (see e.g. Billingsley (1995), p. 186, Problem 13.3) there then exists a (C ⊗ A_{n})-measurable function ψ̃_{n} : Ω × Ω → {0, 1} such that ψ̃_{n} · i = ψ_{n}. We now define two new random variables T̃_{n}, X̃_{n} on Ω × Ω, which depend only on the second argument, that is T̃_{n}(ω_{1}, ω_{2}) = T_{n}(ω_{2}) and X̃_{n}(ω_{1}, ω_{2}) = X_{n}(ω_{2}). Note that T̃_{n} · i = T_{n} and X̃_{n} · i = X_{n}. Also, by construction, (ψ̃_{n})_{n≥1} is admissible for (T̃_{n}, X̃_{n})_{n≥1} for the filtration (C ⊗ A_{n})_{n≥1} . This means that, for n > m,

{ψ̃_{n} = 1} ∩ {ψ̃_{m} = 1} ⊂ {X̃_{m} < X̃_{n}}, P ⊗ P a.s.,

as we can easily check by taking the inverse image i^{−1} .

For c ∈ Ω, we now define ψ_{n}^{c}(ω) = ψ̃_{n}(c, ω). From the admissibility of (ψ̃_{n})_{n≥1} we get, by Fubini’s Theorem, that for almost all c,

{ψ_{n}^{c} = 1} ∩ {ψ_{m}^{c} = 1} ⊂ {X_{m} < X_{n}}, P a.s.

Fubini’s Theorem also implies that each ψ_{n}^{c} is A_{n}−measurable. Therefore we have (ψ_{n}^{c})_{n≥1} ∈ Ψ_{a}, and hence

E_{P} [ ∑_{n:T_{n}≤t} ψ_{n}^{c}] ≤ v(t).

Integrating with respect to c over Ω yields, again by Fubini’s Theorem,

E_{P ×P} [ ∑_{n:T_{n}≤t} ψ̃_{n}] ≤ v(t),

or equivalently, by definition of ψ̃_{n},

E_{P} [ ∑_{n:T_{n}≤t} ψ_{n}] = E_{P ×P} [ ∑_{n:T_{n}≤t} ψ̃_{n}] ≤ v(t),

which completes the proof. [ ]

In a similar way as in the above proposition, we may prove the following Markov-like property. The supremum taken is to be interpreted as the essential supremum of a collection of random variables. We leave the details to the reader.

Proposition 2.2 Let (ψ_{n})_{n} be an admissible strategy with counting process

L_{u} = ∑_{n:T_{n}≤u} ψ_{n}

and with running maximum

M_{u} = max_{n:T_{n}≤u} ψ_{n}X_{n}.

Let τ: Ω → [0, t] be a stopping time with respect to the filtration (F_{u})_{u≥0} . Then

v((t − τ)(1 − M_{τ}))

= sup {E [ ∑_{n:τ<T_{n}≤t} χ_{n} | F_{τ} ] : χ ∈ Ψ_{a} and χ_{n} = ψ_{n} if T_{n} ≤ τ}

Remark. Although both propositions are intuitively clear, a proof was needed, and we thank a referee for insisting on this point. The authors tried to find a reference but apparently such results are not mentioned in the literature we checked. The above proof might have some didactical interest.

Lemma 2.2 The optimal value v(t) is increasing and continuous on IR^{+}. It is Lipschitz with constant 1.

Proof. We already remarked that v is non-decreasing. To prove the continuity of v(t), we will show that |v(t+δ)−v(t)| ≤ |δ|. We suppose, w.l.o.g., δ ≥ 0. Choose ϵ > 0 and let ṽ(t) denote the expected number of X_{j} being selected up to time t under a strategy ψ_{ϵ} ∈ Ψ_{a}, which is ϵ-optimal with respect to the time t + δ. Then,

v(t + δ) − v(t) = (v(t + δ) − ṽ(t + δ)) + (ṽ(t + δ) − ṽ(t))
+ (ṽ(t) − v(t))
≤ ϵ + |ṽ(t + δ) − ṽ(t)|

since ṽ is ϵ-optimal with respect to time t+δ, and ṽ(t)−v(t) ≤ 0 ≤ v(t+δ)−v(t). Of course, no strategy can select more points in the interval [t, t + δ], than there are arrivals in this interval. The expected number of such points equals δ. Hence the last term above, |ṽ(t+δ)−ṽ(t)|, is smaller than δ. This implies the continuity of v with Lipschitz constant 1, because ϵ > 0 was arbitrary. [ ]

Theorem 2.1 v′(t) = dv(t)/dt exists and is continuous on IR^{+} . Further, the function v satisfies equation (1.1) with v′(0) = 1, and v′(t) > 0 for all t ≥ 0.

Proof. We first prove that v′(t) exists everywhere on IR^{+} . This proof is similar to the proof given for a fixed number of variables (see Samuels and Steele (1981), section 2), but now things become slightly more involved. In our case it is more convenient to condition on what happens on an initial time interval [0, δ].

Before we start calculations, let us consider what happens at the first arrival T_{1} , which gives a value X_{1} . Of course there is nothing to say if T_{1} > t. So we concentrate on the set {T_{1} ≤ t}. At time T_{1} , we can either accept the value X_{1} , i.e. put ψ_{1} = 1 or we can refuse it, i.e. we put ψ_{1} = 0. According to proposition 2.2 above, we have the following:

sup {E [ ∑_{n≥2,T_{n}≤t} χ_{n} | F_{T_{1}} ] : χ ∈ Ψ_{a}, χ_{1} = ψ_{1}}

is either v(t − T_{1}) if ψ_{1} = 0 or is v((t − T_{1})(1 − X_{1})) if ψ_{1} = 1. This means that the best strategy is to take ψ_{1} = 1 if v((t − T_{1})(1 − X_{1})) + 1 ≥ v(t − T_{1}) and ψ_{1} = 0 otherwise.

We now confine our interest to the interval [0, δ]. By what precedes, we have

v(t) = E[v(t − δ)1_{{N_{δ}=0}}]
+ E[max(v(t − T_{1})(1 − X_{1})) + 1, v(t − T_{1}))1_{{N_{δ}=1}}]
+ o(δ).

This immediately yields, because conditional on N_{δ} = 1, the arrival time is uniformly distributed over the interval [0, δ]:

\begin{aligned}v(t) − v(t − δ) = & − v(t − δ) (1 − e^{−δ}) \\ & + ∫_{0}^{δ} ds ∫_{0}^{1} dx max(1 + v((t − s)(1 − x)), v(t − s)) \\ & + o(δ) \end{aligned} .

Hence, by the already proven continuity of v, see Lemma 2.2:

\begin{aligned}lim_{δ→0} \frac{v(t) − v(t − δ)}{δ} & = −v(t) + ∫_{0}^{1} dx max(1 + v(t(1 − x)), v(t)) \\ & = ∫_{0}^{1} dx (1 + v(t(1 − x)) − v(t))^{+}. \end{aligned}  (2.3)

By Lemma 2.2, v is Lipschitz and hence absolutely continuous. Its a.s. derivative is identified as ∫_{0}^{1} dx(1 + v(t(1 − x)) − v(t))^{+} and hence is a continuous function. This shows that v is in fact continuously differentiable, i.e. C^{1} . Obviously v′(0) = 1 and v′(t) > 0 for all t ≥ 0. [ ]

Further properties of v′(t).

We will derive two other useful equations involving v′(t). With the change of variables u := xt, equation (2.3) is equivalent to

tv′(t) = ∫_{0}^{t}[1 + v(u) − v(t)]^{+}du, t ≥ 0.  (2.4)

We define

α = inf{t ∈ IR^{+} : v(t) = 1}.  (2.5)

Using definition (2.5) we can drop the positive-part function up to time α so that (2.4) becomes

tv′(t) = ∫_{0}^{t}(1 + v(u) − v(t))du, 0 ≤ t ≤ α.  (2.6)

For t ≥ α we now define the function ϕ as the unique solution of

v(ϕ(t)) + 1 = v(t), t ≥ α.  (2.7)

Moreover, we set ϕ(t) = 0 for all t < α. The function ϕ will play an important role in this paper.

By the implicit function theorem we have for t > α,

v′(ϕ(t))ϕ′(t) = v′(t).  (2.8)

We also note that ϕ is C^{1} on ]α, ∞[ and is continuous and strictly increasing on the half-closed interval [α, ∞[.

For t ≥ α we can write equation (1.1) in the form

tv′(t) = ∫_{ϕ(t)}^{t}(1 − v(t) + v(u)) du = ∫_{ϕ(t)}^{t}(v(u) − v(ϕ(t))) du,  (2.9)

where we used (2.7) in the second equality. Finally, by Fubini’s theorem,

tv′(t) = ∫_{ϕ(t)}^{t} ∫_{ϕ(t)}^{u} v′(s)ds du = ∫_{ϕ(t)}^{t} ∫_{s}^{t} v′(s)du ds

= ∫_{ϕ(t)}^{t} v′(s)(t − s)ds.

Hence equations (2.4) and (2.9) are equivalent to the equation

tv′(t) = ∫_{ϕ(t)}^{t} v′(s)(t − s)ds,  (2.10)

which we will also use later on.

Concavity of v(t).

Before we prove the concavity of the function v(t) let us first see what happens for t ≤ α.

Lemma 2.3 A solution v(t) of equation (1.1) on [0, α] is given by

v(t) = ∫_{0}^{t} \frac{1 − e^{−s}}{s} ds, 0 ≤ t ≤ α,  (2.11)

where α = 1.34501 · · · . Moreover, this solution is unique.

Proof. We use the equivalent equation (2.6). Differentiating (2.6) with respect to t yields

d(tv′(t))/dt = 1 − ∫_{0}^{t} v′(t)du = 1 − tv′(t).

It is easy to verify that this equation, with v(0) = 0, has the unique solution (2.11). We then solve v(t) = 1 which yields α = 1.34501 · · · . [ ]

Remark 2.1 We note that v(t) in (2.11) gives, for each t ∈ [0, α], the expected total number of record observations up to time t. Indeed, since v(t) is increasing on [0, α] to 1, it is optimal to select any admissible observation and hence to select any record on this interval.

Remark 2.2 So far we have proved the uniqueness of the solution v(t) of equation (1.1) only on the interval [0, α]. The solution is in fact unique everywhere, but this requires a different proof. This proof is given in Section 4. The uniqueness of solution v will not be used before Section 4.

Corollary 2.1 v′′(t) < 0 for 0 ≤ t < α (which implies, in particular, that v is strictly concave on [0, α]).

Proof. From (2.11) we obtain v′′(t) = (e^{−t}(t+1)−1)/t^{2} and v′′(0) = −1/2. The numerator of v′′(t), g(t) say, satisfies g(0) = 0 and g′(t) < 0 for t > 0, which implies the above statement. [ ]

We now have sufficient material to show that v is concave on IR^{+} .

Theorem 2.2 Any function v that satisfies equation (1.1) is strictly concave on IR^{+} . In fact a stronger property holds: v is twice continuously differentiable on IR^{+} with v′′(t) < 0 for all t > 0.

Proof. Equation (2.9) tells us that tv′(t) = ∫_{ϕ(t)}^{t}(1 + v(u) − v(t))du and from (2.8) and (2.10) we deduce that tv′(t) is in C^{1} on ]α, ∞[. This means that v′′(t) is continuous on ]α, ∞[. Also, a direct calculation shows that

tv′′(t) + v′(t) = 1 − (t − ϕ(t))v′(t),

and hence

tv′′(t) = 1 − (1 + t − ϕ(t))v′(t), t > α.  (2.12)

Equation (2.12) also implies that

lim_{t→α+} tv′′(t) = 1 − (1 + α)v′(α).

If we compare this expression with the expression of Lemma 2.3 we see that

lim_{t→α+} v′′(t) = lim_{t→α−} v′′(t) > −∞.

This implies that the function v′ is continuously differentiable on ]0, ∞[. But then (2.12) also implies that, for t > α, the function tv′′(t) is continuously differentiable.

We now turn to the proof of v′′(t) < 0 on ]0, ∞[. We already know from Corollary 2.1 that v′′(t) < 0 for t ≤ α, and hence, if we define

T = inf{t : v′′(t) = 0},  (2.13)

we necessarily have α < T ≤ ∞. Of course, the aim is to show that T = ∞.

Let us suppose on the contrary that T < ∞. Since tv′′(t) < 0 for t < T we must have

\frac{d}{dt}(tv′′(t))|_{t=T} ≥ 0.  (2.14)

Moreover, since v′′(t) < 0 for t < T we have also that on [0, T], the function v′ is strictly decreasing, and the implicit function theorem shows that ϕ′(t) < 1 for all α < t ≤ T. Then we get

\frac{d(tv′′(t))}{dt} = −(1 − ϕ′(t))v′(t) + (1 + t − ϕ(t))v′′(t).  (2.15)

But, for t = T, equation (2.15) implies

\frac{d}{dt}(tv′′(t))|_{t=T} = −(1 − ϕ′(T))v′(T) < 0,

which contradicts inequality (2.14).

This shows T = ∞ and completes the proof of the Theorem. It also settles the mentioned conjecture of Gnedin in the affirmative. [ ]

Tight inequalities.

In the following we prove tight inequalities for v(t) as well as several other inequalities which will be used later on.

Corollary 2.2

(i) v′(t) > 0, for all t ≥ 0,

(ii) v′′(t) < 0, for all t ≥ 0,

(iii) tv′′(t) = 1 − v′(t)(1 + t − ϕ(t)) for t ≥ α,

(iv) v′(t)(t − ϕ(t)) ≤ 1 ≤ v′(t)(1 + t − ϕ(t)) for t ≥ α.

Proof. Except for property (iv), all other properties were obtained before. To prove property (iv) we observe that the first inequality follows immediately

SELECTING MONOTONE SUBSEQUENCES

from the concavity of v whereas the second one follows from v′′(t) < 0, and from property (iii). [ ]

Theorem 2.3 The functions v and ϕ satisfy

(i) t − ϕ(t) ≤ \sqrt{2t} for t ≥ α, (ii) v′(t) ≥ \frac{1}{1+\sqrt{2t}} for t ≥ α, (iii) v(t) ≥ \sqrt{2t} − log(1 + \sqrt{2t}) + 1 − \sqrt{2α} + log(1 + \sqrt{2α}) for t ≥ α.

Proof. The function v is concave, and hence v′ is decreasing. Therefore (2.10) implies

v′(t)t = ∫_{ϕ(t)}^{t} v′(s)(t − s)ds ≥ v′(t) ∫_{ϕ(t)}^{t}(t − s)ds = v′(t)\frac{1}{2}(t − ϕ(t))^{2}.

Since v′(t) > 0, this yields (t − ϕ(t))^{2} ≤ 2t, which proves statement (i). But then Corollary 2.2 (iv) implies that v′(t) ≥ 1/(1 + \sqrt{2t}) for t ≥ α,

proving statement (ii).

Finally, integrating this inequality from α to t yields, using v(α) = 1,

v(t) = v(α) + ∫_{α}^{t} v′(s)ds

≥ v(α) + ∫_{α}^{t} \frac{ds}{1 + \sqrt{2s}}

= \sqrt{2t} − log(1 + \sqrt{2t}) + 1 − \sqrt{2α} + log(1 + \sqrt{2α}).

This proves statement (iii) and completes the proof. [ ]

Theorem 2.4 The functions v and ϕ satisfy

(i) v′(t) ≤ \frac{1}{\sqrt{2t}} for t ≥ α, (ii) v(t) ≤ \sqrt{2t} + 1 − \sqrt{2α} < \sqrt{2t} for t ≥ α, (iii) t − ϕ(t) ≥ \sqrt{2t} − 1 for t ≥ α, (iv) |v′′(t)| ≤ \frac{1}{t\sqrt{2t}} for t ≥ α.

F. THOMAS BRUSS and FREDDY DELBAEN

Proof. To prove (i) we first note that, from the concavity of v,

v′(t)t = ∫_{ϕ(t)}^{t}(v(u) − v(ϕ(t)))du ≤ ∫_{ϕ(t)}^{t}(1 + v′(t)(u − t))du,

and therefore

v′(t)t ≤ t − ϕ(t) − v′(t)\frac{1}{2}(t − ϕ(t))^{2}.

This we rewrite as

v′(t) ≤ \frac{t − ϕ(t)}{t + \frac{1}{2}(t − ϕ(t))^{2}} .

But since the function x → x/(t + x^{2}/2) is increasing for x ≤ \sqrt{2t}, we get from this and (i) in Theorem (2.3) that:

v′(t) ≤ \frac{\sqrt{2t}}{t + \frac{1}{2}(\sqrt{2t})^{2}} = \frac{1}{\sqrt{2t}}.

Secondly, direct integration of (i) from α to t yields

v(t) ≤ v(α) + ∫_{α}^{t} \frac{ds}{\sqrt{2s}} = 1 + \sqrt{2t} − \sqrt{2α},

which proves (ii). To prove (iii) we use Corollary 2.2 (iv). This implies

t − ϕ(t) + 1 ≥ \frac{1}{v′(t)} ≥ \sqrt{2t},

or equivalently,

t − ϕ(t) ≥ \sqrt{2t} − 1,

which proves (iii). Finally, to prove (iv), we note that

|v′′(t)| = \frac{v′(t)(1 + t − ϕ(t)) − 1}{t}, (from Corollary 2.2 (iii))

≤ \frac{1 + t − ϕ(t) − \sqrt{2t}}{t\sqrt{2t}}, (from Theorem 2.4 (i))
≤ \frac{1 + \sqrt{2t} − \sqrt{2t}}{t\sqrt{2t}}, (from Theorem 2.3 (i))

= \frac{1}{t\sqrt{2t}}.

This completes the proof. [ ]

Theorem 2.5 The function ϕ satisfies

(i) \frac{ϕ(t)}{t} → 1 as t → ∞,

and

(ii) ϕ′(t) → 1 as t → ∞.

Proof. Since t − ϕ(t) ≤ \sqrt{2t} we immediately get (i) from

1 − \frac{ϕ(t)}{t} ≤ \frac{\sqrt{2t}}{t} → 0, as t → ∞.

The second statement follows from ϕ′(t) = v′(t)/v′(ϕ(t)) since

1 ≥ ϕ′(t) ≥ \frac{\sqrt{2ϕ(t)}}{\sqrt{2t} + 1} → 1, as t → ∞. [ ]

This concludes the study of v(t). Let us remark that the regularity properties of v were all derived from the integral equation (1.1). Hence they are shared by any function which satisies equation (1.1).

Optimal Strategy.

We now have enough material to describe, for each time horizon, the optimal strategy. Without further notice let us fix the time horizon t. For a strategy ψ ∈ Ψ_{a} we denote by L the process that counts the number of accepted values. Of course this process is only relevant for time indices between 0 and t. The running maximum of the accepted values defines a process denoted by M. Proposition 2.2 implies that for each n:

E [L_{T_{n}∧t} + v((t − T_{n} ∧ t)(1 − M_{T_{n}∧t}))] ≤ v(t),

where a ∧ b = min(a, b). A strategy that achieves equality is therefore optimal. The proof of Theorem 2.1 already told us what to do at time T_{1} . Recursively we define

ψ_{n} = 1 if T_{n} ≤ t, X_{n} ≥ max_{k≤n−1}{ψ_{k}X_{k}} and

1 + v((t − T_{n})(1 − X_{n})) ≥ v((t − T_{n})(1 − max_{k≤n−1}{ψ_{k}X_{k}}))

ψ_{n} = 0 otherwise.

The proof that this indeed gives an optimal strategy is based on a martingale theorem. We will freely use notation coming from martingale theory. We refer the reader to Brémaud (1981), Jacod and Shiryaev (1987) or Protter (1995) for any unexplained notion. To state our martingale theorem, suppose that ψ is defined according to the description above, with counting process L^{t} and running maximum process M. We first define a process H, which also depends on t, but we drop this index in order to simplify the notation and because the time horizon, t, is kept fixed. Let

H_{u} = sup {s : 0 ≤ s ≤ 1, v((t − u)(1 − s)) + 1 ≥ v((t − u)(1 − M_{u−}))} .

Clearly the process H is predictable and on the set {(t − u)(1 − M_{u−}) ≥ α}, we have that

(t − u)(1 − H_{u}) = ϕ((t − u)(1 − M_{u−})),

whereas on the set {(t − u)(1 − M_{u−}) < α}, we have:

H_{u} = 1.

We write the process H as H_{u} = h_{u}(M_{u−}), where h : [0, t] × [0, 1] → [0, 1] is a deterministic function (that, as already said, also depends on t). The function h describes the maximum acceptance level. Also, using equation (2.7) and the definition of H_{u}, we see that

(t − u)(H_{u} − M_{u−}) = (t − u)(1 − M_{u−}) − ϕ((t − u)(1 − M_{u−})).  (2.16)

The definition of H_{u} and equality (2.16) will be central in exploiting the following martingale

Theorem 2.6 The process Y_{u}^{t} defined as

Y_{u}^{t} = L_{u}^{t} + v((t − u)(1 − M_{u}))

is a square integrable martingale of bounded variation. The jumps, defined as ΔY_{u}^{t} = Y_{u}^{t} − Y_{u−}^{t}, are nonnegative and bounded by 1.

Proof: The proof is a consequence of the optimality principle or dynamic programming principle. To avoid circular reasonings and to prepare the reader for later use of martingale arguments, we give a proof based on stochastic calculus. Parts of this proof will be used in later sections.

The characteristics (see Brémaud (1981) or Jacod and Shiryaev (1987)) are given by the intensity of the counting process λ_{u}^{t} and the distribution K_{u} of the jump size, given there is a jump at time u. From the definition of the strategy ψ, we immediately get the intensity

λ_{u}^{t} = H_{u} − M_{u−},

as well as, K_{u}(dx), the distribution of the jump size. The latter is given as the law of the random variable

1 + v((t − u)(1 − U)) − v((t − u)(1 − M_{u−})),  (2.17)

where U is uniformly distributed on [M_{u−}, H_{u}].

The predictable compensator of the process Y^{t} can now be calculated and will be shown to be zero. Indeed, an immediate calculation shows that the compensator is given by:

(H_{s} − M_{s−}) ds − v′((t − s)(1 − M_{s−}))(1 − M_{s−}) ds
+( ∫_{M_{s−}}^{h_{s}(M_{s−}} {v((t − s)(1 − y)) − v((t − s)(1 − M_{s−}))}dy)ds

But from the definition of the process H and the integral equation of v, it follows that this equals zero.

Because the process Y^{t} is positive and bounded by N +\sqrt{2t}, it is therefore a square integrable martingale. That it is of bounded variation is obvious since the function v is continuously differentiable and the process L^{t} is non-decreasing. The assertion about the jump size follows from the definition of the strategy ψ. [ ]

Remark 2.3. We immediately get that the strategy used in the previous theorem is optimal. Indeed:

E[L_{t}^{t}] = E[Y_{t}^{t}] = E[Y_{0}^{t}] = v(t).

Also, in accordance with Proposition 2.2 and Lemma 2.1, we find that for every stopping time τ ≤ t, we have:

E[L_{t}^{t} − L_{τ}^{t} | F_{τ}] = E[Y_{t}^{t} − Y_{τ}^{t} + v((t − τ)(1 − M_{τ})) | F_{τ}] = v((t − τ)(1 − M_{τ})).

In other words, as dynamic programming tells us, the strategy ψ is also optimal on the stochastic interval [τ, t].

2B. Fluctuations of the Number of Selected Points.

We now address the problem of finding estimates for the random fluctuation of the number of points which are selected by the optimal strategy. Our first concern is the variance of this number. Recall that, for fixed t ≥ 0, L_{t}^{t} denotes the number of points selected up to time t under the optimal strategy.

Before we give an upper and a lower bound for Var(L_{t}^{t}), let us recall the result from martingale theory (see Protter (1995), squared variation process in Ch. 2, and also Brémaud (1981), p. 235, T3), according to which we have

Var(L_{t}^{t}) = E (∫_{0}^{t}(ΔY_{u}^{t})^{2}dL^{t}(u)) .

Hence,

Var(L_{t}^{t}) = E ( ∫_{0}^{t} du λ_{u}^{t} ∫_{0}^{1} y^{2}K_{u}(dy) )

= E( ∫_{0}^{t} du (H_{u} − M_{u−}) × ∫_{M_{u−}}^{H_{u}} \frac{dx}{(H_{u} − M_{u−})}×

(v((t − u)(1 − x)) + 1 − v((t − u)(1 − M_{u−}))^{2} ).  (2.18)

We first give a lower bound for Var(L_{t}^{t}).

Theorem 2.7

Var(L_{t}^{t}) ≥ \frac{v(t)}{3} , ∀t ≥ 0.

Proof. Since v is concave we have that, for each jump time u, the random variable defined in (2.17)

1 + v((t − u)(1 − U)) − v((t − u)(1 − M_{u−}))

is stochastically larger than a uniformly distributed random variable on [0, 1]. Hence, from equation 2.18,

Var(L_{t}^{t}) ≥ E (∫_{0}^{t} du (H_{u} − M_{u−}) ∫_{0}^{1} x^{2}dx)

≥ \frac{1}{3} E (∫_{0}^{t} du (H_{u} − M_{u−}))

≥ \frac{1}{3} E (∫_{0}^{t} dL_{u}^{t} )

= \frac{1}{3}E(L_{t}^{t}) = \frac{1}{3}v(t). [ ]

We now turn to the problem of finding an upper bound for Var(L_{t}^{t}). Clearly, in order to understand the behaviour of (L_{t}^{t}) sufficiently well, our goal is to find an upper bound which is close to the lower bound so that we can obtain strong limit results. Contrary to the problem of finding a lower bound where we were able to minorize (stochastic) jump sizes, independently of the jump locations, by i.i.d. uniform random variables, a similar approach is now too coarse. Thus we face the additional problem of majorizing, in a suitable way, location-dependent jump sizes.

We will need, among other tools, an elementary Lemma which we state and prove first.

Lemma 2.4 Let a, b ∈ IR with a < b and let φ : IR → IR be a twice differentiable concave function on [a, b] with φ(a) = φ(b) = 0. Suppose that, for some γ ≥ 0,

φ′′(x) ≥ −γ, for all x ∈ [a, b].  (2.19)

Then

∫_{a}^{b} φ(x)dx ≤ \frac{γ}{12}(b − a)^{3}.

Proof. Define the function

p(x) = \frac{γ}{2} (x − a)(b − x) − φ(x).  (2.20)

Then, from (2.19), for x ∈ [a, b],

p′′(x) = −γ − φ′′(x) ≤ 0,

and hence p(x) is concave on [a, b]. Also, φ(a) = φ(b) = 0, and so from (2.20), p(a) = p(b) = 0. Concavity of p on [a, b] implies then that p is non-negative on [a, b]. Hence 0 ≤ φ(x) ≤ (γ/2)(x − a)(b − x), x ∈ [a, b], and thus

∫_{a}^{b} φ(x)dx ≤ ∫_{a}^{b} \frac{γ}{2} (x − a)(b − x)dx = \frac{γ}{12}(b − a)^{3}. [ ]

Theorem 2.8

Var(L_{t}^{t}) ≤ \frac{1}{3}v(t) + c_{1} log(t) + c_{2},

where c_{1} and c_{2} are suitable constants independent of t.

Proof. According to Theorem 2.1, the function v is strictly increasing on IR^{+} . Hence v^{−1} exists. Let β be defined by v(β) = 2. We have v^{−1}(1) = α and v^{−1}(2) = β so that

1 < α < 2 < v^{−1}(2) = β,  (2.21)

where the third inequality follows from v(t) < E(N_{t}) = t for t > 0. Now note that, according to Theorem 2.3 (i),

\frac{(x − ϕ(x))^{2}}{ϕ(x)} ≤ \frac{2x}{x − \sqrt{2x}} .

But this function is decreasing (for x > 2) and hence for x ≥ β > 2

\frac{(x − ϕ(x))^{2}}{ϕ(x)} ≤ \frac{2β}{β − \sqrt{2β}} .  (2.22)

We also note that 0 < β/(β − \sqrt{2β}) < ∞, since β > 2.

Let τ be the stopping time

τ = inf{0 ≤ u ≤ t : (t − u)(1 − M_{u}) ≤ β}.  (2.23)

The time u = t − β clearly satisfies the set prescription underlying τ so that

τ ≤ t − β.  (2.24)

Since τ is the infimum of this set, and M_{u} nondecreasing, we have

(t − u)(1 − M_{u−}) > β, for u ∈ [0, τ[.  (2.25)

Now, by the martingale property,

E (Y_{τ}^{t}(Y_{t}^{t} − Y_{τ}^{t})) = 0,

and hence

Var(L_{t}^{t}) = Var(Y_{t}^{t}) = Var(Y_{τ}^{t}) + Var(Y_{t}^{t} − Y_{τ}^{t}).  (2.26)

Both summands are estimated in a different way. We start with the easier one.

Recall that F_{s} denotes the sigma-field generated by all arrival time points up to time s and their corresponding values. Then

Var(Y_{t}^{t} − Y_{τ}^{t}) = E ( ∑_{τ<u≤t}(Y_{u}^{t} − Y_{u−}^{t})^{2} )
≤ E (L_{t}^{t} − L_{τ}^{t} )
= E (E(L_{t}^{t} − L_{τ}^{t} |F_{τ})) .

SELECTING MONOTONE SUBSEQUENCES

By the martingale property, the latter equals

E ( v((t − τ)(1 − M_{τ})) ) ≤ E(v(β)) = 2,  (2.27)

where the equality follows fom the definitions of τ and β (see (2.21) and (2.23)), and the continuity of v.

The variance of Y_{τ}^{t} requires more work. Recall that

Var(Y_{τ}^{t}) = E (∫_{0}^{τ} du ∫_{M_{u−}}^{H_{u}} (J(s, u))^{2} ds) ,

where, for M_{u−} ≤ s ≤ H_{u},

J(s, u) = 1 + v ((t − u)(1 − s)) − v ((t − u)(1 − M_{u−})) .

Since v is concave, J(s, u) is a concave function of s. Hence

J(s, u) ≥ l(s) := \frac{H_{u} − s}{H_{u} − M_{u−}} , M_{u−} ≤ s ≤ H_{u}.  (2.28)

Also J^{2} − l^{2} ≤ 2(J − l), since 0 ≤ l ≤ J ≤ 1, M_{u−} ≤ s ≤ H_{u}, and hence

(J(s, u))^{2} ≤ (l(s))^{2} + 2(J(s, u) − l(s)), M_{u−} ≤ s ≤ H_{u}.

So we get that the variance of Y_{τ}^{t}, Var(Y_{τ}^{t}), is bounded above by:

E ( ∫_{0}^{τ} du ∫_{M_{u−}}^{H_{u}}(l(s))^{2}ds ) + 2 E ( ∫_{0}^{τ} du ∫_{M_{u−}}^{H_{u}}(J(s, u) − l(s))ds ) .  (2.29)

For the first term in (2.29) we obtain from (2.28) and from τ ≤ t

E ( ∫_{0}^{τ} \frac{1}{3}(H_{u} − M_{u−})du)

≤ E ( ∫_{0}^{t} \frac{1}{3}(H_{u} − M_{u−})du )

= \frac{1}{3}E(L_{t}^{t})

= \frac{1}{3}v(t)  (2.30)

since the intensity of (L_{u}^{t})_{0≤u≤t} is exactly (H_{u} − M_{u−}) du.

To estimate the second term we first note that the function φ(s, u) := J(s, u)−l(s) vanishes in s = M_{u−} and in s = H_{u} and is concave in s on [M_{u−}, H_{u}]. Thus φ(s, u) satisfies the hypotheses of Lemma 2.4 with a = M_{u−} and b = H_{u}. Therefore we obtain for the second term of (2.29)

2 E ( ∫_{0}^{τ} du ∫_{M_{u−}}^{H_{u}}(J(s, u) − l(s))ds )

≤ \frac{1}{6}E ( ∫_{0}^{τ} du (H_{u} − M_{u−})^{3} sup_{s∈[M_{u−},H_{u}]} |v′′((t − u)(1 − s))| (t − u)^{2} ) .  (2.31)

Since (t − u)(1 − M_{u−}) > β (see (2.25)) we obtain from (iv) of Theorem 2.4

|v′′((t − u)(1 − s))| ≤ \frac{1}{\sqrt{2}}((t − u)(1 − H_{u}))^{−3/2}.

Therefore, from (2.31), Var(Y_{τ}^{t}) must satisfy

Var(Y_{τ}^{t}) ≤ \frac{1}{6\sqrt{2}} E ( ∫_{0}^{τ} (H_{u} − M_{u−})^{3}(t − u)^{2} ((t − u)(1 − H_{u}))^{−3/2}du )
= \frac{1}{6\sqrt{2}} E ( ∫_{0}^{τ} \frac{((H_{u} − M_{u−})(t − u))^{3}}{(t − u)^{5/2}(1 − H_{u})^{3/2}} du) .  (2.32)

The latter is, according to equation (2.16), equal to

\frac{1}{6\sqrt{2}}E[ ∫_{0}^{τ} \frac{1}{t − u} (\frac{((t − u)(1 − M_{u−}) − ϕ((t − u)(1 − M_{u−})))^{2}}{ϕ((t − u)(1 − M_{u−}))} )^{3/2} du ].  (2.33)

By inequality (2.22) the last expectation is smaller than

\frac{1}{6\sqrt{2}}E (∫_{0}^{τ} \frac{du}{t − u} (\frac{2β}{β − \sqrt{2β}} )^{3/2}) ,

and thus from (2.24)

≤ (\frac{β}{β − \sqrt{2β}} )^{3/2} \frac{1}{3} ∫_{0}^{t−β} \frac{du}{t − u} ≤ (\frac{β}{(β − \sqrt{2β})})^{3/2} \frac{1}{3} log (\frac{t}{β} ) .  (2.34)

Thus from (2.26), (2.27), (2.30) and (2.34),

Var(L_{t}^{t}) ≤ \frac{1}{3}v(t) + \frac{1}{3} (\frac{β}{(β − \sqrt{2β})})^{3/2} log (\frac{t}{β} ) + 2,

and the proof is complete. [ ] Convergence i.p. - results.

Corollary 2.3

\frac{L_{t}^{t}}{v(t)} → 1 i.p. and \frac{L_{t}^{t}}{\sqrt{2t}} → 1 i.p. as t → ∞.

Proof. This is straightforward from Theorems 2.7 and 2.8 and Chebychev’s inequality. [ ]

Remark 2.4. The bivariate process (L_{u}^{t}, M_{u})_{0≤u≤t} is Markovian. As P. A. Meyer suggested to us, the study of its infinitesimal generator should yield additional results. We will use this approach in a paper we intent to write on a proof of a corresponding functional Central Limit Theorem.

This concludes our study of the overall optimal online rule and its value. The next section will study a restricted class of online rules.

3. GRAPH-RULES.

This section does not deal with the optimal rule but with “limiting best” rules in a very restricted class of rules. We will first motivate our interest in this subclass of rules. Readers who are only interested in the optimal rule may, without loss of understanding, directly turn to Section 4.

Recall that the optimal selection rule is of the following form: Select the first observation (T_{τ} , X_{τ}) (if any) satisfying 1 + v((1 − X_{τ})(t − T_{τ})) ≥ v(t − T_{τ}), and, recursively, if (T_{k}, X_{k}) was the last selected observation, select the first subsequent observation (T_{τ(k)}, X_{τ(k)}) (if any) satisfying 1 + v((1 − X_{τ(k)})(t − T_{τ(k)})) ≥ v(t − T_{τ(k)}). Given that the online requirement means, in practice, to decide without delay, we want to focus our interest on the simplest rules we can imagine, that is drawing a graph through [0, t] × [0, 1] and selecting sequentially all points below the graph which form an increasing sequence. The goal is here to choose the limiting best graphical solution and, as we would like to point out, not an asymptotically optimal rule, which will be treated in Section 4.

Next to our motivation of finding a particularly simple rule we have a second motivation to study graph-rules. This is to understand the concentration of measure of i.i.d. random variables under the condition that they form a record. Deuschel and Zeitouni (1995) have studied curves of concentration of records in a more general context. For the background see Goldie and Resnick (1996). Our Poisson process model can be compared with the case of t (t ∈ IN) uniform [0, 1] random variables. In this case this curve (on [0, 1]^{2} ) is the diagonal line, as Deuschel and Zeitouni (1995) have shown. They also establish the link with the monotone subsequence problem (Lemma 8, p. 874). This shows that a prophet would select the longest subsequence, with expected length in the order of 2\sqrt{t}, essentially along this line. It is intuitive that a lazy decision maker who wants to use a convenient graph-rule rule cannot do better than just trying to mimic a prophet online. We shall prove, that this intuition is true. However, it came as a surprise to see that it is not easy to turn this intuition into a solid proof. The proof consists of several parts which we prepare first.

Definition 3.1 Let f : [0, t] → [0, 1] and let S_{f} = {(s, x) : 0 ≤ s ≤ t, 0 ≤ x ≤ f(s)}. We say that (T_{k}, X_{k}) is a f -record on [0, t] × [0, 1], if X_{k} is a record among (T_{j}, X_{j}1_{{X_{j}≤f(T_{j})}}), j = 1, 2, ⋯, k.

Note that if Y_{j}^{t} := X_{j}1_{{X_{j}≤f(T_{j})}} = 0, then Y_{j}^{t} cannot be a record. Hence f - records are simply records in the planar Poisson process with unit rate confined to the region bounded above by the graph of f.

Definition 3.2 The rule of selecting sequentially all f-records, and only these, will be called f -graph rule. Further, f^{∗} is called optimal, if it maximizes the expected number of f -records for all f : [0, t] → [0, 1].

Lemma 3.1 For a given function f : [0, t] → [0, 1] let r_{f}(t) denote the expected number of f -records. Then

r_{f}(t) = ∫_{0}^{t} ∫_{0}^{f(s)} e^{−Λ_{f} (s,x)} dx ds,  (3.1)

where Λ_{f}(s, x) denotes the Lebesgue measure of the intersection of S_{f} and the North-West region of the plane with respect to the point (s, x).

Proof. The probability of finding exactly one f -record in a rectangle containing (s, x) with area ds × dx equals, according to the Poisson hypothesis,

(dx ds + o(dx ds)) exp{−Λ_{f}(s, x)},

because it is necessary and sufficient that the rectangle contains at least one observation which is not preceded by a f - record with a larger X -value. Further, more than one arrival time in ds has probability o(ds) (more than one X -value in dx has probability o(dx)) so that summing over the probabilities, respectively expectations, are here asymptotically equivalent. Letting ds → 0 and dx → 0, the limiting sum exists and yields then the above double integral, because the integrand is continuous in both s and x. [ ]

Maximizing (3.1) over all f is in general a difficult problem of calculus of variations, but we can reduce the range of functions containing f^{∗}. For sufficiently small t, we have f^{∗} ≡ 1 on [0, t], as we can see easily. Indeed, we know from the definition of α (see (2.5)-(2.6)) that v(t) ≤ 1 for t ≤ α , so that it is optimal to select any record if t < α. But this simple picture changes quickly, even for moderate t. Further, it will become clear that, as t becomes larger, we can confine our interest to increasing functions f. Therefore we first note that

Corollary 3.1 If f is strictly increasing, then equation (3.1) becomes

r_{f}(t) = ∫_{0}^{t} ∫_{0}^{f(s)} exp{− ∫_{f^{−1}(x)}^{s}(f(u) − x)du}dx ds,  (3.2)

where f^{−1}(x) := inf{s : f(s) = x}.

r_{f}(t) in (3.2) can be computed conveniently for f(s) = s/t, and this will give us immediately a lower bound for sup_{f} r_{f}(t). If f(s) = s/t then we denote the corresponding expected number of f -records by r_{d}(t) (d is mnemonic for “diagonal line”).

Lemma 3.2

sup_{f} r_{f}(t) ≥ r_{d}(t) = \sqrt{\frac{π}{2} t} − 1 + o(\frac{1}{t}).  (3.3)

Proof: The inequality in (3.3) is obvious. Further, for f(s) = s/t we have f^{−1}(s) = ts and so from (3.2)

r_{d}(t) = ∫_{0}^{t} ∫_{0}^{s/t} exp\{− ∫_{tx}^{s}(\frac{u}{t} − x)du\}dxds.  (3.4)

With the change of variable s := s/t, (3.4) becomes

r_{d}(t)/t = ∫_{0}^{1} ∫_{0}^{s} exp{−(t/2)(s − x)^{2}}dxds.  (3.5)

We now use

∫_{0}^{s} exp\{−(t/2)(s − x)^{2}\}dx = ∫_{0}^{s} exp\{−(t/2)x^{2}\}dx = \frac{1}{\sqrt{t}} ∫_{0}^{\sqrt{t}s} e^{−w^{2}/2}dw.

Plugging this into (3.5) we see that

r_{d}(t) = \sqrt{t} ∫_{0}^{1}(G(\sqrt{t}s) − G(0))ds,  (3.6)

where G denotes the Gaussian error-integral. (3.6) can be straightforwardly integrated which yields the rhs of (3.3). [ ]

Asymptotically best graph-rules.

To tackle the question of an asymptotically optimal performance, we transform the time by s := s/t, so that we have now a planar Poisson process with rate t on [0, 1]^{2} . In the following we assume throughout that this time transformation has taken place. Consequently, we will confine our interest to those functions f which satisfy 0 ≤ f(s) ≤ 1 for all s ∈ [0, 1]. We first need two preliminary estimates.

Corollary 3.2 Let 0 < m < ∞ and let f(s) = ms on [0, t_{1}], and let r_{f}(t_{1}, t) denote the expected number of f -records up to time t_{1} . Then there exists a constant c_{1} > 1 such that

c_{1}\sqrt{t_{1}f(t_{1})t} ≤ r_{f}(t_{1}, t) ≤ 2\sqrt{t_{1}f(t_{1})t}, 0 < t_{1} ≤ max\{1, 1/m\}  (3.7)

for all t sufficiently large.

Proof. The first inequality in (3.7) follows from the proof of Lemma 3.2 (by time scale transformation). The second inequality holds since r_{f}(t_{1}, t) ≤ v(t_{1}f(t_{1})t) ∼ \sqrt{2t_{1}f(t_{1})t} < 2\sqrt{t_{1}f(t_{1})t}. [ ]

Lemma 3.3 Let 0 < a ≤ 1, and let f(s) ≡ a on [0, t_{1}] for some 0 < t_{1} ≤ 1. Then, for all constants c_{2} > 1, and all t sufficiently large,

r_{a}(t_{1}, t) < c_{2} log(t).  (3.8)

Proof. It is easy to check (and well-known) that the expected number of records from n i.i.d. continuous random variables equals μ(n) = 1 + 1/2 + ⋯ + 1/(n − 1) + 1/n (see e.g. Arnold et al. (1998), p. 23). Since μ(n) ≤ 1 + log(n) we have r_{a}(t_{1}, t) ≤ E(1 + log(N)), where N is a Poisson-distributed random variable with mean at_{1}t. Since log(.) is a concave function, Jensen’s inequality yields E(log(N)) ≤ log(E(N)), and thus

r_{a}(t_{1}, t) ≤ 1 + log(E(N)) = 1 + log(at_{1}) + log(t) ≤ 1 + log(t) < c_{2} log(t),

where the last inequality holds for all t sufficiently large. [ ]

Definition 3.3 An f−graph rule is called asymptotically optimal if

r_{f}(t)/r_{f^{∗}}(t) → 1 as t → ∞,

where f^{∗} is defined in Definition 3.2.

We are now ready for the essential Lemma of this section.

Lemma 3.4 To find an asymptotically optimal continuous function f on [0, 1] as t → ∞, it suffices to study the class of increasing f with f(0) = 0 and f(1) = 1.

Proof. (i) We first show that we can confine to the class of increasing functions f. Recall (3.1), which becomes (in time scale s := s/t)

r_{f}(t) = ∫_{0}^{1} ∫_{0}^{f(s)} te^{−t Λ_{f} (s,x)} dx ds.  (3.9)

Suppose now that f is not increasing on [0, 1]. We will see that the choice f̃(s) := max _{0≤u≤s} f(u) is asymptotically at least as good as f. Clearly, f̃ is well-defined since f is continuous. Since f is not increasing on [0, 1], there exists a largest point, s_{1} < 1 say, such that f is increasing on [0, s_{1}] (where s_{1} = 0 is defined to signify that f decreases in a neigborhood of 0). Again from continuity of f, we can find an ϵ > 0, a δ := δ(ϵ) > 0 and a largest time s_{2} := s_{2}(ϵ) (truncated at 1) such that f(u) ≤ f(s_{1})−ϵ for s_{1} +δ ≤ u ≤ s_{2} . But then Λ_{f}(u, x) is positive and bounded away from 0 on the set U = {(u, x) : s_{1} + δ ≤ u ≤ s_{2}, 0 ≤ x ≤ f(u)}. Therefore t exp{t Λ_{f}(u, x)} → 0 on U as t → ∞, and thus

∫_{s_{1}+δ}^{s_{2}} ∫_{0}^{f(s)} te^{−t Λ_{f} (s,x)} dx ds → 0 as t → ∞.  (3.10)

This is true for 0 < ϵ′ < ϵ as well, and then, having chosen a corresponding δ > 0, also for all δ′ with 0 < δ′ < δ, since s_{1} is maximal. Extending the outer integral in (3.10) to ∫_{s_{1}}^{s_{2}} adds at most δ to the value of the integral, and hence, as t → ∞, the limiting contribution of the time interval [s_{1}, s_{2}] to the expected number of f records is zero. The same argument holds for all subsequent intervals (if any) on which f drops below f(s_{1}). Thus replacing f by f̃ for s ≥ s_{1} cannot but improve on f, since the integrand is positive. Note also that Λf̃(s, x) does not stay bounded away from zero. This implies that we can focus on increasing functions f.

(ii). We now show that an asymptotically optimal f must satisfy f(0) = 0. According to (i), we suppose f is increasing. Suppose f(0) = a > 0. Let, as before, r_{f}(ϵ, t) be the expected number of f -records on [0, ϵ]. The number of f -records which are not a- records is the number of those f -records which lie in the region bounded by the graphs of f and a. Since the Poisson arrival rate is constant everywhere, it has the same distribution as the number of f − a-records (where f − a is shorthand for g(s) := f(s) − a). Hence its expectation is the same as r_{f−a}(ϵ, t). Counting f -records and a-records separately yields the upper bound

r_{f}(ϵ, t) ≤ r_{a}(ϵ, t) + r_{f−a}(ϵ, t),  (3.11)

because all those a-records which are preceded by f -records do not contribute to the number of f -records.

Now note that r_{f−a}(ϵ, t) ≤ v(ϵ(f(ϵ) − a)t). Indeed, v(ϵ (f(ϵ) − a) yields the expected number of selectable points on the box [0, ϵ] × [0, f(ϵ) − a] under the overall optimal selection rule, and the class of all rules contains the class of f -record rules. Also recall that v(t) ∼ \sqrt{2t}. Using this and Lemma 3.3 yields then from (3.11)

r_{f}(ϵ, t)/\sqrt{ϵt} ≤ \sqrt{2}\sqrt{f(ϵ) − a} + η_{t},  (3.12)

where 0 < η_{t} < c_{2} log(t)/\sqrt{ϵt} → 0 as t → ∞. Since f is continuous, the rhs tends to zero as ϵ tends to zero. Replace f on [0, ϵ] (only) by the line joining the origin and the point (ϵ, f(ϵ)), i.e. by g(s) = sf(ϵ)/ϵ > 0. Since f(0) = a > 0 and f is increasing, this line has a finite strictly positive slope for all ϵ > 0. Thus from Corollary 3.2, for t sufficiently large,

\frac{r_{g}(ϵ, t)}{\sqrt{ϵt}} ≥ \frac{c_{1}\sqrt{tϵf(ϵ)}}{\sqrt{ϵt}} = c_{1}\sqrt{f(ϵ)}.

The rhs stays now bounded away from 0, since f(0) = a > 0. Thus there exists ϵ > 0 such that r_{f}(t, ϵ) < r_{g}(t, ϵ) for t sufficiently large, which proves that f is asymptotically suboptimal unless f(0) = 0.

(iii) Finally, suppose that f(1) = b < 1. Replace f on [1 − ϵ, 1] by the line-segment joining (1−ϵ, b) and (1, 1), which has again a strictly positive finite slope for each 0 < ϵ ≤ 1. Similarly to the proof of (ii) we see then that, for some ϵ > 0 this replacement improves on f as t becomes large. This completes the proof. [ ]

We are now ready for the main result.

Theorem 3.1 The f -record rule using the diagonal line f(s) = s is asymptotically optimal in the class of differentiable functions f : [0, 1] → [0, 1].

Proof. According to Lemma 3.4 we suppose that f(0) = 0, f(1) = 1 and f′(s) ≥ 0 on [0, 1]. The latter implies that Λ_{f}(s, f(s)) = 0 and that each point (s, x) with 0 ≤ x < f(s) has a single connected North-West region below f attached to it. For 0 ≤ β ≤ 1 let

B(β) = {(s, x) ∈ [0, 1]^{2} : 0 ≤ x ≤ f(s), Λ_{f}(x, s) ≤ β}.  (3.13)

Note that B(β) is bounded above by B(0), i.e. the graph of f, and below by the curve c(s, β) := c_{f}(s, β) defined by Λ_{f}(s, x) = β, both being well defined and continuous in β since f is increasing and continuous. Therefore the Lebesgue measure of B(β) denoted by L(B(β)) is right-continuous in β = 0.

Recall (3.9). As t increases, t exp{−t Λ_{f}(s, c(s, β))} → 0 for each β > 0, so that integration on the complement of B(β) is asymptotically negligible for any fixed β > 0. This means that the asymptotic behaviour of the double integral (3.9) is solely determined by the behaviour of the integrand on B(β) as β → 0+. Now interpret (3.9) as t times the Laplace transform of Λ_{f}. This opens the way to applying an Abelian Theorem (see e.g. Feller, Vol. II, Chapter XIII, section 5, Theorem 4). First we see from this theorem that maximizing (3.9) over the set of f is equivalent to maximizing t^{ρ}L(B(β)) for some factor ρ > 0. The value of ρ is not yet determined by the Abelian theorem, but we know more. Indeed, we will see that ρ must be equal to 1/2. Recall the inequality sup_{{f}} r_{f}(t) ≤ v(t) and the asymptotic relationship v(t) ∼ \sqrt{2t}. Also, from Lemma 3.2, sup_{\{f\}} r_{f}(t) ≥ c\sqrt{t} for each c < \sqrt{2π} and t sufficiently large. This yields a two-sided inequality of the order of \sqrt{t}. Hence, since the above maximization problem is equivalent for some power ρ, it can only be ρ = 1/2.

Now, to study the limiting behaviour of

\sqrt{t}L(B(β)) = \sqrt{t} ∫_{0}^{1}(f(s) − c(s, β))ds,  (3.14)

as β → o+ we use the differentiability of f. Note that

\begin{aligned}Λ_{f}(s, c(s, β)) & = \frac{1}{2}(s − f^{−1}(c(s, β))(f(s) − c(s, β)) \\ & = \frac{1}{2} \frac{(f(s) − c(s, β))^{2}}{f′(s)} + o(β). \end{aligned}

Since Λ_{f}(s, c(s, β)) = β, this implies

f(s) − c(s, β) = \sqrt{2β}\sqrt{f′(s)} + o(β^{1/2}).  (3.15)

Therefore

L(B(β)) = ∫_{0}^{1}(f(s) − c(s, β))ds = ∫_{0}^{1} \sqrt{f′(s)}ds + o(β^{1/2}).

The Cauchy-Schwarz inequality implies, however, that

∫_{0}^{1} \sqrt{f′(s)}ds ≤ \sqrt{∫_{0}^{1} ds}\sqrt{∫_{0}^{1} f′(s)ds} = \sqrt{f(1) − f(0)} = 1,

and that equality holds if and only if f′(s) is proportional to 1 on [0, 1]. With the border conditions this implies that only f(s) = s is asymptotically optimal, and the proof is complete. [ ]

4. UNIQUENESS OF v(t) AND RELATIONS WITH BIN-PACKING PROBLEMS.

We now return again to the overall optimal rule and first tackle the question of its uniqueness. As we know this uniqueness is implied by the uniqueness of the solution v of (1.1) with boundary condition v(0) = 0. As observed before, we never used uniqueness so far, but we now give a complete proof. One referee indicated an analytic method of proof which should work out. We prefer however to present a purely probabilistic proof. Profiting from the martingale result established before, it is seemingly shorter and also illustrates the martingale method.

Theorem 4.1 The solution v of equation (1.1) with boundary condition v(0) = 0 is unique.

Proof. We have seen already that (1.1) is equivalent to equation (2.4) with initial condition v(0) = 0.

Suppose now that w(t) is another solution of (2.4), that is w(t) satisfies

tw′(t) = ∫_{0}^{t}[w(u) + 1 − w(t)]^{+}du,  (4.1)

with initial condition w(0) = 0. Of course, w(t) then also satisfies all the properties of v(t), because they are all derived from (1.1). Recall that the solution v induced two other intrinsic functions linked to v, namely the “strict positive part lower bound” denoted by ϕ and, what we called the “maximum acceptance level”, denoted by the function h_{u} : [0, 1] → [0, 1]. Recall also that, since v is increasing, we have seen that these are uniquely defined by v, i.e. v can be more explicitly described by the triple (v, ϕ, h). With these functions we constructed the strategy yielding the counting process L^{t} = (L_{u}^{t}) _{0≤u≤t} and the running maximum process M = (M_{u}) _{0≤u≤t}.

Let now (w, φ, k) be the corresponding triple for w. This means we have for each t > 0 a strategy described in terms of φ and the maximum acceptance level k to achieve w(t). This strategy induces a counting process L^{′ t} and a running maximum M′. Similarly as before, L^{′ t} must satisfy E(L_{t}^{′ t}) = w(t).

Since v(t) is defined as the supremum of the expected number of selected points over all admissible strategies on [0, t], we must have w(t) ≤ v(t). Therefore, to show the equality of v and w, it suffices to show w(t) ≥ v(t) for all t ≥ 0. This remaining part will follow from the following Lemma.

Lemma 4.1 The process (L_{s}^{t} + w((t − s)(1 − M_{s})))_{0≤s≤t} is a supermartingale, and hence

E (L_{t}^{t}) ≤ w(t).

Proof. Computing the predictable compensator now yields (compare Theorem 2.6)

C_{s,t} = (h_{s}(M_{s−}) − M_{s−}) ds − w′((t − s)(1 − M_{s−}))(1 − M_{s−}) ds
+ ∫_{M_{s−}}^{h_{s}(M_{s−})} {w((t − s)(1 − y)) − w((t − s)(1 − M_{s−}))} dy ds.

By equation (4.1) together with the definition of the functions φ and k, we get

w′ ((t − s)(1 − M_{s−})) (1 − M_{s−})
= ∫_{M_{s−}}^{k_{s}(M_{s−})} {1 + w((t − s)(1 − y)) − w((t − s)(1 − M_{s−}))} dy.

Hence C_{s,t} can be written as

C_{s,t} = (h_{s}(M_{s−}) − M_{s−}) ds − (k_{s}(M_{s−}) − M_{s−}) ds

− ∫_{M_{s−}}^{k_{s}(M_{s−})} {w((t − s)(1 − y)) − w((t − s)(1 − M_{s−}))} dy ds

+ ∫_{M_{s−}}^{h_{s}(M_{s−})} {w((t − s)(1 − y)) − w((t − s)(1 − M_{s−}))} dy ds

= ∫_{k_{s}(M_{s−})}^{h_{s}(M_{s−})} {1 + w((t − s)(1 − y)) − w((t − s)(1 − M_{s−})} dy ds.

But the expression under the integral sign is, by the definition of the function k, non-negative or non-positive according to y ≤ k_{s}(M_{s−}) or y ≥ k_{s}(M_{s}), respectively. It follows that C_{s,t} is always negative or zero. Again we have an easy upper bound, which is

L_{u}^{t} + w((t − u)(1 − M_{u})) ≤ Y_{u}^{t},

and hence (L_{s}^{t} + w((t − s)(1 − M_{s}))_{0≤s≤t} is a supermartingale. This ends the proof of Lemma 4.1 and completes the proof of Theorem 4.1.[ ]

Application of the uniqueness theorem.

As an application of the preceding theorem we address the link between socalled bin-packing problems and problems of selecting monotone subsequences. This link was discovered by Coffman et al. (1987) for a fixed number of arrivals. We start by listing two equivalent problems.

Equivalent Problems. Let, as before, (N_{t})_{t≥0} be a Poisson process with rate 1 defined on the positive halfline, and occurrence times T_{1} < T_{2} < · · · . a.s.. Let X_{1}, X_{2}, ⋯ be i.i.d. random variables following a common distribution F, and let U_{1}, U_{2}, ⋯ be i.i.d. U[0, 1] random variables.

Problem 1. We observe sequentially (T_{1}, X_{1}), (T_{2}, X_{2}), ⋯ and want to find, for a given t > 0, an online strategy maximizing the expected number of selected X_{j} ′s satisfying

X_{j_{1}} < X_{j_{2}} < · · · .

This is our online Poisson selection problem for a general distribution function F for the X -values.

Problem 2. (Online Poisson bin-packing problem) We observe sequentially (T_{1}, U_{1}), (T_{2}, U_{2}), ⋯ and want to find, for a given t > 0, an online strategy maximizing the expected number of selected U_{j} ’s satisfying

U_{j_{1}} + U_{j_{2}} + ⋯ ≤ 1.

Theorem 4.2 If F is continuous then Problem 1 and Problem 2 are equivalent.

Proof. We give the essential steps of the proof. We first look at Problem 1. Since F is monotone increasing, 0 < F (X_{j_{1}}) < F (X_{j_{2}}) < ⋯ implies X_{j_{1}} < X_{j_{2}} < · · ·. Similarly, the converse holds almost surely. Also, since F is continuous, we have F (X_{1}) ∼ U_{1}, F (X_{2}) ∼ U_{2}, · · ·. Hence, with respect to the objective of maximizing the expected number, Problem 1 is equivalent to the online monotone subsequence problem for i.i.d. uniform X′_{k}s studied in Section 2 of this paper.

Now we turn to Problem 2. Let w(t) be its value. More explicitly, let w(s, x) be the value of the continuation of the optimal strategy, if we have a remaining time s and a remaining bin capacity x, that is, if the sum of the selected U_{j} ’s up to time t − s equals 1 − x. It follows that 0 ≤ x ≤ 1, and w(t, 1) = w(t) by definition.

Now we derive a (partial) differential equation for w(s, x), by conditioning on what happens in [s, s+ϵ[. We can again confine our interest to arrival numbers 0 or 1 on [t − s, t − s + ϵ[, because all probabilities concerning more than one arrival sum up to o(ϵ). There are now three possibilities: either there is no arrival, or there is one, but the associated U -value is too large, or finally there is an arrival with U -value satisfying U ≤ x. Using independence of arrival times and associated U -values we can write the complementary probability of the first two events as (1 − ϵx + o(x)). Then, passing over without a selection yields the future value w(s − ϵ, x), whereas selecting an arrival yields w(s − ϵ, x − u), where u is the realization of a U[0, x] random variable. Hence we obtain

w(s, x) = (1 − ϵx − o(ϵx))w(s − ϵ, x)

+(ϵx + o(ϵx)) ∫_{0}^{x} \frac{max\{1 + w(s − ϵ, x − u), w(s − ϵ, x\}}{x} du.

This is equivalent to

\frac{w(s, x) − w(s − ϵ, x)}{ϵ} = \frac{o(ϵx)}{ϵ} − xw(s − ϵ, x)

+\frac{1}{x} ∫_{0}^{x} max\{1 + w(s − ϵ, x − u), w(s − ϵ, x)\}du.

Clearly the limit of the rhs of this equation exits as ϵ → 0, and so the limit of the lhs exists and equals

\frac{∂w(s, x)}{∂s} = ∫_{0}^{x}[1 + w(s, x − u) − w(s, x)]^{+}du.

Replace x − u by u, s by t, and x by 1. Also, applying the same time-and-rate change as in the proof of Lemma 2.1 we can check that w(t, u) = w(tu, 1) = w(tu). Hence the above equation becomes

\frac{∂w(t, 1)}{∂t} = w′(t) = ∫_{0}^{x}[1 + w(tu) − w(t)]^{+}du,

and since w(0) = 0 this is exactly equation (1.1). From Theorem 4.1, the solution v of (1.1) is unique. Hence w = v. Since v allows for a single optimal strategy yielding at time t the value v(t), it suffices to describe any strategy for Problem 2 which yields v(t):

Define U_{j_{1}} (i.e. the first U_{j} which we select in Problem 2) as being X′_{j_{1}} for Problem 1. Then define recursively S_{k} = U_{j_{1}} + … + U_{j_{k}}, k = 1, 2, ⋯ with U_{j_{k+1}} as being the first U_{j} observed after time T_{j_{k}} such that S_{k} + U_{k+1} does not exceed the maximum acceptance level under the optimal strategy in Problem 1. It is easy to check that this strategy must yield the value v(t), because the increments S_{k+1} − S_{k} in Problem 2 have the same distribution as the increments of the current maximum in Problem 1. [ ]

A trick to display the essence of the equivalence of both problems graphically is to graph the ribbon [0, t]×[0, 1] and to interpret the selection of an observation for both problems simultaneously:

Look at a selected point (T, x), say, in the subsequence problem, say. Playing optimally after time T means in this problem playing optimally on the North-East window [T, t] × [x, 1], where the next acceptable point must exceed x. Reflecting this window on the line y = 1/2 through the ribbon gives us the South-East window of same shape and measure. Interpret 1 − x in this window as the available space for the next increment of the sum for the bin-packing problem.

Concluding remarks

Note that the uniformity assumption for the U′_{j}s is essential for the equivalence between the two problems because it is necessary that the location of the available space is irrelevant. On the other hand, the constant rate of the Poisson arrival process is not essential. If we have a inhomogeneous Poisson process we simply change the rate back to a constant rate by a time scale transformation which, of course, does not affect the distribution of the X_{k} or U_{k}.

Does the asymptotic result for graph-rules (see Corollary 3.1 and Theorem 3.1) for the monotone subsequence problem hold as well for Problem 2? Clearly yes, because it suffices to select each U_{k} which does not push the sum of the previously selected U_{j} ’s above the diagonal line. (We expect this rule also to be limiting optimal among all graph-rules for bin-packing problems, but we do not investigate this question any further.)

Back to Problem 1: One practical solution of the problem is thus to graph the line f(s) = s/t through the ribbon [0, t] × [0, 1] and to select greedily all f - records. This is the “laziest” graph-rule. For finite (even large) t the projection argument is for online strategies of limited value, of course, and there are other simple strategies which perform better. According to the optimality conditions implied by Lemma 2.1, for instance, we can do better by replacing after each selection the old diagonal line by a new one passing through the presently selected point and the point (t, 1). A little reflection shows that this rule is indeed always strictly better.

However, this rule of drawing new lines after each selection is more complicated, so that a convenient approximation of the optimal rule by “close-to-opimal” rules become comparable with respect to online speed, and, due to their asymptotic optimality, clearly preferable. Such close-to-optimal rules are easy to obtain. According to Theorem 2.3 (iii) and Theorem 2.4 (ii) we have close lower and upper bounds for v. Using for instance an approximation v̂ of v in Lemma 2.3 between these bounds (v̂(t) = \sqrt{2t} − \frac{1}{4} log(t), say) will yield close-to-optimal asymptotically optimal results.

Acknowledgment. We thank several referees for very detailed criticisms and thoughtful comments. The Editors and an Associate Editor made further comments and suggestions. We are also grateful to P. A. Meyer for a discussion on infinitesimal generators of martingales.

References

Aldous D.J. and P. Diaconis (1999). Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem. Bulletin Amer. Math. Society, Vol. 36, 413-432.

Arnold, B.C., N. Balakrishnan and H.N. Nagaraja (1998) Records. John Wiley & Sons, New-York, Chichester, Weinheim, Brisbane, Singapore, Toronto.

Baik, J. , P.A. Deift and K. Johansson (1999). On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations. Technical Report math.Co/99810105. To appear in J. Amer. Math. Society.

Baik, J. and E. M. Rains (1999). Algebraic Aspects of Increasing Subsequences. Technical report math.CO/9905083, XXX, Math Archiv.

Baryshnikov Y.M. and A.V. Gnedin (2000). Sequential Selection of an Increasing Sequence from a Multidimensional Random sample. Ann. Appl. Probab., to appear.

Billingsley, P (1995), Probability and Measure Wiley Series in Probability, New York, Chichester, Toronto, Singapore.

Boshuisen, F.A. and R.P. Kertz (1999) Smallest-fit Selection of Random Sizes under a Sum Constarint: Weak convergence and Moment Comparisons. Adv. Appl. Prob. 31, 178-198.

Brémaud, J. (1981). Point Processes and Queues. Springer Verlag New York - Heidelberg - Berlin.

Bruss, F. T. and J. Robertson (1991) “Wald’s Lemma” for Sums of Order Statistics of I.I.D. Random Variables. Adv. Appl. Prob., 23, No. 3, 612-623.

Coffman, E.G. Jr., L. Flatto and R. R. Weber (1987) Optimal Selection of Stochastic Intervals under a Sum Constraint. Adv. Appl. Prob., 19, No. 2, 454-473.

Critchlow, D. (1988). Ulam’s Metric. In Encyclopedia of Statistical Sciences, Vol. 9, 379-380.

Deuschel J.-D. and O. Zeitouni (1995). Limiting Curves for i.i.d. Records. Ann. Probab. 23, 852-878.

Feller, W. (1971) An Introduction to Probability Theory and its Applications, Volume II. Second edition. John Wiley & Sons, New York, London, Sidney, Toronto.

Gnedin, A.V. (1999) Sequential Selection of an Increasing Subsequence from a Sample of Random Size. J. Appl. Prob., 36, No. 4, 1074-1085.

Gnedin, A.V. (2000) Sequential Selection of an Increasing Subsequence from a Random Sample with Geometrically Distributed Sample-Size. In Papers in honor of T.S. Ferguson, (F. Thomas Bruss and Lucien Le Cam, Editors), Lectures Notes of the Institute of Mathematical Statistics - Monograph Series, Vol.35, 101-109.

Gnedin, A.V. (2000 b) A Note on Sequential Selection from Permutations. Combinatorics, Probability and Computing 9, 13-17.

Goldie, C.M. and S.I. Resnick (1996) Ordered Independent Scattering. Commun. Statist.-Stochastic Models, 12 (4), 523-528.

Hammersley, J.M. (1972). A Few Seedlings of Research. Proc. Sixth Berkeley Symp. Math. Stat. Prob. 1, 345-394.

Jacod J. and A.N. Shiryaev (1987). Limit Theorems for Stochastic Processes. Springer Verlag Berlin, Heidelberg, New York, London Paris, Tokyo.

Logan, B.F. and L.A. Shepp (1977). A Variational Problem for Random Young Tableaux. Advances in Math., 26, 206 -222.

Mallows, C.L. (1973). Patience Sorting. Bull. Inst. Math. Appl. 9 216-224.

Protter, P. (1995). Stochastic Integration and Differential Equations. Springer Verlag, Berlin, Heidelberg, New York.

Rhee, W. and M. Talagrand (1991) A Note on the Selection of Random Variables under a Sum Constraint. J. Appl. Prob., 28, 919-923.

Samuels, S.M. and J.M. Steele (1981). Optimal Sequential Selection of a Monotone Sequence from a Random Sample. Ann. Probab. 9, 937-947.

Ulam, S.M. (1972). Some Ideas and Prospects in Biomathematics. Ann. Rev. Biophys. Bioengin., Vol.1, 277-292.

Vers̀ik A.M. and S.V. Kerov (1977). Asymptotics of the Plancherel Measure of the Symmetric Group and the Limiting Form of the Young Tables. Soviet Math. Dokl. 18, 527 - 531.

Authors’ addresses

F. Thomas Bruss, Université Libre de Bruxelles, Département de Mathématique et ISRO, Campus Plaine, CP 210, B-1050 Brussels. (Email: tbruss@ulb.ac.be)

Freddy Delbaen, Eidgenössische Technische Hochschule, Departement für Mathematik, CH-8092 Zürich. (Email: delbaen@math.ethz.ch)