Georgia Institute of Technology
Comparison of sequences generated by a hidden Markov model
Abstract
dc:description.abstractThe length LCn of the longest common subsequences of two strings X = (X1, \ldots, Xn) and Y = (Y1, \ldots, Yn) is way to measure the similarity between $X$ and $Y$. We study the asymptotic behavior of LCn 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 (Xi, Yi) is generated according to a distribution depending of the state of Zi for every $i \geq 1$. The letters Xi and Yi each take values in a finite alphabet $\mathcal{A}$. The goal of this work is to build upon asymptotic results for LCn obtained for sequences of iid random variables. Under some standard assumptions regarding the model we first prove convergence results with rates for \mathbb{E}[LCn]. Then, versions of concentration inequalities for the transversal fluctuations of LCn 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.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Mathematics
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2019
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Kerchev, George Georgiev
- Advisor dc:contributor.advisor
-
- Houdré, Christian
- Committee members dc:contributor.committeemember
-
- Damron, Michael
- Foley, Robert
- Koltchinskii, Vladimir
- Tikhomirov, Konstantin
Subjects
dc:subject × 2Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/61254