Lower Bounds on the Generalized Central Moments of the Optimal Alignments Score of Random Sequences

Ruoting Gong (), Christian Houdré () and Jüri Lember ()
Additional contact information
Ruoting Gong: Illinois Institute of Technology
Christian Houdré: Georgia Institute of Technology
Jüri Lember: University of Tartu

Journal of Theoretical Probability, 2018, vol. 31, issue 2, 643-683

Abstract: Abstract We present a general approach to the problem of determining tight asymptotic lower bounds for generalized central moments of the optimal alignment score of two independent sequences of i.i.d. random variables. At first, these are obtained under a main assumption for which sufficient conditions are provided. When the main assumption fails, we nevertheless develop a “uniform approximation” method leading to asymptotic lower bounds. Our general results are then applied to the length of the longest common subsequences of binary strings, in which case asymptotic lower bounds are obtained for the moments and the exponential moments of the optimal score. As a by-product, a local upper bound on the rate function associated with the length of the longest common subsequences of two binary strings is also obtained.

Keywords: Longest common subsequence; Optimal alignment; Last passage percolation; 05A05; 60C05; 60F10 (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-016-0730-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jotpro:v:31:y:2018:i:2:d:10.1007_s10959-016-0730-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-016-0730-4

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().