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

[摘要] 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.

[发布日期] 2001-12-01

[关键词] 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