## 3.7 THE HIDDEN MARKOV MODEL (HMM)

A class of stochastic processes now referred to as Hidden Markov models (HMM) are described in the two important papers published by Petrie [1969] and Baum et al. [1969]. The application of HMM to automatic speech recognition (ASR) was quickly recognized, and is detailed in the survey papers by Levinson et al. [1983], Rabiner and Juang [1986] and Poritz [1988]. We outline the main ideas and show how HMM may be applied to cryptanalyze a monoalphabetic substitution.

A hidden Markov model (HMM) is a two-stage random process; both the input *X* = (*X*_{0}, *X*_{1},…, *X*_{n}) and output states *Y* = (*Y*_{0}, *Y*_{1},…, *Y*_{n}) consists of integers in . The HMM is constructed from

- A Markov chain with parameters (
*π*, *P*) generating (hidden) states *X*
- An
*output* probability distribution *q*(*j/i*) = Pr{*Y*_{t} = *j*/*X*_{t} = *i*} for each hidden state *i*

**Figure 3.3** Observing the hidden states.

The evolution of the HMM may be described as follows:

- The initial hidden state
*X*_{0} = *x*_{0} is chosen with probability ...