A Central Limit Theorem for the Optimal Alignments Score in Multiple Random Words

Abstract

Let ${\mathbf{X}}_n^{(1)},\dots ,{\mathbf{X}}_n^{(m)}$, where ${\mathbf{X}}_n^{(i)}=(X_1^{(i)},\dots ,X_n^{(i)})$, $i=1,\dots ,m$, be $m$ independent sequences of independent and identically distributed random variables taking their values in a finite alphabet $\mathcal{A}$. Let the score function $S$, defined on ${\mathcal{A}}^m$, be non-negative, bounded, permutation-invariant, and satisfy a bounded differences condition. Under a variance lower-bound assumption, a central limit theorem is proved for the optimal alignments score of the $m$ random words.

30 pages

References in corpus (4)

• A new method of normal approximation
• A Central Limit Theorem for the Length of the Longest Common Subsequences in Random Words
• Sparse long blocks and the variance of the longest common subsequences in random words
• New Kolmogorov bounds for functionals of binomial point processes

Cited by in corpus (3)

• A Central Limit Theorem for the Length of the Longest Common Subsequences in Random Words
• Lower Bounds on the Generalized Central Moments of the Optimal Alignments Score of Random Sequences
• On an alternative sequence comparison statistic of Steele