{
  "id": "1001.1273",
  "version": "v3",
  "published": "2010-01-08T14:06:03.000Z",
  "updated": "2010-11-12T13:25:42.000Z",
  "title": "Fluctuations of the Longest Common Subsequence for Sequences of Independent Blocks",
  "authors": [
    "Heinrich Matzinger",
    "Felipe Torres"
  ],
  "comment": "PDFLatex, 40 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "The problem of the fluctuation of the Longest Common Subsequence (LCS) of two i.i.d. sequences of length $n>0$ has been open for decades. There exist contradicting conjectures on the topic. Chvatal and Sankoff conjectured in 1975 that asymptotically the order should be $n^{2/3}$, while Waterman conjectured in 1994 that asymptotically the order should be $n$. A contiguous substring consisting only of one type of symbol is called a block. In the present work, we determine the order of the fluctuation of the LCS for a special model of sequences consisting of i.i.d. blocks whose lengths are uniformly distributed on the set $\\{l-1,l,l+1\\}$, with $l$ a given positive integer. We showed that the fluctuation in this model is asymptotically of order $n$, which confirm Waterman's conjecture. For achieving this goal, we developed a new method which allows us to reformulate the problem of the order of the variance as a (relatively) low dimensional optimization problem.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2010-11-12T13:25:42.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60F10"
    ],
    "keywords": [
      "longest common subsequence",
      "independent blocks",
      "fluctuation",
      "low dimensional optimization problem",
      "confirm watermans conjecture"
    ],
    "note": {
      "typesetting": "PDFLaTeX",
      "pages": 40,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}