A CENTRAL LIMIT THEOREM FOR THE OPTIMAL

SELECTION PROCESS FOR 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 provides a refinement of the main results for the monotone subsequence selection problem, previously obtained by Bruss and Delbaen (2001). Let (N_{s})_{s≥0} be a Poisson process with intensity 1 defined on the positive half-line. Let T_{1}, T_{2}, ⋯ be the corresponding occurence times, and 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 observe the (T_{k}, X_{k}) sequentially. Call X_{k} the observed value at time T_{k}. For a given horizon t, consider the objective to select in sequential order, without recall on preceding observations, a subsequence of monotone increasing values of maximal expected length. Let L_{t}^{t} be the random number of selected values under the optimal strategy. Extending the objective of our first paper the main goal of the present paper is to understand the whole process (L_{u}^{t})_{0≤u≤t}. We show that this process obeys, under suitable normalization, a Central Limit Theorem. In particular, we show that this holds in a more complete sense than one would expect. The problem of interdependence of this process with two other processes studied before is overcome by the simultaneous study of three associated martingales. This analysis is based on refined martingale methods, and a non-negligible level of technical sophistication seems unavoidable. But then, the results are rewarding. We not only get the ”right” functional Central Limit Theorem for t tending to infinity but also the (singular) covariance matrix of the three-dimensional process summarizing the interacting processes. We feel there is no other way to understand these interactions, and believe that this adds value to our approach.

Keywords: Martingales, normalization, optimality principle, online selection, Poisson process, intensities, Dynkin’s Theorem, squared variation, predictable process, compensator, infinitesimal generator, bracket process, covariance of processes, functional Central Limit Theorem.

AMS 1991 subject classification: 60G40

Short running title: CLT for Subsequence Selection Process.

1. Introduction. We first recall the problem. For convenience, we use the same notation as in Bruss and Delbaen (2001). This reference will be abbreviated as B&D (2001). Let (N_{s})_{s≥0} be a Poisson process with intensity 1 and with occurrence times 0 < T_{1} < T_{2} < ⋯ a.s.. Define T_{0} = 0. 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. The bivariate variables (T_{k}, X_{k})_{k=1,2,···} can be observed sequentially. For a given horizon t, our objective is to select, under the online-constraint, 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.

1.1 History, update and motivation. The ”father” of this problem, as well as of some other monotone subsequence problems, is, in some sense, the problem of the distribution of the longest increasing subsequence in a random permutation of n different numbers (sometimes called ”Ulam’s problem”). We say ”in some sense” because monotone subsequence problems belong nowadays to two classes, which are indeed very different in structure. One is with and one without sequential selection. The class without selection, to which Ulam’s problem belongs, should be seen as the older and hence classical problem type. The sequential selection type (as in our case), is that class of problems where the numbers are inspected one by one, and where the observer must select on spot (online).

We refer to Aldous and Diaconis (1999) for the (larger) history of the first type. Here, Baik et al (1999) made the essential breakthrough of determining the desired distribution. More recent papers on this problem are Groeneboom’s (2001) new look at the limiting expected lenght (∼ 2\sqrt{n}) and Löwe et al.’s (2002) study of moderate deviations for the length of the longest monotone increasing subsequence. The second type, initiated by Samuels and Steele (1981), is less known. It compensates however through the constraint of sequential selection/search, which is natural in many real-world problems. It thus has some appeal for applications, as exemplified by its link with binpacking problems (Gnedin (2000) and B&D (2001)) and with selection problems under sum-constraints, (Coffman et al.(1987), Bruss and Robertson (1991), Rhee and Talagrand (1991)).

Having said this, we do not imply that this applicational appeal would necessarily bear over to the Central Limit Theorem we are proving in this paper. However, this limit theorem is rewarding because it gives the description of the interdependence of the involved processes in a comprehensive and precise form. Our approach is new, and we believe it truly advertizes the use of sophisticated martingale techniques also outside the more familiar area of cohabitation with stopping times.

1.2 Preliminaries. From B&D (2001) we know that the optimal selection strategy exists, and that the resulting total random number of selections L_{t}^{t} allows for the following tight bounds in expectation and variance. Let v(t) = E(L_{t}^{t}) and σ^{2}(t) = Var(L_{t}^{t}). Then we know already from B&D (2001)

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

and

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

where c, c_{1} and c_{2} are known constants. (See Theorem 2.3 (iii) and Theorem 2.4 (ii), and Theorems 2.7 and 2.8, respectively). These inequalities will be strengthened in Section 3.

The optimal strategy defines at the same time the continuous time counting process of sequential selections, denoted by (L_{u}^{t})_{0≤u≤t}. Associated with this process is the process keeping track of the maximum of the accepted values. We call it the running maximum process, denoted by (M_{u}^{t})_{0≤u≤t} (see page 325 of B&D (2001)). The process M^{t} := (M_{u}^{t}) is basic, the process L^{t} := (L_{u}^{t}) simply counts the jumps of M^{t}. The running maximum sets, by the monotonicity constraint of our problem, a lower threshold for selecting a current observation. Now, if that selection had too large a value, we would restrict ourselves too much in the selection of future values. Hence a time-dependent control is needed. This control is provided by the process of maximum acceptance values which we denote by (h_{u}^{t})_{0≤u≤t}. This process h_{t} : [0, t] × [0, 1] → [0, 1] is linked to the optimal expected length v(t) through an auxiliary function ϕ(t), implicitly defined by v(ϕ(t)) + 1 = v(t), as well as a value α defined by v(α) = 1, or, equivalently, ϕ(α) = 0 (see B&D (2001), Definitions (2.5) and (2.7)). Provided that (t − u)(1 − x) ≥ α, this link is given by the solution of the equation

(1.1)  v((t − u)(1 − h^{t}(u, x))) + 1 = v((t − u)(1 − x)),

where h^{t}(u, x) stands for h_{u}^{t} given that M_{u}^{t} = x. If (t − u)(1 − x) < α, then v((t − u)(1 − x)) < 1, and so it is optimal to accept on the next observation bigger than x. This means we have to define h^{t}(u, x) = 1 if (t − u)(1 − x) < α. Using again the function ϕ, (see B&D (2001, p. 326)), extended by the definition ϕ(y) = 0 for y ∈ [0, α[, we can rewrite this for all 0 ≤ u ≤ t and 0 ≤ x ≤ 1 in the form

(1.2)  h^{t}(u, x) − x = \frac{(t − u)(1 − x) − ϕ((t − u)(1 − x))}{(t − u)}.

We can now describe the properties of the current maximum M^{t} as follows: There are

(i) jumps with intensity λ_{u}^{t} = h^{t}(u, M_{u−}^{t}) − M_{u−}^{t}, 0 ≤ u ≤ t,

and

(ii) jump sizes uniform over [0, h^{t}(u, M_{u−}^{t}) − M_{u−}^{t}], 0 ≤ u ≤ t.

These define the characteristics of the process (M_{u}^{t})_{0≤u≤t}.

To prove our intended limit theorem we must time-scale the processes (L_{u}^{t}) and (M_{u}^{t}) to become (l_{u}^{t}) and (m_{u}^{t}), say, which we define, respectively, by

(1.3)  l_{s}^{t} = L_{st}^{t}, m_{s}^{t} = M_{st}^{t},  0 ≤ s ≤ 1,

and which are our central objects of study.

1.3 Objective and organization of the paper. The main objective of this paper is to understand the whole process (L_{u}^{t})_{0≤u≤t} in more detail, and, in particular, its limiting behaviour as t tends to infinity. Instigated by earlier results (see Theorems 2.7 and 2.8 and Corollary 2.3 of B&D (2001)) we know already that we can expect some Central Limit Theorem to hold. However, it is not easy to see which Central Limit Theorem holds for the whole process, (L_{u}^{t})_{0≤u≤t}. This process is itself a function of the process (M_{u}^{t})_{0≤u≤t} and is therefore an intricate process. Our attack to overcome this difficulty is to study three different processes at the same time. All three will be, as seen in the paper, suitably normalized versions of the following three basic martingales:

(1.4)  l_{s}^{t} − ∫_{0}^{s} du t (h^{t} (ut, m_{u}^{t}) − m_{u}^{t}) ,  0 ≤ s ≤ 1,

(1.5)  l_{s}^{t} + v(t(1 − s)(1 − m_{s}^{t})) − v(t),  0 ≤ s ≤ 1,

(1.6)  m_{s}^{t} − ∫_{0}^{s} du (\sqrt{\frac{t}{2}}(h^{t}(ut, m_{u}^{t}) − m_{u}^{t}))^{2}, 0 ≤ s ≤ 1.

To understand these martingales we must first understand the behavior of h^{t}(ut, m_{u}^{t}) − m_{u}^{t} sufficiently well. This will be studied in Section 2. But then, to control jumps of the martingales (1.4) and (1.6), we need, as we will see, a result of the form

(1.7)  ∫_{0}^{1} (\sqrt{\frac{t}{2}}(h^{t}(ut, m_{u}^{t}) − m_{u}^{t}))^{3}du → 1, as t → ∞.

This is true, and the proof is given, in more generality, in Section 3. Using these results, the Central Limit Theorem is then stated in its precise form and proved in Section 4. This Section also contains our conclusions. In order not to overload the notation, we will not mention the filtration we are using. This is of course the obvious filtration, (F_{u})_{u≥0} coming from the Poisson process and the observed values, see B&D (2001). Since we time transformed the processes, the filtration we will use for horizon t is given by (F_{st})_{0≤s≤1} .

2. The Running-Maximum Process (m_{u}^{t}).

In order to study h^{t}(ut, m_{u}^{t}) − m_{u}^{t}, we must begin with m_{u}^{t}. The process (m_{u}^{t})_{0≤u≤t} is Markov, and its generator can be computed directly from

(2.1)  E [\frac{g(m_{s+ϵ}^{t}) − g(m_{s}^{t})}{ϵ} | m_{s}^{t} = x] → (B_{s}^{t}g)(x) := t ∫_{x}^{h^{t}(st,x)}(g(y) − g(x)) dy.

This is defined for 0 ≤ s ≤ 1 and functions g in the set C[0, 1], the set of continuous functions on [0, 1]. We will use Dynkin’s formula, (see e.g. Protter (1995), p. 48), from which we conclude that for such functions g the processes

(2.2)  D_{s} := (g(m_{s}^{t}) − ∫_{0}^{s}(B_{u}^{t}g)(m_{u}^{t})du)_{0≤s≤1}

are martingales adapted to the filtration (F_{st})_{0≤s≤1}. Using the definition of the intensity (see (i) of Section 1) we then get

(2.3)  E[L_{st}^{t}] = E[l_{s}^{t}] = E[ ∫_{0}^{st} λ_{u}^{t}du]

= t E[ ∫_{0}^{s}(h^{t}(ut, m_{u}^{t}) − m_{u}^{t})du],

where, under integration, the distinction between m_{u−}^{t} and m_{u}^{t} is, of course, irrelevant.

Using Dynkin’s formula for the choice of g being the identity together with the initial condition m_{0}^{t} = 0, we obtain

(2.4)  E[m_{s}^{t}] = E[ ∫_{0}^{s}(B_{u}^{t}g)(m_{u}^{t}) du]

= E[ ∫_{0}^{s} t ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})}(y − m_{u}^{t}) dy du]

= \frac{t}{2}E[ ∫_{0}^{s}(h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{2} du].

Now let

(2.5)  f^{t}(s, x) = \sqrt{t/2} (h^{t}(st, x) − x).

Then we obtain from (2.3) and (2.5)

E[\frac{l_{1}^{t}}{\sqrt{2t}}] = E[\frac{L_{t}^{t}}{\sqrt{2t}}] = E[ ∫_{0}^{1} f^{t}(s, m_{s}^{t}) ds],

which is, by the Cauchy-Schwarz inequality, not larger than

(2.6)  (E[ ∫_{0}^{1} f^{t}(s, m_{s}^{t})^{2}ds])^{1/2} = \sqrt{E[m_{1}^{t}]},

where we used (2.4) in the last equality. Since m_{1}^{t} is bounded by 1, the latter is clearly not larger than 1, so that we get from (2.3) and (2.4) the already known result (see B&D(2001), Theorem 4.2 (ii)),

(2.7)  \frac{v(t)}{\sqrt{2t}} = E[\frac{l_{1}^{t}}{\sqrt{2t}}] ≤ 1.

We also know from B&D (2001) that E[L_{t}^{t}] = v(t) differs from \sqrt{2t} by at most c_{1} log(t) + c_{2} , so that E[L_{t}^{t}/\sqrt{2t}] → 1 as t → ∞. Further we note that

∥f^{t}∥_{1} ≤ ∥f^{t}∥_{2} ≤ 1

and that lim_{t→∞} ∥f^{t}∥_{1} = 1, where all norms are defined on Ω × [0, 1]. But then

∥1 − f^{t}∥_{2}^{2} = E [∫_{0}^{1} (1 − f^{t}(s, m_{s}^{t}))^{2} ds]
= 1 − 2 E[ ∫_{0}^{1} f^{t}(s, m_{s}^{t})ds] + ∥f^{t}∥_{2}^{2}
= 1 − 2∥f^{t}∥_{1} + ∥f^{t}∥_{2}^{2}
≤ 2(1 − ∥f∥_{1})
≤ c log(t)/\sqrt{2t} → 0, as t → ∞.

This implies that, for all 0 ≤ s ≤ 1,

(2.8)  E[ ∫_{0}^{s} (1 − f^{t}(u, m_{u}^{t}))^{2}du] → 0, as t → ∞, ,

so that, for all 0 ≤ s ≤ 1,

E[ ∫_{0}^{s} f^{t}(u, m_{u}^{t}) du] → s, as t → ∞,

which we can rewrite as

(2.9)  E[\frac{L_{st}^{t}}{\sqrt{2t}}] → s, as t → ∞, for all 0 ≤ s ≤ 1.

We now look at the asymptotic behaviour of the expectations of m_{s}^{t} and (m_{s}^{t})^{2} .

The first one is easy, namely, from (2.6) and (2.8),

(2.10)  ∀ 0 ≤ s ≤ 1 : E[m_{s}^{t}] = E[ ∫_{0}^{s} (f^{t}(u, m_{u}^{t}))^{2}du] → s, as t → ∞.

The second one behaves also in the way we hope, but the proof is more intricate. We state this result as a separate Lemma.

Lemma 2.1 For all 0 ≤ s ≤ 1

E[(m_{s}^{t})^{2}] → s^{2} as t → ∞.

Proof. By Dynkin’s formula, now applied with the choice g(x) = x^{2}, we obtain from (2.1) and (2.2)

(2.11)  E[(m_{s}^{t})^{2}] = E[ ∫_{0}^{s} du t ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})} (y^{2} − (m_{u}^{t})^{2})dy]

which can be written in the form

E[ t ∫_{0}^{s} du(\frac{1}{3}[(h^{t}(ut, m_{u}^{t}))^{3} − (m_{u}^{t})^{3}] − (m_{u}^{t})^{2}(h^{t}(ut, m_{u}^{t}) − m_{u}^{t}))].

We now re-arrange the terms in view of obtaining an integral of more tractable (squared and cubic) differences [(h) − (m)]^{3} and [(h) − (m)]^{2}. This yields

(2.12)  E[(m_{s}^{t})^{2}] = E[ ∫_{0}^{s} du t \frac{1}{3}[h^{t}(u, m_{u}^{t}) − m_{u}^{t}]^{3}]

+ E[ ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{2}m_{u}^{t}]

= E_{1}^{t} + E_{2}^{t}, say.

The first term in (2.12), E_{1}^{t}, is up to the factor 2/3,

E[ ∫_{0}^{s} du \frac{t}{2}(h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{3}],

and hence according to (2.5),

E_{1}^{t} = \frac{2}{3}E[ ∫_{0}^{s} (f^{t}(u, m_{u}^{t}))^{2} (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}) du].

However we know from (2.6) that

f^{t}(u, m_{u}^{t}) → 1 in L^{2}(Ω × [0, 1]).

This ensures that (f^{t}(u, m_{u}^{t}))^{2} is uniformly integrable in L^{1}(Ω × [0, 1]). Also

h^{t}(ut, m_{u}^{t}) − m_{u}^{t} = \sqrt{\frac{2}{t}}f^{t}(u, m_{u}^{t}) → 0 i.p.

as t tends to infinity. Note also that the latter is bounded by 1, so that Lebesgue’s Theorem of bounded convergence applies with

E[ ∫_{0}^{s} du t \frac{1}{3}(h^{t}(u, m_{u}^{t}) − m_{u}^{t})^{3}] → 0, as t → ∞.

Hence the first term E_{1}^{t} in (2.12) vanishes as t → ∞.

To look at the second term E_{2}^{t}, we use the following simple Lemma:

Lemma 2.2 If Z_{n} → 1 in L^{1} and E [V_{n}] → x as n → ∞ with 0 ≤ V_{n} ≤ 1, then E[V_{n}Z_{n}] → x.

Proof. |E[V_{n}Z_{n}] − E[V_{n}]| = |E[V_{n}Z_{n} − V_{n}]| ≤ E[V_{n}|Z_{n} − 1|] → 0, as n → ∞.

Returning to the proof of Lemma 2.1 we note that, as t → ∞,

t(h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{2} = 2(f^{t}(u, m_{ut}))^{2} → 2.

Hence, using Lemma 2.2, the second term in (2.9) satisfies:

lim_{t→∞} E[ ∫_{0}^{s} du t m_{u}^{t}(h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{2}]

= lim_{t→∞} E[ ∫_{0}^{s} du 2m_{u}^{t}] = s^{2},

which completes the proof of Lemma 2.1.

We also have the following result as an immediate consequence:

Corollary 2.1 m_{s}^{t} → s i.p. as t → ∞, more precisely sup_{s} |s − m_{s}^{t}| → 0 i.p..

Proof. Using Lemma 2.1 we obtain

(2.13)  E[(s − m_{s}^{t})^{2}] = s^{2} − 2sE[m_{s}^{t}] + E[(m_{s}^{t})^{2}] → 0, as t → ∞,

which proves convergence in mean m_{s}^{t} → s. This implies that m_{s}^{t} → s i.p. as t → ∞. The second part of the corollary follows as well known, from the monotonicity of the process m^{t}.

2.2 The compensator of (m_{u}^{t})_{0≤u≤1}.

Since we know the characteristics of (m_{u}^{t}), we can write its compensator in the form

∫_{0}^{s} du t (h^{t} (ut, m_{u}^{t}) − m_{u}^{t}) ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})} dy(y − m_{u}^{t})\frac{1}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}}

= \frac{1}{2} ∫_{0}^{s} du t (h^{t} (ut, m_{u}^{t}) − m_{u}^{t})^{2}

= ∫_{0}^{s} du (f^{t}(u, m_{u}^{t}))^{2} .

In fact, this is Dynkin’s formula as written in (2.2), and hence from (2.4)

(2.14)  (m_{s}^{t} − ∫_{0}^{s} du (f^{t}(u, m_{u}^{t}))^{2})_{0≤s≤1} is a martingale.

To prove a Central Limit Theorem for the processes L^{t} and M^{t} the above results are not yet sufficient and we need further refinements. In particular, as we indicated already in the Introduction, we need a result about the limiting behavior of ∫_{0}^{s} (f^{t}(ut, m_{u}^{t}))^{3}du. Actually, we will study this problem in the more general form where the power 3 of the integrand is replaced by k ≥ 2. This special case k = 3 seemingly does not reduce the technical difficulties. Hence it is justified to give the more general proof. However, this proof, using several other preliminaries will turn out to be technical indeed, and so the reader may prefer to drop the following section at the first reading.

3. Important technical results.

3.1 Preliminaries

We recall from B&D (2001) the two basic inequalities

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

and the identity

iii) v′(t) = (1 − e^{−t})/t, 0 ≤ t ≤ α,

where α, defined by α = inf{s ≥ 0; v(t) ≥ 1} = 1.34501...., was introduced in (2.5) of B&D(2001).

We now obtain a strengthening of these through the following elementary Lemma.

Lemma 3.1 For 0 ≤ t ≤ 2, and hence in particular for 0 ≤ t ≤ α,

\frac{1}{1 + \sqrt{2t}} ≤ \frac{1 − e^{−t}}{t} ≤ \frac{1}{\sqrt{2t}}

Proof. Let f(t) = \sqrt{2t} and g(t) = t/(1 − e^{−t}). We show that f(t) ≤ g(t) ≤ f(t) + 1 on [0, 2]. f is concave and f(2) = 2, f′(2) = 1/2, hence f(t) ≤ 1 + t/2. Also, g′′ ≥ 0 on [0, 2] since sign{g′′(t)} = sign{e^{−t}(t + 2) + t − 2} ≥ 0 if log(2 + t) − log(2 − t) ≥ t, and this follows from log(2 + t) − log(2 − t) = ∫_{2−t}^{2+t} u^{−1}du = ∫_{0}^{t} ((2 + u)^{−1} + (2 − u)^{−1}) du ≥ ∫_{0}^{t} du = t. Hence g is convex. Therefore, with f(0) < g(0+) = 1 and f(2) < g(2) < f(2) + 1 = 3, we have f(t) ≤ 1 + t/2 ≤ g(t) ≤ 1 + t ≤ f(t) + 1 on [0, 2], and hence the proof.

From Lemma 3.1 and i), ii) and iii) above we now have the following uniform bounds for all t ≥ 0,

(3.1)  v(t) = ∫_{0}^{t} v′(s)ds ≤ ∫_{0}^{t} \frac{1}{\sqrt{2s}} ds = \sqrt{2t}

(3.2)  v(t) = ∫_{0}^{t} v′(s)ds ≥ ∫_{0}^{t} \frac{1}{\sqrt{2s + 1}} ds = \sqrt{2t} − log(1 + \sqrt{2t}).

Note that these bounds are simpler and slightly sharper than our previous ones (B&D, 2001).

3.2 A central result of convergence.

We will use the previous bounds to prove the following theorem, the proof of which will be divided in several parts.

Theorem 3.1 Let f_{u}^{t} be short notation for f^{t}(ut, m_{u}^{t}) (as defined in (2.5)). Then, for all k ≥ 0,

∫_{0}^{1} (f_{u}^{t})^{k} du → 1 i.p. as t → ∞.

The first part of the proof consists in proving the following lemma.

Lemma 3.2 For all s ≤ 1 − \sqrt{2/t} log(1 + \sqrt{2t}) we have

E [1 − m_{s}^{t}] ≤ \frac{4}{s^{2}} (1 − s).

Proof. We first note that

(3.3)  E[L_{st}^{t}] = t E [∫_{0}^{s}(h^{t}(ut, m_{u}^{t}) − m_{u}^{t}) du]

≤ t s^{1/2} (E [∫_{0}^{s}(h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{2}du])^{1/2}

≤ s^{1/2}\sqrt{2t} (E [∫_{0}^{s}(f_{u}^{t})^{2}du])^{1/2}
≤ s^{1/2}\sqrt{2t} (E [m_{s}^{t}])^{1/2} ,

where we applied the Cauchy-Schwarz inequality in the first upper estimate and the definitions of f and m_{s}^{t} in the second and third. Hence

(3.4)  E[m_{s}^{t}] ≥ \frac{1}{s} (E [\frac{L_{st}^{t}}{\sqrt{2t}}])^{2} .

From the dynamic programming principle we recall that, having selected already L_{st}^{t} values, the optimal continuation of our selection strategy yields the expected number v((t(1 − s)(1 − m_{s}^{t})) of acceptable values, so that the total expected number selected under the optimal strategy up to time t, v(t), must satisfy

v(t) = E[L_{st}^{t}] + E[v((t(1 − s)(1 − m_{s}^{t}))].

Equivalently,

E[L_{st}^{t}] = v(t) − E[v((t(1 − s)(1 − m_{s}^{t}))],

and so we obtain from the upper and lower bounds (3.1) and (3.2),

E[L_{st}^{t}] ≥ \sqrt{2t} − log(1 + \sqrt{2t}) − E[\sqrt{2t(1 − s)(1 − m_{s}^{t})}].

From this we deduce

(\frac{E [L_{st}^{t}]}{\sqrt{2t}})^{2} ≥ (1 − \frac{log(1 + \sqrt{2t})}{\sqrt{2t}} − \sqrt{1 − s} E [(1 − m_{st}^{t})^{1/2}])^{2} .

≥ 1 − 2 \frac{log(1 + \sqrt{2t})}{\sqrt{2t}} − 2\sqrt{1 − s} E [(1 − m_{st}^{t})^{1/2}] ,

where we simply neglected the other non-negative terms. From this and from the estimate (3.4) we then get

E [1 − m_{st}^{t}] ≤ 1 − \frac{1}{s}(1 − 2\frac{log(1 + \sqrt{2t})}{\sqrt{2t}} − 2\sqrt{1 − s} E [(1 − m_{st}^{t})^{1/2}] )

≤ 1 − \frac{1}{s} + \frac{2}{s} \frac{log(1 + \sqrt{2t})}{\sqrt{2t}} + \frac{2}{s}\sqrt{1 − s} E [(1 − m_{st}^{t})^{1/2}] .

We note that, for the choice of (1−s) ≥ 2 log(1+\sqrt{2t})/\sqrt{2t}, the first three terms sum up to a negative contribution. Therefore we have

E [1 − m_{st}^{t}] ≤ \frac{2}{s}\sqrt{1 − s} E [(1 − m_{st}^{t})^{1/2}] ≤ \frac{2}{s}\sqrt{1 − s} (E [1 − m_{st}^{t}])^{1/2} ,

which implies

E [1 − m_{st}^{t}] ≤ \frac{4}{s^{2}} (1 − s),

completing the proof.

Remark 3.1 We note, however, that this inequality does not hold in the limit as s → 1−, because m_{st}^{t} is bounded by 0 and 1, and strictly smaller than 1 with positive probability. Thus we need a condition on s.

Lemma 3.3 Let k ≥ 2 and let 0 < ϵ ≤ 1/4. Choose t sufficiently large such that δ = δ(t) := 2 log(1 + \sqrt{2t})/\sqrt{2t} < ϵ. Then

∫_{1−ϵ}^{1−δ} (f_{u}^{t})^{k} du ≤ 4\sqrt{ϵ},

except on a set of measure of at most 8(2ϵ)^{1/k}/(2^{1/k} − 1).

Proof. For the proof we use the inequality

(3.5)  ∀ 0 ≤ u ≤ 1 : f_{u}^{t} = f^{t}(ut, m_{u}^{t}) ≤ \sqrt{\frac{1 − m_{u}^{t}}{1 − u}} ,

which we prove first.

Recall definition (2.5) and equation (1.2). This yields

f_{u}^{t} = \sqrt{\frac{t}{2}} \frac{t(1 − u)(1 − m_{u}^{t}) − ϕ (t(1 − u)(1 − m_{u}^{t}))}{t(1 − u)},

where ϕ(x) = 0 for x ≤ α. We rewrite this as

f_{u}^{t} = \frac{1}{\sqrt{2t}} \frac{t(1 − u)(1 − m_{u}^{t}) − ϕ (t(1 − u)(1 − m_{u}^{t}))}{1 − u},

and use the known result x − ϕ(x) ≤ \sqrt{2x}, x ≥ α (see B&D(2001), Theorem 2.3 (i)). This implies, at the same time, x − ϕ(x) ≤ \sqrt{2x} for x ≤ α, since then, with α < \sqrt{2}, and ϕ(x) = 0, we have x − ϕ(x) = x ≤ \sqrt{2x}. Hence

f_{u}^{t} ≤ \frac{1}{\sqrt{2t}} \frac{\sqrt{2t(1 − u)(1 − m_{u}^{t})}}{1 − u} ≤ \sqrt{\frac{1 − m_{u}^{t}}{1 − u}} ,

as desired.

Now, with δ = 2 log(1+\sqrt{2t})/\sqrt{2t} as defined above, we let n_{0} be the integer such that

2^{n_{0}}δ ≤ ϵ < 2^{n_{0}+1}δ.

Our goal is to find a suitable upper bound for ∫_{1−(2^{n_{0}+1})δ}^{1−δ} (f_{u}^{t})^{k} du. We split this integral into the sum

∫_{1−(2^{n_{0}+1})δ}^{1−δ} (f_{u}^{t})^{k} du = ∑_{j=0}^{n_{0}} ∫_{1−(2^{j+1})δ}^{1−2^{j}δ} (f_{u}^{t})^{k} du,

and define

A_{n} := A_{n}(δ, β) = {ω ∈ Ω : 1 − m_{1−2^{n+1} δ}^{t} > (2^{n} δ)^{β}} , n = 0, 1, ⋯, n_{0},

where β = β(k) = (k − 1)/k. Further let A = A_{0} ∪ A_{1} ∪ · · · . From the preceding Lemma (3.2) and Markov’s inequality we find the simple upper bound

(3.6)  P [A_{n}] ≤ (2^{n}δ)^{−β} E [1 − m_{1−2^{n+1}δ}^{t}]

≤ (2^{n}δ)^{−β} 2^{n+1} δ \frac{1}{(1 − 2^{n+1} δ)^{2}}

≤ 8δ^{1−β} 2^{n(1−β)}
= 8δ^{1/k}2^{n/k}.

The probability of the realization of at least one of the events A_{n} has an upper bound which can be made arbitrarily small, as we will show. Indeed, using (3.6), we see that this probability satisfies

(3.7)  P [ ⋃_{n=0}^{n_{0}} A_{n}] ≤ ∑_{n=0}^{n_{0}} 8δ^{1−β}(2^{1−β})^{n},

≤ 8δ^{1−β} \frac{2^{(1−β)(n_{0}+1)} − 1}{2^{(1−β)} − 1}

≤ \frac{8 × 2^{1/k}}{2^{1/k} − 1} ϵ^{1/k}

where the last inequality follows from 0 < ϵ ≤ 1/4 and β = 1 − 1/k.

We now look at the complement, that is ( ⋃_{n=0}^{n_{0}} A_{n})^{c}, and its probability. For 1 − 2^{n+1} δ ≤ u ≤ 1 − 2^{n}δ and 0 ≤ n ≤ n_{0} we have 1 − u ≥ 2^{n}δ and obtain, using again the upper bound (3.5),

f_{u}^{t} ≤ \sqrt{\frac{1 − m_{u}^{t}}{1 − u}} ≤ \sqrt{(2^{n}δ)^{β}} × \sqrt{2^{−n}δ} = (2^{n}δ)^{−1/(2k)} ,

since, by the definition of A_{n}, we have 1 − m_{u}^{t} ≤ 2^{n+1} δ on [1 − 2^{n+1}δ, 1 − 2^{n} δ]. Therefore (f_{u}^{t})^{k} ≤ (2^{n}δ)^{−1/2} and hence

(3.8)  ∫_{1−2^{n+1}δ}^{1−2^{n}δ} (f_{u}^{t})^{k} du ≤ 2^{n} δ (2^{n}δ)^{−1/2} = (2^{n}δ)^{1/2}.

Consequently, the sum of the preceding integrals for n = 0, 1, ⋯, n_{0} is bounded on A^{c} by

(3.9)  ∑_{n=0}^{n_{0}} \sqrt{2^{n}δ} ≤ \sqrt{δ} \frac{2^{(n_{0}+1)/2}}{\sqrt{2} − 1}

≤ 4δ^{1/2}2^{n_{0}/2} ≤ 4\sqrt{ϵ},

where we used \sqrt{2}/(\sqrt{2} − 1) = 2 + \sqrt{2} ≤ 4 in the first inequality in (3.9), and 2^{n_{0}}δ < ϵ in its second one. Taking both arguments with the bounds (3.6) and (3.7) together we conclude that, except on a set of measure of at most 8 × (2ϵ)^{1/k}/(2^{1/k} − 1), the statement

∫_{1−ϵ}^{1−δ} (f_{u}^{t})^{k} du ≤ 4\sqrt{ϵ}

holds. This proves Lemma 3.3

Before we pass to the next Lemma and its proof, we should motivate it: We have information on the product space [0, 1] × Ω, and we need information regarding the L^{k} -behaviour of the time integrals, and this for large sets of ω ∈ Ω. This is in the spirit of a Fubini theorem. However, we only have information about L^{2} -convergence, that has to be turned into L^{k} -convergence or boundedness for k > 2. This is only possible if we have an extra upper bound going beyond the exponent k, that is, in our case, the L^{∞} -bound. The upper bound only holds up to time 1 − ϵ, since there the integrands are bounded by a number depending on ϵ only.

Lemma 3.4 For all ϵ > 0 there exists t_{0} := t_{0}(ϵ) such that, except on a set of measure at most ϵ, we have

∀ t ≥ t_{0} : |1 − ∫_{0}^{1−ϵ} (f_{u}^{t})^{k} du| < 2ϵ.

Proof: For given ϵ > 0 we take η > 0 such that

(3.10)  (a) (1 + η^{1/k})^{k} ≤ 1 + ϵ and (b) ((1 − ϵ)^{1/k} − η^{1/k})^{k} ≥ 1 − 2ϵ.

Since (a) and (b) both hold strictly in η = 0 for all k = 1, 2, ⋯, and both functions of η are continuous, such η > 0 exists.

Our construction will use the triangle inequality for the L^{k} norms of the indicator of the interval [0, 1 − ϵ] and of (1 − f). The latter is estimated by η^{1/k}, the former is precisely (1 − ϵ)^{1/k}. Indeed, we know that for u ≤ 1 − ϵ, |1 − f_{u}^{t}|^{k} is uniformly bounded by K = \sqrt{1/(1 − ϵ)}, and hence

∫_{0}^{1−ϵ} |1 − f_{u}^{t}|^{k} du ≤ ∫_{0}^{1−ϵ} K^{k−2} |1 − f_{u}^{t}|^{2} du ≤ ∫_{0}^{1} K^{k−2} |1 − f_{u}^{t}|^{2} du.

This tends to 0 in probability as t → ∞, since f_{u}^{t} tends to 1 in L^{2} on Ω × [0, 1]. We therefore have that, for t sufficiently large,

∫_{0}^{1−ϵ} |1 − f_{u}^{t}|^{k} ≤ η,

except on a set of measure at most ϵ. The triangular inequality for the L^{k} -norm and (3.10) (a) now imply that

(3.11)  ∫_{0}^{1−ϵ} (f_{u}^{t})^{k} du ≤ (1 + η^{1/k})^{k} ≤ 1 + ϵ.

The same triangular inequality implies with (3.10) (b) that

(3.12)  ∫_{0}^{1−ϵ} (f_{u}^{t})^{k} du ≥ ((1 − ϵ)^{1/k} − η^{1/k})^{k} ≥ 1 − 2ϵ.

Clearly, (3.11) and (3.12) imply the Lemma. . Finally, we must study the integral over the remaining interval [1 − δ, 1]. Lemma 3.5 For all ϵ > 0 there exists t_{0} such that for t > t_{0}

∫_{1−δ}^{1}(f_{u}^{t})^{k}du ≤ ϵ, except on a set of mesure ≤ ϵ,

where, as before, δ = δ(t) = \sqrt{2/t} log(1 + \sqrt{2t}). Proof. Using h^{t}(ut, m_{u}^{t}) − m_{u}^{t} ≤ 1 − m_{u}^{t} we have f_{u}^{t} ≤ \sqrt{\frac{t}{2}} (1 − m_{u}^{t}), and hence

∫_{1−δ}^{1} (f_{u}^{t})^{k} du ≤ ∫_{1−δ}^{1} (\frac{t}{2})^{k/2} (1 − m_{u}^{t})^{k}du.

Now E (1 − m_{1−δ}^{t}) ≤ 4δ/(1 − δ)^{2} because of Lemma 3.2. For given ϵ > 0 take now K ≤ 8/ϵ. Then

P(1 − m_{1−δ} > Kδ) ≤ 4/(K(1 − δ)^{2}) ≤ ϵ

since 1/(1 − δ)^{2} ≤ 2 for t ≥ t_{0} . Therefore ∫_{1−δ}^{1} (f_{u}^{t})^{k} du ≤ (t/2)^{k/2}(Kδ)^{k}δ (except on a set of measure ≤ ϵ)

≤ K^{k}2^{−k/2}t^{k/2} (\frac{2}{\sqrt{2t}} log(1 + \sqrt{2t}))^{k+1}

≤ (\frac{8}{ϵ})^{k} \sqrt{\frac{2}{t}} (log(1 + \sqrt{2t}))^{k+1}

≤ ϵ, for t ≥ t_{0},

except on a set of measure of at most ϵ, as required.

3.3 Return to the main proof. We are now ready to return to the proof of Theorem 3.1.

Combining the statements of the four preceding results (that is Lemma 3.2 - Lemma 3.5) and writing

∫_{0}^{1} (f_{u}^{t})^{k} du = ∫_{0}^{1−ϵ} (f_{u}^{t})^{k} du + ∫_{1−ϵ}^{1−δ} (f_{u}^{t})^{k} du + ∫_{1−δ}^{1} (f_{u}^{t})^{k} du,

we conclude that, for arbitrary ϵ > 0, and except on a set of measure of at most constant times ϵ^{1/k} (with the constant not depending on ϵ) exceeds 1 − 2ϵ but does not exceed 1 + 5ϵ. This shows that ∫_{0}^{1} (f_{u}^{t})^{k} du → 1 i.p. as t → ∞, proving Theorem 3.1.

We can also show (but omit the proof) that Theorem 3.1 implies

Corollary 3.1 For all 1 < k < ∞ we have

∫_{0}^{1} |1 − f_{u}^{t}|^{k} du → 0 i.p., as t → ∞.

4. The Central Limit Theorem.

4.1 The three martingales.

Recall the three martingales defined in (1.4) - (1.6), that is

(i) l_{s}^{t} − ∫_{0}^{s} du t (h^{t} (ut, m_{u}^{t}) − m_{u}^{t})
(ii) l_{s}^{t} + v(t(1 − s)(1 − m_{s}^{t})) − v(t)
(iii) m_{s}^{t} − ∫_{0}^{s} du (f^{t}(ut, m_{u}^{t}))^{2},

where we used for (iii) the now familiar f^{t}(., .)-notation introduced in (2.5). We will now normalize these three martingales and then compute the skew brackets at time 1.

For our approach we refer to Jacod and Shiryaev ((1987), see pp. 429-432)

4.2 Choice of adequate normalization.

Remember that for a martingale (V_{u})_{0≤u≤1} , the skew bracket process ⟨V, V ⟩ is defined as the compensator of the process [V, V]. Recall also that our martingales are of finite variation, and hence

(4.1)  [V, V]_{s} = ∑_{0<u≤s} (ΔV_{u})^{2} < ∞, 0 ≤ s ≤ 1.

We follow the order of the martingales as given above.

Martingale (i) Jumps, whenever they occur, are of size 1. Recall (2.8) and remember that

(4.2)  ∫_{0}^{1} du t (h^{t}(ut, m_{m}^{t}) − m_{u}^{t}) → 1 as t → ∞.

This implies

Var (L_{t}^{t} − ∫_{0}^{t} du (h^{t}(u, M_{u}^{t}) − M_{u}^{t}))
= Var (l_{1}^{t} − ∫_{0}^{1} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}))
= E [∫_{0}^{1} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})]
= \sqrt{2t} E [∫_{0}^{1} du f^{t}(u, m_{u}^{t})] ∼ \sqrt{2t}.

This asymptotic behaviour suggests the normalization (\sqrt{2t})^{1/2} and leads us to the process

(4.3)  ^{1}Z_{s}^{t} := \frac{(l_{s}^{t} − ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}))}{(\sqrt{2t})^{1/2}}

with the skew bracket process satisfying, as t tends to infinity,

(4.4)  ⟨^{1}Z_{s}^{t}, ^{1}Z_{s}^{t}⟩_{s} = \frac{1}{\sqrt{2t}} ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}) → s.

Martingale (ii) This is more work because the jump sizes (when jumps occur) are now

(4.5)  j(s, m_{s}^{t}) := 1 + v(t(1 − s)(1 − m_{s}^{t})) − v(t(1 − s)(1 − m_{s−}^{t})).

Using the characteristics this gives a skew bracket

∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}) ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})} \frac{(j(u, z))^{2} dz}{h^{t}(ut − m_{u}^{t}) − m_{u}^{t}}

≥ \frac{1}{3} ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}) .

Here we used that jump sizes are, according to the Poisson process setting, uniform on [0, h^{t}(ut − m_{u}^{t}) − m_{u}^{t}] (yielding under integration the factor 1/3 for the squared term), and also the concavity of v. (See the proof of Theorem 2.7 of B&D (2001)). This is a lower bound. The upper bound

\frac{1}{3} ∫_{0}^{s} du t (h^{t}(ut − m_{u}^{t}) − m_{u}^{t}) + c_{1} + c_{2} log(t)

can be obtained similarly. This suggests the normalization (\frac{1}{3} \sqrt{2t})^{1/2} , and hence we define

2Z_{s}^{t} := \frac{l_{s}^{t} + v(t(1 − s)(1 − m_{s}^{t})) − v(t)}{(\frac{1}{3} \sqrt{2t})^{1/2}}.

Its skew bracket process satisfies

⟨^{2}Z^{t}, ^{2}Z^{t}⟩_{s} = \frac{1}{(1/3)\sqrt{2t}} ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})

×\frac{1}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}} ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})} dz (j(u, z))^{2})

≥ \frac{1}{\sqrt{2t}} ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}),

with an error term of order \frac{log(t)}{\sqrt{t}}. But then for all 0 ≤ s ≤ 1,

⟨^{2}Z^{t}, ^{2}Z^{t}⟩_{s} − ∫_{0}^{s} du f^{t}(u, m_{u}^{t}) → 0 i.p., as t → ∞.

This implies ⟨^{2}Z^{t}, ^{2}Z^{t}⟩_{s} → s i.p. as t tends to infinity.

Martingale (iii)

This is the most challenging one. Using characteristics we obtain

(4.6)  ∫_{0}^{t} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}) \frac{1}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}} ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})}(y − m_{u}^{t})^{2} dy

= \frac{1}{3} ∫_{0}^{s} t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{3}du

= \frac{1}{3} ∫_{0}^{s} (\sqrt{\frac{t}{2}} (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}))^{3} \frac{2^{3/2}}{t^{1/2}} du

= \frac{2}{3}\sqrt{\frac{2}{t}} ∫_{0}^{s} du (f^{t}(u, m_{u}^{t}))^{3} .

So we define ^{3}Z_{s}^{t} by

3Z_{s}^{t} := (\frac{3}{2}\sqrt{\frac{t}{2}})^{1/2} (m_{s}^{t} − ∫_{0}^{s} du(f^{t}(ut, m_{u}^{t}))^{2}) .

Lemma 3.3 with k = 3 now applies and this yields that ⟨^{3}Z^{t},^{3}Z^{t}⟩_{s} tends to s i.p..

4.2 The computation of the ⟨^{i}Z^{t}, ^{j}Z^{t}⟩_{s}.

In order to get a Central Limit Theorem we must also control the processes ⟨^{i}Z^{t}, ^{j}Z^{t}⟩_{s} for j ≠ i, (which we call the (i, j)-terms, respectively.)

For the (1, 2)-term we obtain

⟨^{1}Z^{t}, ^{2}Z^{t}⟩_{s} = (\frac{1}{\sqrt{2t}})^{1/2} ( \frac{1}{\sqrt[\frac{1}{3}]{2t}})^{1/2} ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})

×\frac{1}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}} ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})} (1 + v (t(1 − u)(t − z)) − v (t(1 − u)(1 − m_{u}^{t}))) dz,

which is, by concavity of v, at least as large as

\begin{matrix}√ & \overline{3} \\ √ & \overline{2t} \end{matrix} ∫_{0}^{s} du t(h^{t}(ut, m_{u}^{t}) − m_{u}^{t})\frac{1}{2}

= \frac{\sqrt{3}}{2} ∫_{0}^{s} du\sqrt{t/2}(h^{t}(ut, m_{u}^{t}) − m_{u}^{t}).

The latter tends, as we know from Section 2, to (\sqrt{3}/2)s as t tends to infinity. The same trick can, as we shall see, be applied to compute the difference

E [⟨^{1}Z^{t}, ^{2}Z^{t}⟩_{s} − \frac{\sqrt{3}}{2} ∫_{0}^{1} du\sqrt{\frac{t}{2}} (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}))] .

Indeed, we see that the expression

\begin{matrix}√ & \overline{3} \\ √ & \overline{2t} \end{matrix} E[ ∫_{0}^{1} du t h^{t}(ut, m_{u}^{t}) − m_{u}^{t}) × \frac{1}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}}

× ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})} {1 + v(t(1 − u)(1 − z)) − v((t(1 − u)(1 − m_{u}^{t})

− (\frac{h^{t}(ut, m_{u}^{t}) − z}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}} ) \} dz ]

is bounded by \sqrt{3/2t} (c_{1} + c_{2} log(t)) and tends therefore to zero as t tends to infinity.

It follows that ⟨^{1}Z^{t}, ^{2}Z^{t}⟩_{s} → (\sqrt{3}/2) s as t → ∞.

We now deal with the (1, 3)-term ⟨^{1}Z^{t}, ^{3}Z^{t}⟩_{s}, which is rather straightforward. The characterization yields

(\frac{1}{\sqrt{2t}})^{1/2} (\frac{3}{2}\sqrt{\frac{t}{2}})^{1/2} ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})

×\frac{1}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}} ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})} 1 (y − m_{u}^{t})dy

= \frac{\sqrt{3}}{2} ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{2} \frac{1}{2},

which tends, as we know from before, to (\sqrt{3}/2) × 2s × (1/2) = (\sqrt{3}/2)s as t → ∞.

The (2, 3)-term ⟨^{2}Z^{t}, ^{3}Z^{t}⟩_{s} is again more difficult. We obtain

(4.7)  (\frac{3}{\sqrt{2t}})^{1/2} ((3/2)\sqrt{t/2})^{1/2} ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})

× ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})} \frac{(y − m_{u}^{t})}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}}

×(1 + v(t(1 − u)(1 − y)) − v(t(1 − u)(1 − m_{u}^{t}))dy

≥ \frac{3}{2} ∫_{0}^{s} du t ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})}(y − m_{u}^{t}) \frac{h^{t}(ut, m_{u}^{t}) − y}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}} dy

With the substitution

z = (y − m_{u}^{t})/(h^{t}(ut, m_{u}^{t}) − m_{u}^{t})

it is straightforward to check that the rhs of (4.7) equals

\frac{3}{2} ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{2} ∫_{0}^{1} z(1 − z)dz

= \frac{1}{4} ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{2} ,

which tends to (1/4) × 2s = s/2 as t tends to infinity.

To see that this is the exact expression, we apply the same trick as before, although it is now more involved:

E[ ∫_{0}^{1} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}) × ∫_{m_{u}^{t}}^{h^{t}(ut,m_{u}^{t})} \frac{(y − m_{u}^{t})}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}}

(1 + v(t(1 − u)(1 − y)) − v(t(1 − u)(1 − m_{u}^{t}) − \frac{h^{t}(ut, m_{u}^{t}) − y}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}} )dy]

(4.8)  ≤ E[ ∫_{0}^{s} t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t}) \frac{1}{2} × sup_{y∈[m_{u}^{t},h^{t}(ut,m_{u}^{t})]}\{η^{t}(u, y)\} du],

where

(4.9)  η^{t}(u, y) = 1 + v(t(1 − u)(1 − y)) − v(t(1 − u)(1 − m_{u}^{t}) − \frac{h^{t}(ut, m_{u}^{t}) − y}{h^{t}(ut, m_{u}^{t}) − m_{u}^{t}} .

But now η^{t}(u, y) lies between 0 and 1 so that the same is true for the corresponding supremum, η_{u}^{t} say, in the integrand of (4.8). Moreover, for each 0 ≤ u ≤ 1 we know that m_{u}^{t} → u as t → ∞ and hence

t(1 − u)(1 − m_{u}^{t}) → t(1 − u)^{2} as t → ∞.

For any 0 ≤ u ≤ 1 the latter is larger than α (see B&D (2001)) for t big enough, so that we can bound η_{u}^{t} from above exactly as in Lemma 2.4 of B&D (2001), that is, bound it by

(4.10)  c sup_{y∈[m_{u}^{t},h^{t}(ut,m_{u}^{t})]} {v′′(t(1 − u)(1 − y))(−1)t^{2}(1 − u)^{2} (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{2}}

= c t (1 − u)^{2} ( sup_{y∈[m_{u}^{t},h^{t}(ut,m_{u}^{t})]} {v′′(t(1 − u)(1 − y))(−1)})

×((h^{t}(ut, m_{u}^{t}) − m_{u}^{t})^{2} \frac{t}{2}).

The last factor tends to 1 i.p. as we know. Also, since m_{u}^{t} and h^{t}(ut, m_{u}^{t}) both tend to u i.p as t → ∞, the middle factor behaves asymptotically like

(t(1 − u)^{2})^{−3/2} .

Taking both arguments together this implies that the supremum η_{u}^{t} tends to 0 i.p. with an order t^{−1/2} as t → ∞.

Finally, we note that the functions (t/2) (h^{t}(u, t, m_{u}^{t}) − m_{u}^{t})^{2} are uniformly integrable on L^{1}(Ω × [0, 1]) so that Lebesgue’s Theorem applies, and the whole expression tends to zero.

Hence we conclude that

⟨^{2}Z^{t}, ^{3}Z^{t}⟩_{s} → \frac{1}{4}s i.p as t → ∞.

4.4 The control of jumps of Z^{t} as a martingale in IR^{3}.

The next step is the control of jumps of Z^{t}. For this, of course, only the jumps of the process ^{3}Z^{t} have to be controlled.

Previous estimates showed that, conditioned on the event of a jump at time s, the corresponding jump size is bounded by

h^{t}(st, m_{s}^{t}) − m_{s}^{t} ≤ min \{ 1 − m_{s}^{t}, \sqrt{\frac{2(1 − m_{s}^{t})}{(1 − s)t}} \}

We will now show that

(4.11)  sup_{0≤s≤1} {(h^{t}(st, m_{s}^{t}) − m_{s}^{t}) t^{1/4}} → 0 i.p. as t → ∞.

This will imply that

sup_{0≤s≤1} |ΔZ_{s}| → 0 i.p.,

a result we need in order to apply the conditions as presented by Jacod and Shiraev (see Jacod and Shiraev (1987), Ch VI, Prop. 3.2.6 and Ch VIII, Sect. 3.b)

To see this, let ϵ > 0 and K = 1/ϵ^{2}. Further let I_{1} = [0, 1 − Kt^{−1/2}] and I_{2} =]1 − Kt^{−1/2}, 1]. Then clearly

(4.12)  sup_{0≤s≤1} {(h^{t}(st, m_{s}^{t}) − m_{s}^{t}) t^{1/4}} ≤ (sup_{I_{1}} + sup_{I_{2}}) {(h^{t}(st, m_{s}^{t}) − m_{s}^{t}) t^{1/4}} .

On the one hand we have on I_{1}

(4.13)  t^{1/4} (h^{t}(st, m_{s}^{t}) − m_{s}^{t}) ≤ t^{1/4}\sqrt{\frac{2(1 − m_{s}^{t})}{(1 − s)t}} ≤ \sqrt{2} t^{1/4}\sqrt{\frac{1}{Kt^{1/2}}} = \sqrt{2} ϵ.

On the other hand, on I_{2} we have the upper bound

sup_{s∈I_{2}} (1 − m_{s}^{t}) t^{1/4} ≤ t^{1/4} (1 − m_{1−Kt^{−1/2}}^{t}) ,

and here a closer analysis is needed. We look first at the expectation of this bound, that is E [t^{1/4} (1 − m_{1−Kt^{−1/2}}^{t})] , and use the bounds obtained in Section 2 (see (2.4)-(2.6)). This yields for all 0 ≤ s ≤ 1,

(4.14)  E [m_{s}^{t}] ≥ \frac{(E [L_{st}^{t}])^{2}}{2t}

Therefore

(4.15)  μ(t, k) := E [t^{1/4} (1 − m_{1−Kt^{−1/2}}^{t})]

≤ t^{1/4} (1 − \frac{(E [L_{t(1−Kt^{−1/2})}^{t}])^{2}}{2t} )

= t^{1/4} (1 − \frac{(E [L_{t−K\sqrt{t}}^{t}])^{2}}{2t} ) .

Secondly, the dynamic programming equality in B&D (2001) gave us, for all u ∈ [0, t],

E[L_{u}^{t}] + E[v((t − u)(1 − m_{u}^{t}))] = E[L_{t}^{t}] = v(t)

and hence, recalling m_{u}^{t} = M_{ut}^{t},

E [L_{t−K\sqrt{t}}^{t}] = v(t) − E [v(K\sqrt{t}(1 − M_{t−K\sqrt{t}}^{t}))] .

Now use that t−K\sqrt{t} ≥ t−tϵ^{4} for t sufficiently large so that M_{t−K\sqrt{t}}^{t} ≥ M_{t−ϵ^{4}t}^{t}. Using this and our upper bound (3.1) we get

E [L_{t−K\sqrt{t}}^{t}] ≥ v(t) − E [v(K\sqrt{t}(1 − M_{t−ϵ^{4}t}))]
≥ v(t) − E [\sqrt{2K\sqrt{t}(1 − M_{t−ϵ^{4}t})}]
≥ v(t) − (2K\sqrt{t})^{1/2}E[\sqrt{1 − M_{t−ϵ^{4}t}}],

and hence, from Jensen’s inequality,

(4.16)  E [L_{t−K\sqrt{t}}^{t}] ≥ v(t) − (2K\sqrt{t})^{1/2} (E[1 − M_{t−ϵ^{4}t}])^{1/2} .

Now, we know that E[M_{t−ϵ^{4}t}] → 1 − ϵ^{4} as t → ∞. Therefore we have, in

particular, E[1 − M_{t−ϵ^{4}t}] ≤ 2ϵ^{4} for t sufficiently large, so that from (4.15),

E [L_{t−K\sqrt{t}}^{t}] ≥ v(t) − (2K\sqrt{t})^{1/2}\sqrt{2} ϵ^{2},

≥ v(t) − 2ϵt^{1/4}, for t sufficiently large.

This implies from (4.15)

μ(t, k) ≤ t^{1/4} (1 − \frac{(v(t) − 2ϵt^{1/4}))^{2}}{2t} ) ,

and since, for t big enough, v(t) ≥ \sqrt{2t} − c log(t) ≥ \sqrt{2t} − ϵt^{1/4}, we get

μ(t, k) ≤ t^{1/4} (1 − \frac{(\sqrt{2t} − 3ϵt^{1/4}))^{2}}{2t} )

≤ t^{1/4} (1 − \frac{1}{2t} (2t − 6ϵ\sqrt{2t} t^{1/4} + 4ϵ^{2}t^{1/2}))

≤ t^{1/4}(3ϵ t^{−1/4}), for t sufficiently large,

≤ 3ϵ.

Hence, taking the bounds on I_{1} and I_{2} (see (4.13) and (4.17)) together, these add up to \sqrt{2} ϵ + 3ϵ < 5ϵ, and so

E [ sup_{0≤s≤1} |Δ(^{3}Z^{t})_{s}|] ≤ 5 ϵ, for t sufficiently large.

4.5 Conclusions. This finishes the study of the control of all the relevant terms and we can now apply the mentioned theorem (Jacod and Shiraev (1987)). According to this, wo otain the main result:

Theorem 4.1 (The functional Central Limit Theorem.) The threedimensional process (Z_{s}^{t})_{0≤s≤1} with components

1Z_{s}^{t} := \frac{1}{(\sqrt{2t})^{1/2}} (l_{s}^{t} − ∫_{0}^{s} du t (h^{t}(ut, m_{u}^{t}) − m_{u}^{t})),

2Z_{s}^{t} := \frac{1}{(\frac{1}{3} \sqrt{2t})^{1/2}} (l_{s}^{t} + v(t(1 − s)(1 − m_{s}^{t})) − v(t)),

3Z_{s}^{t} := (\frac{3}{2}\sqrt{\frac{t}{2}})^{1/2} (m_{s}^{t} − ∫_{0}^{s} du(f^{t}(ut, m_{u}^{t}))^{2}) ,

tends to a three-dimensional Brownian Motion X^{t} with covariance matrix given by

(4.17)  C = ( \begin{matrix}1 & \frac{\sqrt{3}}{2} & \frac{\sqrt{3}}{2} \\ \frac{\sqrt{3}}{2} & 1 & \frac{1}{2} \\ \frac{\sqrt{3}}{2} & \frac{1}{2} & 1 \end{matrix} ) .

Furthermore we have

E [X_{s} · X′_{u}] = min{s, u} · C, 0 ≤ s, u ≤ 1.

Corollary 4.1 (The Central Limit Theorem.) The random variables

\frac{L_{t}^{t} − v(t)}{(\frac{1}{3} \sqrt{2t})^{1/2}}

and

\frac{L_{t}^{t} − \sqrt{2t}}{(\frac{1}{3} \sqrt{2t})^{1/2}}

tend to a standard normal variable.

Proof. This follows from the functional Central Limit where we have put s = 1 in the second martingale ^{2}Z^{t}. The second line of the statement follows easily since the difference between v(t) and \sqrt{2t} is of order log(t).

We will now use the functional Central Limit Theorem to get another convergence theorem. First we recall from section 2, that ∥1 − f^{t}∥_{2}^{2} ≤ \frac{c log(t)}{\sqrt{t}}. From

this it follows that (t)^{1/4} ∫_{0}^{1}(1 − f_{u}^{t})^{2} du converges to zero i.p.. This can also be written as

sup_{0≤s≤1}(t)^{1/4} |∫_{0}^{s} f_{u}^{t} du − \frac{1}{2} ∫_{0}^{s}(1 + (f_{u}^{t})^{2}) du| → 0 i.p.

The first martingale can therefore be tranformed into

z_{s}^{t} = \frac{1}{(\sqrt{2t})^{1/2}} (l_{s}^{t} − \frac{\sqrt{2t}}{2} ∫_{0}^{s}(1 + (f_{u}^{t})^{2}) du) ,

which will converge to a normalised Brownian Motion. Furthermore the three dimensional process (z^{t}, ^{2}Z^{t}, ^{3}Z^{t}) converges to a three dimensional process having the same covariance matrix as the limit of (^{1}Z^{t}, ^{2}Z^{t}, ^{3}Z^{t}). Introducing the third martingale in the definition of z^{t}, allows us to write this as

z_{s}^{t} = \frac{1}{(\sqrt{2t})^{1/2}} (l_{s}^{t} − \frac{\sqrt{2t}}{2} (s + m_{s}^{t} − (m_{s}^{t} − ∫_{0}^{s}(f_{u}^{t})^{2} du))) ,

which of course is the same as

z_{s}^{t} = \frac{1}{(\sqrt{2t})^{1/2}} (l_{s}^{t} − \sqrt{2t} \frac{s + m_{s}^{t}}{2} ) + \frac{\sqrt{2t}^{1/2}}{2} (m_{s}^{t} − ∫_{0}^{s}(f_{u}^{t})^{2} du) ,

We now multiply this expression with \sqrt{3} and substract the process ^{3}Z^{t}. The resulting process will, as a simple calculation using the covariances shows, converge to a normalised Brownian motion. We get the following

Corollary 4.2 The process, defined for 0 ≤ s ≤ 1 by

\frac{\sqrt{3}}{(\sqrt{2t})^{1/2}} (l_{s}^{t} − \sqrt{2t} \frac{s + m_{s}^{t}}{2} ) ,

converges to a standard Brownian Motion.

Remark 4.1 The covariance-matrix in Theorem 4.1 is singular. The linear combination \sqrt{3}^{1}Z^{t} − ^{2}Z^{t} − ^{3}Z^{t} tends to zero in law and therefore also in probability. More precisely

sup_{0≤s≤1} |\sqrt{3}^{1}Z_{s}^{t} − ^{2}Z_{s}^{t} − ^{3}Z_{s}^{t}| → 0 i.p.

The difference between

\frac{\sqrt{3}}{(\sqrt{2t})^{1/2}} (l_{s}^{t} − \sqrt{2t} \frac{s + m_{s}^{t}}{2} )

and ^{2}Z^{t} is a process that also tends to zero. The reader can check that, after some tedious calculations, the above implies that (2t)^{1/4}(s−m_{s}^{t})^{2} → 0 i.p. but it does not give more information on the nature of the limit of (2t)^{1/4}(s − m_{s}^{t}). We remark that the inequalities (2.6) and the ones preceding it yield that E[m_{1}^{t}] ≥ (v(t)/\sqrt{2t})^{2} . Since v(t) ≥ \sqrt{2t} − log(1 + \sqrt{2t}), this implies that E[1 − m_{1}^{t}] ≤ c log(t)/\sqrt{2t}. As a consequence we have that (2t)^{1/4}(1 − m_{1}^{t}) → 0 i.p..

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.

Baik, J., P.A. Deift and K. Johansson (1999). On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations. J. Amer. Math. Society, 12, 1119-1178.

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.

Bruss, F. T. and F. Delbaen (2001) Optimal Rules for the Sequential Selection of Monotone Subsequences of Maximum Expected Length. Stoch. Proc. Applic., 96, 313-342.

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.

Gnedin, A.V. (2000) Sequential Selection of an Increasing Subsequence from a Random Sample with Geometrically Distributed Sample-Size. In Lect. Notes of the Inst. of Math. Stat. (F. T. Bruss and L. Le Cam, Editors) Vol. 35, 101-109.

Groeneboom, P. (2001) Ulam’s Problem and Hammersley’s Process. Ann. Probab., 29, 683-690.

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

Löwe, M., F. Merkl, and S. Rolles (2002) Moderate Deviations for Longest Increasing Subsequences. J. Theoretical Probability, Vol. 15, No 4, 1031-1047.

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. Bioeng. 1, 277-292.

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)