Diffusion Approximations in the Online Increasing Subsequence Problem

Alexander Gnedin, Amirlan Seksenbayev

Published 2020-01-07Version 1

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.