On Pattern Occurrences in a Random Text

Ioannis Fudos, Evaggelia Pitoura, Wojciech SzpankowskiInf. Process. Lett 1996 · DOI

TL;DR

This paper tackles the fundamental problem of predicting how often a specific pattern will appear in a randomly generated text, considering that each character in the text can have a different probability of occurring. The authors derive a generating function for this probability and provide asymptotic formulas that are crucial for understanding pattern frequencies in various applications, from data compression to bioinformatics.

What Problem Does This Paper Address?

In many areas of computer science, telecommunications, and biology, understanding how often specific sequences (patterns) appear within larger sequences (texts) is critical. For instance, in DNA analysis, identifying recurring motifs is key to understanding gene function. In data compression, knowing the frequency of patterns helps in designing efficient encoding schemes.

Previous work, notably by Guibas and Odlyzko, laid the groundwork for analyzing pattern occurrences, primarily under the assumption of a "symmetric Bernoulli model" where each character in the alphabet has an equal probability of appearing. However, real-world scenarios often involve "asymmetric Bernoulli models," where characters have different probabilities. This paper addresses the challenge of precisely calculating the probability of a given pattern appearing exactly r times in a random text generated under such an asymmetric model. This includes counting overlapping occurrences, which is a common and important scenario.

Methods

The core of the paper's methodology lies in the use of generating functions. The authors define a generating function, $T_r(z)$, that encodes the probabilities of a pattern occurring exactly $r$ times in a text of varying lengths. This approach allows them to elegantly combine probabilities and derive asymptotic behaviors.

Key techniques include:

  • Correlation Polynomials: These polynomials, denoted $C_{FH}(z)$, capture the overlap properties between two strings, $F$ and $H$. The autocorrelation polynomial, $A_H(z)$, specifically describes the self-overlap of a pattern $H$. These are crucial for understanding how a pattern can "fit" within itself.
  • Asymmetric Bernoulli Model: The text is generated by independently selecting characters, each with a specific probability. This is a generalization of the simpler symmetric model.
  • Generating Function Manipulation: The paper derives systems of linear equations involving generating functions for different probabilities (e.g., $T_r(z)$ and $S_r(z)$, which represents the probability of a pattern ending at a specific position). Solving these systems yields the desired generating functions.
  • Asymptotic Analysis: Using techniques like Hadamard's theorem and Laurent series expansion around dominant singularities, the authors extract the long-term behavior (as the text length $n$ grows) of the probabilities. This provides practical approximations for large texts.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses abstract models of random texts and patterns rather than specific datasets.

Key Insights and Ideas

  • Generalization to Asymmetric Models: The paper successfully extends previous results from symmetric to asymmetric Bernoulli models, making the analysis more applicable to real-world scenarios where character probabilities are unequal.
  • Exact Probability Calculation: The derivation of the generating function $T_r(z)$ provides a precise way to calculate the probability of exactly r occurrences, which is more detailed than just estimating the probability of at least one occurrence.
  • Asymptotic Behavior as a Powerful Tool: The asymptotic formulas derived are not just theoretical curiosities. They offer practical approximations for large texts, allowing researchers to estimate pattern frequencies without computationally intensive simulations. The formula $T_{r,n} \sim \alpha_{r-1} n^{r-1} p_H^{n-r+1} P(H^*)$ (where $p_H$ is a root of a specific equation) is particularly insightful, showing how the probability scales with text length and depends on the pattern's structure and probabilities.
  • Random Patterns: The paper also considers the scenario where the pattern itself is randomly generated, providing insights into the expected number of occurrences in such cases.

Key Results

  • Theorem 3: This theorem provides the core results.
  • Part (i) gives the generating function $T_r(z)$ for the probability of exactly $r$ occurrences of a pattern $H$ in a text of length $n$ under the asymmetric Bernoulli model.
  • Part (ii) provides asymptotic formulas for $T_{r,n}$ (the coefficient of $z^n$ in $T_r(z)$) as $n \to \infty$. For $r \ge 1$, $T_{r,n}$ behaves as $O(n^{r-1} p_H^{n-r+1})$, where $p_H$ is the largest root less than 1 of the autocorrelation polynomial $A_H(z)$. For $r=1$, a more precise asymptotic is given as $T_{1,n} \sim \alpha_0 n p_H^{n-1} P(H^*)$, where $H^*$ is the pattern maximizing $p_H$.
  • Theorem 6: This theorem addresses the case where both the pattern and the text are random. It provides bounds and asymptotic relations for the probability of occurrences.

Limitations and Future Work

  • Computational Complexity of $p_H$: While the asymptotic formulas rely on $p_H$, finding this root can be computationally challenging for complex patterns. The paper notes that the asymptotic formula (13) is not very useful if $p_H = 1$, which can occur in certain cases.
  • Focus on Exact Occurrences: The paper primarily focuses on the probability of exactly r occurrences. While it touches upon the probability of at least R occurrences, a more detailed analysis of this aspect could be a future direction.
  • Generalization to More Complex Models: The analysis is based on the asymmetric Bernoulli model. Extending these results to more complex random text generation models (e.g., Markov chains) would be a natural next step.
  • Practical Applications: While the paper mentions applications in coding theory, data compression, and bioinformatics, further research could explore how these theoretical results can be directly applied to design and analyze specific algorithms or systems in these fields.

Summary updated

BibTeX
@article{fudos1996pattern,
  author = {Ioannis Fudos and Evaggelia Pitoura and Wojciech Szpankowski},
  title = {{On Pattern Occurrences in a Random Text}},
  journal = {Inf. Process. Lett.},
  year = {1996},
  doi = {10.1016/0020-0190(96)00022-1},
}

Loading related content...

Figure