This thesis introduces a new pattern statistics framework, which enables exact and efficient calculation of probabilities of pattern occurrences in sequence data. Statistics of pattern occurrences in data are formulated in terms of finite automata state transitions embedded into a Markov chain. This enables the analysis of continuous or discrete sequence data where the underlying generation process is governed by a Markov source, and where occurrences of specific patterns in the Markov state sequence is of interest. Through this new methodology, the full joint distribution of pattern statistics can be obtained in a conceptually simple and computationally efficient way. This new methodology can be adopted for many applications, and is here applied to change point estimation problems as an example.