An Extreme Value Theory for Sequence Matching
序列匹配的极值理论
Consider finite sequences $X_1, X_2,\cdots, X_m$ and $Y_1, Y_2,\cdots, Y_n$ where the letters ${X_i}$ and ${Y_i}$ are chosen i.i.d. on a countable alphabet with $p=P(X_1=Y_1)\in(0,1)$ We study the distribution of the longest contiguous run of matches between the X's and Y's allowing at most k mismatches. The distribution is closely approximated by that of the maximum of (1 - p)mn i.i.d. negative binomial random variables. The latter distribution is in turn shown to behave…