Limiting Theorems for the Optimal Alignments Score in Multiple Random Words

Let X_n⁽¹⁾,...,X_n^(m), where X_n⁽ⁱ⁾ = (X₁⁽ⁱ⁾,...,X_n⁽ⁱ⁾), i = 1,...,m, be m independent sequences of independent and identically distributed random variables taking their values in a finite alphabet A. Let the score function S, defined on 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. This is in contrast to the Bernoulli matching problem or to the random permutations case, where the limiting law is the Tracy-Widom distribution. In particular, when S(x) = 1_{{ x1 =...=xm }}, a central limit theorem is obtained for the length of the longest common subsequence of random words X_n⁽¹⁾,...,X_n^(m). (Joint work with Christian Houdré and Umit Işlak)

Event Topic

Discrete Applied Math Seminar