{
  "id": "0810.2982",
  "version": "v1",
  "published": "2008-10-16T18:34:52.000Z",
  "updated": "2008-10-16T18:34:52.000Z",
  "title": "On the Limiting Shape of Markovian Random Young Tableaux",
  "authors": [
    "Christian Houdré",
    "Trevis J. Litherland"
  ],
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Let $(X_n)_{n \\ge 0}$ be an irreducible, aperiodic, homogeneous Markov chain, with state space an ordered finite alphabet of size $m$. Using combinatorial constructions and weak invariance principles, we obtain the limiting shape of the associated Young tableau as a multidimensional Brownian functional. Since the length of the top row of the Young tableau is also the length of the longest (weakly) increasing subsequence of $(X_k)_{1\\le k \\le n}$, the corresponding limiting law follows. We relate our results to a conjecture of Kuperberg by showing that, under a cyclic condition, a spectral characterization of the Markov transition matrix delineates precisely when the limiting shape is the spectrum of the traceless GUE. For $m=3$, all cyclic Markov chains have such a limiting shape, a fact previously known for $m=2$. However, this is no longer true for $m \\ge 4$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-10-16T18:34:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60F05",
      "60F17",
      "60G15",
      "60G17",
      "05A16"
    ],
    "keywords": [
      "markovian random young tableaux",
      "limiting shape",
      "markov transition matrix delineates",
      "multidimensional brownian functional"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0810.2982H"
    }
  }
}