Analysis of Algorithms, Gdańsk, July 3-7, 2000

On Pattern Frequency Occurrences in a Markovian Sequence

Mireille Régnier^{∗} and Wojciech Szpankowski^{†}

INRIA, Rocquencourt, 78153 Le Chesnay Cedex, France Department Computer Science, Purdue University, W. Lafayette, IN 47907, U.S.A.

Consider a given pattern and a random text generated by a Markovian source of any order. We study the frequency of pattern occurrences in a random text when overlapping copies of the pattern are counted separately (cf. [1, 2, 3]). More precisely: let us consider two strings, a given pattern string H = h_{1}h_{2} … h_{m} and a random text string T = t_{1}t_{2} … t_{n} of respective lengths equal to m and n over an alphabet S of size V. We shall write P (H_{i}^{j}) = Pr{T_{i+k}^{j+k} = H_{i}^{j}} for the probability of the substring H_{i}^{j} = h_{i} … h_{j} occurrence in the random text T_{i+k}^{j+k} between symbols i + k and j + k for any k. We define also the H-conditional generating function of a language L (i.e., a set of words satisfying certain properties) as L_{H}(z) = ∑_{w∈L} P (w|w_{−m} = h_{1} ⋯ w_{−1} = h_{m})z^{|w|}, where w_{−i} stands for a symbol preceding the first character of w at distance i. Finally, we define the so called autocorrelation polynomial A(z) as: Given a string H, let A_{H}(z) = ∑_{kϵHH} P (H_{k+1}^{m}|H_{1}^{k})z^{m−k} where HH is the set of positions of H for which a prefix of H is equal to a suffix of H, e.g., k ∈ HH means that the last k symbols of H are equal to the first k symbols of H.

In the sequel, we denote by O_{n}(H) a random variable representing the number of occurrences of H in a random text T of size n. We introduce the generating function of the language T_{r} of words that contains exactly r occurrences of H: T^{(r)}(z) = ∑_{n≥0} Pr{O_{n}(H) = r}z^{n} for |z| ≤ 1. We also define a bivariate generating function as follows: T (z, u) = ∑_{r=1}^{∞} T^{(r)}(z)u^{r} = ∑_{r=1}^{∞} ∑_{n=0}^{∞} Pr{O_{n}(H) = r}z^{n}u^{r}. Our main results for the Markovian model are summarized in the following two theorems proved in [4] (see [5] for extensions of these findings to approximate pattern occurrences):

Theorem 1 Let H be a given pattern of size m, and T be a random text of length n generated according to a stationary Markov chain (of any order) over a V -ary alphabet S. The generating functions T^{(r)}(z) and T (z, u) can be computed as follows:

T^{(r)}(z) = R(z)M_{H}^{r−1}(z)U_{H}(z) ,
T (z, u) = R(z) \frac{u}{1 − uM_{H}(z)} U_{H}(z) ,

where, after defining

D_{H}(z) = (1 − z)(A_{H}(z) + (P_{H}(H) − P (H))z^{m}) + z^{m}P (H) ,

we have

M_{H}(z) = 1 + \frac{z − 1}{D_{H}(z)} ,
U_{H}(z) = \frac{1 − M_{H}(z)}{1 − z} = \frac{1}{D_{H}(z)} ,

and R(z) = z^{m}P (H)U_{H}(z). In the above, P (H) = P (w = H) and P_{H}(H) = P (w = H|w_{−1}^{−m} = H).

The above theorem is a key to the next asymptotic results. These results are derived using analytical tools.

Theorem 2 Let the hypotheses of Theorem 1 be fulfilled, and in addition nP (H) → ∞. The following results hold.

(i) Moments. For all n ≥ m

EO_{n}(H) = P (H)(n − m + 1) ,
Var O_{n}(H) = nP (H)c_{1} + P (H)c_{2} ,

where c_{1} and c_{2} are explicitly computable constants (cf. [4]).

(ii) Case r = O(1). Let ρ_{H} be the smallest root of D_{H}(z) = 0 outside the unit circle |z| < 1, and let ρ > ρ_{H}. Then:

Pr\{O_{n}(H) = r\} ∼ ∑_{j=1}^{r+1}(−1)^{j}a_{j} \binom{n}{j − 1}ρ_{H}^{−(n+j)}

where a_{j} are explicitly computable constants (cf. [4]).

(iii) Case r = EO_{n} + x\sqrt{Var O_{n}}. Let x = O(1). Then:

Pr\{O_{n}(H) = r\} = \frac{1}{\sqrt{2πc_{1}n}} e^{− \frac{1}{2} x^{2}} (1 + O (\frac{1}{\sqrt{n}})) ,

(iv) Case r = (1 + δ)EO_{n}. Let a = 1 + δ and δ ≠ 0. Define ρ(t) to be the root of 1 − e^{t}M_{H}(e^{ρ}) = 0 , and ω_{a} to be the root of ρ′(ω_{a}) = a Then:

Pr\{O_{n}(H) = r\} = \frac{1}{ω_{a}\sqrt{2πc_{1}n}} e^{−((n−m+1)I(a)} (1 + O (\frac{1}{n}))

where I(a) = aω_{a} − ρ(ω_{a}).

References

[1] L. Guibas and A. W. Odlyzko, String Overlaps, Pattern Matching, and Nontransitive Games, J. Combin.Theory Ser. A, 30, 183-208, 1981.

[2] S. R. Li, A Martingale Approach to the Study of Occurrences of Sequence Patterns in Repeated Experiments, Ann. Probab., 8, 1171-1176, 1980.

[3] B. Prum, F. Rodolphe, and E. Turckheim, Finding Words with Unexpected Frequencies in Deoxyribonucleic Acid Sequence, J.R. Stat. Soc. B, 57, 205-220, 1995.

[4] M. Regnier and W. Szpankowski, A Last Word on Pattern Frequency Occurrence in a Markovian Sequence?, Purdue University, CSD-TR-96-043, 1996.

[5] M. Regnier and W. Szpankowski, On the Approximate Pattern Occurrence in a Text, Purdue University, CSD-TR-96-083, 1996.

∗Supported by the ESPRIT LTR Project No. 20244 (ALCOM IT), and NATO Collaborative Grant CRG.950060.

†Supported by NSF Grants NCR-9206315 and NCR-9415491, and NATO Collaborative Grant CRG.950060.