Tight Bounds and Approximations for Scan Statistic Probabilities for Discrete Data

Let X1,X2,. be a sequence of independently and identically distributed integer-valued random variables. Let Yt.m+1,t for t=m,m+1,. denote a moving sum of m consecutive Xi's. Let Nm,T=maxm.t.T{Yt.m+1,t} and let .k,m be the waiting time until the moving sum of Xi's in a scanning window of m trials is as large as k. We derive tight bounds for the equivalent probabilities P(.k,m>T)=P(Nm,T<k). We apply the bounds for two problems in molecular biology: the distribution of the length of the longest almost-matching subsequence in aligned amino acid sequences and the distribution of the largest net charge within any m consecutive positions in a charged alphabet string.