Diffusion Approximations in the Online Increasing Subsequence Problem
Authors:
- Alexander GnedinAGAlexander Gnedin
- Amirlan SeksenbayevASAmirlan Seksenbayev
Preprint
Abstract
The online increasing subsequence problem is a stochastic optimisation task with the objective to maximise the expected length of subsequence chosen from a random series by means of a nonanticipating decision strategy. We study the structure of optimal and near-optimal subsequences in a standardised planar Poisson framework. Following a long-standing suggestion by Bruss and Delbaen (Stoch. Proc. Appl. 114, 2004), we prove a joint functional limit theorem for the transversal fluctuations about the diagonal of the running maximum and the length processes. The limit is identified explicitly with a Gaussian time-inhomogeneous diffusion. In particular, the running maximum converges to a Brownian bridge, and the length process has another explicit non-Markovian limit.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Asymptotics and renewal approximation in the online selection of increasing subsequenceBernoulli, 2021
- An adaptive O(log n)‐optimal policy for the online selection of a monotone subsequence from a random sampleRandom Structures & Algorithms, 2017
- The Surprising Mathematics of Longest Increasing Subsequences2014
- Markov Processes, Gaussian Processes, and Local Times2006
- A central limit theorem for the optimal selection process for monotone subsequences of maximum expected lengthStochastic Processes and their Applications, 2004
- Optimal rules for the sequential selection of monotone subsequences of maximum expected lengthStochastic Processes and their Applications, 2001
- Sequential selection of an increasing sequence from a multidimensional random sampleThe Annals of Applied Probability, 2000
- The longest increasing subsequence in a random permutation and a unitary random matrix modelMathematical Research Letters, 1998
- Optimal Sequential Selection of a Monotone Sequence From a Random SampleThe Annals of Probability, 1981
- Stochastic Processes in Queueing Theory1976