{
  "id": "1407.2860",
  "version": "v2",
  "published": "2014-07-10T16:49:25.000Z",
  "updated": "2014-12-23T09:11:09.000Z",
  "title": "Increasing subsequences of random walks",
  "authors": [
    "Omer Angel",
    "Richárd Balka",
    "Yuval Peres"
  ],
  "comment": "17 pages, 2 figures",
  "categories": [
    "math.PR"
  ],
  "abstract": "Given a sequence of $n$ real numbers $\\{S_i\\}_{i\\leq n}$, 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 $\\mathbb{E} L=(2+o(1)) \\sqrt{n}$. We consider the case when $\\{S_i\\}_{i\\leq 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\\geq c\\sqrt{n}$. Our main result is an upper bound $\\mathbb{E} L\\leq n^{\\frac 12 + o(1)}$, establishing the leading asymptotic behavior. If $\\{S_i\\}_{i\\leq n}$ is a simple random walk on $\\mathbb{Z}$, we improve the lower bound by showing that $\\mathbb{E} L \\geq 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\\leq n}$ of expected length at least $cn^{\\frac 13}$ that is increasing in each coordinate. The above one-dimensional result yields an upper bound of $n^{\\frac 12 + o(1)}$. The problem of determining the correct exponent remains open.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-07-10T16:49:25.000Z",
      "abstract": "From a given sequence of numbers $(S_i)$ of length $n$, we consider the longest weakly increasing subsequence, namely $i_1<i_2<\\dots <i_m$ with $S_{i_k} \\leq S_{i_{k+1}}$ and $m$ maximal. The Erd\\H{o}s-Szekeres Theorem states that there is either a weakly increasing or a weakly decreasing subsequence of length $\\sqrt{n}$. When the elements $S_i$ are i.i.d.\\ uniform random variables, Vershik and Kerov, and Logan and Shepp proved that with high probability the longest increasing sequence has length $(2+o(1)) \\sqrt{n}$. We consider the case when $S_n$ is a simple random walk on $\\mathbb{Z}$. As a main result of our paper, we prove an upper bound of $n^{1/2 + o(1)}$ with high probability, establishing the leading asymptotic behavior. It is easy to prove that $\\sqrt{n}$ is a lower bound with high probability. We improve this by giving a lower bound of $c \\sqrt{n} \\log{n}$.",
      "comment": "12 pages, 2 figures",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-12-23T09:11:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60G17",
      "60G50"
    ],
    "keywords": [
      "high probability",
      "lower bound",
      "uniform random variables",
      "simple random walk",
      "theorem states"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1407.2860A"
    }
  }
}