论文标题
在线增加子序列问题的扩散近似
Diffusion Approximations in the Online Increasing Subsequence Problem
论文作者
论文摘要
在线增加的子序列问题是一项随机优化任务，目的是通过非预期的决策策略最大化从随机系列中选择的子序列的预期长度。我们研究了标准化平面泊松框架中最佳和近乎最佳子序列的结构。根据Bruss和Delbaen的长期建议（Stoch。Proc。Appl。114，2004），我们证明了有关运行最大值对角线和长度过程的横向波动的关节功能极限定理。用高斯时间抗均匀扩散明确识别极限。特别是，运行最大值将收敛到布朗桥，并且长度过程具有另一个明确的非马克维亚限制。
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.
