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

F. Thomas Bruss and Freddy Delbaen

Stochastic Processes and their Applications, 2001, vol. 96, issue 2, 313-342

Abstract: 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 Ltt up to time t. We first show that v(t), v'(t) and v''(t) exist everywhere on . Then, in particular, we prove that v''(t)

Keywords: 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 (search for similar items in EconPapers)
Date: 2001
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304-4149(01)00122-3
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:96:y:2001:i:2:p:313-342

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().