Lower bounds for moments of global scores of pairwise Markov chains

Abstract

Let $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ 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,\dots ,X_n;Y_1,\dots ,Y_n)$ that measures the homology (relatedness) of words $(X_1,\dots ,X_n)$ and $(Y_1,\dots ,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-E{L}_n{|}^r$ in the case where two-dimensional process $(X_1,Y_1),(X_2,Y_2),\dots$ 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-E{L}_n{|}^r\asymp n^{\frac{r}{2}}$. We also perform simulations indicating the validity of the condition.