Increasing subsequences of random walks

DOI10.1017/S0305004116000797MaRDI QIDQ5360458zbMATH OpenFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(11)

• Longest convex chains
• scientific article; zbMATH DE number 5204618 (Why is no real title available?)
• 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
• On Increasing Subsequences of I.I.D. Samples
• 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

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)