Lower bounds for moments of global scores of pairwise Markov chains

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|^rasymp n^{rover 2}$. We also perform simulations indicating the validity of the condition.