Exercise $2\mathrm{.}5.$ There is a casino that sometimes uses a fair die and sometimes uses a loaded die. You get to see the outcomes of the rolls, but not which die is used. For each die, you are given the probabilty of the faces, which are numbered $1$ to $6.$ You are also given the probabilities of switching dice and the probability of starting with each die type $-$ in short, an HMM.

Suppose you know that an Occasionally Dishonest Casino never uses the loaded die more than $2$ times in a row. If you do nothing about this, the state sequence returned by the Viterbi algorithm may be an impossible one with $3$ or more consecutive uses of the loaded die. This may happen if$,$ by chance, some fair rolls that look more likely under the loaded model are adjacent to loaded rolls that also look more likely under the loaded model.

Your friend says, $"$No problem! As you trace back, if you have already gone through $2$ consecutive instances of the "loaded"; state, automatically trace back to the "fair" state next, ignoring the calculated deltas.

This is easy to implement, and it will give you a state sequence with no runs of $3$ or more "loaded" states. However, it is not guaranteed to be the most likely sequence with no runs of $3$ or more "loaded" states.