Probabilistic models for pattern statistics
Dipartimento di Scienze dell'Informazione,
Università degli Studi di Milano, via Comelico 39/41, 20135 Milano, Italy;
firstname.lastname@example.org & email@example.com.
In this work we study some probabilistic models for the random generation of words over a given alphabet used in the literature in connection with pattern statistics. Our goal is to compare models based on Markovian processes (where the occurrence of a symbol in a given position only depends on a finite number of previous occurrences) and the stochastic models that can generate a word of given length from a regular language under uniform distribution. We present some results that show the differences between these two stochastic models and their relationship with the rational probabilistic measures.
Mathematics Subject Classification: 68Q45 / 68Q10 / 60J99
Key words: Pattern statistics / Markov chains / probabilistic automata / rational formal series.
© EDP Sciences, 2006