Roland Aydin

Analysis of Pattern Occurances

Abstract

This paper will summarize the proof for the formula to compute the expected number of occurrences of a given pattern H in a text of size n. The intuitive solution of E[O_n(H)]=P(H)(n-m+1) will be verified utilising generating functions. Frequency analysis will rely on the decomposition of the text T onto languages, the so-called initial, minimal, and tail languages. Going from there to their generating functions both for a Markovian and a Bernoulli environment, the formula will be shown to work due to properties of the respective generating functions.