ON PATTERN OCCURRENCES IN A RANDOM TEXT

Consider a given pattern H and a random text T of length n. We assume that symbols in the text occur independently, and various symbols have different probabilities of occurrence (i.e., the so-called asymmetric Bernoulli model). We are concerned with the probability of exactly r occurrences of H in the text T. We derive the generating function of t his probability, and show that asymptotically it behaves as alpha n(r) rho(H)(n-r-1), where alpha is an explicitly computed constant, and rh o(H) < 1 is the root of an equation depending on the structure of the pattern. We then extend these findings to random patterns.