# Lower bounds for moments of global scores of pairwise Markov chains

Research paper by **Jüri Lember, Heinrich Matzinger, Joonas Sova, Fabio Zucca**

Indexed on: **18 Feb '16**Published on: **18 Feb '16**Published in: **Mathematics - Probability**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### 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.