Lower bounds for moments of global scores of pairwise Markov chains

preprint2016arXivOpen access

Abstract

Let X1,X2,…X_1,X_2,\ldots and Y1,Y2,…Y_1,Y_2,\ldots be two random sequences so that every random variable takes values in a finite set A\mathbb{A}. We consider a global similarity score Ln:=L(X1,…,Xn;Y1,…,Yn)L_n:=L(X_1,\ldots,X_n;Y_1,\ldots,Y_n) that measures the homology (relatedness) of words (X1,…,Xn)(X_1,\ldots,X_n) and (Y1,…,Yn)(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∣Ln−ELn∣rE|L_n-EL_n|^r in the case where two-dimensional process (X1,Y1),(X2,Y2),…(X_1,Y_1),(X_2,Y_2),\ldots is a Markov chain on A×A\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∣Ln−ELn∣r≍nr2E|L_n-EL_n|^r\asymp n^{r\over 2}. We also perform simulations indicating the validity of the condition.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.