Back to search

Georgia Institute of Technology

Comparison of sequences generated by a hidden Markov model

Abstract

dc:description.abstract

The 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 × 2

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Kerchev, George Georgiev. Comparison of sequences generated by a hidden Markov model. Doctoral thesis, Georgia Institute of Technology, 2019. http://hdl.handle.net/1853/61254