A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:114

Article

Bruss, FT ; Delbaen, F

关键词: 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;   

DOI  :  10.1016/j.spa.2004.09.002

来源: Elsevier

【 摘 要 】

This article provides a refinement of the main results for the monotone subsequence selection problem, previously obtained by Bruss and Delbaen (Stoch. Proc. Appl. 96 (2001) 313). Let (N-s)(sgreater than or equal to0) be a Poisson process with intensity 1 defined on the positive half-line. Let T-1, T-2, ... be the corresponding occurrence 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 less than or equal to u less than or equal to t), where the random variable L-u(t) denotes the number of the selected values up to time it under the t-optimal strategy. 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. (C) 2004 Elsevier B.V. All rights reserved.

【 授权许可】

Free