Artificial Intelligence: Hidden Markov Model

Consider a two-bit register. The register has four possible states: 00, 01, 10 and 11. Initially, at time 0, the contents of the register is chosen at random to be one of these four states, each with equal probability. At each time step, beginning at time 1, the register is randomly manipulated as follows: with probability 1/2, the register is left unchanged; with probability 1/4, the two bits of the register are exchanged (e.g., 01 becomes 10); and with probability 1/4, the right bit is flipped (e.g., 01 becomes 00). After the register has been manipulated in this fashion, the left bit is observed. Suppose that on the first three time steps, we observe 0, 0, 1.

a. Show how the register can be formulated as an HMM. What is the probability of transitioning from every state to every other state? What is the probability of observing each output (0 or 1) in each state?

b. Use the filtering algorithm to determine the probability of being in each state at time t after observing only the first t bits, for t=1,2,3.

c. Use the forward-backward algorithm to determine the probability of being in each state at time k given all three observed bits, for k=0,1,2,3.

d. What is the most likely sequence of states given all three observed bits? (Be sure to include the initial state at time 0 in your sequence.)