Optimal rules for the sequential selection of monotone subsequences of maximum expected length

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:96

Article

Bruss, FT ; Delbaen, F

关键词: Poisson process;    online selection problems;    Baker's problem;    bin-packing;    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;   

DOI  :  10.1016/S0304-4149(01)00122-3

来源: Elsevier

【 摘 要 】

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 nu (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 nu (t), nu'(t) and nu(t) exist everywhere on R+. Then, in particular, we prove that nu(t) < 0 for all t is an element of [0, infinity[, implying that v is strictly concave on R+. This settles a conjecture of Gnedin and opens the way to stronger bounds for v and its derivatives. We can show nu'(t)root 2t similar to 1 from which we derive new and much tighter bounds for nu (t), namely root 2t - log(1 + root 2t) + c less than or equal to nu (t) less than or equal to root 2t. Using a martingale approach, we can show that the variance of L-t(t) satisfies 1/3v(t) less than or equal to Var(L-t(t)) less than or equal to 1/3v(t) + c(1) log(t) + c(2). Further we obtain several results on the process (L-u(t))(0 less than or equal tou less than or equal tot), 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 nu (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. (C) 2001 Published by Elsevier Science B.V.

【 授权许可】

Free