A New Method of Approximating the Probability of Matching Common Words in Multiple Random Sequences

In this paper we consider R independent sequences of length T formed by independent, not necessarily uniformly distributed letters drawn from a finite alphabet. We first develop a new and efficient method of calculating the expectation $\mathbb{E}(N_{R}) = \mathbb{E}(N_{R}(m,T))$ of the number of distinct words of length m, N R (m, T), which are common to R such sequences. We then consider the case of four uniformly distributed letters. We determine a b R = b R (m, T) ≥ 0 such that the interval $[\mathbb{E}(N_{R}) - b_{R}; \mathbb{E}(N_{R})]$ contains the probability p R = ℙ(N R ≥ 1) that there exists a word of length m common to the R sequences. We show that $b_{R} \approx 0.07\mathbb{E}(N_{R})$ if R = 3 and $b_{R} \leq 0.05 \mathbb{E}(N_{R})$ if R ≥ 4. Thus, for unusual common words, i.e. such that p R is small, E(N R ) provides a very accurate approximation of this probability. We then compare numerically the intervals $[\mathbb{E}(N_{R})-b_{R}, \mathbb{E}(N_{R})]$ with former approximations of p R provided by Karlin and Ost (Ann Probab 16:535–563, 1988) and Naus and Sheng (Bull Math Biol 59(3):483–495, 1997).