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

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:125

Article

Arlotto, Alessandro¹  Nguyen, Vinh V.¹  Steele, J. Michael² 

[1] Duke Univ, Fuqua Sch Business, Durham, NC 27708 USA

[2] Univ Penn, Wharton Sch, Dept Stat, Philadelphia, PA 19104 USA

关键词: Bellman equation;    Online selection;    Markov decision problem;    Dynamic programming;    Monotone subsequence;    De-Poissonization;    Martingale central limit theorem;    Non-homogeneous Markov chain;   

DOI  :  10.1016/j.spa.2015.03.009

来源: Elsevier

【 摘 要 】

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 pi(n)* that is optimal in the sense that it maximizes the expected value of L-n (pi(n)*), the number of selected observations. We investigate the distribution of L-n (pi(n)*); in particular, we obtain a central limit theorem for L-n (pi(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. (C) 2015 Elsevier B.V. All rights reserved.

【 授权许可】

Free