Hidden Markov Models: The Viterbi Algorithm

Given an output sequence and a Hidden Markov Model, the Viterbi algorithm determines the most likely sequence of hidden states that the given model would travel through to generate the observation sequence. It does so by building a matrix of probabilities starting with the initial probabilities that each state would output each observation. The likelihood that a state emits the next output symbol is then equal to the emission probability of that state, output symbol pair times the most likely sequence to that state.

To implement this algorithm, I'll use the example of a dice roller who claims to have fair die. Given a sequence of observations we will consider a few HMMs to see the probability that the sequence we observe was generated by fair die vs loaded die.