Diffusion approximations in the online increasing subsequence problem

DOI10.1016/J.SPA.2021.06.001MaRDI QIDQ2048141zbMATH OpenOpenAlexWikidataFDO

Authors Amirlan Seksenbayev, Alexander Gnedin

Publication date 5 August 2021

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.02249

zbMATH Keywords

functional limitsincreasing subsequenceonline selection strategy

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Stochastic processes (60G99)

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.

Recommendations

• Asymptotics and renewal approximation in the online selection of increasing subsequence
• Asymptotic expansions and strategies in the online increasing subsequence problem
• Optimal online selection of a monotone subsequence: a central limit theorem
• A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
• Quickest online selection of an increasing subsequence of specified size

Cites work

• A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
• An adaptive O( n)-optimal policy for the online selection of a monotone subsequence from a random sample
• Asymptotics and renewal approximation in the online selection of increasing subsequence
• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 4034749 (Why is no real title available?)
• scientific article; zbMATH DE number 3711116 (Why is no real title available?)
• scientific article; zbMATH DE number 3500818 (Why is no real title available?)
• Markov Processes, Gaussian Processes, and Local Times
• Maxima in hypercubes
• On sequential selection and a first passage problem for the Poisson process
• Optimal online selection of a monotone subsequence: a central limit theorem
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• Optimal selection of stochastic intervals under a sum constraint
• Optimal sequential selection of a monotone sequence from a random sample
• Record sequences and their applications.
• Sequential selection of an increasing sequence from a multidimensional random sample.
• Sequential selection of an increasing subsequence from a sample of random size
• Stochastic-Process Limits
• The longest increasing subsequence in a random permutation and a unitary random matrix model
• The surprising mathematics of longest increasing subsequences

Cited in

(2)

• Asymptotics and renewal approximation in the online selection of increasing subsequence
• Asymptotic expansions and strategies in the online increasing subsequence problem

This page was built for publication: Diffusion approximations in the online increasing subsequence problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048141)