• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Comparison of sequences generated by a hidden Markov model

    Thumbnail
    View/Open
    KERCHEV-DISSERTATION-2019.pdf (524.4Kb)
    Date
    2019-03-26
    Author
    Kerchev, George Georgiev
    Metadata
    Show full item record
    Abstract
    The length $LC_n$ of the longest common subsequences of two strings $X = (X_1, \ldots, X_n)$ and $Y = (Y_1, \ldots, Y_n)$ is way to measure the similarity between $X$ and $Y$. We study the asymptotic behavior of $LC_n$ when the two strings are generated by a hidden Markov model $(Z, (X, Y))$. The latent chain $Z$ is an aperiodic time-homogeneous and irreducible finite state Markov chain and the pair $(X_i, Y_i)$ is generated according to a distribution depending of the state of $Z_i$ for every $i \geq 1$. The letters $X_i$ and $Y_i$ each take values in a finite alphabet $\mathcal{A}$. The goal of this work is to build upon asymptotic results for $LC_n$ obtained for sequences of iid random variables. Under some standard assumptions regarding the model we first prove convergence results with rates for $\mathbb{E}[LC_n]$. Then, versions of concentration inequalities for the transversal fluctuations of $LC_n$ are obtained. Finally, we have outlined a proof for a central limit theorem by building upon previous work and adapting a Stein's method estimate.
    URI
    http://hdl.handle.net/1853/61254
    Collections
    • Georgia Tech Theses and Dissertations [22401]
    • School of Mathematics Theses and Dissertations [399]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology