On an alternative sequence comparison statistic of Steele
arXiv:1803.04052 · doi:10.23638/DMTCS-22-1-18
Abstract
The purpose of this paper is to study a statistic that is used to compare the similarity between two strings, which is first introduced by Michael Steele in 1982. It was proposed as an alternative to the length of the longest common subsequences, for which the variance problem is still open. Our results include moment asymptotics and distributional asymptotics for Steele's statistic and a variation of it in random words and random permutations.
arXiv comment17 pages
References in corpus (4)
- Normal approximation for nonlinear statistics using a concentration inequality approach
- A Central Limit Theorem for the Length of the Longest Common Subsequences in Random Words
- A Central Limit Theorem for the Optimal Alignments Score in Multiple Random Words
- The Length of the Longest Common Subsequence of Two Independent Mallows Permutations