Optimal online selection of a monotone subsequence: a central limit theorem

Alessandro Arlotto, Vinh V. Nguyen and J. Michael Steele

Stochastic Processes and their Applications, 2015, vol. 125, issue 9, 3596-3622

Abstract: Consider a sequence of n independent random variables with a common continuous distribution F, and consider the task of choosing an increasing subsequence where the observations are revealed sequentially and where an observation must be accepted or rejected when it is first revealed. There is a unique selection policy πn∗ that is optimal in the sense that it maximizes the expected value of Ln(πn∗), the number of selected observations. We investigate the distribution of Ln(πn∗); in particular, we obtain a central limit theorem for Ln(πn∗) and a detailed understanding of its mean and variance for large n. Our results and methods are complementary to the work of Bruss and Delbaen (2004) where an analogous central limit theorem is found for monotone increasing selections from a finite sequence with cardinality N where N is a Poisson random variable that is independent of the sequence.

Keywords: Bellman equation; Online selection; Markov decision problem; Dynamic programming; Monotone subsequence; De-Poissonization; Martingale central limit theorem; Non-homogeneous Markov chain (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414915001003
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:125:y:2015:i:9:p:3596-3622

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

DOI: 10.1016/j.spa.2015.03.009

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 ().