Lower bounds for moments of global scores of pairwise Markov chains

2016/02/17 by Jüri Lember, Heinrich Matzinger, Lember, Jüri +5
Mathematics · #41A25 #60C05 #60K35 #FOS: Mathematics #Probability (math.PR) #math.PR #msc:41A25 #msc:60C05 #msc:60K35

paper · pdf · doi:10.48550/arxiv.1602.05560

arxiv created 2016/02/18 · arxiv updated 2016/02/19

Abstract

Let X₁,X₂,… and Y₁,Y₂,… be two random sequences so that every random variable takes values in a finite set \mathbbA. We consider a global similarity score L_n:=L(X₁,…,X_n;Y₁,…,Y_n) that measures the homology (relatedness) of words (X₁,…,X_n) and (Y₁,…,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₁,Y₁),(X₂,Y₂),… is a Markov chain on \mathbbA× \mathbbA. 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.

Related

• Lower Bounds on the Generalized Central Moments of the Optimal Alignments Score of Random Sequences
• On the rate of convergence for the length of the longest common\n subsequences in hidden Markov models
• Full Randomness in the Higher Difference Structure of Two-state Markov Chains
• Concentration inequalities for Markov processes via coupling
• Approximating Laplace transforms of meeting times for some symmetric Markov chains