A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition

II Discrete Markov processes

1. What is a first-order discrete Markov chain?
   A system in one of \(N\) states that changes state at regular times with probabilities depending only on the current state: \(P[q_t = S_j \mid q_{t-1} = S_i, q_{t-2}, \ldots] = P[q_t = S_j \mid q_{t-1} = S_i] = a_{ij}\), time-independent, with \(a_{ij} \ge 0\), \(\sum_j a_{ij} = 1\).
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), II Discrete Markov processes
2. Why is a plain Markov chain called an “observable” Markov model?
   Its output at each time is the state itself, each state corresponding to a physical, observable event (e.g. rain, cloudy, sunny in Rabiner’s weather example).
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), II Discrete Markov processes
3. With weather transition probabilities, how is the probability of a weather sequence computed?
   Multiply the initial state probability by the transition probabilities along the sequence: \(P(O) = \pi_{q_1} \prod_t a_{q_{t-1} q_t}\). E.g. sunny then sun-sun-rain-rain-sun-cloudy-sun is \(1 \cdot a_{33} a_{33} a_{31} a_{11} a_{13} a_{32} a_{23}\).
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), II Discrete Markov processes
4. What duration distribution does a Markov chain imply for staying in a state, and its mean?
   Geometric (“exponential”): \(p_i(d) = a_{ii}^{d-1}(1 - a_{ii})\), with expected duration \(\bar{d}_i = \frac{1}{1 - a_{ii}}\). With \(a_{33} = 0.8\), sunny spells last 5 days on average.
   • Rabiner, 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (Proceedings of the IEEE), II Discrete Markov processes