Lower bounds for moments of global scores of pairwise Markov chains

Jüri Lember, Heinrich Matzinger, Joonas Sova and Fabio Zucca

Stochastic Processes and their Applications, 2018, vol. 128, issue 5, 1678-1710

Abstract: Let X1,… and Y1,… be random sequences taking values in a finite set A. We consider a similarity score Ln≔L(X1,…,Xn;Y1,…,Yn) that measures the homology of words (X1,…,Xn) and (Y1,…,Yn). A typical example is the length of the longest common subsequence. We study the order of moment E|Ln−ELn|r in the case where the two-dimensional process (X1,Y1),(X2,Y2),… is a Markov chain on A×A. This general model involves independent Markov chains, hidden Markov models, Markov switching models and many more. Our main result establishes a condition that guarantees that E|Ln−ELn|r≍nr2. We also perform simulations indicating the validity of the condition.

Keywords: Random sequence comparison; Longest common sequence; Fluctuations; Waterman conjecture (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414917302004
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:128:y:2018:i:5:p:1678-1710

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2017.08.009

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().