{
  "id": "math/9904042",
  "version": "v3",
  "published": "1999-04-09T22:30:59.000Z",
  "updated": "1999-07-01T23:09:41.000Z",
  "title": "On the Distributions of the Lengths of the Longest Monotone Subsequences in Random Words",
  "authors": [
    "Craig A. Tracy",
    "Harold Widom"
  ],
  "comment": "30 pages, revised version corrects an error in the statement of Theorem 4",
  "journal": "Probab. Theory Relat. Fields 119 (2001), 350-380",
  "doi": "10.1007/PL00008763",
  "categories": [
    "math.CO",
    "math.PR",
    "nlin.SI",
    "solv-int"
  ],
  "abstract": "We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlev\\'e V equations. We show further that in the weakly increasing case the generating function gives the distribution of the smallest eigenvalue in the k x k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N -> infinity limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k x k hermitian matrices of trace zero.",
  "revisions": [
    {
      "version": "v3",
      "updated": "1999-07-01T23:09:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A15",
      "47B35",
      "60C05",
      "82B23"
    ],
    "keywords": [
      "longest monotone subsequences",
      "random words",
      "distribution function",
      "toeplitz determinant representations",
      "smallest eigenvalue"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "1999math......4042T"
    }
  }
}