2.5. Hidden Markov Models 232.5.1 Decision RuleFinding the best matching sequence of positions sT1for a given sequence of mea-surements xT1is defined under the Bayesian approach by finding the maximum jointprobability:s1T= argmax p( xT1, sT1)sT1applying the product rule leads to:Ts1T= argmax p( xt, st| x1t- 1, s1t- 1)sT1t=1In the HMM formalism, there is no condition on the previous emission vectors. Theycan be dropped:TsT1= argmax p( xt, st| s1t- 1)sT1t=1and there is only a dependency on the previous state(first-order Markov ):Ts1T= argmax p( xt, st| st- 1)sT1t=1T= argmax p( st| st- 1) · p( xt| st- 1, st)s1Tt=1T= argmax p( st| st- 1) · p( xt| st)sT1t=1Therefore, calculating the probability of a sequence sT1is reduced to iteratively com-bining the transition probability of a jump and the emission probability for a mea-sured signal vector xtat the jump destination. This is a very cheap operation, sop( x1T, sT1) can be determined in fractions of microseconds.With this representation, a solution for the maximization can already be foundwith a brute force approach. The product has to be evaluated for all possible statesequences s1T. But with N possible transitions from one state s into another s, thecomputational complexity is given by NTsolutions. This makes a brute force searchintractable.2.5.2 Viterbi AlgorithmThe Viterbi Algorithm is an efficient dynamic programming algorithm for finding themost probable state sequence sT1for an observed vector sequence x1T. The Algorithmexploits the memorylessnes of the model that is induced by the Markov property.The Algorithm is defined as a set of recursive equations starting with:tQ( t, s):= max p( x, s| s - 1)s1t: st= s=1