Hidden Markov Model for three-sided dice

Question

I was taught HMM and given this homework problem. I understood a part of it, but I'm not sure if its correct. The problem is:

Consider a different game where the dealer is not flipping a coin, but instead rolling a three-sided die with labels 1, 2, and 3. (Try not to think about what a three-sided die might look like.) The dealer has two loaded dice D1 and D2. For each die Di, the probability of rolling the number i is 1/2, and the probability of each of the other two outcomes is 1/4. At each turn, the dealer must decide whether to (1) keep the same die, (2) switch to the other die, or (3) end the game. He chooses (1) with probability 1/2 and each of the others with probability 1/4. At the beginning the dealer chooses one of the two dice with equal probability.

• Give an HMM for this situation. Specify the alphabet, the states, the transition probabilities, and the emission probabilities. Include a start state start, and assume that the HMM begins in state start with probability 1. Also include an end state end.

• Suppose that you observe the following sequence of die rolls: 1 1 2 1 2 2. Find a sequence of states which best explains the sequence of rolls. What is the probability of this sequence? Find the answer by completing the Viterbi table. Include backtrack arrows in the cells so you can trace back the sequence of states. Some of the following facts may be useful:

  log2(0) = −∞
  log2(1/4) = −2
  log2(1/2) = −1
  log2(1) = 0

• There are actually two optimal sequences of states for this sequence of die rolls. What is the other sequence of states?

If I'm not wrong for the first part I have to do something like here http://en.wikipedia.org/wiki/Hidden_Markov_model#A_concrete_example But I didn't get what is to assume start with probability 1.

Also, I'm not sure what I have to do for Viterbi table in the second part of the question. If any body can give me some hint or clue, that will be great.

Answer 1

To assume your starting probability is one: In HMM you either have a fixed starting-state or a probability-distribution over all states which states how likely it is to start in state X. To assume that your starting probability of a given state is 1 equals the first alternativ.

Viterbi-algorithm: In the viterbi-matrix the ith row offten corresponds to the ith states and the jth column corresponds to the prefix of lenth j of your emitted symbol. In each entry (i,j) is the maximal probability to that you have seen prefix j already and your are in state i.

For your backtracking you need to keep track for every (i,j)-cell which maximal precursor was involved in the computation of the (i,j)-cell. If you have this information you can backtrack from the cell with the highest value in the last column to the beginning. Reverse this backtrack and you got your viterbi-path.