Affordable Access

Lower bounds for moments of global scores of pairwise Markov chains

Authors
  • Lember, Jüri
  • Matzinger, Heinrich
  • Sova, Joonas
  • Zucca, Fabio
Type
Preprint
Publication Date
Feb 18, 2016
Submission Date
Feb 17, 2016
Identifiers
arXiv ID: 1602.05560
Source
arXiv
License
Yellow
External links

Abstract

Let $X_1,X_2,\ldots$ and $Y_1,Y_2,\ldots$ be two random sequences so that every random variable takes values in a finite set $\mathbb{A}$. We consider a global similarity score $L_n:=L(X_1,\ldots,X_n;Y_1,\ldots,Y_n)$ that measures the homology (relatedness) of words $(X_1,\ldots,X_n)$ and $(Y_1,\ldots,Y_n)$. A typical example of such score is the length of the longest common subsequence. We study the order of central absolute moment $E|L_n-EL_n|^r$ in the case where two-dimensional process $(X_1,Y_1),(X_2,Y_2),\ldots$ is a Markov chain on $\mathbb{A}\times \mathbb{A}$. This is a very general model involving independent Markov chains, hidden Markov models, Markov switching models and many more. Our main result establishes a general condition that guarantees that $E|L_n-EL_n|^r\asymp n^{r\over 2}$. We also perform simulations indicating the validity of the condition.

Report this publication

Statistics

Seen <100 times