Back to search

Georgia Institute of Technology

Topics in sequence analysis

Abstract

dc:description.abstract

This thesis studies two topics in sequence analysis. In the first part, we investigate the large deviations of the shape of the random RSK Young diagrams, associated with a random word of size n whose letters are independently drawn from an alphabet of size m=m(n). When the letters are drawn uniformly and when both n and m converge together to infinity, m not growing too fast with respect to n, the large deviations of the shape of the Young diagrams are shown to be the same as that of the spectrum of the traceless GUE. Since the length of the top row of the Young diagrams is the length of the longest (weakly) increasing subsequence of the random word, the corresponding large deviations follow. When the letters are drawn with non-uniform probability, a control of both highest probabilities will ensure that the length of the top row of the diagrams satisfies a large deviation principle. In either case, both speeds and rate functions are identified. To complete our study, non-asymptotic concentration bounds for the length of the top row of the diagrams, are obtained for both models. In the second part, we investigate the order of the r-th, 1<= r < +∞, 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, the r-th central moment is shown to be of order n^{r/2}. In particular, when r=2, we get the order of the variance of the longest common subsequence.

Degree

thesis:*
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ma, Jinyong
Advisors dc:contributor.advisor
  • Houdré, Christian
  • Houdré, Christian
Committee members dc:contributor.committeemember
  • Bakhtin, Yuri
  • Foley, Robert
  • Koltchinskii, Vladimir
  • Matzinger, Heinrich

Subjects

dc:subject × 5

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/45908

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ma, Jinyong. Topics in sequence analysis. Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/45908