Consider a Hidden Markov Model defined by four states (y₁, y₂, y₃, y₄), five output symbols (x₁, x₂, x₃, x₄, x₅), and the following transition probabilities (see the left table) and emission probabilities (see the right table).

Run the Viterbi algorithm on the observation sequence { x₁, x₄, x₂, x₂, x₄ } to find the most likely sequence of labels given this observation sequence. It is necessary and sufficient to show the final labeled sequence y and the probability of the best path ending up at each state after processing each output symbol in the observation sequence.

yi yi-1 0.6 0.2 0.15 0.05 y 0.2 0.3 0.45 0.05 y0.2 0.1 0.40.3 y40.3 0.2 0.2 0.3 START0.3 0.3 0.2 0.2 y10.4 0.1 0.2 0.2 0.1 y2 0.2 0.2 0.2 0.3 0.1 y3 0.1 0.4 0.25 0.05 0.2 y40.1 0.2 0.3 0.2 0.2 yi yi-1 0.6 0.2 0.15 0.05 y 0.2 0.3 0.45 0.05 y0.2 0.1 0.40.3 y40.3 0.2 0.2 0.3 START0.3 0.3 0.2 0.2 y10.4 0.1 0.2 0.2 0.1 y2 0.2 0.2 0.2 0.3 0.1 y3 0.1 0.4 0.25 0.05 0.2 y40.1 0.2 0.3 0.2 0.2