A finite state machine with probabilities for each transition, that is, a probability that the next state is s_j given that the current state is s_i.