Viterbi Table start 1.00000 0.00000 0.00000 0.00000 0.00000 v 0.00000 0.15000 0.03000 0.00810 0.00000 n 0.00000 0.20000 0.04050 0.00810 0.00000 end 0.00000 0.00000 0.00000 0.00000 0.00405 START ground control station END Backtrace start -1 -1 -1 -1 -1 v -1 Start n n -1 n -1 Start v v -1 end -1 -1 -1 -1 v START ground control station END =============================================================== Tags (answer 1): start v n v end Tags (answer 2): start v v n end There are two equal probability paths (tag sequences). Notice that doesn't mean the model does nothing. There are 8 possible tag sequences, and 6 of them are eliminated. In the calculations below v2(1) stands for the Viterbi value at time 2 for the state indexed 1 in the Viterbi table. Looking at the order of the rows in the Viterbi table, using 0-based indexing, that's v. So v2(1) is the viterbi value of the v-state at time t = 2. ================================================================ t = 1 V1(1) = max(0.30000 * 1.00000 * 0.50000,0.30000 * 0.00000 * 0.10000,0.30000 * 0.00000 * 0.50000,0.30000 * 0.00000 * 0.00000) V1(1) = max(0.15000,0.00000,0.00000,0.00000) V1(1) = 0.15 # The terms in the max are supplied by the states we may have come from # on this best path and they are listed in the same order as the # states in the backtrace table, so the state supplying the amx path # prob is Start backtrace[v][1] = Start V1(2) = max(0.40000 * 1.00000 * 0.50000,0.40000 * 0.00000 * 0.90000,0.40000 * 0.00000 * 0.50000,0.40000 * 0.00000 * 0.00000) V1(2) = max(0.20000,0.00000,0.00000,0.00000) V1(2) = 0.2 backtrace[n][1] = Start --------------------------------------------------------------------- t = 2 V2(1) = max(0.30000 * 0.00000 * 0.50000,0.30000 * 0.15000 * 0.10000,0.30000 * 0.20000 * 0.50000,0.30000 * 0.00000 * 0.00000) V2(1) = max(0.00000,0.00450,0.03000,0.00000) V2(1) = 0.03 backtrace[v][2] = v V2(2) = max(0.30000 * 0.00000 * 0.50000,0.30000 * 0.15000 * 0.90000,0.30000 * 0.20000 * 0.50000,0.30000 * 0.00000 * 0.00000) V2(2) = max(0.00000,0.04050,0.03000,0.00000) V2(2) = 0.0405 backtrace[n][2] = v ---------------------------------------------------------------------- t = 3 V3(1) = max(0.40000 * 0.00000 * 0.50000,0.40000 * 0.03000 * 0.10000,0.40000 * 0.04050 * 0.50000,0.40000 * 0.00000 * 0.00000) V3(1) = max(0.00000,0.00120,0.00810,0.00000) V3(1) = 0.0081 backtrace[v][3] = n V3(2) = max(0.30000 * 0.00000 * 0.50000,0.30000 * 0.03000 * 0.90000,0.30000 * 0.04050 * 0.50000,0.30000 * 0.00000 * 0.00000) V3(2) = max(0.00000,0.00810,0.00607,0.00000) V3(2) = 0.0081 backtrace[n][3] = v ------------------------------------------------------------------------- t = 4 V4(3) = max(1.00000 * 0.00000 * 0.00000,1.00000 * 0.00810 * 0.50000,1.00000 * 0.00810 * 0.50000,1.00000 * 0.00000 * 0.00000) V4(3) = max(0.00000,0.00405,0.00405,0.00000) V4(3) = 0.00405 backtrace[end][4] = v (Of course it's a tie with n)