{
  "id": "1212.3265",
  "version": "v4",
  "published": "2012-12-13T18:48:27.000Z",
  "updated": "2016-04-20T23:44:57.000Z",
  "title": "On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words",
  "authors": [
    "Christian Houdré",
    "Jinyong Ma"
  ],
  "comment": "Final version, to appear in HDP VII, Progress in Probability, Birkhauser",
  "categories": [
    "math.PR"
  ],
  "abstract": "We investigate the order of the $r$-th, $1\\le r < +\\infty$, central moment of the length of the longest common subsequence of two independent random words of size $n$ whose letters are identically distributed and independently drawn from a finite alphabet. When all but one of the letters are drawn with small probabilities, which depend on the size of the alphabet, a lower bound is shown to be of order $n^{r/2}$. This result complements a generic upper bound also of order $n^{r/2}$.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-08-05T01:29:20.000Z",
      "title": "On the Order of the Central Moments of the Length of the Longest Common Subsequence",
      "comment": "Updated manuscript. 29 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v4",
      "updated": "2016-04-20T23:44:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K35",
      "60C05",
      "05A05"
    ],
    "keywords": [
      "longest common subsequence",
      "central moment",
      "generic upper bound",
      "independent random words",
      "result complements"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1212.3265H"
    }
  }
}