A hidden Markov model
(HMM) consists of a set of states connected by directed edges.
Each state assigns probabilities to the characters of the
alphabet used in the sequence and to the edges
leaving the state.
There is usually a designated start state and a designated stop state
(though some HMMs allow starting or stopping in any state).
A path in an HMM is a sequence of states such that there is an edge from each state in the path to the next state in the path. The length of a path is the number of states in the sequence, and the probability of a path is the product of the probabilities of the edges traversed.
Each path through the HMM gives a probability distribution for each position in a string of the same length, based on the probabilities for the characters in the corresponding states. The probability of the sequence given a particular path is the product of the probabilities of the characters.
The probability of any sequence of characters is the sum, over all paths whose length is the same as the sequence, of the probability of the path times the probability of the sequence given the path:
If the HMM has designated start and stop states, then the sum is limited to those paths that start and end in the correct states. The above equation has omitted the renormalization needed to get the ``probabilities'' to sum to 1.
For computational reasons, it is often better to look not at all paths, but only at the path that maximizes the probability of the given sequence. It is also convenient to switch from path probabilities to encoding cost, by taking the negative log likelihood,
.
The Viterbi cost of a sequence, given an HMM, is the cost of the minimum-cost path through through the HMM.
This encoding cost for the best path (which is easily found with the Viterbi algorithm) can be assigned to individual positions in a cost map by assigning the cost of the edge into a state of the path and the cost of the character in that state to the corresponding position in the cost map.