Increasing subsequences of random walks

DOI10.1017/S0305004116000797zbMATH Open1387.60110arXiv1407.2860MaRDI QIDQ5360458FDOQ5360458

Authors: Omer Angel, Richárd Balka, Yuval Peres 

Publication date: 28 September 2017

Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

Abstract: Given a sequence of $n$ real numbers ${S_i}_{ileqn}$, we consider the longest weakly increasing subsequence, namely $i_1<i_2<dots<i_L$ with $S_{i_k}leq{S}_{i_{k+1}}$ and $L$ maximal. When the elements $S_i$ are i.i.d. uniform random variables, Vershik and Kerov, and Logan and Shepp proved that $mathbbEL=(2+o(1))sqrtn$. We consider the case when ${S_i}_{ileqn}$ is a random walk on $mathbbR$ with increments of mean zero and finite (positive) variance. In this case, it is well known (e.g., using record times) that the length of the longest increasing subsequence satisfies $mathbbELgeqcsqrtn$. Our main result is an upper bound $mathbbELleq{n}^{1/2+o(1)}$, establishing the leading asymptotic behavior. If ${S_i}_{ileqn}$ is a simple random walk on $mathbbZ$, we improve the lower bound by showing that $mathbbELgeqcsqrtnlogn$. We also show that if $mathbf{S}_i$ is a simple random walk in $mathbb{Z}^2$, then there is a subsequence of ${mathbf{S}_i}_{ileqn}$ of expected length at least $c{n}^{1/3}$ that is increasing in each coordinate. The above one-dimensional result yields an upper bound of $n^{1/2+o(1)}$. The problem of determining the correct exponent remains open.

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

Recommendations

• Non-universality for longest increasing subsequence of a random walk
• On increasing subsequences of random permutations
• Empirical scaling of the length of the longest increasing subsequences of random walks
• On Increasing Subsequences of I.I.D. Samples
• On the length of the longest excursion

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Random walk: A modern introduction
• On the distribution of the length of the longest increasing subsequence of random permutations
• Random walks in cones
• Title not available (Why is that?)
• A variational problem for random Young tableaux
• Title not available (Why is that?)
• The surprising mathematics of longest increasing subsequences
• Hausdorff measures of different dimensions are isomorphic under the continuum hypothesis
• Restrictions of continuous functions
• Restrictions of Brownian motion
• Measurable functions are of bounded variation on a set of dimension \(\frac{1}{2}\)
• Title not available (Why is that?)
• Restrictions of Hölder continuous functions

Cited In (10)

• LIL for the length of the longest increasing subsequences
• On the number of coincidences of two homogeneous random walks with positive increments
• Restrictions of Hölder continuous functions
• Divergence of a random walk through deterministic and random subsequences
• Empirical scaling of the length of the longest increasing subsequences of random walks
• Restrictions of Brownian motion
• Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
• Non-universality for longest increasing subsequence of a random walk
• Title not available (Why is that?)
• Longest convex chains

This page was built for publication: Increasing subsequences of random walks

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