2. Markov chains and probabilistic finite-state automata

A Markov chain is a probabilistic finite-state automaton. It is used to model the dynamics of a process that can be in a finite number of possible states. We will denote S = {e ₁ ,..., e _N } the set of N possible states of a Markov chain and s _t the random variable representing the state at time t of a Markov process (with ∀t, s _t ∊ S).

By Markovian hypothesis we mean the assumption that the state of the process at a given point in time depends only on the state of the process at p previous points in time. In this case, we say that the Markov chain is a chain of order p. The vast majority of work based on Markovian models in pattern recognition exploits Markov chains of order 1, and...