dc.contributor.advisor Houdre, Christian dc.contributor.author Kerchev, George Georgiev dc.date.accessioned 2019-05-29T14:03:09Z dc.date.available 2019-05-29T14:03:09Z dc.date.created 2019-05 dc.date.issued 2019-03-26 dc.date.submitted May 2019 dc.identifier.uri http://hdl.handle.net/1853/61254 dc.description.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. dc.format.mimetype application/pdf dc.language.iso en_US dc.publisher Georgia Institute of Technology dc.subject Sequences comparison dc.subject Asymptotic behavior dc.title Comparison of sequences generated by a hidden Markov model dc.type Dissertation dc.description.degree Ph.D. dc.contributor.department Mathematics thesis.degree.level Doctoral dc.contributor.committeeMember Damron, Michael dc.contributor.committeeMember Foley, Robert dc.contributor.committeeMember Koltchinskii, Vladimir dc.contributor.committeeMember Tikhomirov, Konstantin dc.date.updated 2019-05-29T14:03:09Z
﻿