Increasing subsequences of random walks

Abstract

Given a sequence of $n$ real numbers $\{S_i{\}}_{i\le n}$, we consider the longest weakly increasing subsequence, namely $i_1<i_2<\cdots <i_L$ with $S_{i_k}\le 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 $\mathbb{E}L=(2+o(1))\sqrt{n}$. We consider the case when $\{S_i{\}}_{i\le n}$ is a random walk on $\mathbb{R}$ 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 $\mathbb{E}L\ge c\sqrt{n}$. Our main result is an upper bound $\mathbb{E}L\le n^{1/2+o(1)}$, establishing the leading asymptotic behavior. If $\{S_i{\}}_{i\le n}$ is a simple random walk on $\mathbb{Z}$, we improve the lower bound by showing that $\mathbb{E}L\ge c\sqrt{n}\log n$. 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{\}}_{i\le n}$ 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.

18 pages, 2 figures

References in corpus (2)

• Random walks in cones
• Restrictions of Brownian motion

Cited by in corpus (6)

• Large deviations of the length of the longest increasing subsequence of random permutations and random walks
• How many longest increasing subsequences are there?
• Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
• Asymptotic behavior of the length of the longest increasing subsequences of random walks
• A numerical investigation into the scaling behavior of the longest increasing subsequences of the symmetric ultra-fat tailed random walk
• Longest weakly increasing subsequences of discrete random walks on the integers with heavy tailed distribution of increments