{
  "id": "1110.1324",
  "version": "v2",
  "published": "2011-10-06T16:58:32.000Z",
  "updated": "2012-08-23T21:14:40.000Z",
  "title": "Asymptotics for the Length of the Longest Increasing Subsequence of Binary Markov Random Word",
  "authors": [
    "Christian Houdré",
    "Trevis J. Litherland"
  ],
  "comment": "To appear in: Malliavin Calculus and Stochastic Analysis: A Festschrift in Honor of David Nualart",
  "categories": [
    "math.PR"
  ],
  "abstract": "Let $(X_n)_{n\\ge 0}$ be an irreducible, aperiodic, and homogeneous binary Markov chain and let $LI_n$ be the length of the longest (weakly) increasing subsequence of $(X_k)_{1\\le k \\le n}$. Using combinatorial constructions and weak invariance principles, we present elementary arguments leading to a new proof that (after proper centering and scaling) the limiting law of $LI_n$ is the maximal eigenvalue of a $2 \\times 2$ Gaussian random matrix. In fact, the limiting shape of the RSK Young diagrams associated with the binary Markov random word is the spectrum of this random matrix.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-08-23T21:14:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60F05",
      "60F17",
      "60G15",
      "60G17",
      "05A16"
    ],
    "keywords": [
      "binary markov random word",
      "longest increasing subsequence",
      "asymptotics",
      "homogeneous binary markov chain",
      "gaussian random matrix"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1110.1324H"
    }
  }
}